TY - GEN

T1 - Quantum information and the PCP theorem

AU - Raz, Ran

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2005

Y1 - 2005

N2 - Our main result is that the membership x ∈ SAT (for x of length n) can be proved by a logarithmic-size quantum state |ψ〉, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |ψ〉 the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP / qpoly contains all languages. That is, for any language L (even non-recursive), the membership x ∈ 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 |ψ 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. The advice |ψ L, n> given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test.

AB - Our main result is that the membership x ∈ SAT (for x of length n) can be proved by a logarithmic-size quantum state |ψ〉, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |ψ〉 the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP / qpoly contains all languages. That is, for any language L (even non-recursive), the membership x ∈ 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 |ψ 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. The advice |ψ L, n> given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test.

UR - http://www.scopus.com/inward/record.url?scp=33745189567&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745189567&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2005.62

DO - 10.1109/SFCS.2005.62

M3 - Conference contribution

AN - SCOPUS:33745189567

SN - 0769524680

SN - 9780769524689

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 459

EP - 468

BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

Y2 - 23 October 2005 through 25 October 2005

ER -