PACM Colloquium: Quantum Oracle Classification: The Case of Group Structure

PACM Colloquium
  • Mark Zhandry
  • Princeton University
Dec 12, 2016
4 pm
Fine Hall 214

The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems.

In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation; polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have other applications.

We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is, we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality. Unfortunately, solving this counting problem in general is a non-trivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic message authentication codes in the quantum setting.

______________________

Mark Zhandry received his bachelor’s degree from UC Berkeley, where he majored in electrical engineering, computer science, and physics, and minored in mathematics.  He earned his PhD in computer science in 2015 from Stanford University, and subsequently was a postdoctoral associate at MIT.  Since Summer 2016, he is an assistant professor in the computer science department at Princeton University.  His main research area is cryptography, with focuses on software obfuscation and the impacts of quantum computers to cryptography.