An approximate Fourier transform useful in quantum factoring

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)

Cited by in corpus (106)

• Elementary gates for quantum computation
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum Algorithms Revisited
• Quantum computing with trapped ions
• Two-Bit Gates are Universal for Quantum Computation
• Dynamics of Loschmidt echoes and fidelity decay
• Information and Computation: Classical and Quantum Aspects
• Qudits and high-dimensional quantum computing
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum algorithms for algebraic problems
• Implementation of the Quantum Fourier Transform
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• Automated optimization of large quantum circuits with continuous parameters
• A Lambda Calculus for Quantum Computation
• How to perform the most accurate possible phase measurements
• Toward an architecture for quantum programming
• Application-Oriented Performance Benchmarks for Quantum Computing
• Qibo: a framework for quantum simulation with hardware acceleration
• Quantum Software Engineering: Landscapes and Horizons
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Quantum Computation
• Quantum Circuits with Unbounded Fan-out
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Experimental Implementation of the Quantum Baker's Map
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Classification with Quantum Machine Learning: A Survey
• Factoring in a Dissipative Quantum Computer
• A Deductive Verification Framework for Circuit-building Quantum Programs
• Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Quantum Simulation of Nuclear Inelastic Scattering
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Experimental simulation of quantum tunneling in small systems
• Quantum Computation Beyond the Circuit Model
• Quantum Computing: Lecture Notes
• Towards Quantum Computational Mechanics
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Tower: Data Structures in Quantum Superposition
• Implementation of group-covariant POVMs by orthogonal measurements
• Filter Functions for Quantum Processes under Correlated Noise
• On efficient quantum block encoding of pseudo-differential operators
• Extending the Variational Quantum Eigensolver to Finite Temperatures
• The Road to Quantum Artificial Intelligence
• Time-coded Spiking Fourier Transform in Neuromorphic Hardware
• Universal set of scalable dynamically corrected gates for quantum error correction with always-on qubit couplings
• Obtaining the Quantum Fourier Transform from the Classical FFT with QR Decomposition
• Qibolab: an open-source hybrid quantum operating system
• Quantum Simulation of Klein Gordon Equation and Observation of Klein Paradox in IBM Quantum Computer
• Towards Large-Scale Quantum Computation
• Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers -- How They Work, How They Fail, How to Test Them?
• Generalized Quantum Baker Maps as perturbations of a simple kernel
• Automated Generation of Shuttling Sequences for a Linear Segmented Ion Trap Quantum Computer
• Circuit for Shor's algorithm using 2n+3 qubits
• Quantum algorithms for matrix operations and linear systems of equations
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• On Quantum A/D and D/A Conversion
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
• Power of Uninitialized Qubits in Shallow Quantum Circuits
• An entangling-probe attack on Shor's algorithm for factorization
• Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition
• The geometry of quantum learning
• Shor's Factoring Algorithm and Modular Exponentiation Operators
• On computation with 'probabilities' modulo k
• A Universal Quantum Circuit Design for Periodical Functions
• Q# as a Quantum Algorithmic Language
• Realization of Shor's Algorithm at Room Temperature
• Quantum Computing and a Unified Approach to Fast Unitary Transforms
• Generic Quantum Fourier Transforms
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• How to Compile Some NAND Formula Evaluators
• Evaluating Three Levels of Quantum Metrics on Quantum-Inspire Hardware
• Quantum locally linear embedding for nonlinear dimensionality reduction
• Microfabrication techniques for trapped ion quantum information processing
• Quantum mean value approximator for hard integer value problems
• Automated Verification of Silq Quantum Programs using SMT Solvers
• Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
• ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
• Efficient Light Propagation Algorithm using Quantum Computers
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Cosine series quantum sampling method with applications in signal and image processing
• A quantum Johnson-Lindenstrauss lemma via unitary t-designs
• Classical Cryptosystems In A Quantum Setting
• Optimal Qubit Mapping Search for Encoding Classical Data into Matrix Product State Representation with Minimal Loss
• A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
• Simulations of Shor's Algorithm using Matrix Product States
• An integral version of Shor's factoring algorithm
• Generating Compilers for Qubit Mapping and Routing
• Composability of global phase invariant distance and its application to approximation error management
• State of practice: evaluating GPU performance of state vector and tensor network methods
• Quantum Compiling with Approximation of Multiplexors
• Quantum computing classical physics
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer
• Filter Function Formalism and Software Package to Compute Quantum Processes of Gate Sequences for Classical Non-Markovian Noise
• A quantum algorithm for Viterbi decoding of classical convolutional codes
• The limits of quantum circuit simulation with low precision arithmetic
• Low Rank Approximation in Simulations of Quantum Algorithms
• Realization of t-bit semiclassical quantum Fourier transform on IBM's quantum cloud computer
• Ptychographic estimation of pure multiqubit states in a quantum device
• Linear algebra and quantum algorithm
• Implementation of the quantum Fourier transform on a hybrid qubit-qutrit NMR quantum emulator
• On exact counting and quasi-quantum complexity
• An Optimum Algorithm for Quantum Search