Opening Quantum Complexity
Quantum Complexity
- Length
- 1 h 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2018
Chapter 1 of 7: Before the lecture
O'Donnell writes quantum acceptance probabilities as sums over computational paths to prove that BQP is contained in PP.
Quantum complexity theory asks where BQP, the class of decision problems solved by polynomial-size quantum circuits with bounded error, sits among classical complexity classes. O'Donnell, in session 26 of Carnegie Mellon's 15-859BB, defines BQP, recasts factoring as a decision problem, and draws a map of P, BPP, NP, co-NP, QMA and PP. He then simulates quantum circuits classically, first by computing every amplitude in exponential time and space. The Bernstein–Vazirani path-sum method cuts that to polynomial space. A refinement of the same sum gives the Adleman–Demaris–Huang result that . The material assumes quantum circuits with Hadamard, NOT and CNOT gates, and the standard definitions of P, NP and randomized classes.
Quantum complexity theory asks where BQP, the class of decision problems solved by polynomial-size quantum circuits with bounded error, sits among classical complexity classes. O'Donnell, in session 26 of Carnegie Mellon's 15-859BB, defines BQP, recasts factoring as a decision problem, and draws a map of P, BPP, NP, co-NP, QMA and PP. He then simulates quantum circuits classically, first by computing every amplitude in exponential time and space. The Bernstein–Vazirani path-sum method cuts that to polynomial space. A refinement of the same sum gives the Adleman–Demaris–Huang result that . The material assumes quantum circuits with Hadamard, NOT and CNOT gates, and the standard definitions of P, NP and randomized classes.
Paper by Raz and Tal
This lecture
Lecture 26 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. What comes after is on the rightat the bottom. 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