Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Review: "A Comparison of Quantum and Traditional Fourier Transform Computations"

Matthias Troyer

Published Aug 20, 2020• 2 citations
Publisher

Abstract

The manuscript "A Comparison of Quantum and Traditional Fourier Transform Computations" discusses a very important and often overlooked aspect of quantum computing, namely a fair and detailed comparison of a quantum algorithm, its classical simulation, and its classical counterpart taking into account the complexity of I/O. Such an article is valuable and worth publishing. The current manuscript, however, still contains some inaccuracies that should be fixed and I will make suggestion on how the presentation can be improved.Let me first summarize the main result in my own words: a quantum Fourier transform (QFT) can calculate the Fourier transform of a vector with time complexity \(O\left(\log^2N\right)\), compared to the complexity \(O\left(N\log N\right)\) of a classical FFT. However, if one needs to read out the full vector instead, the complexity becomes \(O\left(N \text{ polylog}(N) \right)\) again, without an advantage over the classical algorithm. It is actually worse than the author discusses, if one also takes into account the complexity of loading the initial state. Loading an initial classical data vector has complexity \(O\left(N\right)\), and this has to be repeated at every repetition, giving a complexity of \(O\left(N^2\ \text{polylog}\ N\right)\), worse than classical. As the author correctly mentions, the QFT is thus a useful algorithm if the input data is prepared algorithmically, and limited sampling of the result vector is sufficient, as is the case for Shor's algorithm.This is a valuable observation that deserves a paper in CiSE, since these important considerations are not all known to people outside the quantum computing community, and are sometimes ignored even by quantum computing specialists. I thus want to encourage the author to improve the presentation to make it more accessible to a broader audience and fix a couple of technical flaws.Before discussing presentation issues, I want to address one technical flaw and a few points where more clarity is needed: This statement towards the end is too simplistic and needs to be clarified: "... if we want to measure each coefficient, we must redo our operations for each coefficient (since our wave function will collapse for every measurement)." The manuscript does not explain how to read out a specific coefficient. If one samples the wave function, one measures the result and gets a certain value \((s_1, \cdots,\ s_N)\) with a probability depending on the wave function. More complex amplitude-estimation algorithms are needed to read out specific coefficients, which then takes time \(O(N/\epsilon)\). This needs to be better explained. This also raises another issue of normalization and precision. The quantum wave function has to be normalized to have an \(L_2\) norm of \(1\). We thus need to measure to a precision of epsilon divided by the \(L_2\) norm of the classical data, and if that increases with \(N\) the scaling is even worse. For example, if all entries are of order unity, the \(L_2\) norm is \(\sqrt{N}\). The one technical flaw in the paper is in preparing the input state to the QFT, and the complexity of the classical simulation of the quantum algorithm. There, the numbers are wrong. The classical complexity can easily be estimated by realizing that any sparse quantum gate (such as a 1-qubit or 1-qubit gate) can be simulated in time \(O(N)=O(2^n)\), where \(N=2^n\). Thus, the overhead is just \(O(N)\), not \(O(N^2)\), and the simulation complexity is just \(O(N)\) times the complexity of the quantum algorithm. This will be more apparent if, as I propose below, the author shows the quantum algorithm also through a sequence of quantum gates. However, note that in the simulation we then have the full vector, and thus do not incur the overhead of quantum state tomography. We need to simulate the algorithm only once and not \(O(N/\epsilon)\) times. This means the simulation remains at \(O(N\ \log^2{N})\) even if we read out all entries, which is not bad compared to the classical \(O(N\ \log{N})\) of the FFT. The reason why the author seems to end with a different complexity is that his Matlab simulation does not simulate the quantum algorithm but the computation of the effect of the QFT applied to just one basis state. That is a suboptimal implementation. I thus propose to replace the Matlab code by a discussion of how a quantum gate (Hadamard or controlled phase rotation) can be implemented, and that will then nicely give the scaling discussed above.As mentioned in my summary at the beginning, the value of the paper can be increased if the author could also discuss the complexity of quantum state preparation from classical input data, e.g., following Shende-Bullock-Markov \citep{markov2006}, which has a complexity of \(O\left(N\ \log\ \frac{1}{\epsilon}\right)\). That means, that if the data is read from a classical vector (and not computed as, e.g., in Shor's algorithm), then the complexity of state preparation of \(O\left(N\ \log\ \frac{1}{\epsilon}\right)\) completely dominates the QFT itself, and if one furthermore wants to read out the full vector instead of sampling it, the complexity becomes \(O\left(N^2\log^2\left(\frac{1}{\epsilon}\right)\right)\).In the conclusion the author writes that "QEC research is still in very early development and it is currently difficult to determine how the required resources for these corrections could scale with qubit usage." That is incorrect, as the overhead is pretty well known by now for certain QEC codes, such as the surface code. The asymptotic scaling of the overhead has long been known, and also detailed resource costs have been worked out for various algorithms. I suggest to focus the QEC section on the need for fault tolerance, and the large overhead associated with it. This is definitely not something that can be done on NISQ devices at an interesting scale. I would also use another reference for QEC than the Gil Kalai paper.Now, to suggestions for improved presentation:In the abstract, I suggest to present fewer technical details. "radix-2 DIT case of the Cooley-Tukey Algorithm" can just be called Fast Fourier transform, the QUBIT4MATLAB package does not need to be mentioned in the abstract, and neither does the "Master Theorem" have to be mentioned.In the abstract and in the rest of the paper, it is also better to talk about quantum speedup and not quantum supremacy. The paper is about asymptotic scaling (the author uses the big-O notation throughout), and not about supremacy, which is a specific size problem that is solved better on quantum hardware rather than classical hardware. A supremacy claim needs all constants to be worked out, and assumptions for the specific classical and quantum hardware. Replacing quantum supremacy by quantum speedup can fix this. The observations are still valuable and correct.The first section is called "The shortcomings of classical computing and the early developments of quantum computing". That title sounds strange to me. What are the shortcomings? The author may rather want to stress the additional capabilities of quantum computers. Given that most readers will not be physicists and have no experience with quantum mechanics, it would be valuable to expand this first section. Discuss equation (3) before equation (1), and then introduce equation (1), to show that this means that the state of a qubit is actually a two-dimensional complex vector, After that only go to the many-quit state. After equation 4 it may be good to talk about amplitudes first, and then probabilities. Saying that the state is determined by "the qubit simply has a probability...", ignores the all important phases that are the crucial difference between quantum computing and probabilistic classical computing. "Quantum gates, unlike classical gates, do not delete information and are fully reversible." Needs further explanation. This comes from the reversibility of the microscopic laws of physics. Here it may be worthwhile to mention that, as quantum gates are time evolution of a quantum system, they are unitary operators on the Hilbert space that was introduced above. The discussion in the next sentence about them not using energy is misleading as well. In fact, the control and operation of the quantum gate always needs energy. It is only the free evolution of a quantum system that conserves energy. The part on " subatomic systems such as a superposition of quantum states. " would also need more explanation. Does the author here want to describe specific implementations of qubits? If so, more detail is needed. If not, I propose to drop this part."The definition and use of the classical discrete Fourier transform": here is an abrupt jump from Shor's algorithm to the DFT. Since Shor's algorithm again gets mentioned later on as a case where the QFT is better than a classical DFT, it make sense to discuss more details of Shor's algorithm, and that in essence it solvers the factor problem by using a QFT to find the period of a function. In light of the above complexity discussion this is important: we don't deal with classical data that one has to load but with a state that is computed (the function f(x) = a^x mod N ), and one is not interested in the full vector but just in finding the period. This can be done just by measuring the result of the QFT, which in this particular case will return a random multiple of the base frequency, and with a few repeated measurements one can then extract the period).The Fourier transform should be well known to the reader, and it is thus not obvious to me that equation 6 is needed. I would instead introduce \omega in equation 5. For the discussion of the implementation I suggest to mention that the rest of the paper limits itself to the case of powers of 2, i.e. N=2^n, for which the radix-2 version applies. Since the implementation is well known for most computational scientists, it could be moved from to supplementary material, as can be the derivation of the O(N log N) complexity, which is also well known.In the discussion of the QFT, unfortunately the quantum algorithm is not presented. What is presented is the mathematical unitary operation. It would be very valuable for the reader to see an actual implementation of the quantum algorithm, i.e. the sequence of O(n^2) Hadamard gates and controlled rotations – either as a circuit drawing, or more useful as quantum code, either using a quantum programming language that allows loops (such as Q#), or as some quantum pseudo code with loops. Then the reader will see the sequence of O(n^2) operations and how it creates the unitary operation of the QFT."The implementation of the QFT in MATLAB...". This section can be improved as well., As discussed above, the Matlab code does not implement the quantum algorithm but rather implements the application of the unitary operation to one of the basis states. It would be more useful for the reader to instead get implementations of the Hadamard and controlled phase gates, which could then be combined with the above quantum algorithm (maybe all in Matlab even?) for a full simulation of the algorithm – and in time O(N n^2), not O(N^2 n^2)."Evaluating the complexity of the QFT Implementation" – I discussed the issues with the complexity estimates already above. If one replaces it by an estimate of the complexity of simulating the H and controlled phase gate each in O(N) operations then it both becomes simpler and the complexity becomes just O(N) times that of the quantum version"Evaluating the complexity of the theoretical form of the QFT Implementation”. I assume that by "theoretical" the author means the actual quantum operation? The comparison section needs to be fixed, since that's where there is the mentioned flaw based on the suboptimal Matlab code, and that will also change table 1. I suggest that table 1 could have three cases: A) ignoring state preparation and one only wants to sample the output a constant number of times; B) ignoring state preparation but one wants to read the full vector; C) including state preparation from classical data and one only wants to sample the output a constant number of times; D) including state preparation from classical data and one wants to read the full vectorThe reader will then see that only case A has a speedup, and that in the other cases even the simulation of the quantum algorithm is faster than the quantum algorithm on a quantum computer.The conclusions should then be updated, taking these slightly modified comparisons into account. The case of Shor's algorithm, which falls into category A) above, is indeed interesting but deserves a deeper explanation so that the reader understands that Shor's algorithm can compute the input with complexity \(O\left(N^3\right)\) (up to log factors), and why only a few samples of the output are needed. That way, the exponential speedup over the FFT remains, and the super polynomial speedup over the name sieve. However, if classical data has to be loaded or should be returned then there is no speedup. I call this the I/O problem of quantum algorithms, which indeed—as the author writes—means that in these cases quantum computing is no better than classical computing.This is an important observation that the paper beautifully works out. Fixing the flaw in the simulation section and improving the presentation will make this a very nice paper.

DOI
10.22541/au.159795474.47457948

Related papers

A Comparison of Quantum and Traditional Fourier Transform Computations

Damian Musk

The quantum Fourier transform (QFT) can calculate the Fourier transform of a vector of size $N$N with time complexity $\mathcal {O}(\log ^2~N)$O(log2N) as compared to the classical complexity of $\mathcal {O}(N \;\log N)$O(NlogN). However, if one wanted to measure the full output state, then the QFT complexity becomes $\mathcal {O}(N \;\log ^2~N)$O(Nlog2N), thus losing its apparent advantage, indicating that the advantage is fully exploited for algorithms when only a limited number of samples is required from the output vector, as is the case in many quantum algorithms. Moreover, the computational complexity worsens if one considers the complexity of constructing the initial state. In this article, this issue is better illustrated by providing a concrete implementation of these algorithms and discussing their complexities as well as the complexity of the simulation of the QFT in matlab.

Computing in Science & Engineering•Sep 15, 2020•22 citations

A review on quantum Fourier transform

Tomás Barros, Pablo Álvarez, Bárbara Vidal +1 more

This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.

Quantum Information Processing•Jan 27, 2026•2 citations

Quantum supremacy: some fundamental concepts

Man‐Hong Yung

Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!

National Science Review•Jul 4, 2018•22 citations

The quantum FFT can be classically simulated

Dorit Aharonov, Zeph A. Landau, Johann A. Makowsky

In this note we describe a simple and intriguing observation: the quantum Fourier transform (QFT) over $Z_q$, which is considered the most ``quantum'' part of Shor's algorithm, can in fact be simulated efficiently by classical computers. More precisely, we observe that the QFT can be performed by a circuit of poly-logarithmic path-width, if the circuit is allowed to apply not only unitary gates but also general linear gates. Recalling the results of Markov and Shi [MaSh] and Jozsa [Jo] which provided classical simulations of such circuits in time exponential in the tree-width, this implies the result stated in the title. Classical simulations of the FFT are of course meaningless when applied to classical input strings on which their result is already known; Our observation might be interesting only in the context in which the QFT is used as a subroutine and applied to more interesting superpositions. We discuss the reasons why this idea seems to fail to provide an efficient classical simulation of the entire factoring algorithm. In the course of proving our observation, we provide two alternative proofs of the results of [MaSh,Jo] which we use. One proof is very similar in spirit to that of [MaSh] but is more visual, and is based on a graph parameter which we call the ``bubble width'', tightly related to the path- and tree-width. The other proof is based on connections to the Jones polynomial; It is very short, if one is willing to rely on several known results.

arXiv:quant-ph/0611156•Nov 14, 2006•42 citations

News

The fast Fourier transform (FFT) is the unsung digital workhorse of modern life.It's a clever mathematical shortcut that makes possible the many signals in our device-connected world.Every minute of every video stream, for instance, entails computing some hundreds of FFTs.The FFT's importance to practically every data-processing application in the digital age explains why some researchers have begun exploring how quantum computing can run the FFT algorithm more efficiently still."The fast Fourier transform is an important algorithm that's had lots of applications in the classical world," says Ian Walmsley, physicist at Imperial College London."It also has many applications in the quantum domain.[So] it's important to figure out effective ways to be able to implement it."The first proposed killer app for quantum computers-finding a number's prime factors-was discovered by mathematician Peter Shor at AT&T Bell Laboratories in 1994.Shor's algorithm scales up its factorization of numbers more efficiently and rapidly than any classical computer anyone could ever design.And at the heart of Shor's phenomenal quantum engine is a subroutine called-you guessed it-the quantum Fourier transform (QFT).Here is where the terminology gets a little out of hand.There is the QFT at the center of Shor's algorithm, and then there is the QFFT-the quantum fast Fourier transform.They represent different calculations that produce different results, although both are based on the same core mathematical concept, known as the discrete Fourier transform.

IEEE Spectrum•Dec 30, 2020•0 citations

THEORETICAL FRAMEWORK AND ALGORITHMIC IMPLEMENTATION OF THE QUANTUM FOURIER TRANSFORM AND PHASE ESTIMATION

Medak Srinivas

The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.

Iterative International Publishers eBooks•May 1, 2026•0 citations
The manuscript "A Comparison of Quantum and Traditional Fourier Transform Computations" discusses a very important and often overlooked aspect of quantum computing, namely a fair and detailed comparison of a quantum algorithm, its classical simulation, and its classical counterpart taking into account the complexity of I/O. Such an article is valuable and worth publishing. The current manuscript, however, still contains some inaccuracies that should be fixed and I will make suggestion on how the presentation can be improved.Let me first summarize the main result in my own words: a quantum Fourier transform (QFT) can calculate the Fourier transform of a vector with time complexity (O\left(\log^2N\right)), compared to the complexity (O\left(N\log N\right)) of a classical FFT. However, if one needs to read out the full vector instead, the complexity becomes (O\left(N \text{ polylog}(N) \right)) again, without an advantage over the classical algorithm. It is actually worse than the author discusses, if one also takes into account the complexity of loading the initial state. Loading an initial classical data vector has complexity (O\left(N\right)), and this has to be repeated at every repetition, giving a complexity of (O\left(N^2\ \text{polylog}\ N\right)), worse than classical. As the author correctly mentions, the QFT is thus a useful algorithm if the input data is prepared algorithmically, and limited sampling of the result vector is sufficient, as is the case for Shor's algorithm.This is a valuable observation that deserves a paper in CiSE, since these important considerations are not all known to people outside the quantum computing community, and are sometimes ignored even by quantum computing specialists. I thus want to encourage the author to improve the presentation to make it more accessible to a broader audience and fix a couple of technical flaws.Before discussing presentation issues, I want to address one technical flaw and a few points where more clarity is needed: This statement towards the end is too simplistic and needs to be clarified: "... if we want to measure each coefficient, we must redo our operations for each coefficient (since our wave function will collapse for every measurement)." The manuscript does not explain how to read out a specific coefficient. If one samples the wave function, one measures the result and gets a certain value ((s_1, \cdots,\ s_N)) with a probability depending on the wave function. More complex amplitude-estimation algorithms are needed to read out specific coefficients, which then takes time (O(N/\epsilon)). This needs to be better explained. This also raises another issue of normalization and precision. The quantum wave function has to be normalized to have an (L_2) norm of (1). We thus need to measure to a precision of epsilon divided by the (L_2) norm of the classical data, and if that increases with (N) the scaling is even worse. For example, if all entries are of order unity, the (L_2) norm is (\sqrt{N}). The one technical flaw in the paper is in preparing the input state to the QFT, and the complexity of the classical simulation of the quantum algorithm. There, the numbers are wrong. The classical complexity can easily be estimated by realizing that any sparse quantum gate (such as a 1-qubit or 1-qubit gate) can be simulated in time (O(N)=O(2^n)), where (N=2^n). Thus, the overhead is just (O(N)), not (O(N^2)), and the simulation complexity is just (O(N)) times the complexity of the quantum algorithm. This will be more apparent if, as I propose below, the author shows the quantum algorithm also through a sequence of quantum gates. However, note that in the simulation we then have the full vector, and thus do not incur the overhead of quantum state tomography. We need to simulate the algorithm only once and not (O(N/\epsilon)) times. This means the simulation remains at (O(N\ \log^2{N})) even if we read out all entries, which is not bad compared to the classical (O(N\ \log{N})) of the FFT. The reason why the author seems to end with a different complexity is that his Matlab simulation does not simulate the quantum algorithm but the computation of the effect of the QFT applied to just one basis state. That is a suboptimal implementation. I thus propose to replace the Matlab code by a discussion of how a quantum gate (Hadamard or controlled phase rotation) can be implemented, and that will then nicely give the scaling discussed above.As mentioned in my summary at the beginning, the value of the paper can be increased if the author could also discuss the complexity of quantum state preparation from classical input data, e.g., following Shende-Bullock-Markov \citep{markov2006}, which has a complexity of (O\left(N\ \log\ \frac{1}{\epsilon}\right)). That means, that if the data is read from a classical vector (and not computed as, e.g., in Shor's algorithm), then the complexity of state preparation of (O\left(N\ \log\ \frac{1}{\epsilon}\right)) completely dominates the QFT itself, and if one furthermore wants to read out the full vector instead of sampling it, the complexity becomes (O\left(N^2\log^2\left(\frac{1}{\epsilon}\right)\right)).In the conclusion the author writes that "QEC research is still in very early development and it is currently difficult to determine how the required resources for these corrections could scale with qubit usage." That is incorrect, as the overhead is pretty well known by now for certain QEC codes, such as the surface code. The asymptotic scaling of the overhead has long been known, and also detailed resource costs have been worked out for various algorithms. I suggest to focus the QEC section on the need for fault tolerance, and the large overhead associated with it. This is definitely not something that can be done on NISQ devices at an interesting scale. I would also use another reference for QEC than the Gil Kalai paper.Now, to suggestions for improved presentation:In the abstract, I suggest to present fewer technical details. "radix-2 DIT case of the Cooley-Tukey Algorithm" can just be called Fast Fourier transform, the QUBIT4MATLAB package does not need to be mentioned in the abstract, and neither does the "Master Theorem" have to be mentioned.In the abstract and in the rest of the paper, it is also better to talk about quantum speedup and not quantum supremacy. The paper is about asymptotic scaling (the author uses the big-O notation throughout), and not about supremacy, which is a specific size problem that is solved better on quantum hardware rather than classical hardware. A supremacy claim needs all constants to be worked out, and assumptions for the specific classical and quantum hardware. Replacing quantum supremacy by quantum speedup can fix this. The observations are still valuable and correct.The first section is called "The shortcomings of classical computing and the early developments of quantum computing". That title sounds strange to me. What are the shortcomings? The author may rather want to stress the additional capabilities of quantum computers. Given that most readers will not be physicists and have no experience with quantum mechanics, it would be valuable to expand this first section. Discuss equation (3) before equation (1), and then introduce equation (1), to show that this means that the state of a qubit is actually a two-dimensional complex vector, After that only go to the many-quit state. After equation 4 it may be good to talk about amplitudes first, and then probabilities. Saying that the state is determined by "the qubit simply has a probability...", ignores the all important phases that are the crucial difference between quantum computing and probabilistic classical computing. "Quantum gates, unlike classical gates, do not delete information and are fully reversible." Needs further explanation. This comes from the reversibility of the microscopic laws of physics. Here it may be worthwhile to mention that, as quantum gates are time evolution of a quantum system, they are unitary operators on the Hilbert space that was introduced above. The discussion in the next sentence about them not using energy is misleading as well. In fact, the control and operation of the quantum gate always needs energy. It is only the free evolution of a quantum system that conserves energy. The part on " subatomic systems such as a superposition of quantum states. " would also need more explanation. Does the author here want to describe specific implementations of qubits? If so, more detail is needed. If not, I propose to drop this part."The definition and use of the classical discrete Fourier transform": here is an abrupt jump from Shor's algorithm to the DFT. Since Shor's algorithm again gets mentioned later on as a case where the QFT is better than a classical DFT, it make sense to discuss more details of Shor's algorithm, and that in essence it solvers the factor problem by using a QFT to find the period of a function. In light of the above complexity discussion this is important: we don't deal with classical data that one has to load but with a state that is computed (the function f(x) = a^x mod N ), and one is not interested in the full vector but just in finding the period. This can be done just by measuring the result of the QFT, which in this particular case will return a random multiple of the base frequency, and with a few repeated measurements one can then extract the period).The Fourier transform should be well known to the reader, and it is thus not obvious to me that equation 6 is needed. I would instead introduce \omega in equation 5. For the discussion of the implementation I suggest to mention that the rest of the paper limits itself to the case of powers of 2, i.e. N=2^n, for which the radix-2 version applies. Since the implementation is well known for most computational scientists, it could be moved from to supplementary material, as can be the derivation of the O(N log N) complexity, which is also well known.In the discussion of the QFT, unfortunately the quantum algorithm is not presented. What is presented is the mathematical unitary operation. It would be very valuable for the reader to see an actual implementation of the quantum algorithm, i.e. the sequence of O(n^2) Hadamard gates and controlled rotations – either as a circuit drawing, or more useful as quantum code, either using a quantum programming language that allows loops (such as Q#), or as some quantum pseudo code with loops. Then the reader will see the sequence of O(n^2) operations and how it creates the unitary operation of the QFT."The implementation of the QFT in MATLAB...". This section can be improved as well., As discussed above, the Matlab code does not implement the quantum algorithm but rather implements the application of the unitary operation to one of the basis states. It would be more useful for the reader to instead get implementations of the Hadamard and controlled phase gates, which could then be combined with the above quantum algorithm (maybe all in Matlab even?) for a full simulation of the algorithm – and in time O(N n^2), not O(N^2 n^2)."Evaluating the complexity of the QFT Implementation" – I discussed the issues with the complexity estimates already above. If one replaces it by an estimate of the complexity of simulating the H and controlled phase gate each in O(N) operations then it both becomes simpler and the complexity becomes just O(N) times that of the quantum version"Evaluating the complexity of the theoretical form of the QFT Implementation”. I assume that by "theoretical" the author means the actual quantum operation? The comparison section needs to be fixed, since that's where there is the mentioned flaw based on the suboptimal Matlab code, and that will also change table 1. I suggest that table 1 could have three cases: A) ignoring state preparation and one only wants to sample the output a constant number of times; B) ignoring state preparation but one wants to read the full vector; C) including state preparation from classical data and one only wants to sample the output a constant number of times; D) including state preparation from classical data and one wants to read the full vectorThe reader will then see that only case A has a speedup, and that in the other cases even the simulation of the quantum algorithm is faster than the quantum algorithm on a quantum computer.The conclusions should then be updated, taking these slightly modified comparisons into account. The case of Shor's algorithm, which falls into category A) above, is indeed interesting but deserves a deeper explanation so that the reader understands that Shor's algorithm can compute the input with complexity (O\left(N^3\right)) (up to log factors), and why only a few samples of the output are needed. That way, the exponential speedup over the FFT remains, and the super polynomial speedup over the name sieve. However, if classical data has to be loaded or should be returned then there is no speedup. I call this the I/O problem of quantum algorithms, which indeed—as the author writes—means that in these cases quantum computing is no better than classical computing.This is an important observation that the paper beautifully works out. Fixing the flaw in the simulation section and improving the presentation will make this a very nice paper.
The quantum Fourier transform (QFT) can calculate the Fourier transform of a vector of size NNNN with time complexity O(log⁡2 N)\mathcal {O}(\log ^2~N)O(log2 N)O(log2N) as compared to the classical complexity of O(N  log⁡N)\mathcal {O}(N \;\log N)O(NlogN)O(NlogN). However, if one wanted to measure the full output state, then the QFT complexity becomes O(N  log⁡2 N)\mathcal {O}(N \;\log ^2~N)O(Nlog2 N)O(Nlog2N), thus losing its apparent advantage, indicating that the advantage is fully exploited for algorithms when only a limited number of samples is required from the output vector, as is the case in many quantum algorithms. Moreover, the computational complexity worsens if one considers the complexity of constructing the initial state. In this article, this issue is better illustrated by providing a concrete implementation of these algorithms and discussing their complexities as well as the complexity of the simulation of the QFT in matlab.
This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
In this note we describe a simple and intriguing observation: the quantum Fourier transform (QFT) over ZqZ_qZq​, which is considered the most ``quantum'' part of Shor's algorithm, can in fact be simulated efficiently by classical computers. More precisely, we observe that the QFT can be performed by a circuit of poly-logarithmic path-width, if the circuit is allowed to apply not only unitary gates but also general linear gates. Recalling the results of Markov and Shi [MaSh] and Jozsa [Jo] which provided classical simulations of such circuits in time exponential in the tree-width, this implies the result stated in the title. Classical simulations of the FFT are of course meaningless when applied to classical input strings on which their result is already known; Our observation might be interesting only in the context in which the QFT is used as a subroutine and applied to more interesting superpositions. We discuss the reasons why this idea seems to fail to provide an efficient classical simulation of the entire factoring algorithm. In the course of proving our observation, we provide two alternative proofs of the results of [MaSh,Jo] which we use. One proof is very similar in spirit to that of [MaSh] but is more visual, and is based on a graph parameter which we call the ``bubble width'', tightly related to the path- and tree-width. The other proof is based on connections to the Jones polynomial; It is very short, if one is willing to rely on several known results.
The fast Fourier transform (FFT) is the unsung digital workhorse of modern life.It's a clever mathematical shortcut that makes possible the many signals in our device-connected world.Every minute of every video stream, for instance, entails computing some hundreds of FFTs.The FFT's importance to practically every data-processing application in the digital age explains why some researchers have begun exploring how quantum computing can run the FFT algorithm more efficiently still."The fast Fourier transform is an important algorithm that's had lots of applications in the classical world," says Ian Walmsley, physicist at Imperial College London."It also has many applications in the quantum domain.[So] it's important to figure out effective ways to be able to implement it."The first proposed killer app for quantum computers-finding a number's prime factors-was discovered by mathematician Peter Shor at AT&T Bell Laboratories in 1994.Shor's algorithm scales up its factorization of numbers more efficiently and rapidly than any classical computer anyone could ever design.And at the heart of Shor's phenomenal quantum engine is a subroutine called-you guessed it-the quantum Fourier transform (QFT).Here is where the terminology gets a little out of hand.There is the QFT at the center of Shor's algorithm, and then there is the QFFT-the quantum fast Fourier transform.They represent different calculations that produce different results, although both are based on the same core mathematical concept, known as the discrete Fourier transform.
The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.