BQP is the class of promise problems decided by uniform polynomial-size quantum circuits with bounded error. Completeness and soundness are conventional; BQP error reduction shows that other fixed separated thresholds give the same class.
Independent runs of a BQP algorithm with fresh ancilla qubits can be combined by a classical threshold rule. If completeness exceeds soundness by , a Hoeffding inequality bounds the error after runs by . Polynomial repetition handles inverse-polynomial gaps. This does not automatically preserve the restricted gate and measurement rules of a stoquastic circuit.
Articles by others on the same topic
BQP stands for "Bounded-error Quantum Polynomial time." It is a complexity class in computational complexity theory that comprises decision problems solvable by a quantum computer in polynomial time, with an error probability of less than 1/3 for all instances.
P for quantum computing!
Heck, we know nothing about this class yet related to non quantum classes!
- conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
- conjectured to be larger than P, but we don't have a single algorithm provenly there:
- it is believed that the NP complete ones can't be solved
- if they were neither NP-complete nor P, it would imply P != NP
- we just don't know if it is even contained inside NP!