Quantum Complexity Theory

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.

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}$$