BQP

related topics
{math, number, function}
{math, energy, light}
{rate, high, increase}
{government, party, election}

In computational complexity theory BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue of the complexity class BPP.

In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem with high probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 that it will give the wrong answer.

Similarly to other "bounded error" probabilistic classes the choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. Detailed analysis shows that the complexity class is unchanged by allowing error as high as 1/2 − nc on the one hand, or requiring error as small as 2nc on the other hand, where c is any positive constant, and n is the length of input.

Contents

Definition

BQP can also be viewed as a bounded-error uniform family of quantum circuits. A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits \{Q_n:n \in \mathbb{N}\}, such that

  • For all n \in \mathbb{N}, Qn takes n qubits as input and outputs 1 bit
  • For all x in L, \mathrm{Pr}(Q_{|x|}(x)=1)\geq 2/3
  • For all x not in L, \mathrm{Pr}(Q_{|x|}(x)=0)\geq 2/3

Quantum computation

The number of qubits in the computer is allowed to be a polynomial function of the instance size. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits (Shor's algorithm).

Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of quantum state to one of the basis states. It can be said that the quantum state is measured to be in the correct state with high probability.

Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Some prominent examples are:

Full article ▸

related documents
Vector calculus
Commutative diagram
Atlas (topology)
Sather
Symmetric tensor
Cauchy's integral theorem
Catalan's conjecture
Constant term
Linear prediction
Finitely generated abelian group
Wreath product
Matrix addition
Interpreted language
Nilpotent group
Addition of natural numbers
Hilbert's basis theorem
Merge algorithm
Infinite set
Axiom of extensionality
Directed set
Condition number
Removable singularity
Canonical LR parser
Symbolic logic
Dirichlet's theorem on arithmetic progressions
Most significant bit
Bucket sort
Recursively enumerable language
NC (complexity)
List of small groups