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 Fehlerwahrscheinlichkeit von unter 1/4 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/4 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


Wikimedia Foundation.

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

  • 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

  • BPP (Komplexitätsklasse) — In der Komplexitätstheorie steht BPP (engl. bounded error probability polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es eine polynomiell zeitbeschränkte probabilistische Turingmaschine gibt …   Deutsch Wikipedia

  • 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

  • Quantencomputer — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er nicht auf der Basis der Gesetze der klassischen Physik bzw. Informatik …   Deutsch Wikipedia

  • Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia

Share the article and excerpts

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