We could expect the first large-scale fault-tolerant quantum computers to be few in number and only accessible to the masses via some sort of cloud service, where users would send computing tasks to remote quantum computers. Under the common belief that quantum computers will be more powerful than classical ones (i.e., that BPP is strictly contained in BQP), this raises the following question : if a quantum computer can efficiently perform a computation that a classical computer cannot, can the classical computer at least efficiently verify its result? Over the years, many techniques have been developed to make delegated quantum computations verifiable classically, using interaction and various assumptions. Notable examples include the protocols of Aharonov, Ben-Or, Eban and Mahadev ( [ https://arxiv.org/abs/1704.04487 | https://arxiv.org/abs/1704.04487 ] ), Broadbent, Fitzsimons and Kashefi ( [ https://arxiv.org/abs/0807.4154 | https://arxiv.org/abs/0807.4154 ] ), and Mahadev ( [ https://arxiv.org/abs/1804.01082 | https://arxiv.org/abs/1804.01082 ] ). However, none of these techniques are known to relativize to oracle problems, some of which provably separate BPP and BQP and aren't trivially verifiable by a classical agent.
In this talk, I will introduce the first ever protocols for some of these oracle problems, namely Simon's problem and the Forrelation problem, by adapting known verification techniques in novel ways. I will also discuss the possibility of the existence of an oracle problem that is efficiently solvable by a quantum computer, but for which there couldn't exist a verification protocol between a quantum prover and a classical verifier. This talk is based on results from my PhD thesis, which are yet unpublished.