__
TR05-038 | 10th April 2005 00:00
__

#### Quantum Information and the PCP Theorem

TR05-038
Authors:

Ran Raz
Publication: 11th April 2005 15:56

Downloads: 1337

Keywords:

**Abstract:**
We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$

by a single quantum state $|\Psi \rangle$ 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 \rangle$ 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} \rangle$ (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 \rangle$,

together with a polynomial-size classical proof consisting of

blocks of length $polylog(n)$ bits each, such that after measuring

the state $|\Psi \rangle$ 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

{\em quantum low-degree-test} that may be interesting

in its own right.