A Caltech Library Service

Quantum proof systems for iterated exponential time, and beyond

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.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
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
Funding AgencyGrant Number
Ministry of Education (Singapore)UNSPECIFIED
National Research Foundation of KoreaUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA2386-15-1-4082
National Research Foundation (Singapore)NRF-NRFF2013-01
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
University of California, BerkeleyUNSPECIFIED
Record Number:CaltechAUTHORS:20190204-112657116
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92629
Deposited By: Bonnie Leung
Deposited On:06 Feb 2019 17:26
Last Modified:16 Nov 2021 03:52

Repository Staff Only: item control page