CS Paper Radar

Depth-1 expanders on the unitary group and applications

Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram W. Harrow, Xinyu Tan

cs.CC quant-phcond-mat.str-elcs.ITmath.GR ·submitted 2026-09-01 17:59 UTC · v1

Abstract

We construct a constant-degree and constant-gap quantum expander on $n$ qubits where each unitary can be implemented by a depth-$1$ and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation $S = Θ(Δ^{-1/2})$; this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states. Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single $T$ gate, a single $T^{\dagger}$ gate, or a depth-$1$ Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.

Comment
36 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.61
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

Learning Clifford-structured quantum unitaries and Hamiltonians

cs.CC quant-ph ·2026-08-10 ·Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii
similarity 0.61
Abstract

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

0.42

Verifiable quantum advantage in extremely low depth

cs.CR quant-ph ·2026-09-01 ·Alexandru Gheorghiu
similarity 0.60
Abstract · Revised admissibility conditions, corrected and clarified the supporting security analysis, and expanded the discussion of assumptions and r…

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

0.52

Explicit channels with unbounded gains in classical communication using entangled inputs

cs.IT quant-phmath-ph ·2026-09-22 ·Hao-Chung Cheng, Benjamin Lovitz, Peixue Wu
similarity 0.59
Abstract · Update: a complete Lean verification is added

A seminal result of Hastings showed that entangled inputs can increase the rate of classical communication through independent uses of a quantum channel. While Hastings' result proved the existence of this phenomenon, it has remained a major open problem to find an explicit channel with this property. In this work, we resolve this question by constructing an explicit family of finite-dimensional quantum channels for which entangling inputs between pairs of channel uses yields an unbounded separation from the achievable communication rate using unentangled inputs. We describe a circuit implementation of our channel that uses only deterministic qudit Clifford unitaries and a single binary measurement with classical feedforward. The key ingredient is a careful design of the measurement and feedforward process that yields the required one-copy and two-copy output entropy bounds from moment estimates alone, without requiring strong convergence of the underlying unitary family.

0.35

Shallow Clifford circuits on square lattices

cs.ET quant-ph ·2026-11-14 ·Dmitri Maslov
theory similarity 0.58
Abstract · Preliminary version. Comments are welcome

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\%.

0.15

Depth-Optimal Quantum Compilation

cs.CC quant-ph ·2026-09-28 ·Francisca Vasconcelos
theory similarity 0.58
Abstract

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

0.48

Data informed Ansatz Selection for Variational Quantum Circuits

cs.LG quant-ph ·2026-11-03 ·Manav Seksaria, Advith Desu, Anil Prabhakar
theory similarity 0.58
Abstract

Choosing a variational quantum circuit (VQC) usually means searching over ansatze and depths, and training each candidate. We give three rules that fix these choices from the data and the gate set alone, before any training. First, a circuit without entangling gates has a rank-one Fourier coefficient tensor on every subset of qubits. A singular value decomposition of a dataset's Fourier coefficients therefore indicates whether entanglement is needed, which qubits it connects, and a lower bound on the error of omitting it. Second, the rank of the quantum Fisher information matrix grows by $p_0$ per layer, after a first-layer deficit $d_0$, until it reaches a ceiling set by the dynamical Lie algebra. This law fixes the depth. Third, reading out all $2^N - 1$ Pauli-Z products from one batch of shots resolves half of the state's directions, the most any single-basis readout can. A single-qubit readout resolves an exponentially small fraction. For the Madelon dataset, the rules prescribe 7 blocks of 3 qubits at depth 3: a 239-parameter classifier with 78.5% test accuracy, found without a grid search. Ablations confirm three predicted effects: shallower circuits, smaller blocks and dropping reuploading all lower accuracy.

0.27

$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation

cs.CC quant-ph ·2026-10-13 ·Diyi Liu, Shuchen Zhu, Wibe Albert de Jong, Di Fang, David Williams-Young +1 more
similarity 0.58
Abstract

We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the previous exponent $5/4$. The construction uses $\widetilde{O}(N^{6/7})$ clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error $ε\in(0,1/2)$, let $L=\log_2(N/ε)$, the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using $\widetilde{O}(N^{8/7}L^{3/7}+NL)$ $T$ gates and $\widetilde{O}(N)$ clean ancillas whenever $L\le N$. We also prove that, at constant precision, the exponent $8/7$ is optimal within a sequential block-SELECT model.

0.14