CS Paper Radar

Shallow Clifford circuits on square lattices

Dmitri Maslov

cs.ET quant-ph ·submitted 2026-11-14 23:49 UTC · v1
theory

Abstract

We study the depth of CZ circuits, Clifford state preparation, and Clifford unitary synthesis over the two-dimensional square lattice. A programmable circuit on a $2{\times}k$ ladder ($n{=}2k$) implements an arbitrary CZ computation in depth at most $\frac{3n}{2}{+}3$ up to reversal of both rails. This improves the best-known LNN (Linear Nearest-Neighbor)-compliant depth-$(2n{+}2)$ construction by about 25\%. For state preparation, we consider a Phase gate programmable -H-{CNOT+P}-LC- circuit and derive matching obstructions to attaining the CZ-span counting lower bound of $2\lceil\frac{n}{2}\rceil{-}1$ for depth by the entangling gates. For cycle connectivity $C_n$, we prove that the minimum depth is exactly $2\lceil\frac{n}{2}\rceil{-}1$ when $n$ is not a multiple of four and $2\lceil\frac{n}{2}\rceil$ when $n\,{=}\,4k$. We construct a hole-free minimum-perimeter square-lattice patch with a Hamiltonian cycle for every even size, giving optimal-depth programmable circuits to implement Clifford states for all $n\,{=}\,4k{+}2$. Exhaustive and heuristic searches address the remaining cases for $n$ up to 256, and selected values up to 1,024 qubits. The improvement against comparable state-of-the-art, an LNN-compliant depth-$(2n{+}2)$ solution, is about 50\%. Finally, combining state synthesis circuits developed in this work with a known four-diagonal-stage decomposition gives rise to a depth $4n{-}4$ for $n\,{=}\,4k{+}2$ and depth $4n$ for $n\,{=}\,4k$ implementation of arbitrary Clifford unitaries. This improves the most relevant state-of-the-art, an LNN-compliant depth $7n{-}4$ construction, by about 43\%.

Comment
Preliminary version. Comments are welcome

Closest papers

Nearest neighbours by meaning across the whole index.

Clifford synthesis is NP-complete

cs.CC quant-ph ·2026-10-29 ·Søren Fuglede Jørgensen
similarity 0.66
Abstract

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

0.05

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

cs.CC quant-phcond-mat.str-elcs.IT ·2026-08-19 ·Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun
theory similarity 0.66
Abstract · 33 pages, 2 figures, 1 table

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

0.38

Exact $T$-counts of CCZ layers from an isotropy bound

cs.CC quant-ph ·2026-10-01 ·Arul Rhik Mazumder
theory similarity 0.65
Abstract · 35 pages, 5 figures, 5 tables; supplementary notes (35 pages) as an ancillary file. v3: condensed to the core results, with the remaining ma…

The $T$-count is a dominant cost of fault-tolerant Clifford$+T$ computation. We prove that every Hadamard-free Clifford$+T$ circuit with clean ancillas for a layer of $m$ disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, uses at least $6m+1$ $T$ gates. Campbell and Howard gave a circuit with $6m+1$, and to our knowledge this is the first proof that it is optimal for general $m$. The proof combines Campbell and Howard's self-orthogonality of the columns of the parity matrix with a rank (flattening) bound, sharpened by one. More generally, the argument gives a lower bound on the $T$-count of every diagonal gate in the third level of the Clifford hierarchy, the isotropy floor, computable by Gaussian elimination. It is never below the stabilizer nullity $ν$ and reaches $2ν+1$ on non-Clifford gates whose phase is purely cubic. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ ($ν=3$) with four $T$ gates and the layer with $4m$, where the floor gives seven and $6m+1$. The floor also recovers Campbell and Howard's count $4m+3$ for a fan-out of Toffolis. On the output of PyZX's TODD-based optimizer, relative to its Hadamard placement, it certifies $193$ of $311$ phase-polynomial blocks $T$-optimal once repeated parities are merged (at the best of five optimizer seeds), against $113$ for nullity, including $37$ of the $72$ blocks too large for exhaustive search.

0.33

Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?

cs.CC quant-ph ·2026-09-28 ·Keisuke Fujii
similarity 0.63
Abstract · 12 pages, 2 figures, 1 table

A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in $\mathrm{NP}\cap\mathrm{BQP}$ and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at $k=1$, recovering the repetition number contains finite-field discrete logarithm over $\mathbb{F}_{2^r}^{\times}$. In general, restricting every exponent to $\{0,1\}$ removes the Abelian-group closure and makes feasibility NP-complete for variable $k$, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.

0.36

Complexity separations for optimal matchgate-Clifford synthesis

cs.CC quant-ph ·2026-10-05 ·Berta Casas, Diego García-Martín, Yuxuan Zhang
benchmarktheory similarity 0.63
Abstract · 20 + 21 pages, 4 + 1 figures

Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.

0.37

Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac{1}{2}$ Circuits and Lower Bounds

cs.CC cs.DSmath.GR ·2026-08-26 ·Joshua A. Grochow, Gülce Kardeş, Michael Levet
publishedtheory similarity 0.62
Abstract · New result: lower-bound against CNF-of-XORs. 69 pages

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. (We also extend this to a limited class of depth-3 circuits, namely $\textsf{CNF}$-of-$\textsf{XOR}$s.) We complement this with upper bounds of uniform depth-$2\frac{1}{2}$ circuits of quasipolynomial-size: depth 3 circuits with poly-logarithmic bottom fan-in. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to $3\frac{1}{2}$; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-$2\frac{1}{2}$ construction follows a fundamentally different strategy that exploits structure more specific to groups. We guess a composition series for each group, together with generators for its terms and the isomorphism types of its composition factors. We then inductively verify that the corresponding extensions at each level of the two composition series are compatible. A central part in this approach brings to bear the extensive work on the Short Presentation Conjecture, in tandem with the algorithmic theory of group extensions and cohomology.

0.42

Improved Transversal Non-Clifford Gates from Cup Products

cs.IT quant-ph ·2026-08-17 ·Louis Golowich, Itzhak Tamo, Guanyu Zhu
published similarity 0.62
Abstract

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC codes (with constant-weight stabilizers) of polynomial distance $d\geq n^{(1-ε)/r}$ supporting transversal $C^{r-1}Z$ gates on a close-to-linear number $k\geq n^{1-ε}$ of disjoint tuples of logical qubits, for arbitrarily small $ε>0$. Our construction is the first with constant-weight stabilizers that obtains $dk\gg n$, and as a consequence achieves arbitrarily small magic state overhead exponent $γ=\log(n/k)/\log(d)>0$. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many $k=Ω(n)$ logical $C^{r-1}Z$ gates, though with stabilizer weight and physical circuit depth $n^ε$. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal $C^{r-1}Z$. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.

0.60

Computational Power of Clifford and Ising Quantum Computers

cs.CC quant-phmath.QA ·2026-11-09 ·Sawyer Dobson, Zhenghan Wang
theory similarity 0.60
Abstract · 52 pages, 26 figures

We extend the efficient classical simulation of Ising quantum computers from braidings to measurements. We investigate several different definitions of efficient Clifford quantum computation by varying the power of the circuit generator. In case the circuit generator can see the entire input, we give a detailed proof that efficient simulation of classical computation would imply the separation of complexity classes $\mathbf{P}$ and $\mathbf{PSPACE}$. If the circuit generator sees only the input length, we prove that Clifford quantum computers decide what we call affine languages.

0.30