QUROPE Quantum Information Processing and Communication in Europe

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}.

Normalizer circuits [1,2] are generalized Clifford circuits that act on arbitrary finite-dimensional systems Hd1⊗...⊗Hdn with a standard basis labeled by the elements of a finite Abelian group G=Zd1×...×Zdn. Normalizer gates implement operations associated with the group G and can be of three types: quantum Fourier transforms, group automorphism gates and quadratic phase gates.

The paper provides new evidence that quantum computers cannot be efficiently simulated by classical computers. In particular, the authors consider a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number in each mode. While this model is not known or believed to be universal for quantum computation, it is shown that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.