This work presents a precise connection between Clifford circuits, Shor's
factoring algorithm and several other famous quantum algorithms with
exponential quantum speed-ups for solving Abelian hidden subgroup problems. We
show that all these different forms of quantum computation belong to a common
new restricted model of quantum operations that we call \emph{black-box
normalizer circuits}. To define these, we extend the previous model of
normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which
are built of quantum Fourier transforms, group automorphism and quadratic phase
gates associated to an Abelian group $G$. In previous works, the group $G$ is
always given in an explicitly decomposed form. In our model, we remove this
assumption and allow $G$ to be a black-box group. While standard normalizer
circuits were shown to be efficiently classically simulable
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer
circuits are powerful enough to factorize and solve classically-hard problems
in the black-box setting. We further set upper limits to their computational
power by showing that decomposing finite Abelian groups is complete for the
associated complexity class. In particular, solving this problem renders
black-box normalizer circuits efficiently classically simulable by exploiting
the generalized stabilizer formalism in
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our
connection to draw a few practical implications for quantum algorithm design:
namely, we give a no-go theorem for finding new quantum algorithms with
black-box normalizer circuits, a universality result for low-depth normalizer
circuits, and identify two other complete problems.
