Questions: BQP and Quantum Complexity Classes

Question 1

Which of the following best describes the relationship between BQP and NP?

• A. BQP contains NP — quantum computers can solve all NP problems efficiently
• B. NP contains BQP — every quantum polynomial-time problem is also in NP
• C. BQP and NP are believed to be incomparable — neither contains the other
• D. BQP equals NP — they are the same class

Answer: (C)

BQP and NP are believed to be incomparable. BQP contains problems (like factoring and simulating quantum systems) that are not known to be in NP. NP contains NP-complete problems (like SAT) that Grover's algorithm can speed up only quadratically, not enough for polynomial time. There is no proof of separation — just strong evidence from the structure of known algorithms. The oracle separation results support incomparability.

Question 2

BQP is contained in PSPACE because a classical computer with polynomial space can simulate any polynomial-time quantum computation.

• T. True
• F. False

Answer: True

A quantum circuit on n qubits has a state vector of 2^n amplitudes, each requiring polynomial bits of precision. A classical computer can simulate the entire computation by tracking this state vector, using exponential time but only polynomial space (process one amplitude at a time, or use the Feynman path integral approach). Since PSPACE allows exponential time with polynomial space, BQP is in PSPACE. This does not make quantum computers useless — the time savings can be exponential, even if the space requirements are the same.

Question 3

What is QMA, and how does it relate to NP? Give an example of a QMA-complete problem.

Model answer: QMA (Quantum Merlin Arthur) is the class of problems where a quantum verifier can check a quantum proof (witness state) in polynomial time. It is the quantum analog of NP (or more precisely, MA). NP is contained in QMA because a classical proof can be encoded as a quantum state. The Local Hamiltonian problem is QMA-complete: given a sum of local Hamiltonians, determine whether the ground-state energy is below a threshold. This is the quantum analog of the Cook-Levin theorem — it was proved by Kitaev.

QMA generalizes NP in two ways: the proof can be a quantum state (exponentially hard to describe classically), and the verifier is a quantum computer. The Local Hamiltonian problem being QMA-complete means it is the hardest problem in QMA — if you could solve it efficiently, you could solve all QMA problems. The connection to physics is direct: determining the ground-state energy of a quantum system is computationally hard even for quantum computers (QMA-hard), which is why quantum chemistry simulation requires clever algorithms rather than brute force.