Semiclassical Fourier Transform for Quantum Computation

Abstract

Shor's algorithms for factorization and discrete logarithms on a quantum computer employ Fourier transforms preceding a final measurement. It is shown that such a Fourier transform can be carried out in a semi-classical way in which a ``classical'' (macroscopic) signal resulting from the measurement of one bit (embodied in a two-state quantum system) is employed to determine the type of measurement carried out on the next bit, and so forth. In this way the two-bit gates in the Fourier transform can all be replaced by a smaller number of one-bit gates controlled by classical signals. Success in simplifying the Fourier transform suggests that it may be worthwhile looking for other ways of using semi-classical methods in quantum computing.

Latex 6 pages, two figures on one page in uuencoded Postscript

References in corpus (4)

• Elementary gates for quantum computation
• Two-Bit Gates are Universal for Quantum Computation
• Conditional Quantum Dynamics and Logic Gates
• Universality in Quantum Computation

Cited by in corpus (184)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Quantum sensing
• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Measurement-based quantum computation with cluster states
• Quantum Chemistry in the Age of Quantum Computing
• Quantum Algorithms Revisited
• Quantum computing with trapped ions
• Reliable Quantum Computers
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Entanglement-free Heisenberg-limited phase estimation
• Realization of a scalable Shor algorithm
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• A quantum information processor with trapped ions
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Rapid high-fidelity multiplexed readout of superconducting qubits
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
• Consistent Histories and Quantum Reasoning
• Optimal Quantum Measurements of Expectation Values of Observables
• Do we really understand quantum mechanics?
• How to perform the most accurate possible phase measurements
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Teleportation as a quantum computation
• Approximate Quantum Fourier Transform and Decoherence
• Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
• Quantum Computation in Quantum-Hall Systems
• Emerging quantum computing algorithms for quantum chemistry
• Choice of Consistent Family, and Quantum Incompatibility
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Quantum information and precision measurement
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Quantum dynamics as a physical resource
• Past quantum states
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Pretending to factor large numbers on a quantum computer
• Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements
• Quantum information and physics: some future directions
• Two qubit copying machine for economical quantum eavesdropping
• Basic circuit compilation techniques for an ion-trap quantum machine
• Parallelizing Quantum Circuits
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• Quantum limits on phase-preserving linear amplifiers
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Quantum Computation
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Decoherence Bounds on Quantum Computation with Trapped Ions
• Experimental Phase Estimation Enhanced By Machine Learning
• Quantum measurement of a mesoscopic spin ensemble
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Information theoretic treatment of tripartite systems and quantum channels
• Efficient Quantum Transforms
• Experimental optical phase measurement approaching the exact Heisenberg limit
• Mid-circuit measurements on a single species neutral alkali atom quantum processor
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• On the Role of Coherence in Shor's Algorithm
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• The fully entangled fraction as an inclusive measure of entanglement applications
• Robust Single-Shot Spin Measurement with 99.5% Fidelity in a Quantum Dot Array
• Quantum-enhanced magnetometry by phase estimation algorithms with a single artificial atom
• Quantum computation with phase drift errors
• Quantum computing applied to calculations of molecular energies: CH2 benchmark
• Quantum metrology with a transmon qutrit
• Calculating Unknown Eigenvalues with a Quantum Algorithm
• The Hidden Subgroup Problem - Review and Open Problems
• Quantum Data Compression of a Qubit Ensemble
• Evaluating energy differences on a quantum computer with robust phase estimation
• Optimizing quantum phase estimation for the simulation of Hamiltonian eigenstates
• Quantum Fourier Transform using Dynamic Circuits
• Efficient implementation of bipartite nonlocal unitary gates using prior entanglement and classical communication
• Towards security recommendations for public-key infrastructures for production environments in the post-quantum era
• Constrained Optimization via Quantum Zeno Dynamics
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Quantum Fourier transform for quantum sensing
• Quantum fast Fourier transform using multilevel atoms
• Quantum Locality
• Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Adaptive Measurements in the Optical Quantum Information Laboratory
• Geometric Effects and Computation in Spin Networks
• Relativistic quantum chemistry on quantum computers
• Optimal Eavesdropping in Quantum Cryptography. II. Quantum Circuit
• Mixed state discrimination using optimal control
• Bayesian Quantum Multiphase Estimation Algorithm
• Algorithm for the solution of the Dirac equation on digital quantum computers
• Quantum Teleportation in a Solid State System
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• From Classical State-Swapping to Quantum Teleportation
• Qunity: A Unified Language for Quantum and Classical Computing (Extended Version)
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Types of quantum information
• How to simulate quantum measurement without computing marginals
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Entangled and sequential quantum protocols with dephasing
• Quantum algorithm for obtaining the energy spectrum of a physical system
• Entanglement Simulations of Shor's Algorithm
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Gauge Theory Couplings on Anisotropic Lattices
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Digital Quantum Estimation
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Quantum-circuit guide to optical and atomic interferometry
• Non-asymptotic Heisenberg scaling: experimental metrology for a wide resources range
• Introduction to Quantum Information Processing
• Benchmarking Machine Learning Algorithms for Adaptive Quantum Phase Estimation with Noisy Intermediate-Scale Quantum Sensors
• Classical simulability and the significance of modular exponentiation in Shor's algorithm
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Shor's discrete logarithm quantum algorithm for elliptic curves
• Optimizing phase estimation algorithms for diamond spin magnetometry
• Quantum Abacus for counting and factorizing numbers
• Efficient implementations of the Quantum Fourier Transform: an experimental perspective
• Quantum algorithms for scientific computing
• Fault-tolerant quantum metrology
• Linear optical demonstration of quantum speed-up with a single qudit
• Experimental Hamiltonian Learning of An 11-qubit Solid-State Quantum Spin Register
• Shor's factorization algorithm with a single control qubit and imperfections
• Inferring physical properties of symmetric states from the fewest copies
• Quantum computing Floquet energy spectra
• Quantum divisibility test and its application in mesoscopic physics
• Implementation of Shor's Algorithm with a Single Photon in 32 Dimensions
• Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits
• Symmetric extension of bipartite quantum states and its use in quantum key distribution with two-way postprocessing
• Tensor network methods with graph enhancement
• Compilation of a simple chemistry application to quantum error correction primitives
• Measurement-based universal blind quantum computation with minor resources
• Classicality of quantum information processing
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• Hybrid divide-and-conquer approach for tree search algorithms
• Consistency testing for robust phase estimation
• Projective measurement of energy on an ensemble of qubits with unknown frequencies
• Pauli Noise Learning for Mid-Circuit Measurements
• Realization of Shor's Algorithm at Room Temperature
• RISQ - reduced instruction set quantum computers
• Quantum mean estimation for lattice field theory
• De-quantisation of the Quantum Fourier Transform
• Advantages of a modular high-level quantum programming framework
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Measured Quantum Fourier Transform of 1024 Qubits on Fiber Optics
• Sequential quantum-enhanced measurement with an atomic ensemble
• Understanding the Quantum Computational Speed-up via De-quantisation
• Quantum phase estimation algorithm in presence of static imperfections
• Efficient quantum walk on the grid with multiple marked elements
• Quantum Information: What Is It All About?
• Design of gates for quantum computation: the three-spin XOR gate in terms of two-spin interactions
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Efficient state initialization by a quantum spectral filtering algorithm
• Calculation of the moscovium ground-state energy by quantum algorithms
• Quantum-accelerated algorithms for generating random primitive polynomials over finite fields
• Quantum Computing Discrete Logarithms with the Help of a Preprocessed State
• CNOT-count optimized quantum circuit of the Shor's algorithm
• Quantum Zeno approach for molecular energies with maximum commuting initialHamiltonians
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Microfabrication techniques for trapped ion quantum information processing
• Quantum Phase Estimation with an Arbitrary Number of Qubits
• Quantum Phase Estimation Algorithm for Finding Polynomial Roots
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
• An Improvement in Quantum Fourier Transform
• Revisiting Shor's quantum algorithm for computing general discrete logarithms
• Time-adaptive phase estimation
• The Study of Entangled States in Quantum Computation and Quantum Information Science
• Some Notes on Parallel Quantum Computation
• Experimental investigation of a multi-photon Heisenberg-limited interferometric scheme: the effect of imperfections
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Experimental protocol for qubit-environment entanglement detection
• Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
• Semiclassical Shor's Algorithm
• Improved Bounds for the Approximate QFT
• Quantum Fourier Transform in Oscillating Modes
• A Multilayer Network Approach to Quantum Computing
• Real-time hybrid quantum-classical computations for trapped-ions with Python control-flow
• Optimizing the Phase Estimation Algorithm Applied to the Quantum Simulation of Heisenberg-Type Hamiltonians
• Quantum phase estimation with optimal confidence interval using three control qubits
• Quantum Weighted Model Counting
• Modular quantum computing and quantum-like devices
• Quantum-optical reset with classical memory
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
• Entanglement Trajectory and its Boundary
• Quantum Phase Estimation Algorithm with Gaussian Spin States
• Quantum Algorithms for Discrete Log Require Precise Rotations