2006/11/23 by Nadav Yoran, Anthony J. Short, Anthony Short · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Applied mathematics #Computer science #Discrete Fourier transform (general) #Fourier analysis #Fourier transform #Fractional Fourier transform #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum computer #Quantum many-body systems #Quantum mechanics #Quantum simulator #Statistical physics #quant-ph
paper · pdf · doi:10.1103/physreva.76.042321
published as Phys. Rev. A 76, 042321 (2007). · 5 pages, 3 figures
arxiv created 2006/11/23 · openalex publication_date 2007/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.