This note is part of [[quantum/Practical Quantum Information System]]. > [!info] Course code > Use the companion repository for this lecture's runnable lab, helper functions, and regression checks: > - [notebooks/by_concept/quantum_complexity_theory.ipynb](https://github.com/montekkundan/quantum-code/blob/main/notebooks/by_concept/quantum_complexity_theory.ipynb) > - [qcourse/analysis.py](https://github.com/montekkundan/quantum-code/blob/main/qcourse/analysis.py) > - [tests/test_analysis.py](https://github.com/montekkundan/quantum-code/blob/main/tests/test_analysis.py) [TODO: add video - Quantum Complexity Theory] ## What This Concept Is After learning several famous algorithms, it is tempting to jump straight to dramatic claims about what quantum computers can and cannot do. Quantum complexity theory is the part of the subject that slows you down and asks for disciplined statements instead. The key question is not simply whether quantum computers are powerful. It is how that power fits into the broader map of efficient, inefficient, classical, and quantum computation. Classes such as BQP are attempts to name that map precisely. ## Foundation Terms You Need First BQP is the class of problems solvable efficiently by a quantum computer with bounded error. Classical classes such as BPP and NP describe different efficiency and verification regimes. [[quantum/Glossary#Query complexity|Query complexity]] and black-box lower bounds are useful because they tell you where even quantum computation still faces hard limits. The big beginner mistake here is to treat one successful quantum algorithm as evidence for every ambitious complexity claim you might want to make. Complexity theory exists partly to prevent that shortcut. ## How The Idea Actually Works The course's algorithm notes already give you several case studies. Deutsch-Jozsa shows black-box separation. Simon's algorithm exposes hidden structure. Shor shows an exponential speedup for a structured arithmetic problem. Grover shows a quadratic speedup for unstructured search. Quantum complexity theory asks how to organize those examples. Which ones rely on algebraic structure? Which ones are black-box results? Which ones say something about general-purpose efficiency classes and which ones do not? This note is especially important because public discussion of quantum computing often overgeneralizes. A speedup for factoring is not the same as a proof about NP-complete optimization. A black-box lower bound is not the same as a hardware impossibility. Complexity theory gives you the vocabulary to separate those statements. That is why this note should feel like synthesis rather than another protocol. It is where you learn to say exactly what your course evidence supports, what it suggests, and what it still leaves open. ## Why It Matters - It organizes the algorithm notes into a broader theoretical picture. - It stops overclaiming before it starts. - It helps you interpret research and news claims about quantum advantage more carefully. ## Source Reading Lens Read `qclec.pdf` Lectures 23-25 when you want the technical boundary: BBBV, collision-style problems, Element Distinctness, parity lower bounds, and the relationship between black-box algorithms and complexity classes. Read *Quantum Computing since Democritus* when you want the conceptual boundary. The book is especially useful for separating "quantum states are exponentially large mathematical objects" from "you can read out exponentially many classical bits." That distinction is the reason complexity theory is needed rather than slogans. > [!question] Why is BQP not the same kind of claim as "quantum computers solve NP-complete problems"? >> [!answer] BQP names problems solvable efficiently with bounded error on a quantum computer. Known flagship speedups, such as Shor's algorithm, exploit special structure. Grover gives only a quadratic black-box speedup for unstructured search, and BBBV-style lower bounds show that this quadratic behavior is optimal in that model. None of that proves efficient quantum algorithms for NP-complete problems. > [!question] Why does an $n$-qubit state not automatically give you $2^n$ readable classical bits? >> [!answer] The state vector may require exponentially many amplitudes to describe classically, but measurement does not let you freely read out all those amplitudes. The accessible classical information is constrained by the measurement process and by results such as Holevo-style limits. Quantum algorithms get power from interference and structure, not from dumping the whole state vector into a classical output register. ## Additional Study Notes **Check yourself: NP versus BQP** It is not known that NP is contained in BQP, and it is not known that BQP and NP are incomparable. These are open complexity-class questions, not settled theorems. **Check yourself: classical help does not exceed BQP** A polynomial-time quantum computer can simulate polynomial-time classical computation, so "a classical and quantum computer working together" does not define a stronger class than BQP in the usual model. **Key fact: factoring versus period finding** Shor's factoring algorithm is not proven to beat every possible classical factoring algorithm, because no superpolynomial classical lower bound for factoring is known. The black-box period-finding separation is a different, provable statement. **Check yourself: black-box search** Grover gives a quadratic speedup for unstructured search, and that quadratic improvement is optimal in the black-box model. This is a query lower-bound statement, not a proof that every search-flavored problem behaves the same way. **Question: Why is "factoring is in BQP" weaker than "BQP contains NP"?** Factoring is one specific structured number-theory problem. NP contains many verification problems, including NP-complete problems. An efficient quantum algorithm for factoring does not imply efficient quantum algorithms for all NP problems. ## Study Checks Use these after the explanation, not before it. ### Quick Checks - MCQ: Which claim is correct about BQP? A. BQP is known to contain all NP-complete problems B. BQP is bounded-error polynomial-time quantum computation C. BQP means any exponential state can be read out D. BQP is the same as P **Answer:** B. BQP is bounded-error polynomial-time quantum computation. - Why is "quantum states have exponentially many amplitudes" not enough to prove exponential classical information output? **Answer:** Measurement gives limited classical information, and quantum algorithms must arrange interference so the desired information becomes observable. ### Oral Exam Anchors > [!question] Oral exam anchor > Explain BQP and the role of bounded error. A good answer should say: BQP is the class of decision problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. Typically, the algorithm must accept yes-instances with probability at least 2/3 and accept no-instances with probability at most 1/3, or equivalent constants separated from 1/2. The exact constants are not essential because success probability can usually be amplified by repetition. Bounded error is important because quantum algorithms are probabilistic after measurement. BQP captures efficient quantum computation with reliable enough output, not deterministic certainty from a single run. ## Practical Lab This is mostly a synthesis note, so the practical side should be comparative rather than protocol-heavy. - Build one summary notebook or page that compares the structure exploited by Deutsch-Jozsa, Simon, Shor, and Grover. - Sort those algorithms by the kind of speedup they achieve. - Record one claim about quantum complexity that your course evidence supports and one claim it does not support. ## Homework Use the homework to enforce precision. - Define BQP in plain language. - Explain one thing quantum algorithms do not automatically prove about NP-complete problems. - Compare black-box lower bounds with structured-problem speedups in one short paragraph. ## References - Scott Aaronson, [Introduction to Quantum Information Science](https://www.scottaaronson.com/qclec.pdf), Lectures 23 and 24. - Scott Aaronson, *Quantum Computing since Democritus*, Chapters 6, 10, 14, 15, and 17. - MIT OpenCourseWare, [6.845 Quantum Complexity Theory](https://ocw.mit.edu/courses/6-845-quantum-complexity-theory-fall-2010/). - Scott Aaronson, [Shtetl-Optimized](https://scottaaronson.blog/).