Depth-1 expanders on the unitary group and applications
2026-09-01 • Computational Complexity
Computational ComplexityInformation Theory
AI summaryⓘ
The authors build a special quantum tool called a quantum expander that acts on n qubits using very simple, shallow circuits. They apply this tool to create 1D quantum systems with ground states that show an important relationship between entanglement and energy gap, which was previously unknown. They also develop a method to efficiently test whether certain complex quantum states appear in a data stream. Additionally, they improve on past work by extending their expander to work on a large set of quantum operations with guaranteed stability properties. This work connects quantum circuits, Hamiltonians, and group theory in a new way.
quantum expanderqubitsdepth-1 circuitPauli gatesCNOT gatesfrustration-free Hamiltonianentanglement gap1D volume-law statesClifford circuitunitary group
Authors
Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram W. Harrow, Xinyu Tan
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.