BQP

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.