BQP

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 Fehlerwahrscheinlichkeit von unter 1/2 lösbar sind. Sie ist das Äquivalent zur Klasse BPP, die für den Zeitaufwand auf Turingmaschinen definiert ist. Wie bei der Klasse BPP ist auch bei BQP die Festlegung der Fehlerwahrscheinlichkeit auf 1/2 willkürlich, durch mehrmaliges Anwenden eines BQP-Algorithmus kann eine beliebig niedrige Fehlerwahrscheinlichkeit erreicht werden.

Inhaltsverzeichnis

Beziehung zu anderen Komplexitätsklassen

Die Komplexitätsklassen P und BPP sind in BQP enthalten, BQP ist in PP und PSPACE enthalten. Es ist unbekannt, ob diese Inklusionen echt sind oder nicht.

Probleme in BQP

Es sind mehrere Probleme in BQP bekannt, von denen vermutet wird, dass sie nicht in BPP liegen. Das bekannteste ist das Faktorisierungsproblem, das mit dem Algorithmus von Shor gelöst werden kann.

Literatur

  • L. Adleman, J. Demarrais, M.A. Huang. Quantum computatbility. SIAM J. Comp., 26(5): 1524-1540, 1997.
  • E. Bernstein, U. Vazirani. Quantum complexity theory. SIAM J. Comp., 26(5): 1411-1473, 1997.

Weblinks

  • BQP. In: Complexity Zoo. (englisch)

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 — 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.… …   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 (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 — 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 — Примерное положение 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”