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.
Now consider the following, this paper 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!