Samuel Ducharme

There are many known oracle problems that provably separate BPP and BQP. There are also many kinds of interactive proof systems that have been developed over the last twenty years to make quantum computations done by a BQP machine verifiable by a BPP machine. Sadly, none of these techniques trivially relativize to oracle problems. This leads us to the following question: do these oracle problems also admit an interactive proof between a BQP prover and a BPP verifier, or is the existence of such interactive proof provably impossible? We show that Simon's problem and the Forrelation problem, two of the very few known oracle problems for which the previous question was still unanswered, do admit interactive proofs, under the assumption that the verifier has small and limited quantum capabilities. To do so, we introduce the first ever known interactive proofs with a BQP prover for these problems, as well as their corresponding proofs of security (completeness and soundness).

There are many known oracle problems that provably separate BPP and BQP. There are also many kinds of interactive proof systems that have been developed over the last twenty years to make quantum computations done by a BQP machine verifiable by a BPP machine. Sadly, none of these techniques trivially relativize to oracle problems. This leads us to the following question: do these oracle problems also admit an interactive proof between a BQP prover and a BPP verifier, or is the existence of such interactive proof provably impossible? We show that Simon's problem and the Forrelation problem, who were pretty much the only known oracle problems for which the previous question was still unanswered, do admit interactive proofs, under the assumption that the verifier has small and limited quantum capabilities. To do so, we introduce the first ever known interactive proofs with a BQP prover for these problems, as well as their corresponding proofs of security (completeness and soundness).

Simon's problem is one of the few black-box problems known to be in BQP but not in BPP. Although Simon's algorithm can be used to solve this problem efficiently, it isn't so easy for someone with access to a large-scale quantum computer (the prover) to convince someone whose computing power is in BPP (the verifier) of the validity of their computation. I present an interactive protocol that aims to accomplish this goal if the verifier has access to a quantum computer with a constant number of qubits. This protocol adapts some of the known techniques using quantum authentication schemes for non-black-box problems. It also uses a novel technique that consists of randomly doing “trap rounds” that are similar to Simon's algorithm iterations but instead ask the prover to call the black-box function on a randomly-generated polynomial-size superposition state chosen so that the verifier can detect the prover's attempts at cheating.