Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups

Details Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups

2012-01-23

arxiv.org/abs/1201.4867v1

Physics

Quantum Physics

23 pages + appendices

Scientific paper

The quantum Fourier transform (QFT) is sometimes said to be the source of various exponential quantum speed-ups. In this paper we introduce a class of quantum circuits which cannot outperform classical computers even though the QFT constitutes an essential component. More precisely, we consider normalizer circuits. A normalizer circuit over a finite Abelian group is any quantum circuit comprising the QFT over the group, gates which compute automorphisms and gates which realize quadratic functions on the group. We prove that all normalizer circuits have polynomial-time classical simulations. The proof uses algorithms for linear diophantine equation solving and the monomial matrix formalism introduced in our earlier work. We subsequently discuss several aspects of normalizer circuits. First we show that our result generalizes the Gottesman-Knill theorem. Furthermore we highlight connections to Shor's factoring algorithm and to the Abelian hidden subgroup problem in general. Finally we prove that quantum factoring cannot be realized as a normalizer circuit owing to its modular exponentiation subroutine.

Affiliated with

Also associated with

No associations

Rating

Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105268