Quantum Information and the PCP Theorem

Ran Raz

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,...…