Rotation Synthesis (Clifford+T)

It is typical in fault-tolerant quantum computing to consider only the discrete Cliffords augmented with the T gate for universality, like H, S, T, X and CNOT, the Clifford+T set. A continuous rotation such as rz(0.6) is not a member of this set, so before a kernel can run on such hardware every rotation must be synthesized into a sequence of digital operations which approximates it.

CUDA-Q does this with Gridsynth (Ross and Selinger, arXiv:1403.2975). Given an angle and a tolerance epsilon, it finds a short Clifford+T sequence \(U\) satisfying \(\|R_z(\theta) - U\| \le \epsilon\) in the operator norm.

There are two ways to use it. cudaq.synth is a Python API for approximating individual rotations, and is shown first. Synthesizing a whole kernel is done by a compiler pass, which is opt-in. It is not part of any default target pipeline, and the targets that run it are benchmarking targets for estimating how many T gates an algorithm would cost.

Synthesizing a rotation

To approximate a rotation, use cudaq.synth.gridsynth. Note that the synth submodule is imported explicitly:

from cudaq import synth

# Approximate a rotation of `theta` radians about the Z axis to within an
# operator-norm error of `epsilon`.
theta, epsilon = 0.6, 1e-10
seq = synth.gridsynth(theta, epsilon, seed=1234)

print(f"T count: {seq.t_count}")
print(f"gates:   {str(seq)[:32]}...")

# The achieved error is computed exactly and never exceeds the epsilon that was
# asked for.
print(f"error:   {synth.rz_error(theta, seq):.3e}")
assert synth.rz_error(theta, seq) <= epsilon

T count: 102
gates:   HTHTHTSHTHTSHTSHTHTHTSHTSHTHTSHT...
error:   9.665e-11

gridsynth returns a CliffordTSequence. Its t_count is the number of T gates, and str() gives the gate string over {H, S, T, X, W}, where W is the global phase \(\omega = e^{i\pi/4}\). The gates are listed in matrix-multiplication order, so as a circuit they apply right to left.

cudaq.synth.rz_error reports the error the sequence actually achieves. It is computed exactly in arbitrary precision, and it never exceeds the epsilon you asked for.

A CliffordTSequence can also be built directly from a gate string, which is useful for inspecting Clifford+T circuits that came from somewhere else. normalized rewrites a sequence into Matsumoto-Amano normal form. An exactly equal sequence with the smallest possible T count.

# A sequence can also be built directly from a gate string, which is useful for
# inspecting Clifford+T circuits that came from somewhere else.
imported = synth.CliffordTSequence("TST")
print(f"imported:   {imported} (T count {imported.t_count})")

# `normalized` rewrites a sequence into Matsumoto-Amano normal form. The result
# is exactly equal and has the smallest possible T count.
reduced = imported.normalized()
print(f"normalized: {reduced} (T count {reduced.t_count})")

# `gridsynth` already returns normal form, so normalizing its output changes
# nothing.
print(f"already normal form: {seq.normalized() == seq}")

imported:   TST (T count 2)
normalized: SS (T count 0)
already normal form: True

gridsynth already returns sequences in normal form, so normalizing its output changes nothing.

To use a synthesized sequence in a circuit, to_kernel builds a kernel that takes a single qubit, ready for apply_call:

# `to_kernel` builds a kernel taking a single qubit, for use with `apply_call`.
# Sandwiching the rotation between two Hadamards turns the phase it applies
# into a measurable population, so the counts below depend on theta.
kernel = cudaq.make_kernel()
qubit = kernel.qalloc()
kernel.h(qubit)
kernel.apply_call(seq.to_kernel(), qubit)
kernel.h(qubit)
kernel.mz(qubit)

# The same circuit built with an exact `rz`, for comparison.
exact = cudaq.make_kernel()
exact_qubit = exact.qalloc()
exact.h(exact_qubit)
exact.rz(theta, exact_qubit)
exact.h(exact_qubit)
exact.mz(exact_qubit)

cudaq.set_random_seed(13)
print(f"synthesized: {cudaq.sample(kernel, shots_count=1000)}")
cudaq.set_random_seed(13)
print(f"exact rz:    {cudaq.sample(exact, shots_count=1000)}")

synthesized: { 0:908 1:92 }
exact rz:    { 0:908 1:92 }

The synthesized sequence reproduces the exact rotation. Note that to_kernel drops the W phase factors, so the kernel it returns equals \(R_z(\theta)\) only up to a global phase. That phase has no effect when the kernel is used on its own, but it becomes an observable relative phase if the kernel is made the target of a controlled operation. The compiler-bench-ftqc-clifford-t target does not have this limitation. It emits the phase explicitly, so the circuit it produces is exactly equal to the original.

Estimating the T count of a kernel

The T gate is the expensive resource on fault-tolerant hardware, so the T count of a circuit is the number usually worth measuring. The compiler-bench-ftqc-clifford-t target runs synthesis over a whole kernel so that count can be read off directly. It reduces rx, ry and r1 rotations to rz, synthesizes each one, and optimizes the result. Its epsilon argument sets the per-rotation tolerance and defaults to 1e-10.

import cudaq

# Rewrite every rotation in the kernel into Clifford+T. `epsilon` is the
# per-rotation approximation tolerance.
cudaq.set_target("compiler-bench-ftqc-clifford-t", epsilon="1e-10")


@cudaq.kernel
def circuit():
    q = cudaq.qvector(2)
    h(q[0])
    rz(0.6, q[0])
    ry(0.25, q[1])
    x.ctrl(q[0], q[1])
    mz(q)


operations = cudaq.estimate_resources(circuit).to_dict()

# Only Clifford+T operations are left. The rotations are gone.
CLIFFORD_T = {
    "h", "s", "sdg", "t", "tdg", "x", "y", "z", "cx", "cy", "cz", "swap", "mx",
    "my", "mz"
}

print(f"only Clifford+T: {set(operations) <= CLIFFORD_T}")
print(f"T count:         {operations.get('t', 0) + operations.get('tdg', 0)}")

cudaq.reset_target()

only Clifford+T: True
T count:         208

This is a benchmarking target for resource counting, not a path for compiling kernels to run on hardware. It is also Python only. An nvq++ build accepts the target but does not run the synthesis.

Rotation angles must be compile-time constants when synthesis runs. A kernel whose angle comes from a runtime argument has to be specialized first.

Choosing epsilon

epsilon trades accuracy against cost. A tighter tolerance means more T gates and more compile time; the T count grows roughly with \(\log(1/\epsilon)\), while compile time grows much faster and becomes significant below about 1e-30.

Synthesis results are cached per distinct angle, so a kernel that applies the same rotation a hundred times pays the cost once.

Synthesis is randomized. Repeated calls with the same angle and tolerance return sequences with the same T count, but not necessarily the same gates. Pass seed to make a run reproducible, as the example above does. The remaining arguments to gridsynth are work budgets that trade compile time against T count; see the Python API reference for what each one bounds.

Dependencies

Rotation synthesis uses exact arbitrary-precision arithmetic, provided by the GMP and MPFR libraries. These ship with every CUDA-Q binary distribution, so no action is needed to use the feature. See Dynamic linking to GMP and MPFR for details on how they are packaged and how to substitute your own builds.