Quantum Computational Complexity

By John Watrous. Encyclopedia of Complexity and Systems Science, 2008

349 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/22545e90a5189e601a18014b3b15bea8edce4062

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Circuit complexity in quantum field theory (2017, background): “In computer science, the notion of computational complexity refers to the minimum number of operations necessary to implement a given task [36, 37].”
Complexity of formation in holography (2016, background): “However, this problem was recently overcome with a careful analysis of the boundary terms which must be added to the (1)See [5, 11] for further details.”
Quantum computational supremacy (2017, background): “We can express PostBPP and PostBQP as well in terms of f count .”
Faithful Squashed Entanglement (2010, background): “[ 60 ]), which works in this case since the verification measurement is LOCC [63].”
Complexity and entanglement for thermofield double states (2018, background): “In quantum computing, this function becomes a unitary operation Û which maps an input quantum state for some number of qubits to an output quantum state on an equal number of qubits [17–19].”
Quantum circuits and low-degree polynomials over F2 (2016, background): “The class of decision problems which can be solved eﬃciently by a quantum computer (i.e. in time polynomial in the size of the input), with success probability 2 / 3, is known as BQP [45].”
Circuit complexity for free fermions (2018, background): “This question readily extends to quantum information science where the question becomes what is the minimal number of gates chosen from some set of elementary unitaries {VI} to implement a unitary transformation U , which produces a desired map from some n-qubit inputs to the corresponding n-qubit o”
Simulating chemistry using quantum computers. (2010, background): “Likewise, bqp are those problems that are easy for a quantum computer (130).”