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 höchstens 1/3 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/3 willkürlich, durch mehrmaliges Anwenden eines BQP-Algorithmus kann eine beliebig niedrige Fehlerwahrscheinlichkeit erreicht werden.
Beziehung zu anderen Komplexitätsklassen
Die Komplexitätsklassen P und BPP sind in BQP enthalten, BQP ist in PP[2] und damit auch in 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.
Einzelnachweise
- ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
- ↑ Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability. In: SIAM Journal on Computing. Band 26, Nr. 5. SIAM, 1997, S. 1524–1540 (pdf).
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)