Definition(BQP): We say a language $L\in\textnormal{BQP}$ if and only if there exists a polynomial-time uniform family of quantum circuits $\{Q_n:n\in\mathbb{N}\}$, such that:

• $\forall n\in\mathbb{N}$, $Q_n$ takes $n$ qubits and outputs 1 classical bit(by measurement).
• $\forall n\in L,\textnormal{Pr}[Q_{|x|}(x)=1]\geq\frac{2}{3}$.
• $\forall n\notin L,\textnormal{Pr}[Q_{|x|}(x)=0]\geq\frac{2}{3}$.
• $\forall n\in\mathbb{N},Q_n$ consists of $O(n^c)$ gates.
• The gates in $Q_n$ are limited to some universal set, e.g. $\{\textnormal{H,NOT,CNOT,CCNOT}\}$.

In this definition, “polynomial-time uniform” indicates that for $n\in\mathbb{N}$, there exists a deterministic Turing machine that output the diagram of $Q_n$ with input $1^n$ in polynomial time.

Theorem: $\textnormal{BQP}\subseteq \textnormal{PSPACE}$.

Definition: $\textnormal{QMA}(2)$ is the set of all languages $L$ such that there exists a (“BQP”) verifier $V$ such that:

• (Completeness)If $x\in L$, then $\exists |\psi_1\rangle,|\psi_2\rangle$, each with $l=O(n^c)$ qubits long s.t.

$\textnormal{Pr}[V(|x\rangle\otimes |\psi_1\rangle\otimes|\psi_2\rangle)\textnormal{ accepts}]\geq c$

• (Soundness)If $x\notin L$,$\forall |\psi_1\rangle,\psi_2\rangle$, each with $l=O(n^c)$ qubits long s.t.

$\textnormal{Pr}[V(|x\rangle\otimes |\psi_1\rangle\otimes|\psi_2\rangle)\textnormal{ accepts}]\leq s$

Remark: In $\textnormal{QMA}(2)$, 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:

$\textnormal{QMA}_l(k)_{c,s}$

Theorem:
Hugue Blier and Alain Tapp. All languages in np have very short quantum proofs.
In ICQNM ’09.

$\textnormal{NP}\subseteq \textnormal{QMA}_l(2)_{c,s}\textnormal{ with }l=\log(n),c=1,s=1-\frac{1}{\textnormal{poly}(n)}$

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.

$\textnormal{NP}\subseteq\textnormal{QMA}_l(k)_{c,s}\textnormal{ with }l=\log(n),k=\tilde{O}(\sqrt{n}),c=1,s=0.999$