Quantum Computational Complexity Theory

Quantum Computational complexity theory is a imaginary computer science that classifies computational problems based on the resources needed to solve them. These resources include time (computational steps), space (memory used), and randomness (probability in decision-making processes). Traditional complexity theory relies on classical computing models such as deterministic Turing machines (DTMs) and probabilistic Turing machines (PTMs). With the advent of quantum computing, a new computational model emerged—the Quantum Turing Machine (QTM). This shift required redefining complexity classes and analysing the computational advantages of quantum algorithms over classical ones.

Results in Quantum Complexity Theory

1. Deutsch-Jozsa Algorithm (1992): Demonstrated an exponential speedup for a specific decision problem, proving that quantum algorithms can be more efficient for certain computations.
2. Shor’s Algorithm (1994): Provided an efficient quantum algorithm for integer factorization, which is classically hard (believed to require super polynomial time).
3. Grover’s Algorithm (1996): Achieved a quadratic speedup in unstructured search problems, reducing search complexity from O(N) to O(√N).

Quantum versus Classical Complexity Classes

Classical Complexity Classes

• P (Polynomial Time): Problems solvable by a deterministic Turing machine in polynomial time.
• NP (Nondeterministic Polynomial Time): Problems verifiable in polynomial time by a deterministic machine but solvable in polynomial time by a nondeterministic machine.
• BPP (Bounded-Error Probabilistic Polynomial Time): Problems solvable by a probabilistic Turing machine in polynomial time with error probability less than 1/3.
• PSPACE (Polynomial Space): Problems solvable with a polynomial amount of memory.

Quantum Complexity Classes

• EQP (Exact Quantum Polynomial Time): Problems solvable with zero error in polynomial time using a quantum Turing machine.
• BQP (Bounded-Error Quantum Polynomial Time): Problems solvable by a QTM in polynomial time with error probability less than 1/3.
• QMA (Quantum Merlin-Arthur): The quantum analog of NP, where a verifier checks a quantum proof with bounded error.
• QIP (Quantum Interactive Polynomial Time): Problems solvable with an interactive quantum proof system.

Basic Inclusions Between Complexity Classes:

P⊆EQP⊆BQP

BPP⊆BQP⊆PS PACE

These inclusions establish that quantum computers can efficiently simulate classical ones but may have computational advantages over classical probabilistic models.

Quantum Time and Space Complexity

The efficiency of quantum algorithms is primarily analysed in terms of time complexity (how fast an algorithm runs) and space complexity (how much memory is required).

Quantum Time Complexity

The Quantum Turing Machine (QTM) is a fundamental model used to define quantum time complexity. It operates on qubits instead of classical bits and performs unitary transformations instead of deterministic transitions.

• BQP is contained within PSPACE: This means that quantum algorithms, despite their advantages, cannot solve problems requiring more than polynomial space.
• BQP vs. NP: It is still an open question whether BQP is strictly more powerful than NP or whether quantum computers can efficiently solve NP-complete problems.

Quantum Space Complexity

Unlike time complexity, quantum computing does not significantly reduce space complexity. This is because the reversibility of quantum computations restricts the extent to which memory can be reused efficiently.

Quantum Complexity Classes Explained

Quantum complexity classes classify computational problems based on their solvability using quantum computers. These classes are like classical complexity classes but incorporate the principles of quantum mechanics, such as superposition, entanglement, and quantum parallelism.

Basic Quantum Complexity Classes

EQP (Exact Quantum Polynomial Time)

• Represents problems that a quantum Turing machine (QTM) can solve in polynomial time with zero error.
• Equivalent to the classical P class but using quantum computing.
• Mathematically: EQP= {L∣There exists a QTM that decides L in polynomial time with certainty}.
• Inclusion Relation: P⊆EQP⊆BQP

BQP (Bounded-Error Quantum Polynomial Time)

• The most well-known quantum complexity class.
• Represents problems solvable by a quantum computer in polynomial time, where the probability of an incorrect answer is at most 1/3.
• Definition: BQP= {L∣There exists a QTM that decides L in polynomial time with an error probability ≤1/3}.
• BQP includes problems that benefit from quantum algorithms such as Shor’s algorithm (for factoring) and Grover’s algorithm (for search).
• Inclusion Relation: P⊆BPP⊆BQP⊆PSPACE
  • BQP contains BPP (Bounded-Error Probabilistic Polynomial Time) but is believed to be disjoint from NP-complete problems.

QMA (Quantum Merlin-Arthur)

• The quantum analog of NP (Nondeterministic Polynomial Time).
• Represents problems where a “quantum proof” can be efficiently verified by a quantum computer in polynomial time, with a bounded probability of error.
• Inspired by classical Merlin-Arthur (MA) proof systems, where a powerful prover (Merlin) sends a proof to a verifier (Arthur).
• Mathematical Definition:

QMA= {L∣A quantum verifier can check a quantum proof for L in polynomial time, with error probability ≤1/3}.

• Example: The Local Hamiltonian Problem: A generalization of classical constraint satisfaction problems (CSPs), which are QMA-complete.
• Inclusion Relation: NP⊆QMA⊆PSPACE

QMA-Complete

• Analogous to NP-complete problems in classical complexity.
• A problem is QMA-complete if:
  1. It belongs to QMA.
  2. Any other problem in QMA can be efficiently reduced to it.
• Example: The Local Hamiltonian Problem (quantum analog of MAX-SAT).

Interactive and Space Complexity Classes

QIP (Quantum Interactive Polynomial Time)

• The quantum version of IPP (Interactive Polynomial Time).
• Represents problems solvable through an interactive protocol between a quantum prover and a quantum verifier.
• Key result:

QIP=PSPACE

• This means quantum interactive proofs are as powerful as deterministic polynomial-space algorithms.

QSZK (Quantum Statistical Zero Knowledge)

• The quantum analog of SZK (Statistical Zero Knowledge).
• Contains problems where a verifier can check a quantum proof without gaining any extra knowledge.
• Example:
  • Quantum state distinguishability problems.

BQSPACE (Bounded Quantum Space)

• Represents problems solvable by a quantum machine in bounded space.
• Analogous to L (Logarithmic Space) and PSPACE in classical complexity.

Relationships Between Quantum and Classical Complexity Classes

The following relationships are known:

P⊆EQP⊆BQP⊆PSPACE

NP⊆QMA⊆PSPACE

BQP⊆PP

QIP=PSPACE

• BQP contains BPP and is at most as powerful as PSPACE.
• Quantum interactive proofs (QIP) collapse to PSPACE, meaning quantum interactions do not extend computational power beyond polynomial space.
• BQP vs. NP-complete:
  • It is unknown whether BQP can solve NP-complete problems efficiently.
  • Most evidence suggests that BQP does not contain NP-complete problems unless unlikely collapses occur in classical complexity.

Table of Quantum Complexity Classes

Read more about Difference Between Quantum Computational and Communication complexity