BQP complexity class diagram
This svg shows the suspected shape of the BQP of problem space, the range of problems easily solved by quantum computers.
Note that this is not proven; it has not been proved that P!=NP or P!=PSPACE, and if either of these are equal, the shape of BQP would be different.
Diagram based on information found in :
- Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
 |
Ich, der Urheberrechtsinhaber dieses Werkes, veröffentliche es als gemeinfrei. Dies gilt weltweit. In manchen Staaten könnte dies rechtlich nicht möglich sein. Sofern dies der Fall ist: Ich gewähre jedem das bedingungslose Recht, dieses Werk für jedweden Zweck zu nutzen, es sei denn, Bedingungen sind gesetzlich erforderlich. |
Relevante Artikel
BQPDie Komplexitätsklasse BQP 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. .. weiterlesen