Quantum computing · Theory and computer search (AI-assisted)
Shallow Clifford circuits on square lattices
arXiv:2611.19671v1 ↗PDF ↗Submitted 14 November 2026
- Question
- Many processors are square grids with nearest-neighbour two-qubit gates. How shallow can a fixed entangling circuit be that prepares every \(n\)-qubit stabilizer state when only its single-qubit phase gates are reprogrammed, and what about every CZ circuit or every Clifford unitary? The best comparable constructions follow a line of qubits and have entangling depth \(2n+2\) for states and CZ circuits and \(7n-4\) for Clifford unitaries.
- Result
- Any universal programmable circuit of this kind needs entangling depth at least \(2\lceil n/2\rceil-1\) on any hardware. A cycle of qubits attains this exactly unless \(n\) is divisible by four, where one more layer is necessary and sufficient, while no tree, including a line, can attain it. Every even \(n\) has a compact hole-free square-lattice patch containing a Hamiltonian cycle, giving optimal templates for \(n=4k+2\); searches cover other sizes up to 256 qubits. Arbitrary CZ circuits fit in depth \(3n/2+3\) on a \(2\times k\) ladder, and arbitrary Clifford unitaries in depth \(4n-4\) (\(n=4k+2\)) or \(4n\) (\(n=4k\)).
The paper in detail
The paper counts the depth of two-qubit layers, the dominant cost on most hardware, on a fixed patch of the square lattice used by superconducting, trapped-ion and neutral-atom designs. Its target is a programmable template: a fixed pattern of CNOT gates between neighbours, with single-qubit phase gates inserted at chosen points, that can be set to produce any stabilizer state. Every stabilizer state is a graph state up to local Clifford gates, so a template that implements every CZ circuit on \(\ket+^{\otimes n}\) suffices. Any leftover linear reversible map at the end does not matter, because it leaves \(\ket+^{\otimes n}\) unchanged.
Universality reduces to linear algebra. A CNOT network carries parities of the inputs on its wires, and a phase gate on a wire holding the parity \(\ell_w\) contributes the CZ gates between all pairs of inputs in \(w\). The template is universal exactly when these contributions span the \(\binom n2\)-dimensional space of CZ circuits over \(\mathbb F_2\). Each CNOT changes one wire's parity and so adds at most one new direction, and a layer holds at most \(\lfloor n/2\rfloor\) gates, which gives the lower bound \(2\lceil n/2\rceil-1\) on any connectivity.
Meeting the bound is restrictive: every layer must be a maximum matching and every gate must add a new direction, so an edge cannot be reused in consecutive layers. For even \(n\) this excludes graphs with a leaf, bridge or cut vertex, and for cubic graphs it requires a three-edge-colouring, so the Petersen graph fails despite diameter two. No tree on four or more vertices works, so a line of qubits cannot reach the bound. A cycle can: alternating brick layers reach full rank at depth \(n-1\) or \(n\), except when \(n\) is divisible by four, where an invariant of the layer sums forces one more layer.
Odd cycles do not fit on a square lattice, so the construction turns to even sizes: for every even \(n\) a notched rectangle of minimum perimeter, built from two-row strips joined into one Hamiltonian cycle, carries the cycle schedule. That gives optimal-depth templates for all \(n=4k+2\) in a patch about \(\sqrt n\) on a side; the remaining sizes come from exhaustive and heuristic searches. A \(2\times k\) ladder with programmable rung CZ gates implements any CZ circuit in depth \(3k+3\), and pairing a template with its transpose inside a four-stage Clifford decomposition gives the unitary depths \(4n-4\) and \(4n\).
For circuits allowed to depend on the target state, a counting argument over normalised layers gives only about \(0.22n\), a factor of about 4.5 below the templates, and closing that gap is open. Other open questions are whether lattice patches, unlike cycles, can reach \(n-1\) for \(n\) divisible by four, and how the templates behave under realistic noise.
Transferable methods
Phase-polynomial rank criterion and counting bound
Whether a CNOT network with phase slots can implement every CZ circuit is a rank question over \(\mathbb F_2\): each phase slot contributes a fixed vector in the space of CZ circuits. Counting how fast the rank can grow per gate gives a lower bound that holds on any hardware.
A wire carrying the parity \(\ell_w(x)=\bigoplus_{j:w_j=1}x_j\) satisfies \[\ell_w(x)\equiv\sum_jw_jx_j+2\sum_{i<j}w_iw_jx_ix_j\pmod4,\] so a phase gate \(P\) there contributes the CZ vector \(q(w)=(w_iw_j)_{i<j}\) plus linear phases that input phase gates can cancel. The template implements every diagonal Clifford up to its fixed endpoint exactly when \[\mathrm{rank}_{\mathbb F_2}\{q(w)\ \text{over all phase slots}\}=\binom n2.\]
Initially each wire carries one input and \(q(e_j)=0\). A CNOT updates one wire, \(w_t\leftarrow w_t\oplus w_c\), so it adds at most one new vector to the span, and a layer has at most \(\lfloor n/2\rfloor\) gates: \[d\ge\left\lceil\binom n2\Big/\Big\lfloor\frac n2\Big\rfloor\right\rceil=2\Big\lceil\frac n2\Big\rceil-1.\] For six qubits on a cycle, five alternating layers reach ranks 3, 9 and 15 at the phase cuts after layers 1, 3 and 5, and \(15=\binom62\).
Editorial check: computing the rank of the cycle schedule \(\mathcal L_t\) for \(n=3,\dots,20\), with a phase slot after every layer, gives full rank at depth \(2\lceil n/2\rceil-1\) whenever \(4\nmid n\), and deficits of 1, 2, 3, 4 and 5 at \(n=4,8,12,16,20\) (for example 26 of 28 at \(n=8\)) that one extra layer closes, as Lemma 7 states.
How to reuse it
For any programmable circuit family built from linear reversible gates and diagonal phases, track the span of available phase-polynomial terms over \(\mathbb F_2\). Rank gained per gate is both a pruning rule for search and a source of lower bounds.
Matching obstructions and a layer-sum invariant
At the counting bound no gate may be wasted, which forces every layer to be a maximum matching and forbids reusing an edge in consecutive layers. On a cycle with \(n\) divisible by four, a rotation symmetry makes the layer sums linearly dependent, so some gates must be wasted and one extra layer is unavoidable.
Reusing edge \((u,v)\) in consecutive layers produces only parities already present (\(u\), \(v\), \(u\oplus v\)), so the second use adds nothing. For even \(n\) every layer is then a perfect matching, and if the edges lying in perfect matchings formed a disconnected graph no parity could mix the components; a cut vertex makes some edges lie in no perfect matching, which excludes leaves, bridges and cut vertices.
On the cycle \(C_{2m}\) with \(m\) even, interior layers are forced to point uniformly one way around, and within a layer the \(m\) increments are rotations by two sites of one vector. The sum of a layer's increments lies in a rotation-invariant subspace whose dimension is at most \[m+2\Bigl(\frac m2-1\Bigr)=n-2,\] so the \(n-1\) layer sums of a depth-\((n-1)\) circuit are dependent: some nonempty set of gates sums to zero, contradicting that every gate is productive.
On a path the same idea gives a local cancellation at an even vertex with neighbours carrying \(a\) and \(c\): \[\mathrm{CZ}(a,b)\,\mathrm{CZ}(b,c)\,\mathrm{CZ}(a,b\oplus c)\,\mathrm{CZ}(c,a\oplus b\oplus c)\sim I,\] since every pair appears twice and \(\mathrm{CZ}(c,c)\) is trivial (editorial expansion). For the lattice embedding, \(s=\lceil2\sqrt n\rceil\), \(h=2\lfloor(s+1)/4\rfloor\), \(w=s-h\) and a notch of \(r=hw-n\) sites give a minimum-perimeter patch; editorial check: the bounds \(0\le r\le h-2\), \(r\) even and \(w\ge3\) when \(r>0\) hold for every even \(n\le2000\).
How to reuse it
In any regime where every gate must contribute, look for sums over a symmetry orbit of gates: if they live in a smaller space than their number, a forced dependency gives an exact lower bound for that hardware graph, often with a clean dependence on \(n\) modulo a small integer.
Context & limitations
Why it matters. It roughly halves the entangling depth of universal stabilizer-state preparation on grids, with a matching lower bound for that class of circuits, and cuts Clifford-unitary depth by about 43%. Such circuits run randomized-benchmarking recovery, stabilizer-basis readout and error-correction primitives, so on noisy hardware fewer layers directly mean less error.
Limitations. Depth counts only two-qubit layers. The optimality concerns fixed templates that can implement every CZ circuit; an individual state may need much less, and the paper's state-specific lower bound is only about \(0.22n\). Sizes divisible by four and odd sizes rely partly on computer searches, reported up to 256 qubits with selected values to 1024. The acknowledgements state that Codex GPT-6.1 Sol was a co-author of the work, taking part in developing and checking the mathematical arguments, designing and running the search algorithms, independent verification and preparing the manuscript.