10.2 Catalytic basis escape in symplectic Clifford synthesis
On this page · Permalink · Source line 3377
10.2.1 Binary symplectic representation
On this page · Permalink · Source line 3385
Modulo global phase and Pauli translations, an \(n\)-qubit Clifford operation acts on Pauli exponent vectors
through a symplectic matrix
The elementary gates used here act as follows:
Let \(P_n\le{\operatorname{Sp}}(2n,2)\) be the parabolic subgroup stabilizing the \(Z\) Lagrangian
The gates \(S\), \({\operatorname{CZ}}\), and \({\operatorname{CX}}\) preserve \(L_Z\). Hadamard gates do not.
Definition 10.4: Parabolic and ambient Clifford metrics
The restricted alphabet is
and the ambient alphabet is
Targets lie in \(P_n\). We study both total primitive count and entangling count, where \(H_i\) and \(S_i\) have cost zero while \({\operatorname{CX}}\) and \({\operatorname{CZ}}\) have cost one.
This is a precise basis-escape model. It is not the unique meaning of “CSS preserving” or “Clifford cost.” It is chosen because both groups are finite and the restricted subgroup has a clean Lagrangian interpretation.
10.2.2 Exact group sizes
On this page · Permalink · Source line 3428
The finite state spaces are
and
For \(n=1,2,3\) this gives:
| \(n\) | \(|P_n|\) | \(|{\operatorname{Sp}}(2n,2)|\) |
|---|---|---|
| 1 | 2 | 6 |
| 2 | 48 | 720 |
| 3 | 10,752 | 1,451,520 |
These sizes permit exhaustive breadth-first or zero-one search through three qubits.
10.2.3 Total primitive count
On this page · Permalink · Source line 3455
Exact finite computation
With every gate in \(\mathcal S_P\) and \(\mathcal S_C\) assigned unit cost and with SWAP excluded as a primitive, exhaustive search gives:
| \(n\) | restricted diameter | ambient diameter | defective targets | maximum defect |
|---|---|---|---|---|
| 1 | 1 | 3 | 0 | 0 |
| 2 | 5 | 8 | 0 | 0 |
| 3 | 8 | 12 | 24 | 1 |
At \(n=3\), six targets have distance pair \((7,6)\) and eighteen have pair \((8,7)\).
Thus three qubits are the first total-count threshold in this exact swap-free model.
10.2.3.1 A three-qubit witness
On this page · Permalink · Source line 3474
One defective target has symplectic matrix
A restricted word of length seven is
An ambient word of length six is
The Hadamards do not form a matched pair on the same wire. They open and close the Lagrangian excursion in different coordinates. This is a useful warning against assuming that every catalyst has the literal form \(g\cdots g^{-1}\).
10.2.4 SWAP sensitivity
On this page · Permalink · Source line 3516
Add \({\operatorname{SWAP}}_{ij}\) to both alphabets as a unit-cost primitive. The target groups remain unchanged, but the metric changes.
Exact finite computation
For \(n=3\) with unit-cost SWAP gates, the restricted diameter drops from eight to seven, the ambient diameter drops from twelve to eleven, and every one of the \(10,752\) parabolic targets has zero total-count defect.
The preceding twenty-four defects therefore measure a real gate-alphabet distinction, not an invariant of the subgroup inclusion alone. In many architectures SWAP is not elementary and costs three CNOTs, while in others qubit movement or relabeling changes the accounting. The theorem must retain the convention.
10.2.5 Entangling-count defects
On this page · Permalink · Source line 3525
Now assign cost zero to \(H_i\) and \(S_i\) and cost one to \({\operatorname{CX}}\) and \({\operatorname{CZ}}\).
Exact finite computation
The exact censuses are:
| \(n\) | defective targets | distance pairs | maximum defect |
|---|---|---|---|
| 1 | 0 | none | 0 |
| 2 | 4 | \((3,2)\) with multiplicity \(4\) | 1 |
| 3 | 1,624 | \(\begin{array}{c} (3,2):24,\ (4,3):432,\ (5,4):1056,\\ (6,4):48,\ (6,5):64 \end{array}\) | 2 |
The entangling metric has an earlier threshold and a larger exceptional set.
10.2.5.1 A two-qubit witness
On this page · Permalink · Source line 3549
A canonical target is
A restricted realization is
with three entangling gates. An ambient realization is
with two entangling gates.
10.2.6 Census summary
On this page · Permalink · Source line 3585
10.2.6.1 An analytic certificate for the four two-qubit defects
On this page · Permalink · Source line 3586
The four exceptional matrices admit one common lower-bound proof. Work in the declared symplectic quotient and entangling metric, with \(H_i\) and \(S_i\) free and SWAP excluded as a primitive. Put
and define
Theorem 10.5: Two-qubit orbit and exact costs
Each of the four distinct matrices \(M_D\) lies in \(P_2\) and has restricted entangling cost three and ambient entangling cost two. They form one orbit under left multiplication by the free restricted subgroup generated by \(S_0,S_1\).
Proof
The ambient sequence
has matrix \(M_0=\left(\begin{smallmatrix}J_2&0\\I_2&J_2\end{smallmatrix}\right)\). Applying \(S_0^{d_0}S_1^{d_1}\) afterwards left multiplies by \(\left(\begin{smallmatrix}I_2&0\\D&I_2\end{smallmatrix}\right)\) and gives \(M_D\). These matrices are distinct because \(J_2\) is invertible. This also proves their orbit statement and the ambient upper bound two. The displayed restricted sequence for \(M_2\) above gives \(M_{I_2}\) using three CNOT gates and one free \(S_1\). Free final phase gates then give every \(M_D\), proving the restricted upper bound three.
For the restricted lower bound, the upper-left block of a parabolic product is the product of its upper-left blocks. Each \(S\) or CZ contributes \(I_2\), while the two directed CNOTs contribute the elementary matrices
Products using at most two CNOTs belong to \(\{I_2,L,U,LU,UL\}\), which does not contain \(J_2\). Thus any restricted circuit for \(M_D\) requires at least three charged gates.
For the ambient lower bound, reorder the coordinates as \((x_0,z_0\mid x_1,z_1)\). A local Clifford acts by an invertible block-diagonal matrix in this order. In \(M_D\), each of the two diagonal \(2\times2\) blocks is \(\left(\begin{smallmatrix}0&0\\1&0\end{smallmatrix}\right)\) and has rank one. In either directed CNOT or CZ, both diagonal blocks are \(I_2\) and have rank two. Left and right multiplication by local Cliffords preserve these diagonal-block ranks. A circuit with one charged gate has the form \(K_1 E K_2\) with \(K_1,K_2\) local and \(E\) a CNOT or CZ, so it cannot equal \(M_D\). A circuit with no charged gate is local and also has rank-two diagonal blocks. The ambient cost is therefore at least two.
The complete finite census finds exactly four defective targets. Since the theorem supplies four distinct defective targets, it identifies the entire exceptional set in that census. The exact costs and orbit description above have analytic proofs, while completeness of the finite classification retains the exhaustive-search evidence.
The results establish three distinct lessons.
Basis escape produces genuine Clifford defects, not only linear CNOT defects.
The first threshold depends on whether local gates are free.
Adding a SWAP primitive can eliminate a finite total-count threshold.
10.2.7 Search completeness
On this page · Permalink · Source line 3635
The search state is the exact \(2n\times2n\) binary symplectic matrix. Every generator acts by a fixed row update. Ordinary breadth-first search gives exact unit-cost distances. Zero-one breadth-first search gives exact entangling costs. Since every state of \(P_n\) and \({\operatorname{Sp}}(2n,2)\) is reached, comparing the two distance maps is a complete census.
The optimized C++ verifier represents a \(6\times6\) matrix by a \(36\)-bit integer. It enumerates the full three-qubit group in a few seconds in the present environment. The Python implementation is slower but independently expresses the same state model.
10.2.8 Interpretation as symplectic holonomy
On this page · Permalink · Source line 3640
The parabolic subgroup is a fiber over the Lagrangian Grassmannian. A Hadamard moves one coordinate out of the chosen Lagrangian. The ambient path traverses other Lagrangian frames and returns to a target stabilizing \(L_Z\).
This is the symplectic analogue of the unitriangular Schreier loop. The catalyst is a temporary exchange of \(X\) and \(Z\) roles. The consumers are entangling gates that become cheaper in the changed frame.
10.2.9 CSS-preserving extensions
On this page · Permalink · Source line 3645
The parabolic model fixes one Lagrangian, but CSS circuit classes can be defined more narrowly or more broadly. Possible restricted alphabets include:
CNOT and Pauli gates only,
CNOT, \(S\), and diagonal controlled phases,
block-diagonal symplectic transformations preserving separate \(X\) and \(Z\) codes,
logical Clifford gates preserving a CSS stabilizer decomposition,
architecture-constrained versions of the preceding models.
Each produces a different subgroup and metric.
Research template
A full CSS threshold paper should classify cost-preserving orbits of minimal defects, identify a symplectic-flag lower-bound invariant, and determine which defects survive when SWAP, qubit permutation, or local Cliffords are assigned alternative costs.
10.2.10 Depth and parallelism
On this page · Permalink · Source line 3660
Gate-count defects do not automatically imply depth defects. Given a gate sequence, define its dependency graph and schedule commuting or disjoint gates in parallel. The appropriate quantities are
A basis change applied transversally to many qubits may have small depth even when its total count is large. Conversely, a two-gate count saving can increase depth under locality constraints.
10.2.11 Open Clifford problems
On this page · Permalink · Source line 3671
Question 10.6
What are the defect orbits of the twenty-four three-qubit total-count targets under qubit permutations and parabolic conjugation?
Question 10.7
Does the maximum parabolic-versus-Clifford defect grow linearly, as \(n\log n\), or faster under total primitive count?
Question 10.8
Can one prove a symbolic family with entangling-count defect greater than two, rather than relying on finite census data?
Question 10.9
Which finite symplectic parabolics are geodesically convex after SWAP is included as a primitive?
Conjectural frontier
The observed three-qubit defects should admit a small collection of symplectic root motifs analogous to the three-cross, one-phase classification in the unitriangular case. The present monograph records the exact census and witnesses but does not claim that classification.