Depth-1 expanders on the unitary group and applications

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 = \Theta(\Delta^{-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.

Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el); Computational Complexity (cs.CC); Information Theory (cs.IT); Group Theory (math.GR)

arXiv:2609.01605 [quant-ph]

(or arXiv:2609.01605v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.01605 arXiv-issued DOI via DataCite (pending registration)