|
gptkbp:instanceOf
|
theoretical computer science
|
|
gptkbp:amplificationMethod
|
repetition and majority vote
|
|
gptkbp:canBeAmplified
|
yes
|
|
gptkbp:citation
|
gptkb:E._Bernstein_and_U._Vazirani,_'Quantum_Complexity_Theory',_SIAM_J._Comput.,_1997
|
|
gptkbp:computationModel
|
gptkb:quantum_Turing_machine
quantum circuit
|
|
gptkbp:contains
|
gptkb:PSPACE
P
PP
|
|
gptkbp:definedIn
|
problems solvable by a quantum computer in polynomial time with bounded error probability
|
|
gptkbp:describes
|
decision problems
|
|
gptkbp:errorBound
|
less than 1/3
|
|
gptkbp:errorDetection
|
at most 1/3 for all instances
|
|
gptkbp:example
|
gptkb:Grover's_algorithm
gptkb:Shor's_algorithm
integer factorization
discrete logarithm
simulating quantum systems
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
BQP
|
|
gptkbp:input
|
binary strings
|
|
gptkbp:introduced
|
gptkb:Ethan_Bernstein
gptkb:Umesh_Vazirani
|
|
gptkbp:introducedIn
|
1993
|
|
gptkbp:openProblem
|
Is BQP equal to BPP?
Is BQP equal to NP?
Is NP contained in BQP?
|
|
gptkbp:output
|
yes/no answer
|
|
gptkbp:relatedTo
|
gptkb:QMA
gptkb:BPP
NP
|
|
gptkbp:standsFor
|
gptkb:Bounded-error_Quantum_Polynomial_time
|
|
gptkbp:usedIn
|
gptkb:quantum_computing
|
|
gptkbp:bfsParent
|
gptkb:quantum_Turing_machine
|
|
gptkbp:bfsLayer
|
5
|