Incompressibility and spectral gaps of random circuits

arXiv:2406.07478 · quant-ph, cs.CC · Submitted 2024-06-11 · Read on arXiv

quant-ph, cs.CC

Submitted: 2024-06-11

Updated: 2024-12-02

Comments: 79 pages, 5 figures, v2: added references and minor changes to the presentation, v3: updated acknowledgements and minor changes to the presentation

Journal ref: IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), Sydney, Australia, 1304-1312 (2025)

DOI: 10.1109/FOCS63196.2025.00069

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Spectral Gap — 111× in this paper · explained in 5 episodes
• Quantum Circuits — 86× in this paper · explained in 2 episodes
• All-to-All Connectivity — 10× in this paper · explained in 1 episode
• Approximate Unitary t-design — 9× in this paper · explained in 1 episode
• Frustration — 9× in this paper · explained in 2 episodes
• Trace — 8× in this paper · explained in 2 episodes
• Embeddings — 6× in this paper · explained in 2 episodes
• Adam — 5× in this paper · explained in 2 episodes
• Hilbert Space — 5× in this paper · explained in 2 episodes
• Generalization — 4× in this paper · explained in 13 episodes
• Benchmarking — 3× in this paper · explained in 3 episodes
• Adjacency Matrix — 2× in this paper · explained in 1 episode
• Adaptation — 1× in this paper · explained in 1 episode
• Combinatorial Optimization — 1× in this paper · explained in 2 episodes
• Query Complexity — 1× in this paper · explained in 2 episodes
• Shadow Tomography — 1× in this paper · explained in 4 episodes
• Sparsity — 1× in this paper · explained in 4 episodes
• Trace Distance — 1× in this paper · explained in 3 episodes

Sources

• The Detectability Lemma and Quantum Gap Amplification
• A simple proof of the detectability lemma and spectral gap amplification
• The Classification of Reversible Bit Operations
• Models of quantum complexity growth
• A Spectral Gap Theorem in $SU(d)$
• Simple Permutations Mix Even Better
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• A new approach to strong convergence
• Fluctuations of subsystem entropies at late times
• Tame automorphism groups of polynomial rings with property (T) and infinitely many alternating group quotients
• Proof of Aldous' spectral gap conjecture
• Faster integer multiplication using short lattice vectors
• Dynamics of Pseudoentanglement
• Random Quantum Circuits
• Quantum union bounds for sequential projective measurements
• Complexity is not Enough for Randomness

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity