Quantum-Classical Tradeoffs in the Random Oracle Model

We study tradeoffs between quantum and classical queries for hybrid algorithms that have black-box access to a random oracle. Although there are several established techniques for proving query lower bounds for both quantum and classical algorithms, there is no such widely applicable technique for hybrid algorithms and the optimal tradeoffs for many fundamental problems are still unknown $\unicode{x2013}$ an optimal tradeoff for the search problem was only shown recently by Rosmanis, although not in the random oracle model. For another fundamental problem, collision finding, the optimal tradeoff was not known. In this work, we develop a framework for recording a query transcript for quantum-classical algorithms that represents the knowledge gained by the algorithm. The main feature of this framework is to allow us to record queries in two incompatible bases $\unicode{x2013}$ classical queries in the standard basis and quantum queries in the Fourier basis $\unicode{x2013}$ in a consistent way. We call the framework the hybrid compressed oracle as it naturally interpolates between the classical way of recording queries and the compressed oracle framework of Zhandry for recording quantum queries. We demonstrate its applicability by giving a simpler proof of the optimal quantum-classical tradeoff for search and by showing an optimal tradeoff for collision finding.