BQP

Die Komplexitätsklasse BQP (von englisch bounded-error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretische…

BQP
Die Lage von BQP relativ zu anderen Problemklassen[1]

Die Komplexitätsklasse BQP (von englisch 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.

BQP wurde 1993 durch Umesh Vazirani und Ethan Bernstein eingeführt.[2]

Beziehung zu anderen Komplexitätsklassen

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

Vazirani und Bernstein zeigten 1997, dass in Berechenbarkeitsmodellen mit Orakeln BQP keine Teilmenge von BPP ist, und Ran Raz und Avishay Tal 2018, dass BQP Orakel-separiert von PH ist.[4]

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

  1. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
  2. ↑ Bernstein, Vazirani, Quantum complexity theory, SIAM J. Comput., Band 26, Heft 5, 1997, S. 1411–1473, Online auf der Homepage von Varzirani. Eine vorläufige Zusammenfassung erschien im 25. Annual ACM Symp. Theory Comput. (STOC) 1993, S. 11–20.
  3. ↑ 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 (psu.edu [PDF]).
  4. ↑ Raz, Tal, Oracle Separation of BQP and PH, Electronic Colloquium on Computational Complexity, 2018

Literatur

  • L. Adleman, J. Demarrais, M.A. Huang. Quantum computability. SIAM J. Comp., 26(5): 1524–1540, 1997.
  • E. Bernstein, U. Vazirani. Quantum complexity theory. SIAM J. Comp., 26(5): 1411–1473, 1997.
  • BQP. In: Complexity Zoo. (englisch)

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.