PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Computational Complexity

John Watrous

arXiv:0804.3401v1quant-ph

TL;DR

Quantum computational complexity asks how quantum physics changes computational hardness and how quantum models relate to classical complexity classes. This survey synthesizes polynomial-time quantum computation, quantum proof verification, and quantum interactive proofs, alongside selected additional topics. It presents properties of classes such as BQP, QMA, and QIP, while identifying unresolved relationships and explicit scope boundaries.

  • Problem

    Quantum computational complexity studies the implications of quantum physics for computational hardness, problem classifications, and relationships among quantum and classical models.

  • Method

    The article surveys polynomial-time quantum computation, efficient verification of quantum proofs, quantum interactive proof systems, and selected other topics in quantum complexity.

  • Results

    The survey presents properties of quantum complexity classes including BQP, QMA, and QIP, together with oracle results and unresolved class relationships.

  • Takeaways & Limitations

    Quantum algorithms can efficiently solve some structured problems, but oracle results indicate limitations for unstructured search and collision-detection problems.

Abstract

from arXiv · show

This article surveys quantum computational complexity, with a focus on three fundamental notions: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems. Properties of quantum complexity classes based on these notions, such as BQP, QMA, and QIP, are presented. Other topics in quantum complexity, including quantum advice, space-bounded quantum computation, and bounded-depth quantum circuits, are also discussed.

I Definition of the subject and its importance

Quantum computational complexity studies how quantum physics affects computational hardness by classifying problems under quantum models and relating those classes to classical complexity. This survey introduces foundational terminology, quantum complexity classes, and selected related topics while omitting quantum query and communication complexity.

  • I Definition of the subject and its importance: Quantum mechanics is relevant to computation because it accurately describes small physical systems where classical theories fail, while its implications for complexity theory remain less certain.
  • I Definition of the subject and its importance: Quantum computational complexity examines problem hardness, classifications, and relationships among quantum computational models and classical complexity classes.
  • I Definition of the subject and its importance: The survey presents properties and relationships of quantum complexity classes, with additional coverage of quantum advice, space-bounded computation, and bounded-depth circuits.
  • I Definition of the subject and its importance: Quantum query complexity and quantum communication complexity are outside the article’s scope.

II.2 Quantum information

The article represents quantum information with density matrices and completely positive trace-preserving maps, then uses vectorization and natural matrix representations to analyze quantum operations and circuits.

  • II.2 Quantum information: Mixed quantum states are represented by density matrices, and quantum operations by completely positive trace-preserving linear maps.
  • II.2 Quantum information: Vectorization maps density-matrix operators to vectors, enabling quantum operations to be represented as matrices.
  • II.2 Quantum information: A composition of quantum operations corresponds to matrix multiplication in the natural representation.
  • II.2 Quantum information: A quantum circuit is an acyclic network whose gates represent quantum operations and wires represent the qubits on which they act.
  • II.2 Quantum information: The general circuit model allows gates with unequal input and output counts, whereas unitary circuits require equal numbers of input and output qubits.

III.2 A finite universal gate set

A finite gate set supports quantum complexity theory by assigning unit cost to circuit operations while remaining universal for approximating arbitrary quantum operations. Approximation accuracy is measured operationally, and circuit size depends polylogarithmically on inverse accuracy for fixed input and output sizes.

  • III.2 A finite universal gate set: Complexity-theoretic quantum circuits use a fixed finite gate set so each allowed gate can be treated as having unit cost.
  • III.2 A finite universal gate set: The gate set includes Toffoli, Hadamard, phase-shift, ancillary, and erasure gates, with ancillary and erasure gates providing non-unitary operations.
  • III.2 A finite universal gate set: The chosen gate set is universal: every quantum operation can be approximated to any desired accuracy by a quantum circuit.
  • III.2 A finite universal gate set: The distance between operations is the maximum total variation distance between measurement distributions over all initial states and measurements.
  • III.2 A finite universal gate set: For fixed n and m, an operation from n qubits to m qubits has an approximating circuit of size poly(log(1/ε)) within distance ε.
  • III.2 A finite universal gate set: Although general circuits can be converted into unitary purifications, approximating circuits may still be exponential in n and m in the worst case.

III.3 Unitary purifications of quantum circuits

The quantum circuit model represents quantum computations as efficiently generated circuit families, with BQP capturing bounded-error polynomial-time quantum computation. General quantum operations can also be represented through unitary purifications on larger systems.

  • III.3 Unitary purifications of quantum circuits: General quantum operations can be represented by unitary operations on larger systems through unitary purification.This perspective is a manifestation of the Stinespring Dilation Theorem.
  • III.3 Unitary purifications of quantum circuits: Quantum oracle queries are modeled by unitary gates that act on superpositions, and multiple-bit queries can be simulated using single-bit queries via Bernstein–Vazirani.The oracle gate implements a predicate based on the modulo 2 inner product.
  • III.3 Unitary purifications of quantum circuits: BQP consists of promise problems solved by polynomial-time generated quantum circuits with bounded error, using acceptance probabilities for yes- and no-instances.The standard class is BQP = BQP(2/3, 1/3).
  • III.3 Unitary purifications of quantum circuits: A polynomial-time generated circuit family is produced by a polynomial-time deterministic Turing machine that outputs each circuit’s encoding.The encoding must be sensible, efficient, and disallow extreme compression.

IV.2 Error reduction for BQP

BQP error bounds are robust: a polynomially bounded gap can be reduced to extremely small error through polynomially many repetitions. Quantum circuits can also simulate classical probabilistic circuits gate by gate, yielding BPP ⊆ BQP.

  • IV.2 Error reduction for BQP: A polynomially bounded acceptance-probability gap can be amplified to extremely small error using polynomially many repetitions.The repetition strategy obtains overwhelming statistical evidence while remaining polynomial time.
  • IV.2 Error reduction for BQP: Quantum circuits simulate classical randomized circuits by implementing NAND gates, FANOUT gates, and random bits.Phase-damping gates enforce classical-looking behavior but are unnecessary for the quantum simulation itself.
  • IV.2 Error reduction for BQP: BPP ⊆ BQP follows because classical probabilistic circuit families can be simulated gate by gate with quantum gates.The random input bits are chosen uniformly in the BPP construction.

IV.4 The BQP subroutine theorem

The BQP subroutine theorem resolves the difficulty of using bounded-error quantum algorithms coherently as subroutines. It yields clean oracle-like unitary implementations and the closure result BQP^BQP = BQP, while classical counting arguments place BQP within PP and identify PQP with PP.

  • IV.4 The BQP subroutine theorem: BQP algorithms may fail when queried in superposition because their correctness is guaranteed only on classical inputs.The issue can arise from phase damping or other non-coherent behavior inside the original algorithm.
  • IV.4 The BQP subroutine theorem: The BQP subroutine theorem constructs a clean oracle-like unitary subroutine with exponentially small error from any BQP algorithm.Its proof first reduces error and then uses a reversible unitary construction.
  • IV.4 The BQP subroutine theorem: BQPBQP = BQP, expressing closure of BQP under BQP subroutines.This is the main complexity-theoretic implication of the subroutine theorem.
  • IV.4 The BQP subroutine theorem: GapP closure under matrix multiplication supports classical simulation arguments for quantum circuits by representing circuit amplitudes through matrix products.The resulting acceptance probabilities can be expressed using GapP functions.
  • IV.4 The BQP subroutine theorem: BQP ⊆ PP, while the unbounded-error quantum class PQP equals PP.The BQP upper bound can be obtained through counting-complexity representations of quantum computation.

IV.6 Oracle results involving BQP

Oracle results provide relativized evidence about the limits and power of quantum computation. They separate BQP from classical verification in one setting and show that unstructured search and collision problems need exploitable structure for efficient quantum algorithms.

  • IV.6 Oracle results involving BQP: There exists an oracle A such that BQP^A is not contained in MA^A, implying BPP^A ⊊ BQP^A for that oracle.The oracle encodes a problem solvable quantumly but not efficiently verifiable classically.
  • IV.6 Oracle results involving BQP: There exists an oracle A such that NP^A is not contained in BQP^A, formalizing the inability to efficiently search an unstructured exponentially large space.The result supports the view that quantum speedups require exploitable problem structure.
  • IV.6 Oracle results involving BQP: There exists an oracle A such that SZK^A is not contained in BQP^A, ruling out efficient quantum algorithms for unstructured collision detection problems.Graph isomorphism and some cryptographic problems are cited as collision-detection examples.
  • IV.6 Oracle results involving BQP: QMA extends the quantum-computation framework with quantum proofs that serve as witnesses or certificates for efficient verification.The article presents QMA as a quantum analogue of NP.

V.1 Definition of QMA

QMA extends efficient proof verification by allowing quantum states as witnesses, with bounded completeness and soundness errors. The section defines QMA and discusses complete problems and examples that reveal the power of quantum proofs.

  • Definition of QMA: QMA is motivated by extending classical proof strings to quantum states while retaining completeness and soundness conditions with bounded error.The classical analogue is MA rather than NP because quantum verification is probabilistic.
  • Definition of QMA: QMA verification uses a polynomial-size quantum proof accepted with high probability on yes-instances and low probability on no-instances.Completeness requires some proof state to achieve at least a(|x|); soundness requires every proof state to achieve at most b(|x|).
  • QMA-complete problems: The 2-local Hamiltonian problem is QMA-complete with respect to Karp reductions.The problem asks whether a quantum state can achieve sufficiently low total energy under local Hamiltonian penalties.
  • QMA-complete problems: Local Hamiltonian completeness is closely related to the universality of adiabatic quantum computation.Several variants remain QMA-complete, including two-dimensional nearest-neighbor interactions, while the one-dimensional qubit case remains open.
  • QMA-complete problems: Other QMA-complete or QMA-contained examples include density matrix consistency, quantum clique, circuit-property problems, and group non-membership.These examples broaden the evidence for quantum proofs beyond direct analogues of classical combinatorial problems.

The group non-membership problem

The group non-membership problem asks whether a specified group element lies outside a subgroup generated by given elements, and it is in QMA for every group oracle. The section also explains QMA error reduction and contrasts quantum with classical proofs.

  • The group non-membership problem: The group non-membership problem is in QMA for every choice of a group oracle.Yes-instances have g outside the subgroup H generated by h1, ..., hk; no-instances have g in H.
  • Error reduction for QMA: QMA has weak and strong error-reduction procedures that differ in the quantum-proof length required to obtain a target error bound.This proof-length trade-off is specific to working with quantum proofs.
  • Error reduction for QMA: Repetition reduces verification error exponentially when completeness and soundness are separated, but repeated verification apparently destroys the quantum proof.Weak error reduction addresses this issue through a composite verification procedure and repeated inputs.
  • Error reduction for QMA: Strong error reduction achieves exponential error reduction with roughly linear circuit-size growth without increasing the quantum-proof length.The procedure is illustrated using a unitary purification of the verifier and an acceptance decision based on input-qubit alternations.
  • Containment of QMA in PP: Strong error reduction supports the containment QMA ⊆ PP by replacing the proof with a totally mixed state whose exponentially small acceptance probabilities remain separated.The resulting proof-free procedure places the promise problem in PQP = PP.
  • Classical versus quantum proofs: MQA uses classical proofs instead of quantum proofs, and whether MQA is properly contained in QMA remains a central question about quantum-proof power.The group non-membership problem is argued, under a group-theoretic conjecture, likely to be in MQA.

V.6 Are two quantum proofs better than one?

Quantum interactive proofs generalize proof verification to interactions in which provers and verifiers exchange quantum information. They support strong normalization results, including three-message parallelization, while satisfying QIP ⊆ EXP and containing PSPACE.

  • Quantum interactive proof systems: A quantum interactive proof is an interaction in which a quantum prover and verifier exchange and process quantum information under completeness and soundness conditions.The verifier uses private memory and message qubits, while the prover is an unrestricted family of quantum operations.
  • Properties of QIP: Quantum interactive proofs can be simulated in EXP, while PSPACE ⊆ QIP follows because classical interactive proofs can be simulated quantumly.Quantum interactive proofs are not known to be simulatable in PSPACE.
  • Properties of QIP: Every quantum interactive proof can be transformed to perfect completeness at the cost of one additional round, and parallel repetition can exponentially reduce soundness error.The perfect-completeness transformation keeps soundness bounded away from one.
  • Properties of QIP: Any polynomial-round quantum interactive proof can be transformed into an equivalent three-message proof, with weakened error bounds but preserved perfect completeness.Parallel repetition can subsequently reduce soundness error without increasing the message count beyond three.
  • Quantum interactive proof systems: QIP(0) = BQP, QIP(1) = QMA, QIP(2), and QIP(3) = QIP for a wide range of completeness and soundness probabilities.Thus the message count organizes several central quantum complexity classes.
  • Complete problems: The quantum circuit distinguishability problem is QIP-complete with respect to Karp reductions.It asks whether two quantum circuits induce significantly different or approximately identical operations under the relevant metric.

VI.3 Zero-knowledge quantum interactive proofs

Quantum statistical zero-knowledge proofs require that a cheating verifier’s interaction with an honest prover be efficiently approximable without revealing additional information. QSZK has closure, simulation, parallelization, and complete-problem characterizations, although its separation from QIP is conjectural.

  • Definition: A quantum interactive proof is statistical zero-knowledge when every efficient cheating verifier’s induced operation can be efficiently approximated on yes-instances.The induced operation maps the verifier’s pre-protocol knowledge state to its post-protocol knowledge state.
  • Definition: QSZK is the class of promise problems having statistical zero-knowledge quantum interactive proof systems.The article focuses on statistical zero-knowledge because it adapts most easily to the quantum setting.
  • Scope: It is reasonable to conjecture that QSZK is properly contained in QIP, but this separation has not been proved.The zero-knowledge property is described as restrictive, and non-trivial QSZK systems were only recently established.
  • Properties: Quantum statistical zero-knowledge proofs can be parallelized to two messages, implying QSZK ⊆ QIP(2).This is one of the structural properties established for QSZK systems.
  • Properties: QSZK is closed under complementation and is contained in PSPACE.Statistical zero-knowledge quantum interactive proofs can be simulated in polynomial space.
  • Complete problems: The quantum state distinguishability problem is QSZK-complete with respect to Karp reductions.Its promise compares the trace distance of output states from two input-free quantum circuits using thresholds 2/3 and 1/3.

VI.4 Multiple-prover quantum interactive proofs

Multiple-prover quantum interactive proofs extend classical multiple-prover systems by allowing shared entanglement, which can create non-classical correlations and substantially complicate their complexity-theoretic characterization. The section surveys restricted variants, related models, and known equalities and containments.

  • Multiple-prover quantum interactive proofs: Shared entanglement can let quantum provers produce correlations that defeat systems sound against classical provers.This effect is identified with Bell-inequality violations and is the key distinction from classical multiple-prover proofs.
  • Multiple-prover quantum interactive proofs: Without shared entanglement, multiple-prover quantum interactive proofs are equivalent in power to MIP.
  • Open limitations: The relationships and upper bounds for MIP∗ and QMIP remain poorly understood because required entanglement sizes and achievable correlations lack known bounds.Only trivial lower bounds PSPACE ⊆ MIP∗ and QIP ⊆ QMIP are stated, and non-computable languages have not been ruled out.
  • Restricted multiple-prover variants: ⊕MIP equals NEXP for some completeness and soundness parameters, whereas ⊕MIP∗ is contained in QIP(2) and therefore EXP.
  • Public-coin quantum interactive proofs: Public-coin quantum proof variants include QAM and QMAM, with QAM ⊆ QIP(2) but equality unknown, while QMAM = QIP.QMAM retains the full power of QIP even when Arthur uses only a single random bit.
  • Competing provers: Quantum refereed games have the same computational power as classical refereed games: RG = QRG = EXP.The EXP upper bound for QRG uses semidefinite programming, while the lower bound for RG uses arithmetization.

VII Other selected notions in quantum complexity

The survey examines quantum advice, space-bounded quantum computation, and other models beyond its central polynomial-time framework. These results relate quantum resources to classical advice classes and parallel computation while highlighting important scope boundaries.

  • VII.1 Quantum advice: Quantum advice supplies trusted, input-length-dependent quantum states as pre-loaded software for polynomial-time quantum circuits.The advice may depend on n but not on the particular input, and its preparation cost is ignored.
  • VII.1 Quantum advice: At most three distinct classes arise among the considered combinations of quantum, randomized, and deterministic advice and circuits: BQP/qpoly, BQP/poly, and P/poly.The stated equalities include BQP/rpoly = BQP/poly and BPP/qpoly = BPP/rpoly = BPP/poly = P/qpoly = P/rpoly = P/poly.
  • VII.1 Quantum advice: BQP/qpoly is contained in PP/poly, so polynomial-size quantum advice can be simulated by deterministic advice for a PP machine.
  • VII.1 Quantum advice: QMA/qpoly is contained in PSPACE/poly.
  • VII.2 Space-bounded quantum computation: Quantum information does not give a significant increase in computational power in the space-bounded case.Logarithmic-space quantum computations in BQL and PQL are contained in NC and can therefore be efficiently simulated in parallel.

VII.3 Bounded-depth quantum circuits

Bounded-depth quantum circuits can be computationally powerful, unlike the apparently weaker space-bounded quantum model, so the classical equivalence between space and depth is not known to extend to quantum computation. The section summarizes evidence for this gap and identifies broader open directions.

  • VII.3 Bounded-depth quantum circuits: QNC consists of bounded-error quantum computations using logarithmic-space-generated circuits of poly-logarithmic depth.
  • VII.3 Bounded-depth quantum circuits: The classical two-way relationship between space-bounded and depth-bounded computation is not known for quantum computation.Space-bounded quantum computations can be simulated by depth-bounded circuits, but the reverse efficient simulation is not known and is considered unlikely.
  • Evidence for computational power: Acceptance probabilities for constant-depth quantum circuits are as hard to compute as those for arbitrary polynomial-size quantum circuits.
  • Evidence for computational power: Shor’s factoring algorithm can be implemented with logarithmic-depth quantum circuits plus classical pre- and post-processing.
  • Evidence for computational power: Quantum circuit distinguishability remains QIP-complete when restricted to logarithmic-depth quantum circuits.
  • Future directions: The power of multiple-prover quantum interactive proofs and the relationships among major quantum classes remain important unresolved directions.The survey specifically notes that no interesting upper bounds are known for MIP∗ or QMIP and that BQP’s relationship with the polynomial-time hierarchy is unresolved.
Loading 0804.3401v1…