  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.
