<p>co-NP ⊈ MIP* relative to a random oracle.</p>
<p>Given a random oracle <span class="math-container">$A$</span>, define <span class="math-container">$\text{coNP}^A$</span> boolean <span class="math-container">$f$</span> using <span class="math-container">$f(1^n)$</span> iff <span class="math-container">$∀s∈\{0,1\}^n \, ∃i&lt;n \, s1^i∉A$</span>.  We claim that with probability 1, <span class="math-container">$f$</span> is not in the relativized MIP*.</p>
<p>Otherwise, pick a randomized protocol that succeeds for <span class="math-container">$Ω(1)$</span> fraction of <span class="math-container">$A$</span>.  Choose a random <span class="math-container">$A$</span> for which the protocol succeeds and a large enough <span class="math-container">$n$</span> such that <span class="math-container">$f(1^n)$</span> is true.  Let <span class="math-container">$A'$</span> be <span class="math-container">$A$</span> augmented with <span class="math-container">$s1^i$</span> for some random <span class="math-container">$n$</span>-bit binary string <span class="math-container">$s$</span> and all <span class="math-container">$i&lt;n$</span>, and <span class="math-container">$f'$</span> be the <span class="math-container">$f$</span> for <span class="math-container">$A'$</span>.  The possibilities for the provers are unaffected by using <span class="math-container">$A'$</span> in place of <span class="math-container">$A$</span>, so consider provers that for <span class="math-container">$A$</span>, with probability <span class="math-container">$&gt;1-ε$</span>, convince the verifier that <span class="math-container">$f(1^n)$</span> is true, with the verifier making at most <span class="math-container">$m = n^{O(1)}$</span> queries to <span class="math-container">$A$</span>.  Then, since <span class="math-container">$s$</span> is random, with probability <span class="math-container">$≥1-mn/2^n$</span>, <span class="math-container">$s1^i$</span> are not queried, so with probability <span class="math-container">$&gt;1-ε-mn/2^n$</span> (i.e. with high enough probability) the verifier is incorrectly convinced of <span class="math-container">$f'(1^n)$</span>.  Thus (since we independently-enough rule out <span class="math-container">$Ω(1)$</span> fraction of <span class="math-container">$A$</span> for each large enough <span class="math-container">$n$</span>), the verifier must fail for almost all choices of <span class="math-container">$A$</span>.</p>
<p>In place of randomness, I expect that algorithmic randomness suffices, so for example a Chaitin's constant (with the <span class="math-container">$i$</span>th binary digit accessed using <span class="math-container">$i$</span> in binary) in place of <span class="math-container">$A$</span> should then work.</p>
<p>Using BBBV theorem, the above <span class="math-container">$f$</span> for a random oracle <span class="math-container">$A$</span> is not even in the extension of the relativized MIP* that uses a quantum verifier, and quantum interactions between the provers and the verifier.  As before, the possibilities for the provers are unaffected by using <span class="math-container">$A'$</span> in place of <span class="math-container">$A$</span>, so we can assume that they do not query <span class="math-container">$A'$</span>.  By BBBV theorem (optimality of Grover's algorithm) distiguishing <span class="math-container">$A'$</span> from <span class="math-container">$A$</span> (with unlimited access to <span class="math-container">$A$</span>) requires <span class="math-container">$Ω(2^{n/2}/\sqrt{n})$</span> quantum queries to <span class="math-container">$A'$</span>, and thus cannot be done with a polynomial time verifier.</p>

CC BY-SA 4.0
2024-11-20T10:48:03.067Z
Beautiful, thanks a lot for these explanations! The use of the auxiliary strings to make each $1^n$ be in $A$ with probability 1/2 makes perfect sense. It's interesting that the argument for MIP* makes no reference to the quantum power of provers, and it only becomes relevant if we assume the verifier is quantum too. I'm not convinced that algorithmically random oracles are enough, but I'm sure a step or two in the arithmetical hierarchy would do the trick...
Wojowu
CC BY-SA 4.0
2024-11-20T04:24:51.900Z
2024-11-20T04:24:51.900Z
Dmytro Taranovsky
<p>Scott Aaronson has explained in a <a href="https://scottaaronson.blog/?p=4512#comment-1828321" rel="nofollow noreferrer">comment under his blog</a> that the celebrated result of MIP* = RE does not relativize, and in fact claims relative to oracles, MIP* need not even contain coNP.</p>
<p>The argument goes as follows: consider the problem of deciding if the function <span class="math-container">$f:\{0,1\}^n\to\{0,1\}$</span> is everywhere zero. This is a coNP problem, but it cannot be solved in MIP* becase modifying <span class="math-container">$f$</span> at a single input changes the answers, but BBBV Theorem prevents change of one random input from suitably changing the quantum probabilities for this to be detectable by an MIP* protocol.</p>
<p>This makes some vague sense to me but I don't see how it implies such a non-relativization result. Indeed, the first question is how exactly do we phrase this coNP problem - we cannot encode <span class="math-container">$f$</span> fully in an input, it is not blackboxed, so typically we encode it as some sort of circuit, which makes it into the complement of SAT.</p>
<p>But then, the function is not completely blackboxed. Indeed, it cannot be for otherwise a similar argument would show that this coNP problem is not in MIP* even in oracle-free world. The function is encoded as a computation which we can then write an MIP* protocol for. And the way this computation is performed will be influenced by the change of any one input.</p>
<p>As far as I can tell, this sort of &quot;non-argument&quot; is equally valid for any one fixed oracle. The only possible idea I have is that this sort of &quot;black box function&quot; argument still implies unsolvability with respect to some oracle. With all that said, here are my questions:</p>
<blockquote>
<ol>
<li>Can anyone clarify the argument, and how it shows coNP <span class="math-container">$\not\subseteq$</span> MIP* doesn't relativize?</li>
<li>Can one give a reasonably explicit oracle for which this inclusion fails? (it will obviously have to be noncomputable so I'm lenient on what &quot;explicit&quot; means)</li>
<li>Does this argument give non-inclusion relative to a random oracle? If not, do we know or expect it to fail with probability <span class="math-container">$1$</span>?</li>
</ol>
</blockquote>
<p>Edit: in a comment I have put in a sketch of an idea for proving 3 (and hence 1) that I had reading old papers, but I don't know enough relevant theory to know how it could be completed. It makes it vaguely plausible that you can in general translate such blackbox results into random oracle results.</p>
<p>In the meantime I also came up with a different question:</p>
<blockquote>
<ol start="4">
<li>Does MIP* = RE, or at least the inclusion NEXP <span class="math-container">$\subseteq$</span> MIP*, <a href="http://www.scottaaronson.com/papers/alg.pdf" rel="nofollow noreferrer">algebrize</a>?</li>
</ol>
</blockquote>
<p>Given that characterizations of both IP and MIP algebrize, this is certainly more plausible, but I suspect the answer would still be negative.</p>

CC BY-SA 4.0
2024-11-11T13:47:39.540Z
Having looked again at proofs of the random oracle results I had an idea that we could consider random oracle $A$ and consider the set of $n$ such that $A$ vanishes on all length $n$ inputs. However this set is finite almost surely so this doesn't work. We could consider Bennett-Gill's language CORANGE$_A$ consisting of the complement of the image of some pseudorandom function associated with $A$, but I don't understand the relevant quantum stuff well enough to know if it works.
Wojowu
<cc.complexity-theory><quantum-computing><interactive-proofs><relativization>
Non-relativization of MIP* = RE
Wojowu
# Non-relativization of MIP* = RE

(Asked by: username_0 on 2024-11-10)

Scott Aaronson has explained in a [comment under his blog](https://scottaaronson.blog/?p=4512#comment-1828321) that the celebrated result of MIP\* = RE does not relativize, and in fact claims relative to oracles, MIP\* need not even contain coNP.

The argument goes as follows: consider the problem of deciding if the function $f:\{0,1\}^n\to\{0,1\}$ is everywhere zero. This is a coNP problem, but it cannot be solved in MIP\* becase modifying $f$ at a single input changes the answers, but BBBV Theorem prevents change of one random input from suitably changing the quantum probabilities for this to be detectable by an MIP\* protocol.

This makes some vague sense to me but I don't see how it implies such a non-relativization result. Indeed, the first question is how exactly do we phrase this coNP problem - we cannot encode $f$ fully in an input, it is not blackboxed, so typically we encode it as some sort of circuit, which makes it into the complement of SAT.

But then, the function is not completely blackboxed. Indeed, it cannot be for otherwise a similar argument would show that this coNP problem is not in MIP\* even in oracle-free world. The function is encoded as a computation which we can then write an MIP\* protocol for. And the way this computation is performed will be influenced by the change of any one input.

As far as I can tell, this sort of "non-argument" is equally valid for any one fixed oracle. The only possible idea I have is that this sort of "black box function" argument still implies unsolvability with respect to some oracle. With all that said, here are my questions:

> 1. Can anyone clarify the argument, and how it shows coNP $\not\subseteq$ MIP\* doesn't relativize?
> 2. Can one give a reasonably explicit oracle for which this inclusion fails? (it will obviously have to be noncomputable so I'm lenient on what "explicit" means)
> 3. Does this argument give non-inclusion relative to a random oracle? If not, do we know or expect it to fail with probability $1$?

Edit: in a comment I have put in a sketch of an idea for proving 3 (and hence 1) that I had reading old papers, but I don't know enough relevant theory to know how it could be completed. It makes it vaguely plausible that you can in general translate such blackbox results into random oracle results.

In the meantime I also came up with a different question:

> 4. Does MIP\* = RE, or at least the inclusion NEXP $\subseteq$ MIP\*, [algebrize](http://www.scottaaronson.com/papers/alg.pdf)?

Given that characterizations of both IP and MIP algebrize, this is certainly more plausible, but I suspect the answer would still be negative.

**Tags:** cc.complexity-theory, quantum-computing, interactive-proofs, relativization
> **Comments:**
> **username_0**: Having looked again at proofs of the random oracle results I had an idea that we could consider random oracle $A$ and consider the set of $n$ such that $A$ vanishes on all length $n$ inputs. However this set is finite almost surely so this doesn't work. We could consider Bennett-Gill's language CORANGE$_A$ consisting of the complement of the image of some pseudorandom function associated with $A$, but I don't understand the relevant quantum stuff well enough to know if it works.  

---

## 1 answers

### Answer by username_1 on 2024-11-20. Score: 2 | Accepted answer

co-NP ⊈ MIP\* relative to a random oracle.

Given a random oracle $A$, define $\text{coNP}^A$ boolean $f$ using $f(1^n)$ iff $∀s∈\{0,1\}^n \, ∃i. We claim that with probability 1, $f$ is not in the relativized MIP\*.

Otherwise, pick a randomized protocol that succeeds for $Ω(1)$ fraction of $A$. Choose a random $A$ for which the protocol succeeds and a large enough $n$ such that $f(1^n)$ is true. Let $A'$ be $A$ augmented with $s1^i$ for some random $n$-bit binary string $s$ and all $i, and $f'$ be the $f$ for $A'$. The possibilities for the provers are unaffected by using $A'$ in place of $A$, so consider provers that for $A$, with probability $>1-ε$, convince the verifier that $f(1^n)$ is true, with the verifier making at most $m = n^{O(1)}$ queries to $A$. Then, since $s$ is random, with probability $≥1-mn/2^n$, $s1^i$ are not queried, so with probability $>1-ε-mn/2^n$ (i.e. with high enough probability) the verifier is incorrectly convinced of $f'(1^n)$. Thus (since we independently-enough rule out $Ω(1)$ fraction of $A$ for each large enough $n$), the verifier must fail for almost all choices of $A$.

In place of randomness, I expect that algorithmic randomness suffices, so for example a Chaitin's constant (with the $i$th binary digit accessed using $i$ in binary) in place of $A$ should then work.

Using BBBV theorem, the above $f$ for a random oracle $A$ is not even in the extension of the relativized MIP\* that uses a quantum verifier, and quantum interactions between the provers and the verifier. As before, the possibilities for the provers are unaffected by using $A'$ in place of $A$, so we can assume that they do not query $A'$. By BBBV theorem (optimality of Grover's algorithm) distiguishing $A'$ from $A$ (with unlimited access to $A$) requires $Ω(2^{n/2}/\sqrt{n})$ quantum queries to $A'$, and thus cannot be done with a polynomial time verifier.

> **Comments:**
> **username_0**: Beautiful, thanks a lot for these explanations! The use of the auxiliary strings to make each $1^n$ be in $A$ with probability 1/2 makes perfect sense. It's interesting that the argument for MIP* makes no reference to the quantum power of provers, and it only becomes relevant if we assume the verifier is quantum too. I'm not convinced that algorithmically random oracles are enough, but I'm sure a step or two in the arithmetical hierarchy would do the trick...  

---

