Quantum information and the PCP theorem

DOI10.1007/S00453-007-9033-6zbMATH Open1192.68280arXivquant-ph/0504075OpenAlexW2109833455MaRDI QIDQ835644FDOQ835644

Authors: Ran Raz 

Publication date: 31 August 2009

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (10)

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

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)