The Quantum Fourier Transform (QFT) uses $\mathcal {O}(n^{2})$ gates against the $\mathcal {O}(N\log N)$ operations of the Fast Fourier Transform, but this advantage is contingent on state preparation, readout, connectivity, decoherence, and on the classical algorithm chosen for comparison. We introduce the Quantum Fourier Advantage Index (QFAI), a task-, data- and reference-aware resource metric combining state preparation, task-dependent readout, native transpiled gate counts on real coupling maps, and a two-term calibrated noise model with relaxation. The QFAI is a conditional estimate of accessible advantage under stated input-access, task, reference-algorithm and stochastic-noise assumptions, not an intrinsic property of the QFT, and we separate asymptotic, resource-accounting and wall-clock advantage throughout. Across 9 datasets and 7 processors, the conventional dense-FFT reference yields broad windows on all-to-all hardware (peak QFAI 37.68, Quantinuum H2). Two findings qualify this. First, under a common synthetic noise convention and once SWAP-routing permutations are excluded from the measured infidelity, the gate-error amplification constant is modality-independent ( $\kappa _{g}=0.786$ , 0.778, 0.770); against per-qubit calibration snapshots of 4 real IBM processors it spans 0.349 to 0.769 and must be refitted per device. Second, replacing the dense FFT by the task-matched classical algorithm, a sublinear sparse FFT for dominant-mode extraction, reduces the peak to a near-break-even 0.17, whose sign reverses within a factor-of-two change of the unmeasured sparse-FFT constant; we prove this ratio is bounded by a constant, so no asymptotic separation exists, and we propagate fit, calibration and reference uncertainties into explicit bands. A 6G OFDM channel-estimation case study, an end-to-end model of the quantum processing pipeline rather than a measured receiver, shows the framework as a design tool: the quantum route recovers delay taps with precision up to 1.00 yet misses the $\mathrm {125.00~\mu \text {s} }$ slot deadline by five to eleven orders of magnitude, with the per-shot cost of state loading, reset and readout, not gate fidelity, the binding constraint, while a measured single-core dense FFT meets it at $N\le 4096$ . All results are simulation-based, with stated evidence tiers and a released hardware-validation campaign.
The Quantum Fourier Transform (QFT) uses O(n2) gates against the O(NlogN) operations of the Fast Fourier Transform, but this advantage is contingent on state preparation, readout, connectivity, decoherence, and on the classical algorithm chosen for comparison. We introduce the Quantum Fourier Advantage Index (QFAI), a task-, data- and reference-aware resource metric combining state preparation, task-dependent readout, native transpiled gate counts on real coupling maps, and a two-term calibrated noise model with relaxation. The QFAI is a conditional estimate of accessible advantage under stated input-access, task, reference-algorithm and stochastic-noise assumptions, not an intrinsic property of the QFT, and we separate asymptotic, resource-accounting and wall-clock advantage throughout. Across 9 datasets and 7 processors, the conventional dense-FFT reference yields broad windows on all-to-all hardware (peak QFAI 37.68, Quantinuum H2). Two findings qualify this. First, under a common synthetic noise convention and once SWAP-routing permutations are excluded from the measured infidelity, the gate-error amplification constant is modality-independent ( κg=0.786 , 0.778, 0.770); against per-qubit calibration snapshots of 4 real IBM processors it spans 0.349 to 0.769 and must be refitted per device. Second, replacing the dense FFT by the task-matched classical algorithm, a sublinear sparse FFT for dominant-mode extraction, reduces the peak to a near-break-even 0.17, whose sign reverses within a factor-of-two change of the unmeasured sparse-FFT constant; we prove this ratio is bounded by a constant, so no asymptotic separation exists, and we propagate fit, calibration and reference uncertainties into explicit bands. A 6G OFDM channel-estimation case study, an end-to-end model of the quantum processing pipeline rather than a measured receiver, shows the framework as a design tool: the quantum route recovers delay taps with precision up to 1.00 yet misses the 125.00μs slot deadline by five to eleven orders of magnitude, with the per-shot cost of state loading, reset and readout, not gate fidelity, the binding constraint, while a measured single-core dense FFT meets it at N≤4096 . All results are simulation-based, with stated evidence tiers and a released hardware-validation campaign.
Across public tabular benchmarks, quantum machine-learning (QML) models usually lose to carefully tuned classical baselines. We argue that this is a structural property of the datasets rather than merely a limitation of current models. Because an angle-encoded quantum neural network is a partial Fourier series, a genuine advantage can arise only when the target spectrum is simultaneously off-grid, of interaction order at least three, high-frequency, supported by near-independent features, and dense beyond practical enumeration. We call the failure to satisfy these conditions the Fourier wall. We operationalize the conditions as SPECTRA, a two-tier certificate: a simulator-free structural screen followed by a decisive comparison between a matched quantum model and five tuned classical twins using paired-bootstrap confidence bounds. On industrial smart-meter data, SPECTRA correctly refuses the real peak-load target, for which gradient-boosted trees reach a held-out ROC-AUC of 0.999. On the same real energy phases with labels generated by an interacting quantum process, the dynamics-matched quantum model reaches 0.994 versus 0.699 for the best generic classical baseline, and collapses to chance when its interaction couplings are ablated. An exact classical simulator ties the quantum model at small width but incurs measured exponential evaluation cost, with an estimated hardware crossover near 13-19 sites. These results provide a practical recipe for identifying, engineering, and deploying quantum-advantage candidates in tabular data.
The Quantum Pi Benchmark (QPB) is a family of verification, search, counting, frequency-estimation, and collision tasks over the digits of Pi. It is designed as an architecture-neutral specification of mathematically fixed instances, classical comparators, resource boundaries, and admissible claims. The specification fixes zero-based indexing, binary and hexadecimal digit conventions, dense and sparse candidate domains, and task-specific payloads for target-bearing and collision problems. It separates three independent properties that benchmark descriptions can conflate: digit access (lookup or direct), oracle-construction provenance (P0–P4), and controller blindness (B0 or B1). A non-total capability grid retains codes R0–R12 as stable claim labels while stating their named dependencies; a higher-numbered code does not automatically inherit every lower-numbered capability. The evidence protocol requires pre-execution validation, routed-resource accounting, preservation of raw outcomes, outcome-independent eligibility, visible conditioning, uncertainty estimates, protocol separation, and formal record freezing. Collision scaling is stated as a heuristic candidate-domain model: birthday behavior gives D_h = Θ(16^(h/2)), while element distinctness gives O(D_h^(2/3)) coherent queries only under declared access and memory assumptions. These query bounds do not establish the earliest repeat, a quantum frontier, or end-to-end advantage. Frontier status depends on a current classical post-hoc resource audit; advantage requires a predeclared matched cost comparison that includes preparation, oracle construction, error correction, sampling, readout, and verification. The resulting framework classifies future Pi-derived experiments without importing device-specific performance into the foundational definition.
Learning problems involving quantum data are natural candidates for demonstrating an advantage in quantum machine learning. Recent results indicate that, for certain tasks and under noiseless conditions, coherent processing of quantum data outperforms fixed-measurement schemes followed by classical processing. It remained uncertain whether this performance gap persists at a finite scale, and in the presence of noise that is unavoidable with current quantum devices. In this work, we present simulations and analysis of the performance of existing hardware on a learning problem known to exhibit asymptotic advantage, now subjected to noisy quantum data. Comparing coherent quantum processing directly against fixed-measurement schemes, our results demonstrate a clear performance separation at a scale of just 30 to 40 noisy qubits. Already at this scale, the fundamental bottleneck is no longer classical computation but data acquisition; matching the noisy coherent protocol with measure-first strategies would still require months or even years of measurements. By systematically evaluating hardware constraints such as state preparation, gate errors, readout errors, connectivity, and coherence times, we provide evidence that a demonstration of such a strong learning advantage is accessible on near-term devices.
Quantum Fourier sampling may help audit the spectral learnability of delay-based physical unclonable functions (PUFs). We ask whether that promise survives access matching, a strong classical comparator, and oracle synthesis. Three gates structure the evaluation. Structure: low degree is not small support at reachable challenge lengths; for 4-XOR at n=14, degree ≤df(0.1) admits 91% of all 2n characters and the median 90%-mass set spans a third of the spectrum. Algorithmics: constructing the phase oracle logically implies classical membership access, making Kushilevitz--Mansour the correct baseline; across 45 tasks it exhausts each finite domain, and no 4-XOR ideal-sampling case reaches 90% mass within 2n calls. A quantum-kernel diagnostic appears more favorable, with geometric difference rising to 2.151 at N=512 challenges, but it correlates 0.991 with 1/λmin(KC) for the classical Gram matrix KC, and the 4-XOR label-complexity ratio does not exceed a balance-preserving permutation null (p=0.930). Trace-normalized geometric difference can therefore grow through classical ill-conditioning alone, without task-label alignment. Implementation: a simulator-validated fixed-point phase oracle based on the quantum Fourier transform admits an 18.9% routed-depth reduction, yet the least certified precisions have estimated durations of 1.18--1.55× the median dephasing time T2 of the mapped qubits on a static backend snapshot, without hardware execution. We find no end-to-end advantage in the evaluated regime, although ideal sampling does use fewer coherent calls on the thresholded task. The contribution is the Three-Gate Quantum Audit Protocol: a reproducible procedure separating an ideal query advantage from a realizable security benefit. This is not a claim about deployed silicon and not an impossibility result.
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(log2N), compared to the complexity O(NlogN) of a classical FFT. However, if one needs to read out the full vector instead, the complexity becomes O(N polylog(N)) 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(N), and this has to be repeated at every repetition, giving a complexity of O(N2polylogN), 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 (s1,⋯,sN) 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/ϵ). 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 L2 norm of 1. We thus need to measure to a precision of epsilon divided by the L2 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 L2 norm is 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(2n), where N=2n. Thus, the overhead is just O(N), not O(N2), 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/ϵ) times. This means the simulation remains at O(Nlog2N) even if we read out all entries, which is not bad compared to the classical O(NlogN) 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(Nlogϵ1). 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(Nlogϵ1) completely dominates the QFT itself, and if one furthermore wants to read out the full vector instead of sampling it, the complexity becomes O(N2log2(ϵ1)).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(N3) (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.
We present an analysis of quantum circuit fidelity across the full compilation stack, from high-level gate optimization through pulse-level control. We connect a C++ circuit optimizer to a per-gate Lindblad master-equation fidelity model whose decoherence channels are cross-validated against qiskit-dynamics and whose absolute predictions are benchmarked against execution on real hardware. Across a campaign of 4,452 experiment runs over 371 benchmark circuits, gate cancellation provides the dominant improvement (d=1.66, 72% of circuits improved), while circuit size and pulse duration are the strongest negative predictors of process fidelity (input gates r=−0.78; pulse duration r=−0.73, R2=0.53). A formal ablation study shows that pass ordering has no significant effect on two-qubit gate reduction (Kruskal--Wallis p=0.302). Comparing against Qiskit transpilation levels, we show that two-qubit gate count, not total gate count, is the hardware-relevant metric: our optimizer attains superior two-qubit reduction on structured circuits (87.8% on QFT, 100% on QAOA) whereas Qiskit's larger total-gate reduction is dominated by single-qubit (u3) consolidation. Finally, executing eight circuits on the IQM Resonance Garnet processor (8/8 jobs completed, job identifiers released) reveals that the model is a consistent upper bound: it preserves the relative difficulty ordering of circuits but overestimates absolute fidelity by a mean of 0.49, quantifying the error budget (crosstalk, leakage, readout) outside a T1/T2/depolarizing model. We release the framework, data, and scripts as open source.