Samuel Ducharme

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.