Definition(BQP): We say a language if and only if there exists a polynomial-time uniform family of quantum circuits , such that:
- , takes qubits and outputs 1 classical bit(by measurement).
- consists of gates.
- The gates in are limited to some universal set, e.g. .
In this definition, “polynomial-time uniform” indicates that for , there exists a deterministic Turing machine that output the diagram of with input in polynomial time.
Definition: is the set of all languages such that there exists a (“BQP”) verifier such that:
- (Completeness)If , then , each with qubits long s.t.
- (Soundness)If ,, each with qubits long s.t.
Remark: In , we don’t allow entangled provers, so it’s always the tensor product of two separate states.
We can put all parameters in a compact form:
Hugue Blier and Alain Tapp. All languages in np have very short quantum proofs.
In ICQNM ’09.
If we want the soundness probability to be constant:
Theorem: Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor.
The power of unentanglement. volume 5, pages 1–42, 2009.