  A fundamental pursuit in complexity theory concerns reducing worst-case
problems to average-case problems. There exist complexity classes such as
PSPACE that admit worst-case to average-case reductions. However, for many
other classes such as NP, the evidence so far is typically negative, in the
sense that the existence of such reductions would cause collapses of the
polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the
average-case hardness of inverting one-way permutations, on NP-completeness is
a particularly intriguing instance. As there is evidence showing that classical
reductions from NP-hard problems to breaking these primitives result in PH
collapses, it seems unlikely to base cryptographic primitives on NP-hard
problems. Nevertheless, these results do not rule out the possibilities of the
existence of quantum reductions. In this work, we initiate a study of the
quantum analogues of these questions. Aside from formalizing basic notions of
quantum reductions and demonstrating powers of quantum reductions by examples
of separations, our main result shows that if NP-complete problems reduce to
inverting one-way permutations using certain types of quantum reductions, then
coNP $\subseteq$ QIP(2).
