Mark Zhandry: Quantum Query Solvability: A Refinement of Quantum Query Complexity and Applications

Mark Zhandry (Stanford University)
Quantum Query Solvability: A Refinement of Quantum Query Complexity and Applications
QuICS Workshop on the Frontiers of Quantum Information and Computer Science (September 28, 2015)

The standard notion of “difficulty” for quantum oracle problems is that of quantum query complexity, which measures how many quantum queries to an oracle are required to solve a given problem.

In this talk, I will argue that quantum query complexity results typically hide important relationships between quantum queries and the ability to solve problems. Instead, I will argue for a more refined notion of difficulty, called quantum query solvability, which measures how easy it is to solve a given problem using a prescribed number of queries.

To motivate this notion, I will then describe several settings arising from cryptography where quantum query solvability is important/useful. One such setting is that of finding collisions in a function f:{1,...,M}→{1,...,N}. The quantum query complexity of the so-called quantum collision problem has been established in the setting where N≥M, but it is unclear how to extend these results to the case where N is less than M, which is the cryptographically interesting setting. I will show how to solve this problem for arbitrary M,N. The idea is to first determine the quantum oracle solvability of the problem for the regime N≥M, after which a simple reduction extends the result to the case where N is less than M (such a reduction does not apply for quantum query complexity). The quantum oracle solvability when N is less than M implies an optimal quantum query complexity in that regime, thus resolving the quantum query complexity problem for all domain/range sizes.