Opening Quantum "Supremacy"
Quantum "Supremacy"
- Length
- 1 h 21 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2018
Chapter 1 of 12: Before the lecture
Weighs Google's 72-qubit random-circuit sampling plan against Porter–Thomas statistics and cross-entropy.
Quantum supremacy means a real quantum device performing a task that no classical supercomputer can match. O'Donnell, in session 27 of CMU 15-859BB at Carnegie Mellon, starts from the engineering problem of keeping qubits coherent on a 2D grid. Von Neumann's 1952 fault-tolerance sketch, Shor's first quantum error-correcting code and the threshold theorem of Aharonov and Ben-Or follow, with caveats about slow classical decoding. The centre is Google's plan to sample 72-qubit, 20-layer random circuits without error correction, scoring Porter–Thomas outputs by cross-entropy and KL divergence. Complexity evidence closes the argument, from Deutsch's closed time-like curves to a polynomial hierarchy collapse, assuming quantum circuits and basic complexity classes.
Quantum supremacy means a real quantum device performing a task that no classical supercomputer can match. O'Donnell, in session 27 of CMU 15-859BB at Carnegie Mellon, starts from the engineering problem of keeping qubits coherent on a 2D grid. Von Neumann's 1952 fault-tolerance sketch, Shor's first quantum error-correcting code and the threshold theorem of Aharonov and Ben-Or follow, with caveats about slow classical decoding. The centre is Google's plan to sample 72-qubit, 20-layer random circuits without error correction, scoring Porter–Thomas outputs by cross-entropy and KL divergence. Complexity evidence closes the argument, from Deutsch's closed time-like curves to a polynomial hierarchy collapse, assuming quantum circuits and basic complexity classes.
Plan for Achieving Quantum Supremacy
Fazi, Goesslerin, and Laflamme
Harrow and Mehriban paper

This lecture
Lecture 27 of 27 of Quantum Computation and Quantum Information.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in