An approximate Fourier transform useful in quantum factoring
read the original abstract
We define an approximate version of the Fourier transform on $2^L$ elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)
This paper has not been read by Pith yet.
Forward citations
Cited by 19 Pith papers
-
Per-Phase Fidelity Attribution for Quantum Compilers using HBR Decomposition
HBR decomposition quantifies per-phase fidelity loss in quantum compilers, revealing that routing causes up to 60% loss in search circuits while synthesis dominates Hamiltonian simulation, and correctly predicts SDK r...
-
Pixel-Translation-Equivariant Quantum Convolutional Neural Networks via Fourier Multiplexers
QCNN layers equivariant under pixel cyclic shifts are exactly characterized as Fourier-mode multiplexers after QFT, enabling a deep network with constant expected gradient norm at initialization.
-
Accelerating Inference for Multilayer Neural Networks with Quantum Computers
Quantum circuits for coherent multilayer neural network inference achieve quadratic to polylogarithmic speedups over classical methods depending on quantum data access models for inputs and weights.
-
QnRL: Quantum-Native Reinforcement Learning
QnRL is a distributional quantum RL framework that distills conditional action policies from moments of quantum generative models in Hilbert space via the QuAK algorithm, reporting higher scores and fewer parameters t...
-
ATHENA: A Compiler For Optimized Scheduling In Distributed Quantum Computers
ATHENA compiler uses UMS lookahead and EES early scheduling to reduce teleportations by 34% and latency by 2x on average versus prior block-based approaches in distributed quantum computers.
-
$\mathcal{O}(n)$ alternative to Quantum Fourier Transform with efficient neural net classical post-processing
HP-1 circuits achieve O(n) depth while preserving shift invariance and exponentially growing Fisher information, enabling numerical replacement of the QFT in Shor's algorithm with neural net classical post-processing.
-
Communication-Efficient Distributed Inverse Quantum Fourier Transform
A pruned distributed inverse quantum Fourier transform reduces inter-node communication from quadratic to linear scaling in the number of nodes while preserving functional correctness.
-
The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm
Shor's algorithm generates and consumes magic resources in direct proportion to the difficulty of the underlying factoring problem.
-
Synthesis of discrete-continuous quantum circuits with multimodal diffusion models
Multimodal diffusion model generates discrete gate selections and continuous parameters for quantum circuit compilation, claiming better gate counts and noise resilience than prior methods.
-
Unveiling Energetic Advantage in Superconducting Cat-Qubits Quantum Computation
Energy modeling and parameter optimization for cat-qubit superconducting quantum computers performing semiclassical QFT with error correction indicates an energetic advantage over classical systems for more than 26 qu...
-
When Noisy Quantum Order Finding Remains Recoverable for Shor's Algorithm
Empirical study of real NISQ order-finding data identifies dominant verified mass fraction as the strongest predictor of whether standard post-processing recovers the true order.
-
Toward Secure Multitenant Quantum Computing: Circuit Affinity, Crosstalk Patterns, and Grouping Strategies
Crosstalk patterns between quantum circuits on IBM processors are predictable by circuit type and hardware architecture, with high intra-revision consistency and topological decoupling between lattice types.
-
Phase-Fidelity-Aware Truncated Quantum Fourier Transform for Scalable Phase Estimation on NISQ Hardware
A hardware-calibrated truncated QFT reduces gate count 31-44% at 30 qubits while bounding total variation distance error by O(2^{-d}) and outperforming full QFT under moderate noise.
-
Not Your Usual FFT: QFT$\rightarrow$FFT via Classical Quantum-Circuit Simulation
QFT→FFT computes DFT via classical QFT circuit simulation on qsim with AVX/CUDA backends, claiming parity or better performance than FFTW on CPU/GPU plus an approximate variant.
-
Towards an Optimally Distributed Quantum Fourier Transform Circuit
Presents an optimal gate-packing partitioning scheme for the QFT that aims to minimize e-bit count in distributed quantum systems and validates it on hardware.
-
Quantum iterative approach to the Traveling Salesman Problem
The paper outlines a quantum framework combining QPE and Grover-style amplification for TSP, demonstrates it on a small instance, and gives an expected complexity scaling with error tolerance epsilon.
-
Large-Scale Quantum Circuit Simulation on HPC Cluster via Cache Blocking, Boosting, and Gate Fusion Optimization
New merge booster and diagonal detector components, combined with cache blocking and gate fusion, deliver up to 160x speedup on circuit benchmarks and 34x on diagonal-heavy gates versus prior simulators.
-
Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
Review of quantum neural networks on gate-based quantum computers for molecular property prediction and generation in drug discovery.
-
Basic Quantum Algorithms
A review providing detailed circuit-model descriptions of early quantum algorithms including Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon, Shor, Kitaev phase estimation, Grover, and HHL.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.