## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 462-489 |

Number of pages | 28 |

Journal | Algorithmica (New York) |

Volume | 55 |

Issue number | 3 |

DOIs | |

State | Published - Nov 2009 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Low degree test
- Probabilistically checkable proofs
- Quantum advice
- Quantum computation
- Quantum information
- Quantum interactive proofs