Efficient classical simulations of quantum Fourier transforms and Normalizer circuits over Abelian groups
| Autor: | Maarten Van den Nest |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Computer Science::Hardware Architecture
Nuclear and High Energy Physics Computer Science::Emerging Technologies Computational Theory and Mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION General Physics and Astronomy Statistical and Nonlinear Physics Mathematical Physics Theoretical Computer Science |
| Zdroj: | Quantum Information and Computation. 13:1007-1037 |
| ISSN: | 1533-7146 |
| DOI: | 10.26421/qic13.11-12-7 |
| Popis: | The quantum Fourier transform (QFT) is an important ingredient in various quantum algorithms which achieve superpolynomial speed-ups over classical computers. In this paper we study under which conditions the QFT can be simulated efficiently classically. We introduce a class of quantum circuits, called \emph{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. In our main result 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. Our result generalizes the Gottesman-Knill theorem: in particular, Clifford circuits for $d$-level qudits arise as normalizer circuits over the group ${\mathbf Z}_d^m$. We also highlight connections between normalizer circuits and Shor's factoring algorithm, and 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|