<p>I'm glad you're interested in my IP with BQP prover problem!</p>

<p>Unfortunately, I'm not sure I understand your question.  If the function $f$ satisfies the Simon promise, then Merlin can easily convince Arthur of that by telling him the secret string $s$.  If, on the other hand, $f$ is one-to-one, then Merlin can convince <i>himself</i> of that (by using Simon's algorithm to look for $s$ and not finding anything), but the question is how he can convince <i>Arthur</i>.  It clearly won't do for Merlin to say, "Arthur, I looked for $s$, but I found nuthin'!"  For how would Arthur know that Merlin wasn't lying?</p>

<p>Now, it's a known theorem that, if Merlin <i>wasn't</i> around, then Arthur would need to make at least ~$2^{n/2}$ black-box queries to $f$, in order to decide with high probability whether $f$ was one-to-one or satisfied the Simon promise.</p>

<p>It's also known that, if Merlin had <i>unbounded</i> computational power (not just the power of BQP), then there <i>is</i> an interactive protocol by which Merlin could convince Arthur that $f$ is one-to-one.  Namely, Arthur picks a random $x$, evaluates $f(x)$, sends $f(x)$ to Merlin, and asks Merlin to tell him what $x$ was.  If $f$ is one-to-one, then Merlin---provided he has NP search powers---can always answer such challenges correctly.  But if $f$ is two-to-one, then Merlin must be wrong with probability at least $1/2$.</p>

<p>The case I asked about---the one where Merlin has BQP powers, but no more than that---is still open.</p>

<p>To answer your last question: no, one would <i>not</i> need to prove BPP&ne;BQP in order to solve this problem.  The reason is that this problem only concerns the <i>relativized</i> setting: the setting where the function $f$ is a black box, which Arthur and Merlin can learn about only by querying it.  And in the relativized setting---unlike the "real," unrelativized one---we can often prove <i>unconditional</i> separations between complexity classes!  Indeed, I already mentioned one example above: it's known that any classical randomized algorithm to solve Simon's problem has to make exponentially many queries to $f$.  That fact implies the existence of an oracle separating BPP from BQP.</p>

CC BY-SA 3.0
2011-08-11T22:39:14.480Z
2011-08-11T23:41:39.287Z
2011-08-11T23:41:39.287Z
Scott Aaronson
<p><strong>Context:</strong> Aaronson raised the following question: </p>

<blockquote>
  <p>Let f be a black-box function, which is promised either to satisfy the
  Simon promise or to be one-to-one.  Can a prover with the power of BQP
  convince a BPP verifier that f is one-to-one?</p>
</blockquote>

<p><strong>Speculation:</strong> Let's take Arthur-Merlin protocols (I actually don't know in much depth about these protocols so please pardon any inconsistencies that may arise) where one can restrict Merlin's power to BQP instead of unbounded resources and Arthur has BPP resources. Now I realize that there are probabilities to: </p>

<blockquote>
  <p>A problem is considered to be solvable by this protocol if whenever
  the answer is "yes", Merlin has some series of responses which will
  cause Arthur to accept at least 2/3 of the time, and if whenever the
  answer is "no", Arthur will never accept more than 1/3 of the time.</p>
</blockquote>

<p>source: <a href="http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol" rel="nofollow">Wikipedia</a>. </p>

<p>Now consider the following, this <a href="http://arxiv.org/abs/quant-ph/9704027" rel="nofollow">paper</a> gives an algorithm where one can check in quantum polynomial time whether a function satisfies Simon's promise. Merlin can therefore check this, for Arthur we don't know, let's assume it can't. </p>

<p><strong>Question:</strong> Given the above mentioned conjecture, if Arthur sends (through a message) Merlin the function to be computed/checked in the first pass, Merlin can check whether the function satisfies Simon's promise or not, if yes, then we know the answer, if no, then is checking whether a function one-to-one in polynomial time? Also if Arthur can't check whether the function satisfies Simon's promise can the probabilities above mentioned change, since Merlin knows the answer already? </p>

<p>I also think this question might remain open until we know whether BPP != BQP, are there any indirect techniques that can let one evade having to rely on conjectural support in my argument? Thanks!</p>

CC BY-SA 3.0
2011-08-11T21:05:31.677Z
If you're just using Artur to pass the function to Merlin, does it not make more sense to consider MA instead of AM (with appropriately limited provers)?
Joe Fitzsimons
CC BY-SA 3.0
2011-08-11T21:26:06.460Z
Perhaps, but as I understand, there aren't any advantages in using either one in terms of convincing Arthur. (I may be wrong here so feel free to correct me)
dhillonv10
CC BY-SA 3.0
2011-08-11T21:45:03.907Z
If you are considering AM, then it makes sense to consider more general messages from Arthur to Merlin, otherwise you are limiting yourself to MA due to the structure of the message.
Joe Fitzsimons
<cc.complexity-theory><ds.algorithms><time-complexity><nt.number-theory><interactive-proofs>
Arthur-Merlin protocol with BQP power
dhillonv10
# Arthur-Merlin protocol with BQP power

(Asked by: username_0 on 2011-08-11)

**Context:** Aaronson raised the following question:

> Let f be a black-box function, which is promised either to satisfy the
> Simon promise or to be one-to-one. Can a prover with the power of BQP
> convince a BPP verifier that f is one-to-one?

**Speculation:** Let's take Arthur-Merlin protocols (I actually don't know in much depth about these protocols so please pardon any inconsistencies that may arise) where one can restrict Merlin's power to BQP instead of unbounded resources and Arthur has BPP resources. Now I realize that there are probabilities to:

> A problem is considered to be solvable by this protocol if whenever
> the answer is "yes", Merlin has some series of responses which will
> cause Arthur to accept at least 2/3 of the time, and if whenever the
> answer is "no", Arthur will never accept more than 1/3 of the time.

source: [Wikipedia](http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol).

Now consider the following, this [paper](http://arxiv.org/abs/quant-ph/9704027) gives an algorithm where one can check in quantum polynomial time whether a function satisfies Simon's promise. Merlin can therefore check this, for Arthur we don't know, let's assume it can't.

**Question:** Given the above mentioned conjecture, if Arthur sends (through a message) Merlin the function to be computed/checked in the first pass, Merlin can check whether the function satisfies Simon's promise or not, if yes, then we know the answer, if no, then is checking whether a function one-to-one in polynomial time? Also if Arthur can't check whether the function satisfies Simon's promise can the probabilities above mentioned change, since Merlin knows the answer already?

I also think this question might remain open until we know whether BPP != BQP, are there any indirect techniques that can let one evade having to rely on conjectural support in my argument? Thanks!

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, nt.number-theory, interactive-proofs

> **Comments:**
> **username_1**: If you're just using Artur to pass the function to Merlin, does it not make more sense to consider MA instead of AM (with appropriately limited provers)?  
> **username_0**: Perhaps, but as I understand, there aren't any advantages in using either one in terms of convincing Arthur. (I may be wrong here so feel free to correct me)  
> **username_1**: If you are considering AM, then it makes sense to consider more general messages from Arthur to Merlin, otherwise you are limiting yourself to MA due to the structure of the message.  

---

## 1 answers

### Answer by username_2 on 2011-08-11. Score: 7 | Accepted answer

I'm glad you're interested in my IP with BQP prover problem!

Unfortunately, I'm not sure I understand your question. If the function $f$ satisfies the Simon promise, then Merlin can easily convince Arthur of that by telling him the secret string $s$. If, on the other hand, $f$ is one-to-one, then Merlin can convince *himself* of that (by using Simon's algorithm to look for $s$ and not finding anything), but the question is how he can convince *Arthur*. It clearly won't do for Merlin to say, "Arthur, I looked for $s$, but I found nuthin'!" For how would Arthur know that Merlin wasn't lying?

Now, it's a known theorem that, if Merlin *wasn't* around, then Arthur would need to make at least ~$2^{n/2}$ black-box queries to $f$, in order to decide with high probability whether $f$ was one-to-one or satisfied the Simon promise.

It's also known that, if Merlin had *unbounded* computational power (not just the power of BQP), then there *is* an interactive protocol by which Merlin could convince Arthur that $f$ is one-to-one. Namely, Arthur picks a random $x$, evaluates $f(x)$, sends $f(x)$ to Merlin, and asks Merlin to tell him what $x$ was. If $f$ is one-to-one, then Merlin---provided he has NP search powers---can always answer such challenges correctly. But if $f$ is two-to-one, then Merlin must be wrong with probability at least $1/2$.

The case I asked about---the one where Merlin has BQP powers, but no more than that---is still open.

To answer your last question: no, one would *not* need to prove BPP≠BQP in order to solve this problem. The reason is that this problem only concerns the *relativized* setting: the setting where the function $f$ is a black box, which Arthur and Merlin can learn about only by querying it. And in the relativized setting---unlike the "real," unrelativized one---we can often prove *unconditional* separations between complexity classes! Indeed, I already mentioned one example above: it's known that any classical randomized algorithm to solve Simon's problem has to make exponentially many queries to $f$. That fact implies the existence of an oracle separating BPP from BQP.


---

