Fitzsimons, Joseph and Ji, Zhengfeng and Vidick, Thomas and Yuen, Henry (2019) Quantum proof systems for iterated exponential time, and beyond. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC '19). Association for Computing Machinery , New York, NY, pp. 473-480. ISBN 978-1-4503-6705-9. https://resolver.caltech.edu/CaltechAUTHORS:20190204-112657116
![]() |
PDF
- Published Version
See Usage Policy. 769kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 566kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190204-112657116
Abstract
We show that any language solvable in nondeterministic time exp( exp(⋯exp(n))), where the number of iterated exponentials is an arbitrary function R(n), can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1 − exp(−Cexp(⋯exp(n))), where the number of iterated exponentials is R(n)−1 and C>0 is a universal constant. The result was previously known for R=1 and R=2; we obtain it for any time-constructible function R. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC’17). As a separate consequence of this technique we obtain a different proof of Slofstra’s recent result on the uncomputability of the entangled value of multiprover games (Forum of Mathematics, Pi 2019). Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson’s problem on the relation between the commuting operator and tensor product models for quantum correlations.
Item Type: | Book Section | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||||
Additional Information: | © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. We thank the anonymous STOC 2019 referees for helpful comments that have improved the presentation of this paper. Joseph Fitzsimons acknowledges support from Singapore’s Ministry of Education and National Research Foundation, and the US Air Force Office of Scientific Research under AOARD grant FA2386-15-1-4082. This material is based on research funded in part by the Singapore National Research Foundation under NRF Award NRFNRFF2013-01. Thomas Vidick is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, a CIFAR Azrieli Global Scholar award, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). Henry Yuen conducted the research for this work as a postdoctoral fellow at the University of California, Berkeley. | ||||||||||||||||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||||
DOI: | 10.1145/3313276.3316343 | ||||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20190204-112657116 | ||||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190204-112657116 | ||||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||||
ID Code: | 92629 | ||||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||||
Deposited By: | Bonnie Leung | ||||||||||||||||||||||||
Deposited On: | 06 Feb 2019 17:26 | ||||||||||||||||||||||||
Last Modified: | 16 Nov 2021 03:52 |
Repository Staff Only: item control page