Explicit Orthogonal and Unitary Designs
summary
Gives a strongly explicit construction of ε‑approximate k‑designs for O(N) and U(N) with N = 2^n, achieving size poly(N^k/ε) (equivalently seed length O(nk + log(1/ε))). Construction starts from a tiny baby distribution = one random 3‑qubit gate (O(log n) seed), proves its kth‑moment operator is 1−δ away with δ ≳ 1/poly(n,k) (spectral gap arguments, Bourgain–Gamburd density), then amplifies via derandomized squaring and representation‑theory analysis (tau ≥ 0.04, tau ≥ 1−1/m for large m) to produce samplable pseudo‑random circuits that meet the claimed bounds.
AI-written summary · about
chapters (11)
- 0:00Welcome and logistics
- 2:52Workshop introduction
- 3:38Introduction to matrix groups
- 8:16Approximate K-designs
- 12:16Known results and goals
- 17:11De-randomization techniques
- 24:28Construction methodology
- 32:15Baby distribution construction
- 40:44Inductive proof outline
- 49:55Technical theorems
- 53:12Conclusion and open problems
related talks
45mQuantum Pseudo-Randomness From Domain Walls and Spectral Gaps
44mEmergence of Universal Randomness in Quantum Many-body Dynamics
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
24mOptimal synthesis into fixed XX interactions
26mBounds on qLDPC Code Parameters
33mLightning Talks
01h 05mWhen do you need an inverse or controlled unitary oracle?