#
# 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"]