Efficient classical simulation of the approximate quantum Fourier transform

Nadav Yoran, Anthony J. Short

Research output: Contribution to journalArticle (Academic Journal)peer-review

28 Citations (Scopus)


We present a method for classically simulating quantum circuits based on the tensor contraction model of Markov and Shi (e-print arXiv:quant-ph/0511069). Using this method we are able to classically simulate the approximate quantum Fourier transform in polynomial time. Moreover, our approach allow us to formulate a condition for the composability of simulable quantum circuits. We use this condition to show that any circuit composed of a constant number of approximate quantum Fourier transform circuits and log depth circuits with limited interaction range can also be efficiently simulated.

Original languageEnglish
Article number042321
Pages (from-to)-
Number of pages5
JournalPhysical Review A: Atomic, Molecular and Optical Physics
Issue number4
Publication statusPublished - Oct 2007


Dive into the research topics of 'Efficient classical simulation of the approximate quantum Fourier transform'. Together they form a unique fingerprint.

Cite this