Source-linked AI summary
Depth-1 expanders on the unitary group and applications
Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram W. Harrow, Xinyu Tan
TL;DR
The paper addresses open questions about efficient constant-gap quantum expanders and entanglement-gap scaling in one-dimensional frustration-free systems. It constructs depth-1 expanders, applies them to frustration-free Hamiltonians and streaming state testing, and achieves the conjectured scaling S = Θ(1/∆^1/2).
Problem
Efficient quantum expander constructions with shallow one-dimensional circuits were open, as was whether linear 1/∆ entanglement scaling is optimal for one-dimensional frustration-free Hamiltonians.
Method
The paper constructs constant-gap quantum expanders whose defining unitaries are depth-1 circuits, then uses them in frustration-free Hamiltonian constructions and streaming state-testing protocols.
Results
S = Θ(1/∆^1/2) is achieved for the entanglement-gap relation in a frustration-free example, while the paper also gives streaming tests for highly entangled states.
Takeaways & Limitations
The construction illustrates the limits of one-dimensional area laws and supports streaming tests for states generated by constant-depth circuits or constant-bond-dimension MPOs.
Takeaways & Limitations
The main proof only requires sequential or staircase expander circuits, and simpler constructions with fewer unitaries or larger gaps remain open.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper constructs constant-degree, constant-gap quantum expanders whose unitaries are depth-1 circuits on a 1D geometry, and develops applications to entanglement, streaming tests, and unitary-group expansion.
- Depth-1 quantum expanders: Constant-degree and constant-gap quantum expanders exist with defining unitaries implemented as depth-1 circuits of Pauli or CNOT gates.The construction uses CNOT expanders on 1D geometry and adds constant-range generators to obtain a quantum expander.
- Unitary-group expansion: A degree-25 expander on SU(2^n) has constant spectral gap, with each unitary a single T or T† gate or a depth-1 Clifford circuit.The construction extends to SU(d) for all d ≥ 2 with degree at most 5400.
- Unitary-group expansion: Sampling sequences from the expander yields an ε-approximate k-design in depth O(nk + log(1/ε)).These approximate designs match the cardinality lower bound 2^Ω(nk).
- Applications: The construction gives frustration-free 1D Hamiltonians with gap Θ(n^-2), unique ground states, and entanglement entropy Θ(n), achieving S = Θ(Δ^-1/2).This realizes the conjectured entanglement-gap exponent α = 1/2, whereas prior constructions had smaller exponents.
- Applications: A single-pass streaming protocol uses O(Δ^-1 log(1/ε)) memory to implement a measurement close to the projector onto a highly entangled state.The tested target can be replaced by a constant-bond-dimension, translation-invariant matrix product operator without changing the memory cost.
- Open questions: The paper leaves open whether many-particle clock Hamiltonians can amplify the construction’s gap to 1/n while preserving volume-law entanglement.It also leaves open extending the streaming protocol to more natural states such as ground states of translation-invariant Hamiltonians.
2 Depth-1 quantum expanders
The paper constructs constant-degree, constant-gap quantum expanders whose generators are depth-1 circuits on one-dimensional qubit geometries. It develops these constructions first for Pauli/CNOT circuits and then for SU(2^n), with an extension to SU(d) for all d ≥ 2.
- 2 Depth-1 quantum expanders: 16 depth-1 unitary matrices on 3s qubits form a quantum expander with spectral gap at least 1/(2 · 10^8).The first six generators act only on the first three qubits, while the remaining generators are translation-invariant over three-qubit blocks with periodic boundary conditions.
- 2 Depth-1 quantum expanders: The construction promotes a CNOT expander derived from Kassabov’s generators into a quantum expander by adding single-qubit Pauli X and Z gates.Kassabov’s generators correspond to depth-1 CNOT circuits on a 1D local geometry; the augmentation follows a 2-design argument.
- 2 Depth-1 quantum expanders: The resulting expander family has constant degree and constant spectral gap as the number of qubits increases.An expander family keeps both the number of unitaries and the gap fixed while dimensions grow; the construction applies for n = 3s.
- 2 Depth-1 expanders on the special unitary group: For every d ≥ 2, there is an explicit expander on SU(d) of degree at most 5400 with a uniformly bounded spectral gap.For d ≥ 8, the construction uses injective embeddings from SU(2^3s) and at most 216 × 25 generators; smaller dimensions use existing gapped constructions.
3 Application 1: tightness of gap vs entanglement in 1D
The paper constructs frustration-free 1D Hamiltonians with unique, volume-law-entangled ground states and gap Θ(n^-2), achieving the believed optimal relation S = Θ(Δ^-1/2).
- Motivation: The open problem is whether a 1D Hamiltonian can combine Θ(n) bipartite entanglement with a gap larger than the previously known ∼1/n^4.The construction targets constant local dimension and avoids vanishing interaction strengths associated with some earlier examples.
- Construction and theorem: Theorem 3.1 gives a frustration-free 1D Hamiltonian family with a unique ground state having bipartite entanglement entropy Θ(n).The Hamiltonians are defined on a line with O(1) local dimension.
- Construction and theorem: The construction uses data qudits for entanglement and left/right clock qudits to apply quantum-expander unitaries along a 1D snaking geometry.The clock system can be flattened into a line while retaining constant local dimension.
- Construction and theorem: The propagation and checking terms are frustration-free, while the expander constraint makes the Bell-pair ground state unique.The ground state is the state |Γ⟩ of n Bell pairs between the left and right regions.
- Construction and theorem: The spectral gap is Θ(n^-2), primarily because the propagation Hamiltonian has gap approximately π^2/(4α^2n^2).For α = 2, the gap has the lower bound 4/(25n^2).
- Implications: The example saturates the believed frustration-free scaling S ≲ 1/Δ^1/2, while the matching upper-bound question remains open.The paper also notes a limitation: the proof needs sequential/staircase expander circuits, a class broader than constant-depth circuits.
4 Application 2: streaming testing of highly entangled states
The paper converts an expander-based EPR-pair test into a one-pass streaming tester for highly entangled 1D states, using memory that scales inversely with the expander gap.
- Tester: The application tests whether a streamed 2n-qubit state is close to the n-Bell-pair state |Γn⟩.The streaming model delivers qubits in order and provides markers at times 1, n, and 2n.
- Tester: A one-pass test uses O(ℓ + log m) = O(1) qubits and O(1) classical bits of memory for the depth-1 expander.The verifier applies controlled expander unitaries while retaining a rolling window for local and wraparound gates.
- Implementation: The depth-1 expander’s translation-invariance and boundary support allow its unitaries to be implemented with an O(1)-sized lookup table.The controlled gates are applied once all qubits in their support have arrived.
- Amplification: Repeating the expander r times reduces the orthogonal-state norm to at most (1 − ∆)^r and yields space complexity O(∆^-1 log(1/ε)).The verifier keeps an O(rℓ)-qubit window and chooses r so that (1 − ∆)^r = ε.
- Guarantee: The test has zero probability of a false negative on the target state |Γn⟩.The expander-based analysis supplies the accept-probability guarantee for states tested against this target.
- Generalizations: The tester extends to states U|Γn⟩ when U is a constant-depth almost translation-invariant circuit or a constant-bond-dimension MPO.The corresponding operator UAU† remains a sum of a constant number of matrix product operators.
5 Improved local gap scaling of 1D ground states
Building on robust-polynomial and AGSP techniques, the paper improves the frustration-free 1D entanglement upper bound from approximately 1/∆loc to 1/∆loc^3/4+o(1).
- Motivation: The previous best known frustration-free entanglement bound was S ≲ ˜O(1/∆loc), while the conjectured global-gap dependence is closer to O(1/∆gbl^1/2).The paper distinguishes the local gap ∆loc from the global gap ∆gbl.
- Method: The method approximates subchain ground-space projectors using Chebyshev polynomials, robust polynomials, and the detectability lemma.The construction recursively improves polynomial approximations and then combines overlapping left and right approximations into an AGSP.
- Result: The result moves the known upper bound closer to the conjectured frustration-free scaling in the global gap, but does not establish that conjecture.The paper explicitly states that the matching upper-bound question remains open.
- Method: The resulting AGSP has shrinking e^-˜Θ(t^2∆^3/4) and Schmidt rank ˜O(e^t) after setting k = t∆^1/4.The AGSP condition is enforced by choosing t = ˜O(1)/∆^3/4.
6 Spectral gap versus ground state correlation
The section develops geometry-independent upper bounds on spectral gaps for Hamiltonians with highly correlated or CAT-like ground states, and examines how tight those bounds are. It also gives a frustration-free 1D construction attaining the stronger inverse-quadratic scaling while identifying an unresolved exact-CAT case.
- Correlation bounds: A ground state with O(1) correlation across distance d forces the gap to satisfy Δ ≲ 1/d.This follows from exponential correlation decay with correlation length ξ = O(Δ^-1).
- CAT-like states: For CAT-like ground states, a well-separation argument yields the geometry-independent bound Δ ⩽ Θ(1/n).The argument applies when the state has weight on well-separated subspaces, not only for an exact CAT state.
- Proof strategy: A truncated B-only Hamiltonian produces H′ whose ground state has fidelity at least 0.99 with the original state, spectral gap Ω(Δ), and norm O(n).The truncation retains the O(n + 1/Δ) lowest eigenvalues and eigenspaces of the B-only term.
- Tightness: For frustration-free Hamiltonians, a modified Feynman–Kitaev construction achieves the CAT-state bound, while general CAT-like states require the well-separation argument.The construction uses a padded depth-1 circuit and a coupling term between chains.
- Tightness: The XXZ example has inverse-polynomial support on two subspaces separated by Hamming distance V/2, while its spectral gap is O(1/n).This demonstrates that the well-separation technique is nearly tight.
- Open problem: It remains unknown whether a local Hamiltonian close to the CAT state itself can have spectral gap Ω(1/n).A possible low-depth distillation approach is suggested, but its implementation is unresolved.