### 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) |
---|---|

Title of host publication | Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 |

Pages | 459-468 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2005 |

Externally published | Yes |

Event | 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States Duration: Oct 23 2005 → Oct 25 2005 |

### Publication series

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

Volume | 2005 |

ISSN (Print) | 0272-5428 |

### Other

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

Country | United States |

City | Pittsburgh, PA |

Period | 10/23/05 → 10/25/05 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'Quantum information and the PCP theorem'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005*(pp. 459-468). [1530738] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.62