Quantum Information and the PCP Theorem

Details Quantum Information and the PCP Theorem Quantum Information and the PCP Theorem

2005-04-10

arxiv.org/abs/quant-ph/0504075v1

Physics

Quantum Physics

30 pages

Scientific paper

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$ by a single quantum state $|\Psi>$ of size O(n) qubits, such that: for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$, the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved from $|\Psi>$ by a one-round Arthur-Merlin interactive protocol of size polynomial in $n$. This shows how to go around Holevo-Nayak's Theorem, using Arthur-Merlin proofs. We use the new representation to prove the following results: 1) Interactive proofs with quantum advice: We show that the class $QIP/qpoly$ contains ALL languages. That is, for any language $L$ (even non-recursive), the membership $x \in L$ (for $x$ of length $n$) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state $|\Psi_{L,n} >$ (depending only on $L$ and $n$). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. 2) PCP with only one query: We show that the membership $x \in SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $|\Psi >$, together with a polynomial-size classical proof consisting of blocks of length $polylog(n)$ bits each, such that after measuring the state $|\Psi >$ the verifier only needs to read {\bf one} block of the classical proof. While the first result is a straight forward consequence of the new representation, the second requires an additional machinery of quantum low-degree-test that may be interesting in its own right.

Affiliated with

Also associated with

No associations

Rating

Quantum Information and the PCP Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Information and the PCP Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Information and the PCP Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21340