Quantum proof systems for iterated exponential time, and beyond

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(− C exp(⋯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 .

Authors

• Joseph F. Fitzsimons
• Zhengfeng Ji
• Thomas Vidick
• Henry Yuen

Keywords

• quantum entanglement
• quantum correlations
• Quantum multiprover interactive proofs
• self-testing