{
  "annotation_id": "bfcfaced-7912-4e65-bf2c-b7f43436b0de",
  "date_created": "2026-03-02T18:02:15.957000Z",
  "date_modified": "2026-03-02T18:02:15.957000Z",
  "file_hash": "8a108358300356ab7a7a18bf47ae4f6a998766eddc54b2acfd88c4ab03c780b9",
  "private": false,
  "record": {
    "abstract": "We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$ by a single\nquantum state $|\\Psi\u003e$ of size O(n) qubits, such that: for any constant $k$ and\nany $i_1,...,i_k \\in \\{1,...,2^n\\}$, the values of the bits\n$a_{i_1},...,a_{i_k}$ can be retrieved from $|\\Psi\u003e$ by a one-round\nArthur-Merlin interactive protocol of size polynomial in $n$. This shows how to\ngo around Holevo-Nayak\u0027s Theorem, using Arthur-Merlin proofs.\n  We use the new representation to prove the following results:\n  1) Interactive proofs with quantum advice: We show that the class $QIP/qpoly$\ncontains ALL languages. That is, for any language $L$ (even non-recursive), the\nmembership $x \\in L$ (for $x$ of length $n$) can be proved by a polynomial-size\nquantum interactive proof, where the verifier is a polynomial-size quantum\ncircuit with working space initiated with some quantum state $|\\Psi_{L,n} \u003e$\n(depending only on $L$ and $n$). Moreover, the interactive proof that we give\nis of only one round, and the messages communicated are classical.\n  2) PCP with only one query: We show that the membership $x \\in SAT$ (for $x$\nof length $n$) can be proved by a logarithmic-size quantum state $|\\Psi \u003e$,\ntogether with a polynomial-size classical proof consisting of blocks of length\n$polylog(n)$ bits each, such that after measuring the state $|\\Psi \u003e$ the\nverifier only needs to read {\\bf one} block of the classical proof.\n  While the first result is a straight forward consequence of the new\nrepresentation, the second requires an additional machinery of quantum\nlow-degree-test that may be interesting in its own right.",
    "arxiv_id": "quant-ph/0504075",
    "authors": [
      "Ran Raz"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Information and the PCP Theorem",
    "url": "https://arxiv.org/abs/quant-ph/0504075"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "510cbbe5-54c6-4eee-8f9e-f00e02d60157",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}