Quantum information and the PCP theorem

DOI10.1007/S00453-007-9033-6MaRDI QIDQ835644zbMATH OpenOpenAlexFDO

Authors Ran Raz

Publication date 31 August 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0504075

zbMATH Keywords

quantum informationquantum computationquantum adviceprobabilistically checkable proofslow degree testquantum interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Abstract: We show how to encode $2^n$ (classical) bits $a_1,\mathrm{...},a_{2^n}$ by a single quantum state $|Psi>$ of size O(n) qubits, such that: for any constant $k$ and any $i_1,\mathrm{...},i_{k}in1,\mathrm{...},2^n$, the values of the bits $a_{i_1},\mathrm{...},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 $xinL$ (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 $|Ps{i}_{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 $xinSAT$ (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 {�f 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.

Recommendations

• Quantum information theory
• Quantum information theory
• The \(g\)-theorem and quantum information theory
• scientific article; zbMATH DE number 1643848
• Quantum information and correlation bounds
• The theory of quantum information
• Quantum information and entropy
• Quantum probability and quantum information theory
• Quantum information complexity
• Quantum Kolmogorov complexity and information-disturbance theorem

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3497764 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Parallel Repetition Theorem
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Dense quantum coding and quantum finite automata
• IP = PSPACE
• Improved low-degree testing and its applications
• Interactive proofs and the hardness of approximating cliques
• Limitations of Quantum Advice and One-Way Communication
• Non-deterministic exponential time has two-prover interactive protocols
• On the two-state vector reformulation of quantum mechanics
• PCP characterizations of NP: toward a polynomially-small error-probability
• PSPACE has constant-round quantum interactive proof systems
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Polynomial time quantum computation with advice
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Sub-constant error low degree test of almost-linear size
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(9)

• A note about a partial no-go theorem for quantum PCP
• Debates with small transparent quantum verifiers
• A broader view on the limitations of information processing and communication by nature
• A full characterization of quantum advice
• On quantum information before the Page time
• NP vs QMA\(_{\log}(2)\)
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• A quantum characterization of NP
• Verifiable stream computation and Arthur-Merlin communication

This page was built for publication: Quantum information and the PCP theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835644)