English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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