Comparing BQP to P, NP, and PP

Table of Contents

1. Introduction
2. Complexity Classes at a Glance
3. What Is BQP?
4. What Is P?
5. What Is NP?
6. What Is PP?
7. The Inclusion Chain: P ⊆ BPP ⊆ BQP ⊆ PP
8. BQP vs P
9. BQP vs NP
10. BQP vs PP
11. Oracle Separations
12. Does BQP Contain NP-Complete Problems?
13. Is BQP Harder Than NP?
14. Is BQP Equal to PP?
15. Known Problems in BQP
16. Factoring and Discrete Log
17. Grover’s Search and Quadratic Speedups
18. Approximate Counting and BQP
19. PostBQP and the Role of Postselection
20. Implications for Cryptography
21. Quantum Advantage vs Classical Intractability
22. BQP and Quantum Supremacy
23. The Landscape of Complexity Classes
24. Open Problems and Conjectures
25. Conclusion

1. Introduction

Quantum complexity theory raises fundamental questions about the limits and powers of quantum computation. In this article, we compare BQP to the classical classes P, NP, and PP, uncovering their relationships, differences, and implications for computational theory and practice.

2. Complexity Classes at a Glance

3. What Is BQP?

BQP (Bounded-error Quantum Polynomial Time) is the class of decision problems solvable by a quantum computer in polynomial time with error probability ≤ 1/3.

4. What Is P?

P contains problems solvable in polynomial time on a deterministic Turing machine:
\[
P = \{L \mid \exists \text{ a poly-time algorithm } A \text{ such that } A(x) = L(x)\}
\]

5. What Is NP?

NP is the set of problems for which a proposed solution can be verified in polynomial time.

\[
L \in NP \iff \exists \text{ poly-time verifier } V(x, w)
\]

6. What Is PP?

PP (Probabilistic Polynomial Time) accepts if more than 50% of computation paths accept. It allows unbounded error but requires majority vote.

7. The Inclusion Chain: P ⊆ BPP ⊆ BQP ⊆ PP

It is known that:

\[
P \subseteq BPP \subseteq BQP \subseteq PP
\]

• BQP sits between classical randomness and unbounded probabilistic acceptance.

8. BQP vs P

All deterministic problems in P are also in BQP:
\[
P \subseteq BQP
\]

But BQP contains problems believed not to be in P:

• Integer factoring (Shor’s algorithm)

9. BQP vs NP

The relationship between BQP and NP is unresolved:

• BQP can solve some problems outside P
• But is not known to solve NP-complete problems efficiently

10. BQP vs PP

• PP is much larger than BQP in expressive power
• Aaronson proved:
  \[
  \text{PostBQP} = PP
  \]
  This shows that adding postselection to BQP boosts its power dramatically.

11. Oracle Separations

Relative to oracles:

• \( BQP \not\subseteq PH \)
• \( NP \not\subseteq BQP \)
• Suggests BQP and NP are incomparable in power

12. Does BQP Contain NP-Complete Problems?

• No known efficient quantum algorithm solves NP-complete problems
• Believed that NP-complete \(\notin\) BQP

13. Is BQP Harder Than NP?

BQP is not strictly more powerful than NP:

• NP involves non-deterministic search
• BQP relies on unitary evolution and interference

14. Is BQP Equal to PP?

No. But PostBQP = PP
BQP is a subset of PP and cannot solve all PP-complete problems.

15. Known Problems in BQP

• Factoring
• Discrete logarithm
• Simon’s problem
• Order-finding
• Quantum simulation

16. Factoring and Discrete Log

Both are in BQP due to Shor’s algorithm:

• Neither is known to be NP-complete
• Their classical hardness forms basis of modern cryptography

17. Grover’s Search and Quadratic Speedups

Grover’s algorithm provides quadratic speedup for unstructured search:

\[
O(\sqrt{N}) \text{ vs classical } O(N)
\]

But doesn’t make NP-complete problems easy.

18. Approximate Counting and BQP

Quantum algorithms offer improvements for counting problems:

• Related to #P and PP
• Example: Quantum amplitude estimation

19. PostBQP and the Role of Postselection

PostBQP allows quantum circuits to condition on measurement outcomes. Aaronson showed:

\[
\text{PostBQP} = PP
\]

It shows the sensitivity of complexity to model changes.

20. Implications for Cryptography

• BQP threatens RSA, Diffie-Hellman, ECC
• Cryptographic primitives in NP may remain secure if \( NP \not\subseteq BQP \)
• Post-quantum cryptography is needed

21. Quantum Advantage vs Classical Intractability

Quantum algorithms give exponential speedups in some cases, but:

• Do not break all hard problems
• Often require structured input (e.g., periodicity)

22. BQP and Quantum Supremacy

Quantum supremacy refers to quantum computers performing a task infeasible classically, often related to sampling problems, not necessarily BQP-complete problems.

23. The Landscape of Complexity Classes

      NP
     /  \
P ⊆ BPP  \
     \   BQP
       \  /
       PP

Arrows represent containment. Dotted lines denote unknown relations.

24. Open Problems and Conjectures

• Is NP ⊆ BQP? (believed false)
• Are there BQP-complete problems?
• Can BQP be characterized by natural complete problems?

25. Conclusion

BQP represents a fascinating middle ground between classical efficiency (P), classical verifiability (NP), and probabilistic power (PP). While it enables exponential speedups for select problems, it does not unlock all intractable tasks. Understanding where BQP fits helps shape the future of quantum algorithms, complexity theory, and cryptography.