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

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

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

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

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

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

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

  • (Soundness)If xLx\notin L,ψ1,ψ2\forall |\psi_1\rangle,\psi_2\rangle, each with l=O(nc)l=O(n^c) qubits long s.t.

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

Remark: In QMA(2)\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:


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

NPQMAl(2)c,s with l=log(n),c=1,s=11poly(n)\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.

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

編集日 閲覧数