Source code for mimiqcircuits.decomposition.rules.gridsynth

#
# 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.
#
"""Ross–Selinger gridsynth: Clifford+T approximation of Z-rotations.

The synthesis itself is implemented in Rust in the ``mimiqcircuits._core``
extension.

References:
    - N. J. Ross and P. Selinger, "Optimal ancilla-free Clifford+T
      approximation of z-rotations", Quantum Inf. Comput. 16, 901 (2016),
      arXiv:1403.2975.
"""

from __future__ import annotations

import math
import numbers
import operator
import threading
from dataclasses import dataclass
from typing import TYPE_CHECKING, Sequence

from mimiqcircuits._core import gridsynth as _gridsynth
from mimiqcircuits.decomposition.abstract import DecompositionError, RewriteRule

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

_MASK64 = (1 << 64) - 1

# Smaller tolerances still work but take seconds per rotation, and a float
# angle is only known to about 1e-16 anyway.
_GRIDSYNTH_MIN_EPSILON = 1e-100

# Circuits often repeat the same angle (QFT, Trotter steps), and synthesis
# costs milliseconds or more per angle, so results are memoized. The cache
# is cleared rather than evicted when full; entries are cheap to recompute.
_GRIDSYNTH_CACHE: dict[tuple[float, float, int], str] = {}
_GRIDSYNTH_CACHE_LOCK = threading.Lock()
_GRIDSYNTH_CACHE_MAX = 10_000


def _gridsynth_word(epsilon: float, seed: int, theta: float) -> str:
    key = (theta, epsilon, seed)
    with _GRIDSYNTH_CACHE_LOCK:
        cached = _GRIDSYNTH_CACHE.get(key)
    if cached is not None:
        return cached
    word = _gridsynth(theta, epsilon, seed)
    with _GRIDSYNTH_CACHE_LOCK:
        if len(_GRIDSYNTH_CACHE) >= _GRIDSYNTH_CACHE_MAX:
            _GRIDSYNTH_CACHE.clear()
        _GRIDSYNTH_CACHE[key] = word
    return word


[docs] @dataclass(frozen=True) class GridSynthRewrite(RewriteRule): """Rewrite rule that approximates ``GateRZ`` with Clifford+T gates by gridsynth. It implements the Ross–Selinger gridsynth algorithm. For ``GateRZ(λ)`` the rule emits a sequence of ``GateH``, ``GateS``, ``GateSDG``, ``GateZ``, ``GateT`` and ``GateX`` whose unitary ``V`` satisfies ``min_φ ‖RZ(λ) − e^{iφ}V‖ ≤ epsilon`` in operator norm. The approximation holds up to a global phase, which is dropped. The T-count is about ``3·log₂(1/epsilon)`` and, except for rare failures of the integer factoring step, optimal among ancilla-free Clifford+T circuits with this error. Angles that are multiples of ``π/4`` give their exact short decomposition. The factoring step is randomized. For a fixed ``seed``, the same angle and tolerance always give the same sequence. Results are cached per angle, since circuits often repeat the same rotation. The synthesis runs in the compiled ``mimiqcircuits._core`` extension without holding the GIL, so several threads can synthesize in parallel. Args: epsilon: Operator-norm tolerance, with ``1e-100 <= epsilon < 1`` (default ``1e-10``). A rotation takes a few milliseconds at ``1e-10`` and up to about a second at ``1e-100``. seed: Seed of the randomized factoring step, an integer in ``[0, 2**64)`` (default ``0``). Raises: ValueError: If ``epsilon`` or ``seed`` is out of range. TypeError: If ``epsilon`` is not a real number or ``seed`` is not an integer. Supported Operations: - ``GateRZ(λ)`` with a numeric angle ``λ``. Symbolic angles are not matched. ``GateRX``, ``GateRY`` and ``GateU`` must first be reduced to Z-rotations, for example with :class:`ZYZRewrite` and :class:`ToZRotationRewrite`. :class:`CliffordTBasis` does this and uses this rule by default. Examples: >>> from mimiqcircuits import * >>> def tcount(c): ... return sum(isinstance(i.operation, GateT) for i in c) >>> # Approximate one rotation to the default tolerance 1e-10 >>> circ = GridSynthRewrite().decompose_step(GateRZ(0.123), [0], [], []) >>> # A coarser tolerance gives fewer T gates >>> coarse = GridSynthRewrite(epsilon=1e-4).decompose_step(GateRZ(0.123), [0], [], []) >>> tcount(coarse) < tcount(circ) True References: N. J. Ross and P. Selinger, "Optimal ancilla-free Clifford+T approximation of z-rotations", Quantum Inf. Comput. 16, 901 (2016), arXiv:1403.2975. """ epsilon: float = 1e-10 seed: int = 0 def __post_init__(self): if not isinstance(self.epsilon, numbers.Real): raise TypeError(f"epsilon must be a real number, got {self.epsilon!r}") epsilon = float(self.epsilon) if not _GRIDSYNTH_MIN_EPSILON <= epsilon < 1: raise ValueError( f"epsilon must be in [{_GRIDSYNTH_MIN_EPSILON}, 1), got {self.epsilon}" ) seed = operator.index(self.seed) if not 0 <= seed <= _MASK64: raise ValueError(f"seed must be in [0, 2**64), got {self.seed}") object.__setattr__(self, "epsilon", epsilon) object.__setattr__(self, "seed", seed)
[docs] def matches(self, op: Operation) -> bool: """Check if this rule can decompose the operation. Args: op: The operation to check. Returns: True if the operation is a ``GateRZ`` with a numeric angle. """ from mimiqcircuits.operations.gates.standard.rotations import GateRZ return isinstance(op, GateRZ) and not op.is_symbolic()
[docs] def decompose_step( self, op: Operation, qubits: Sequence[int], bits: Sequence[int], zvars: Sequence[int], ) -> Circuit: """Decompose the Z-rotation into Clifford+T gates. Args: op: The ``GateRZ`` to decompose. qubits: Qubit indices for the operation. bits: Classical bit indices (unused). zvars: Z-variable indices (unused). Returns: A new :class:`~mimiqcircuits.Circuit` with the Clifford+T approximation. Raises: DecompositionError: If the operation is not a numeric ``GateRZ``. ValueError: If the angle is not finite. """ from mimiqcircuits.circuit import Circuit from mimiqcircuits.operations.gates.standard.hadamard import GateH from mimiqcircuits.operations.gates.standard.pauli import GateX, GateZ from mimiqcircuits.operations.gates.standard.s import GateS, GateSDG from mimiqcircuits.operations.gates.standard.t import GateT if not self.matches(op): raise DecompositionError( f"GridSynthRewrite cannot decompose {type(op).__name__}" ) theta = float(op.lmbda) if not math.isfinite(theta): raise ValueError(f"GridSynthRewrite: angle {theta} is not finite") word = _gridsynth_word(self.epsilon, self.seed, theta) circ = Circuit() q = qubits[0] # The word is in matrix-product order, so the last letter acts first. i = len(word) - 1 while i >= 0: c = word[i] if c == "S": n = 0 while i >= 0 and word[i] == "S": n += 1 i -= 1 n &= 3 if n == 1: circ.push(GateS(), q) elif n == 2: circ.push(GateZ(), q) elif n == 3: circ.push(GateSDG(), q) continue if c == "H": circ.push(GateH(), q) elif c == "T": circ.push(GateT(), q) elif c == "X": circ.push(GateX(), q) i -= 1 return circ
__all__ = ["GridSynthRewrite"]