A Caltech Library Service

Quantum proof systems for iterated exponential time, and beyond

Fitzsimons, Joseph and Ji, Zhengfeng and Vidick, Thomas and Yuen, Henry (2018) Quantum proof systems for iterated exponential time, and beyond. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that any language in nondeterministic time exp(exp(· · · exp(n))), where the number of iterated exponentials is an arbitrary functionR(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 (unpublished) on the uncomputability of the entangled value of multiprover games. 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:Joseph Fitszsimons 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 NRF-NRFF2013-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 is supported by ARO Grant W911NF-12-1-0541 and NSF Grant CCF-1410022.
Group:IQIM, Institute for Quantum Information and Matter
Funding AgencyGrant Number
NSF Physics Frontiers CenterPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
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
Army Research Office (ARO)W911NF-12-1-0541
Ministry of Education (Singapore)UNSPECIFIED
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:03 Oct 2019 20:46

Repository Staff Only: item control page