10.4 Phase-polynomial and Clifford+\(T\) catalysis
On this page · Permalink · Source line 3879
10.4.1 Why the phase setting is different
On this page · Permalink · Source line 3887
Fault-tolerant quantum compilation rarely assigns equal cost to every gate. Clifford operations are often treated as inexpensive relative to non-Clifford gates, while connectivity and parity computation can dominate the remaining cost. Consequently there is no single Clifford+\(T\) defect. One must specify at least
A catalytic excursion may improve one component and worsen another. The natural comparison is therefore Pareto-valued rather than scalar unless a hardware-specific weight vector is fixed.
Let \(\omega=e^{i\pi/4}\). A phase-polynomial circuit on \(n\) qubits has the form [19], [41]
where \(A\in{\operatorname{GL}}(n,2)\), \(b\in{\mathbb F}_2^n\), and \(P:{\mathbb F}_2^n\to{\mathbb Z}_8\) is represented as a sum of binary linear forms with coefficients in \({\mathbb Z}_8\). The diagonal case has \(A=I\) and \(b=0\).
The restricted model may be chosen in several ways:
diagonal phase gadgets only;
CNOT-dihedral circuits generated by \(X\), CNOT, and \(T\);
parity networks in which every intermediate transformation remains affine on computational basis labels;
a prescribed family of commuting Pauli rotations.
The ambient model may add Hadamards, arbitrary Clifford conjugations, measurements, or ancillas. These choices define different problems.
10.4.2 Pauli-rotation language
On this page · Permalink · Source line 3916
For a Pauli operator \(P\) and angle \(\theta\), write
Every Clifford \(C\) satisfies
Thus a short ambient basis change can rotate a large family of phase gadgets into a different commuting or nearly commuting family, apply them there, and rotate back.
Proved statement
Equation (10.2) is an exact catalytic transport identity. It does not by itself prove a gate-count defect. A defect additionally requires a lower bound showing that the transported family is more expensive in the restricted representation than the opening and closing Clifford layers plus the transported implementation.
The simplest symbolic sandwich is
If the \(P_j\) commute, their conjugates commute. A catalyst can therefore change the geometry of the support without changing the algebra of the angles.
10.4.3 Phase polynomials and parity carriers
On this page · Permalink · Source line 3939
A CNOT network computes linear parities
Applying \(T^k\) to a wire carrying \(\lambda(x)\) contributes
to the phase polynomial. A parity network must create each required parity, expose it to a phase gate, and restore the linear map required at the endpoint.
This makes phase-polynomial synthesis a close relative of the snapshot families in the linear core. A parity row may evolve through
with selected states consumed by phase gates. The difference is that consumption need not copy the parity to another row; it can deposit phase while leaving the carrier unchanged.
Research template
A candidate phase catalyst consists of:
a Clifford \(C\) that opens a non-diagonal frame;
an evolving Pauli or parity carrier in that frame;
several phase rotations consuming intermediate carrier states;
\(C^\dagger\) restoring the original diagonal or CNOT-dihedral model;
a certificate that no restricted parity network attains the same resource vector.
10.4.4 \(T\)-count as a coding problem
On this page · Permalink · Source line 3974
For diagonal Clifford+\(T\) synthesis without ancillas, equivalent phase-polynomial descriptions can differ by identities whose coefficients vanish modulo eight on Boolean inputs. Minimizing the number of odd coefficients is naturally expressed as a coset-decoding problem in a punctured Reed–Muller-type code.
Let \(a\in{\mathbb Z}_8^{2^n-1}\) index nonzero linear forms and let \(\operatorname{odd}(a)\) denote the binary vector recording which coefficients are odd. An abstract restricted \(T\)-count is
An ambient Clifford excursion changes not only the coefficient vector but also the Pauli frame in which the rotations are represented. A lower bound that survives ambient Clifford conjugation must therefore be invariant under the relevant symplectic action or must explicitly charge the frame change.
10.4.5 \(T\)-depth and commuting layers
On this page · Permalink · Source line 3985
Two phase gadgets may share a \(T\) layer when a suitable Clifford network maps their parities to distinct wires or when ancilla resources permit parallel extraction. Define the conflict graph \(\Gamma_P\) whose vertices are odd phase terms and whose edges encode inability to realize two terms in one layer under the chosen ancilla and connectivity rules. Then
for any conflict graph whose edge relation is sound. Catalysis can alter \(\Gamma_P\) by changing the Pauli frame. The right question is not merely whether \(C\) preserves the number of terms, but whether it reduces the chromatic or scheduling obstruction enough to repay its own depth.
10.4.6 A vector-valued defect
On this page · Permalink · Source line 3992
For a target \(U\) in a restricted phase model, define
and similarly \(\mathcal C_{\mathrm{amb}}(U)\). Their Pareto frontiers are denoted \(\operatorname{Pareto}_{\mathrm{res}}(U)\) and \(\operatorname{Pareto}_{\mathrm{amb}}(U)\).
Definition 10.11: Pareto catalytic defect
A target has a Pareto catalytic defect when the ambient Pareto frontier contains a point strictly dominating every restricted cost vector in at least one declared region of resource space.
Scalarization by positive weights \(w\) gives
Different \(w\) can change the magnitude of the defect and whether it is zero or positive. It remains nonnegative because every restricted realization is also an ambient realization with the same resource vector.
10.4.7 Exact finite-search model
On this page · Permalink · Source line 4014
A finite exact atlas can be built [34], [20] for small \(n\) by representing Clifford+\(T\) operators in one of three ways.
Exact matrices over the cyclotomic ring \({\mathbb Z}[1/\sqrt2,i]\) modulo global phase.
Normal forms combining a binary symplectic Clifford with a phase-polynomial record.
Quotients by left and right Clifford actions when only \(T\)-count is charged.
The third model can be dramatically smaller but requires care: quotienting is sound only when the free Clifford actions in the cost model agree with the quotient relation.
Protocol 10.12: Small-width Clifford+\(T\) threshold atlas
Fix exact versus approximate synthesis, ancilla rules, and the resource vector.
Enumerate the restricted target subgroup or a complete set of normal forms.
Compute restricted Pareto frontiers by multiobjective shortest path.
Enumerate ambient states or use meet in the middle for candidate targets.
Store an optimal witness and a lower-bound certificate for every defect.
Classify defects under qubit permutation and free Clifford equivalence.
10.4.8 Lower-bound candidates
On this page · Permalink · Source line 4034
10.4.8.1 Odd-support rank
On this page · Permalink · Source line 4035
The span of odd phase terms is invariant under some restricted rewrites but transforms covariantly under linear changes of variables. Its dimension gives a coarse obstruction.
10.4.8.2 Pauli support geometry
On this page · Permalink · Source line 4038
Represent a commuting Pauli family by an isotropic subspace of \({\mathbb F}_2^{2n}\). Restricted diagonal circuits remain in the \(Z\) Lagrangian. Ambient Clifford circuits move through the symplectic Grassmannian. Distance from the \(Z\) Lagrangian, together with the number of deposited rotations, is the phase analogue of microscopic flag escape.
10.4.8.3 Moment and derivative packets
On this page · Permalink · Source line 4041
For a phase function \(P\), finite differences
separate affine, quadratic, and higher interactions. A hierarchy of derivative tensors can record temporary flow into nonlinear phase packets.
10.4.8.4 Architecture-aware parity rank
On this page · Permalink · Source line 4048
On a coupling graph, each parity has a Steiner cost. A catalyst can be profitable by making several required parities share a Steiner tree. A sound lower bound may combine cut rank with edge congestion and restoration debt.
10.4.9 Tensor and repeated-module questions
On this page · Permalink · Source line 4051
For targets \(U\) and \(V\), independent synthesis gives
when the systems are disjoint and local Clifford cost is ignored. Joint synthesis may be better because phase identities can couple terms across modules. This motivates a stable regularization
A one-copy rigid phase target could still display tensor activation.
Conjectural frontier
There are diagonal or CNOT-dihedral targets whose Pareto frontier is strictly improved by a restored non-diagonal Clifford excursion. The smallest qubit threshold and the resource component in which the first defect appears are open in this monograph.
10.4.10 What would count as a theorem
On this page · Permalink · Source line 4070
A publishable first result in this direction should contain all of the following:
an exact target family and gate alphabets;
explicit ambient circuits;
a restricted lower bound for the same declared cost;
exact treatment of global phase and ancillas;
classification below the first threshold or a proof of minimality;
reproducible symbolic code.
Merely rewriting a phase gadget with Hadamards is not sufficient. The decisive content is the optimality comparison.