Quantum Pseudo-Randomness From Domain Walls and Spectral Gaps
summary
Local brickwork random circuits on n qubits with local dimension q form approximate unitary k designs in depth scaling linear in n and k when q is large, with the 2‑design depth ≈ n + log(1/ε). One proof maps the kth frame potential to a domain wall partition function and counts excitations, another rewrites the single‑layer moment as the gap of a frustration‑free Hamiltonian and applies the Knabe finite size criterion reducing the bound to a 3‑site gap (q ≥ 6 k^2 gives a gap and an extra log q factor). Relatedly, output distributions anti‑concentrate at circuit size N log N (depth ~ log N).
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:46Based on
- 1:39Random quantum circuits are efficient implementations of randomness
- 4:06Quantum chaotic dynamics, universality, dillusion, and phase transitions
- 6:15Overview
- 8:53Intuition for designs
- 12:45Designs are useful!
- 13:31Utility of high-degree designs
- 16:23Designs from domain walls and gaps
- 17:05Moment operators
- 18:48Frame potential for ROCS
- 20:45Frame potential as a partition function
- 22:20RQC domain walls
- 24:31A panoply of domain walls
- 27:39A retreat to operator norms
- 29:49Knabe bounds on the spectral gap
- 31:28Rough recap
- 33:18(Almost) Linear designs from spectral gaps
- 36:31Google experiment
- 37:30Going beyond designs: Anti-concentration
related talks
01h 00mExplicit Orthogonal and Unitary Designs
01h 03mConstant depth pseudoentanglement - Shallow circuits, deep backstory
33mLightning Talks
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
44mEmergence of Universal Randomness in Quantum Many-body Dynamics
51mCircuit Conspiracies
32mTowards local testability for quantum coding
01h 10mQuantum Advantage with Shallow Clifford Circuits