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.