https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=BQPBQP - Versionsgeschichte2026-05-28T21:29:02ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=BQP&diff=277268&oldid=previmported>Dorschleber: ungeeigneten Link entf2023-05-25T00:24:50Z<p>ungeeigneten Link entf</p>
<p><b>Neue Seite</b></p><div>[[Datei:BQP complexity class diagram.svg|mini|Die Lage von BQP relativ zu anderen Problemklassen<ref>Michael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.</ref>]]<br />
Die [[Komplexitätsklasse]] '''BQP''' (von {{enS|''bounded-error quantum polynomial time''}}) ist ein Begriff aus der [[Komplexitätstheorie]], einem Teilgebiet der [[Theoretische Informatik|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 (Komplexitätsklasse)|BPP]], die für den [[Zeitkomplexität|Zeitaufwand]] auf [[Turingmaschine]]n 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.<br />
<br />
BQP wurde 1993 durch [[Umesh Vazirani]] und [[Ethan Bernstein]] eingeführt.<ref>Bernstein, Vazirani, Quantum complexity theory, SIAM J. Comput., Band 26, Heft 5, 1997, S. 1411–1473, [https://people.eecs.berkeley.edu/~vazirani/ Online auf der Homepage von Varzirani]. Eine vorläufige Zusammenfassung erschien im 25. Annual ACM Symp. Theory Comput. (STOC) 1993, S. 11–20.</ref><br />
<br />
== Beziehung zu anderen Komplexitätsklassen ==<br />
Die Komplexitätsklassen [[P (Komplexitätsklasse)|P]] und BPP sind in BQP enthalten, BQP ist in [[Probabilistische Polynomialzeit|PP]]<ref name="ADH97" /> und damit auch in [[PSPACE]] enthalten. Es ist unbekannt, ob diese [[Teilmenge|Inklusionen]] echt sind oder nicht.<br />
<br />
Vazirani und Bernstein zeigten 1997, dass in Berechenbarkeitsmodellen mit [[Orakel-Turingmaschine|Orakeln]] BQP keine Teilmenge von BPP ist, und [[Ran Raz]] und [[Avishay Tal]] 2018, dass BQP Orakel-separiert von [[PH (Komplexitätsklasse)|PH]] ist.<ref>[https://eccc.weizmann.ac.il/report/2018/107/ Raz, Tal, Oracle Separation of BQP and PH], Electronic Colloquium on Computational Complexity, 2018</ref><br />
<br />
== Probleme in BQP ==<br />
Es sind mehrere Probleme in BQP bekannt, von denen vermutet wird, dass sie nicht in BPP liegen. Das bekannteste ist das [[Faktorisierung]]sproblem, das mit dem [[Shor-Algorithmus|Algorithmus von Shor]] gelöst werden kann.<br />
<br />
== Einzelnachweise ==<br />
<references><br />
<ref name="ADH97">{{Literatur<br />
| Autor=Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang<br />
| Titel=Quantum Computability<br />
| Sammelwerk=SIAM Journal on Computing<br />
| Band=26<br />
| Nummer=5<br />
| Verlag=[[SIAM]]<br />
| Jahr=1997<br />
| Seiten=1524–1540<br />
| Online=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.205.8140&rep=rep1&type=pdf<br />
}}</ref><br />
</references><br />
<br />
== Literatur ==<br />
* [[Leonard Adleman|L. Adleman]], J. Demarrais, M.A. Huang. ''Quantum computability''. SIAM J. Comp., 26(5): 1524–1540, 1997.<br />
* E. Bernstein, U. Vazirani. ''Quantum complexity theory''. SIAM J. Comp., 26(5): 1411–1473, 1997.<br />
<br />
== Weblinks ==<br />
* {{Complexity Zoo|BQP|B#bqp}}<br />
<br />
{{SORTIERUNG:Bqp}}<br />
<br />
[[Kategorie:Komplexitätsklasse]]<br />
[[Kategorie:Quanteninformatik]]<br />
[[Kategorie:Abkürzung|BQP]]</div>imported>Dorschleber