Gridsynth: Ross-Selinger synthesis

The core objective of gridsynth is to approximate a continuous single-qubit Z-rotation matrix using a nearby exactly-representable U, unitary matrix whose entries belong to the cyclotomic ring extension \mathbb{D}[\omega] = \mathbb{Z}[\frac{1}{\sqrt{2}}, i] [1]. Here, \mathbb{D} represents the dyadic rationals (m/2^j for m \in \mathbb{Z} and j \geq 0) and \omega = e^{i\pi/4} = (1+i)/\sqrt{2}. This ensures that every matrix entry is a linear combination of the form (p\omega^3 + q\omega^2 + r\omega + s)/2^j, where p, q, r, s \in \mathbb{Z} and j \geq 0, matching the algebraic structure of the Clifford+T gate set. This translates the compilation into finding an exact matrix of the form:

U = \frac{1}{\sqrt{2}^k} \begin{pmatrix} u & -t^* \\ t & u^* \end{pmatrix}

where k \geq 0, u, t \in \mathbb{Z}[\omega], and |u|^2 + |t|^2 = 2^k. In this context, exact denotes that U can be represented with zero error by a finite sequence of Clifford+T gates. Only for certain angles (i.e., when \theta is a multiple of \pm\pi/4), the matrix is exactly representable with t=0. In practice, for other generic angles, no exact Clifford+T circuit exists, which is why we must use an exact matrix U to approximate the operation within \epsilon.

Conceptual workflow

How do we find the integers (p, q, r, s) that satisfy this constraint and how do we obtain the final sequence afterwards?

1. Mapping the Region: The algorithm projects the complex 4D algebraic problem space into a Two-Dimensional Grid Problem (TDGP). The target space where a valid u must reside is a narrow circular segment in the complex plane, sliced from the unit disk with an angular tilt determined by rotation \theta and its half-chord length dictated by precision constraint \epsilon.
2. Grid Projection: As u consists of algebraic ring elements, infinitely many candidates exist in the target space. For computational tractability, the algorithm overlays a discrete coordinate grid over it by enforcing a conjugate constraint, i.e., the algebraic conjugate u^{\bullet} simultaneously lies within the companion unit disk.
3. Lattice Enumeration: The resulting space is often highly skewed; directly searching within this needle-like 2D region is computationally wasteful. The algorithm applies a grid transformation to dynamically reduce skew, reshaping the search space into an upright, tight bounding box where candidate points can be cheaply enumerated without blind trial-and-error.
4. Diophantine Solving: The algorithm lifts these pairs back into the full ring and determines the companion matrix element t by solving the norm equation uu^{*}+tt^{*}=2^k via classical prime factorization.
5. Unitary Construction: Once a valid (u, t) is isolated, they are assembled into the unitary matrix shown above, preserving the exact algebraic structure required for hardware execution.
6. Sequence Generation: Finally, the algorithm maps U to its SO(3) representation and uses the Matsumoto-Amano normal form to recursively peel off Clifford+T syllables, outputting the final gate sequence in polynomial time [2]-[3].

The explicit geometric operations used to flatten this search space, along with the final sequence generation, are explained step by step in our dedicated details tab.

References

[1] N. J. Ross and Peter Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations. arXiv preprint arXiv:1403.2975, (2014).

[2] Brett Giles and Peter Selinger, Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators. arXiv preprint arXiv:1312.6584, (2013).

[3] Ken Matsumoto and Kazuyuki Amano, Representation of Quantum Circuits with Clifford and π/8 Gates. arXiv preprint arXiv:0806.3834, (2008).