Source code for mimiqcircuits.decomposition.abstract

#
# Copyright © 2022-2024 University of Strasbourg. All Rights Reserved.
# Copyright © 2023-2025 QPerfect. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
"""Abstract base classes for the decomposition framework.

This module defines the core abstractions for quantum circuit decomposition:

- :class:`RewriteRule`: Single-step transformation rules
- :class:`DecompositionBasis`: Recursive decomposition to a target gate set
"""

from __future__ import annotations

from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import TYPE_CHECKING, Sequence

if TYPE_CHECKING:
    from mimiqcircuits.circuit import Circuit
    from mimiqcircuits.operations.operation import Operation


[docs] class DecompositionError(Exception): """Raised when an operation cannot be decomposed. A basis raises it from :meth:`DecompositionBasis.decompose` for an operation it is not terminal for and has no rewrite for, and most rules raise it from :meth:`RewriteRule.decompose_step` for an operation they do not match. """ pass
@dataclass(frozen=True) class _AncillaOptions: """Ancilla options of a basis. Every basis that supports them stores one and returns it from ``_ancillaoptions``; the others use the defaults, which keep every decomposition inside the targets of the operation it decomposes. """ borrow: bool = False max_ancillas: int = 0 allow_measurement: bool = False def __post_init__(self): if self.max_ancillas < 0: raise ValueError( f"max_ancillas must be non-negative, got {self.max_ancillas}" ) class _AncillaAllocator: """Clean ancillas handed out while a circuit is decomposed. The iterator keeps it up to date as instructions stream out: ``AncillaAlloc`` raises the window depth of its qubit and ``AncillaFree`` lowers it. A qubit whose depth drops to 0 is free, and stays free until an instruction touches it. Qubits a rule takes leave the free list at once, before their ``AncillaAlloc`` is streamed. """ def __init__(self, next_qubit, remaining): self.next = next_qubit self.remaining = remaining self.depth = {} self.free = [] def available(self): """Number of clean ancillas that can be taken now.""" return len(self.free) + self.remaining def take(self, k): """Take up to ``k`` clean ancillas. Free ones first, lowest index first, then new ones numbered after the circuit. """ self.free.sort() taken = self.free[:k] del self.free[: len(taken)] while len(taken) < k and self.remaining > 0: taken.append(self.next) self.next += 1 self.remaining -= 1 return taken def track(self, inst): from mimiqcircuits.operations.annotations import AncillaAlloc, AncillaFree op = inst.operation if isinstance(op, AncillaAlloc): q = inst.qubits[0] self.depth[q] = self.depth.get(q, 0) + 1 if q in self.free: self.free.remove(q) elif isinstance(op, AncillaFree): q = inst.qubits[0] d = self.depth.get(q, 0) - 1 if d > 0: self.depth[q] = d else: self.depth.pop(q, None) if q not in self.free: self.free.append(q) else: # A qubit touched after it was freed is no longer known to be in |0>. for q in inst.qubits: if q in self.free: self.free.remove(q)
[docs] @dataclass(frozen=True) class DecompositionContext: """State that :func:`decompose` hands to a basis and its rules. The context goes next to the operation and its targets, through :meth:`DecompositionBasis.decompose_ctx` and :meth:`RewriteRule.decompose_step_ctx`. Args: nqubits: Width of the circuit being decomposed. Qubits ``0, ..., nqubits - 1`` that are not targets of the operation may be borrowed. ``0`` means the width is unknown, and nothing is borrowed. borrow: Whether rules may borrow qubits outside the operation's targets. A borrowed qubit can be in any state; the decomposition acts as the identity on it. unitary_only: Set when the result must be unitary, as for the body of a wrapped ``GateDecl`` or of an ``IfStatement``. :func:`decompose` also hands out clean ancillas through the context when the basis has ``max_ancillas > 0``. A rule that takes them brackets their use with :class:`AncillaAlloc` and :class:`AncillaFree` and returns them in ``|0>``. With ``allow_measurement=True`` on the basis, the context also holds a classical bit, numbered after those of the circuit, that rules may measure an ancilla into. Bases and rules that do not use the context inherit the default ``*_ctx`` methods, which drop it and call the method without it. """ nqubits: int = 0 borrow: bool = False unitary_only: bool = False allocator: _AncillaAllocator | None = None # Bit that measuring rules write to, or None when they may not measure. bit: int | None = None def __post_init__(self): if self.nqubits < 0: raise ValueError(f"nqubits must be non-negative, got {self.nqubits}")
[docs] @classmethod def from_basis(cls, basis, nqubits, nbits=0): """The context for a circuit ``nqubits`` wide with ``nbits`` bits. Clean ancillas and the measured bit are numbered after them, so a circuit of unknown width gets none. """ opts = basis._ancillaoptions() alloc = None if opts.max_ancillas > 0 and nqubits > 0: alloc = _AncillaAllocator(nqubits, opts.max_ancillas) bit = nbits if opts.allow_measurement and nbits > 0 else None return cls(nqubits=nqubits, borrow=opts.borrow, allocator=alloc, bit=bit)
[docs] def unitary(self): """The same context for a result that must be unitary.""" return DecompositionContext( nqubits=self.nqubits, borrow=self.borrow, unitary_only=True, allocator=self.allocator, bit=self.bit, )
[docs] def can_measure(self): """Whether a rule may measure an ancilla.""" return self.bit is not None and not self.unitary_only
[docs] def available(self): """Number of clean ancillas that can be taken now.""" return 0 if self.allocator is None else self.allocator.available()
[docs] def take_clean(self, k): """Up to ``k`` clean ancillas for the rule that receives this context.""" if self.allocator is None or k <= 0: return [] return self.allocator.take(k)
_NO_CONTEXT = DecompositionContext() def _uses_context(op): """Whether ``op`` has a rule that uses the decomposition context. Bases take the context for these operations alone, so an override of ``decompose`` for any other operation keeps being called. """ from mimiqcircuits.operations.control import Control from mimiqcircuits.operations.ifstatement import IfStatement return isinstance(op, (Control, IfStatement)) def _borrowable(ctx, qubits, k): """Qubits a rule may borrow for an operation on ``qubits``, at most ``k``. Nearest to the targets first, so that MPS chains stay local. """ if not ctx.borrow or k <= 0: return [] targets = set(qubits) free = [q for q in range(ctx.nqubits) if q not in targets] free.sort(key=lambda q: (min(abs(q - t) for t in qubits), q)) return free[:k]
[docs] class RewriteRule(ABC): """Abstract base class for single-step rewrite rules. A rewrite rule says *how* to rewrite an operation into a circuit of other operations, but not *when* to stop. Apply it once with :func:`decompose_step`, or repeatedly with :func:`decompose`, which wraps it in a :class:`RuleBasis` and rewrites until nothing matches. For a target gate set, see :class:`DecompositionBasis`. A subclass implements :meth:`matches` and :meth:`decompose_step`. Examples: >>> from mimiqcircuits import * >>> # a rule that rewrites a SWAP into three CX gates >>> class SwapToCX(RewriteRule): ... def matches(self, op): ... return isinstance(op, GateSWAP) ... ... def decompose_step(self, op, qubits, bits, zvars): ... # qubits are the targets of the SWAP in the circuit ... a, b = qubits ... circ = Circuit() ... circ.push(GateCX(), a, b) ... circ.push(GateCX(), b, a) ... circ.push(GateCX(), a, b) ... return circ >>> c = Circuit() >>> c.push(GateH(), 0) 1-qubit circuit with 1 instruction: └── H @ q[0] <BLANKLINE> >>> c.push(GateSWAP(), 0, 1) 2-qubit circuit with 2 instructions: ├── H @ q[0] └── SWAP @ q[0:1] <BLANKLINE> >>> # the SWAP matches and is rewritten; the H does not and is kept >>> decompose_step(c, SwapToCX()) 2-qubit circuit with 4 instructions: ├── H @ q[0] ├── CX @ q[0], q[1] ├── CX @ q[1], q[0] └── CX @ q[0], q[1] <BLANKLINE> """
[docs] @abstractmethod def matches(self, op: Operation) -> bool: """Check whether this rule can rewrite an operation. Args: op: The operation to check. Returns: ``True`` if :meth:`decompose_step` accepts ``op``. """ ...
[docs] @abstractmethod def decompose_step( self, op: Operation, qubits: Sequence[int], bits: Sequence[int], zvars: Sequence[int], ) -> Circuit: """Rewrite an operation one step. Call it only on an operation that :meth:`matches` accepts. The result acts on the given indices, so it can be appended in place of the original instruction. Its operations may themselves match the rule again. Args: op: The operation to rewrite. qubits: Qubit indices the operation acts on. bits: Classical bit indices the operation acts on. zvars: Z-variable indices the operation acts on. Returns: A new :class:`~mimiqcircuits.Circuit` that implements ``op`` on those indices. Raises: DecompositionError: If the rule cannot rewrite ``op``. """ ...
[docs] def decompose_step_ctx( self, op: Operation, qubits: Sequence[int], bits: Sequence[int], zvars: Sequence[int], ctx: DecompositionContext, ) -> Circuit: """Apply this rule with a :class:`DecompositionContext`. Rules that use the context, for example to borrow qubits, override this method. The default drops the context and calls :meth:`decompose_step`. """ return self.decompose_step(op, qubits, bits, zvars)
def __repr__(self) -> str: return f"{self.__class__.__name__}()"
[docs] class DecompositionBasis(ABC): """Abstract base class for decomposition targets. A basis decides which operations are terminal, that is kept as they are, and how to rewrite every other operation. :func:`decompose` rewrites each non-terminal operation with :meth:`decompose` and repeats on the result until only terminal operations are left. A subclass implements :meth:`isterminal` and :meth:`decompose`. Examples: >>> from mimiqcircuits import * >>> # a basis of GateU and GateCZ: CX becomes H, CZ, H and the rest >>> # follows the built-in decomposition >>> class CZBasis(DecompositionBasis): ... def isterminal(self, op): ... return isinstance(op, (GateU, GateCZ)) ... ... def decompose(self, op, qubits, bits, zvars): ... if isinstance(op, GateCX): ... control, target = qubits ... circ = Circuit() ... circ.push(GateH(), target) ... circ.push(GateCZ(), control, target) ... circ.push(GateH(), target) ... return circ ... return CanonicalRewrite().decompose_step(op, qubits, bits, zvars) >>> c = Circuit() >>> c.push(GateCX(), 0, 1) 2-qubit circuit with 1 instruction: └── CX @ q[0], q[1] <BLANKLINE> >>> # the H gates are not terminal, so they are decomposed in turn >>> decompose(c, CZBasis()) 2-qubit circuit with 3 instructions: ├── U((1/2)*pi, 0, pi, 0.0) @ q[1] ├── CZ @ q[0], q[1] └── U((1/2)*pi, 0, pi, 0.0) @ q[1] <BLANKLINE> """
[docs] @abstractmethod def isterminal(self, op: Operation) -> bool: """Check whether an operation is terminal in this basis. Terminal operations are the target set: :func:`decompose` keeps them as they are. Args: op: The operation to check. Returns: ``True`` if ``op`` is kept, ``False`` if it is rewritten. """ ...
[docs] @abstractmethod def decompose( self, op: Operation, qubits: Sequence[int], bits: Sequence[int], zvars: Sequence[int], ) -> Circuit: """Rewrite a non-terminal operation one step. Called by :func:`decompose` only for operations that :meth:`isterminal` rejects. The result does not need to be terminal: :func:`decompose` keeps rewriting it. Args: op: The operation to rewrite. qubits: Qubit indices the operation acts on. bits: Classical bit indices the operation acts on. zvars: Z-variable indices the operation acts on. Returns: A new :class:`~mimiqcircuits.Circuit` that implements ``op`` on those indices. Raises: DecompositionError: If the basis has no rewrite for ``op``. """ ...
[docs] def decompose_ctx( self, op: Operation, qubits: Sequence[int], bits: Sequence[int], zvars: Sequence[int], ctx: DecompositionContext, ) -> Circuit: """Decompose a non-terminal operation with a :class:`DecompositionContext`. :func:`decompose` always calls this method. Bases that pass the context on to their rules override it. The default drops the context and calls :meth:`decompose`. """ return self.decompose(op, qubits, bits, zvars)
def _ancillaoptions(self) -> _AncillaOptions: return _AncillaOptions() def __repr__(self) -> str: return f"{self.__class__.__name__}()"
__all__ = [ "RewriteRule", "DecompositionBasis", "DecompositionContext", "DecompositionError", ]