Does the MIP* = RE proof work for limited provers?

Question

MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem. Now assume that we have two entangled provers that are only capable of solving problems in some language $L$ (say a language complete for NEEXP, NEEEXP, etc.).

Question: What constraints on $L$ allow provers to convince a verifier of solutions to $L$?

The nonquantum analogy is that not only is IP = PSPACE, but IP' = PSPACE where IP' provers are only able to solve PSPACE level problems. In particular, L = PSPACE works for the MIP* question. ~~Moreover, provers that are limited to any level of the polynomial hierarchy $\Sigma_k \textrm{P}$ can establish $\Sigma_k \textrm{P} \subset \textrm{PSPACE}$.~~ (Unfortunately, looks like this doesn't work lower in the polynomial hierarchy.)

(I'm blurring over some definitional subtlety here about function problems vs. decision problems; in the above one probably needs the provers to be able to solve $\textrm{FP}^L$ rather than just L.)

Henry Yuen · Accepted Answer · 2020-01-22T02:37:33.960

9

I believe our result shows that if the prover is capable of solving NTIME[poly(T)] problems, and has the ability to manipulate polylog(T) qubits, then they can convince the verifier of YES instances of NTIME[T] problems.

In other words, roughly speaking NTIME[2^poly(Q)] = MIP*[Q] where MIP*[Q] denotes the provers being limited to Q qubits of entanglement.

edited Jan 22 '20 at 02:37

answered Jan 21 '20 at 17:52

Henry Yuen

3,798
1
21
33

Thank you! To clarify: your first statement seems much stronger than the second due to $T$ being the same in both occurrences of NTIME. Would there be some blowup? – Geoffrey Irving Jan 21 '20 at 21:38
1

Yes there's some blow-up, it should be something like NTIME[poly(T)] provers can prove NTIME[T] languages. – Henry Yuen Jan 22 '20 at 02:36
Reasonable to conjecture that for suitably large $T$ the blowup disappears? – Geoffrey Irving Jan 22 '20 at 14:00
1

I think in our proof there is always some blow-up. It's a modest polynomial blow-up, but there nonetheless. – Henry Yuen Jan 22 '20 at 21:05

Does the MIP* = RE proof work for limited provers?

1 Answers1