BQP

In computational complexity theory BQP stands for "Bounded error, Quantum, Polynomial time". It denotes 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.

In other words, there is an algorithm for a quantum computer 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. (no matter if the correct answer is YES or NO).

Similarly to other "bounded error" probabilistic classes the choice of 1/3 in the definition is arbitrary.Changing the constant to any real number p ,! such that p in left(0,1/2 ight) does not change the set BQP.

The idea behind this definition is that for any single run of algorithm the probability of error is lower than p ,!. Thus 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. This number of repeats increases if p ,! becomes closer to 1/2, but it does not depend on the input size. Probability of error is exponentially small with regard to the number of repeats.

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 2"n" 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. Currently, only three such problems are known:
*Integer factorization (see Shor's algorithm)
*Discrete logarithm
*Simulation of quantum systems (see universal quantum computer)

Relationship to other complexity classes

This class is defined for a quantum computer and its natural corresponding class for an ordinary computer (or a Turing machine plus a source of randomness) is BPP.

BQP contains P and BPP and is contained in PP and PSPACE. Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [http://www.cs.berkeley.edu/~vazirani/bv.ps] ] In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the possible difference in power between these similar classes. :mbox{P} subseteq mbox{BPP} subseteq mbox{BQP}subseteq mbox{PP} subseteq mbox{PSPACE}

As the problem of mbox{P} ,^{=}_{ eq}, mbox{PSPACE} has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult.

Relation between BQP and NP is not known.

BQP can be shown to be in the counting complexity class AWPP.

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • BQP — Saltar a navegación, búsqueda En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra… …   Wikipedia Español

  • BQP — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • BQP — Les relations supposées entre BQP et les autres classes de complexité[1]. En théorie de la complexité des algorithmes BQP (Bounded error Quantum Polynomial time) est la classe des problème de décision qui peuvent être résolus par un …   Wikipédia en Français

  • BQP — En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra forma, existe un algoritmo de… …   Enciclopedia Universal

  • bqp — ISO 639 3 Code of Language ISO 639 2/B Code : ISO 639 2/T Code : ISO 639 1 Code : Scope : Individual Language Type : Living Language Name : Busa …   Names of Languages ISO 639-3

  • BQP — abbr. Bounded probability Quantum Polynomial (complexity theory, quantum computing) …   Dictionary of abbreviations

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • Класс BQP — Примерное положение BQP на карте классов NP, P, PSPACE. В теории алгоритмов классом сложности BQP (от англ.& …   Википедия

  • Quantenprozessor — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er auf der Basis quantenmechanischer Zustände, und die Verarbeitung… …   Deutsch Wikipedia

  • Quantenrechner — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er auf der Basis quantenmechanischer Zustände, und die Verarbeitung… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”