Bounded-error Quantum Polynomial time

GPTKB entity

Predicate	Object
gptkbp:instanceOf	theoretical computer science
gptkbp:abbreviation	gptkb:BQP
gptkbp:citation	https://en.wikipedia.org/wiki/BQP
gptkbp:closed	closed under intersection closed under union closed under complement
gptkbp:complexityHierarchy	BPP ⊆ BQP ⊆ PP ⊆ PSPACE
gptkbp:computationModel	gptkb:quantum_Turing_machine quantum circuit model
gptkbp:contains	gptkb:BPP P NP (if quantum computers can solve NP-complete problems efficiently, which is unknown)
gptkbp:definedIn	gptkb:quantum_computing
gptkbp:describes	decision problems solvable by a quantum computer in polynomial time with bounded error probability
gptkbp:errorBound	at most 1/3
gptkbp:errorDetection	less than 1/2 for all inputs
gptkbp:example	gptkb:Grover's_algorithm gptkb:Shor's_algorithm
https://www.w3.org/2000/01/rdf-schema#label	Bounded-error Quantum Polynomial time
gptkbp:introduced	gptkb:Ethan_Bernstein gptkb:Umesh_Vazirani
gptkbp:introducedIn	1993
gptkbp:lowerBoundedBy	P
gptkbp:relatedTo	gptkb:BPP gptkb:PSPACE P NP
gptkbp:upperBoundedBy	gptkb:PSPACE
gptkbp:usedIn	quantum algorithms
gptkbp:bfsParent	gptkb:BQP
gptkbp:bfsLayer	6