Are Random Quantum Circuits PRUs?
summary
Claims that random brickwork circuits are PRUs assuming no efficient algorithm can exactly learn a random circuit’s depth; proves a conditional reduction: if they were not pseudorandom then a polynomial‑query algorithm (constructed nonexplictly via t‑design bounds, a hybrid step, embedding high‑entropy distributions, and a von Neumann minimax amplification) would learn depth with high probability. Result yields t-designs used quantitatively, an ancilla-free PRU construction, a classical reversible analogue, and a poly‑query statistical depth‑learning algorithm.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation
- 2:01The random circuit heuristic
- 9:34Statistical properties
- 17:32Pseudorandom unitaries
- 24:10Main theorem and results
- 37:55Proof sketch and insights
- 44:18Technical details and outlook
- 1:06:33Closing discussion
related talks
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
51mCircuit Conspiracies
37mQuantum Pseudorandomness and Classical Complexity
45mQuantum Pseudo-Randomness From Domain Walls and Spectral Gaps
45mNoise vs Imprecision in the Hardness of Random Quantum Circuits
01h 03mConstant depth pseudoentanglement - Shallow circuits, deep backstory