8
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Geoffrey Irving
    Commented Jan 21, 2020 at 21:38
  • 1
    $\begingroup$ Yes there's some blow-up, it should be something like NTIME[poly(T)] provers can prove NTIME[T] languages. $\endgroup$
    – Henry Yuen
    Commented Jan 22, 2020 at 2:36
  • $\begingroup$ Reasonable to conjecture that for suitably large $T$ the blowup disappears? $\endgroup$
    – Geoffrey Irving
    Commented Jan 22, 2020 at 14:00
  • 1
    $\begingroup$ I think in our proof there is always some blow-up. It's a modest polynomial blow-up, but there nonetheless. $\endgroup$
    – Henry Yuen
    Commented Jan 22, 2020 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.