Kempe, Julia and Kobayashi, Hirotada and Matsumoto, Keiji and Vidick, Thomas (2008) Using Entanglement in Quantum Multi-Prover Interactive Proofs. In: 23rd Annual IEEE Conference on Computational Complexity. IEEE , Piscataway, NJ, pp. 211-222. ISBN 978-0-7695-3169-4. https://resolver.caltech.edu/CaltechAUTHORS:20140910-083116800
|
PDF
- Published Version
See Usage Policy. 413kB | |
|
PDF
- Submitted Version
See Usage Policy. 222kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140910-083116800
Abstract
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.
| Item Type: | Book Section | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||||
| ORCID: |
| ||||||||||||||
| Additional Information: | © 2008 IEEE. Work partly done while at LRI, Univ. de Paris-Sud, Orsay. Partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848, by an Alon Fellowship of the Israeli Higher Council of Academic Research and by a grant of the Israeli Science Foundation. Supported by the Strategic Information and Communications R&D Promotion Programme No. 031303020 of the Ministry of Internal Affairs and Communications of Japan and the Grant-in-Aid for Scientific Research (B) No. 18300002 of the Ministry of Education, Culture, Sports, Science and Technology of Japan. Work partly done while at LRI, Univ. de Paris-Sud, Orsay and DI, École Normale Supérieure, Paris. | ||||||||||||||
| Funders: |
| ||||||||||||||
| DOI: | 10.1109/CCC.2008.6 | ||||||||||||||
| Record Number: | CaltechAUTHORS:20140910-083116800 | ||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20140910-083116800 | ||||||||||||||
| Official Citation: | Kempe, J.; Kobayashi, H.; Matsumoto, K.; Vidick, T., "Using Entanglement in Quantum Multi-prover Interactive Proofs," Computational Complexity, 2008. CCC '08. 23rd Annual IEEE Conference on , vol., no., pp.211,222, 23-26 June 2008 doi: 10.1109/CCC.2008.6 | ||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||
| ID Code: | 49520 | ||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||
| Deposited By: | Ruth Sustaita | ||||||||||||||
| Deposited On: | 10 Sep 2014 19:56 | ||||||||||||||
| Last Modified: | 10 Nov 2021 18:45 |
Repository Staff Only: item control page
