<p>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. </p>

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

CC BY-SA 4.0
2020-01-21T21:38:42.370Z
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
CC BY-SA 4.0
2020-01-22T02:36:59.613Z
Yes there's some blow-up, it should be something like NTIME[poly(T)] provers can prove NTIME[T] languages.
Henry Yuen
CC BY-SA 4.0
2020-01-22T14:00:06.777Z
Reasonable to conjecture that for suitably large $T$ the blowup disappears?
Geoffrey Irving
CC BY-SA 4.0
2020-01-22T21:05:42.107Z
I think in our proof there is always some blow-up. It's a modest polynomial blow-up, but there nonetheless.
Henry Yuen
CC BY-SA 4.0
2020-01-21T17:52:06.570Z
2020-01-22T02:37:33.960Z
2020-01-22T02:37:33.960Z
Henry Yuen
<p><a href="https://arxiv.org/abs/2001.04383" rel="noreferrer">MIP* = RE</a> 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 <span class="math-container">$L$</span> (say a language complete for NEEXP, NEEEXP, etc.).</p>

<p><strong>Question</strong>: What constraints on <span class="math-container">$L$</span> allow provers to convince a verifier of solutions to <span class="math-container">$L$</span>?</p>

<p>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.  <s>Moreover, provers that are limited to any level of the polynomial hierarchy <span class="math-container">$\Sigma_k \textrm{P}$</span> can establish <span class="math-container">$\Sigma_k \textrm{P} \subset \textrm{PSPACE}$</span>.</s> (Unfortunately, looks like this doesn't work <a href="https://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy?rq=1">lower in the polynomial hierarchy</a>.)</p>

<p>(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 <span class="math-container">$\textrm{FP}^L$</span> rather than just L.)</p>

<interactive-proofs>
Does the MIP* = RE proof work for limited provers?
Geoffrey Irving
# Does the MIP* = RE proof work for limited provers?

(Asked by: username_0 on 2020-01-16)

[MIP\* = RE](https://arxiv.org/abs/2001.04383) 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](https://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy?rq=1).)

(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.)

**Tags:** interactive-proofs

---

## 1 answers

### Answer by username_1 on 2020-01-21. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: Yes there's some blow-up, it should be something like NTIME[poly(T)] provers can prove NTIME[T] languages.  
> **username_0**: Reasonable to conjecture that for suitably large $T$ the blowup disappears?  
> **username_1**: I think in our proof there is always some blow-up. It's a modest polynomial blow-up, but there nonetheless.  

---

