Realization of a scalable Shor algorithm

Abstract

Quantum computers are able to outperform classical algorithms. This was long recognized by the visionary Richard Feynman who pointed out in the 1980s that quantum mechanical problems were better solved with quantum machines. It was only in 1994 that Peter Shor came up with an algorithm that is able to calculate the prime factors of a large number vastly more efficiently than known possible with a classical computer. This paradigmatic algorithm stimulated the flourishing research in quantum information processing and the quest for an actual implementation of a quantum computer. Over the last fifteen years, using skillful optimizations, several instances of a Shor algorithm have been implemented on various platforms and clearly proved the feasibility of quantum factoring. For general scalability, though, a different approach has to be pursued. Here, we report the realization of a fully scalable Shor algorithm as proposed by Kitaev. For this, we demonstrate factoring the number fifteen by effectively employing and controlling seven qubits and four "cache-qubits", together with the implementation of generalized arithmetic operations, known as modular multipliers. The scalable algorithm has been realized with an ion-trap quantum computer exhibiting success probabilities in excess of 90%.

5 pages, 3 figures, 4 pages suppl. material (incl. 1 figure)

References in corpus (16)

• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Experimental issues in coherent quantum-state manipulation of trapped atomic ions
• Quantum computation with ions in thermal motion
• Quantum Networks for Elementary Arithmetic Operations
• Shor's quantum factoring algorithm on a photonic chip
• Semiclassical Fourier Transform for Quantum Computation
• 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
• Computing prime factors with a Josephson phase qubit quantum processor
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Fast Quantum Modular Exponentiation
• Two-Qubit State Tomography using a Joint Dispersive Read-Out
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Pretending to factor large numbers on a quantum computer
• Optimal control of entangling operations for trapped ion quantum computing

Cited by in corpus (153)

• The Road Towards 6G: A Comprehensive Survey
• Trapped-Ion Quantum Computing: Progress and Challenges
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum information processing with superconducting circuits: a review
• Demonstration of a small programmable quantum computer with atomic qubits
• Quantum optimization using variational algorithms on near-term quantum devices
• Experimental Comparison of Two Quantum Computing Architectures
• Benchmarking an 11-qubit quantum computer
• Robust determination of molecular spectra on a quantum processor
• A compact ion-trap quantum computing demonstrator
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Low-cost error mitigation by symmetry verification
• Almost-linear time decoding algorithm for topological codes
• Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
• The quasiprobability behind the out-of-time-ordered correlator
• Repeated multi-qubit readout and feedback with a mixed-species trapped-ion register
• Noisy intermediate-scale quantum computers
• A long-lived Zeeman trapped-ion qubit
• Decoding Small Surface Codes with Feedforward Neural Networks
• Quantum networks with neutral atom processing nodes
• Strong coupling of a single ion to an optical cavity
• Sympathetic ground state cooling and time-dilation shifts in an ${}^{27}{\text{Al}}^{+}$ optical clock
• Dynamical topological transitions in the massive Schwinger model with a θ-term
• $\text{omg}$ Blueprint for trapped ion quantum computing with metastable states
• Quantum Algorithms for Fixed Qubit Architectures
• Demonstration of two-atom entanglement with ultrafast optical pulses
• Prime factorization using quantum annealing and computational algebraic geometry
• Compiling quantum algorithms for architectures with multi-qubit gates
• Cryogenic setup for trapped ion quantum computing
• Simulating the performance of a distance-3 surface code in a linear ion trap
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Quantum gate learning in engineered qubit networks: Toffoli gate with always-on interactions
• Scalable creation of long-lived multipartite entanglement
• Noise Analysis for High-Fidelity Quantum Entangling Gates in an Anharmonic Linear Paul Trap
• Realizing coherently convertible dual-type qubits with the same ion species
• Quantum-enhanced magnetometry by phase estimation algorithms with a single artificial atom
• Demonstration of fault-tolerant Steane quantum error correction
• Hybrid quantum computation gate with trapped ion system
• Certification of non-Gaussian states with operational measurements
• A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
• Training Optimization for Gate-Model Quantum Neural Networks
• Observation of Hopping and Blockade of Bosons in a Trapped Ion Spin Chain
• Minimally complex ion traps as modules for quantum communication and computing
• Repetitive readout and real-time control of nuclear spin qubits in ${}^{171}$Yb atoms
• Boson sampling with Gaussian measurements
• Open quantum generalisation of Hopfield neural networks
• Analyzing the Rydberg-based omg architecture for ${}^{171}$Yb nuclear spins
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Engineering Large Stark Shifts for Control of Individual Clock State Qubits
• Approaching the theoretical limit in quantum gate decomposition
• Multiplexed telecom-band quantum networking with atom arrays in optical cavities
• A programmable three-qubit superconducting processor with all-to-all connectivity
• A single strontium Rydberg ion confined in a Paul trap
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• Scalable ion-photon quantum interface based on integrated diffractive mirrors
• Trapping Ions and Atoms Optically
• Modeling Noisy Quantum Circuits Using Experimental Characterization
• Bayesian Quantum Multiphase Estimation Algorithm
• Ultra-low vibration closed-cycle cryogenic surface-electrode ion trap apparatus
• Speeding-up the decision making of a learning agent using an ion trap quantum processor
• Frequency conversion between UV and telecom wavelengths in a lithium niobate waveguide for quantum communication with Yb+ trapped ions
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Active cancellation of servo-induced noise on stabilized lasers via feedforward
• Dense Quantum Measurement Theory
• Entanglement from tensor networks on a trapped-ion QCCD quantum computer
• Two-dimensional linear trap array for quantum information processing
• Experimental study of optimal measurements for quantum state tomography
• Quantum Circuit Design for Objective Function Maximization in Gate-Model Quantum Computers
• Scalable Quantum Tomography with Fidelity Estimation
• Driving-induced amplification of non-Markovianity in open quantum systems evolution
• Efficient sideband cooling protocol for long trapped-ion chains
• Quantum dynamics of trapped ions in a dynamic field gradient using dressed states
• Superconducting qubits beyond the dispersive regime
• Sideband cooling of small ion Coulomb crystals in a Penning trap
• Sideband cooling of the radial modes of motion of a single ion in a Penning trap
• Towards Rydberg quantum logic with trapped ions
• A Quantum von Neumann Architecture for Large-Scale Quantum Computing
• Exact quantization of superconducting circuits
• Finite temperature spectrum at the symmetry-breaking linear-zigzag transition
• Coupling-assisted Landau-Majorana-Stuckelberg-Zener transition in two-interacting-qubit systems
• Multilayer ion trap with three-dimensional microwave circuitry for scalable quantum logic applications
• Tunable quantum gate between a superconducting atom and a propagating microwave photon
• High Fidelity Entangling Gates in a 3D Ion Crystal under Micromotion
• Periodically Driven Three-Level Systems
• Towards multiqudit quantum processor based on a ${}^{171}$Yb${}^{+}$ ion string: Realizing basic quantum algorithms
• Quantum computer-aided design: digital quantum simulation of quantum processors
• Quantum speed-up in solving the maximal clique problem
• Atomic Quantum Technologies for Quantum Matter and Fundamental Physics Applications
• Iterative Precision Measurement of Branching Ratios Applied to 5P states in 88Sr+
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Implementation of quantum compression on IBM quantum computers
• State-selective coherent motional excitation as a new approach for the manipulation, spectroscopy and state-to-state chemistry of single molecular ions
• Performance of Superconducting Quantum Computing Chips under Different Architecture Design
• An architecture for two-qubit encoding in neutral ytterbium-171 atoms
• Spin readout of trapped electron qubits
• Ultrafast, high repetition rate, ultraviolet, fiber based laser source: application towards Yb+ fast quantum-logic
• Quantum computing with superconducting circuits in the picosecond regime
• Mode-Dependent Loss Model for Multimode Photon-Subtracted States
• Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor
• Coherent vs. measurement-based feedback for controlling a single qubit
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
• Simulation of wave-particle duality in multi-path interferometers on a quantum computer
• Multi-GHz repetition rate, multi-watt average power, ultraviolet laser pulses for fast trapped-ion entanglement operations
• State Stabilization for Gate-Model Quantum Computers
• Optimization and implementation of a surface-electrode ion trap junction
• Population dynamics in sideband cooling of trapped ions outside the Lamb-Dicke regime
• Demonstration of quantum advantage by a joint detection receiver for optical communications using quantum belief propagation on a trapped-ion device
• Combining experiments and relativistic theory for establishing accurate radiative quantities in atoms: the lifetime of the ${}^2$P${}_{3/2}$ state in ${}^{40}$Ca${}^{+}$
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• A room-temperature ion trapping apparatus with hydrogen partial pressure below $10^{-11}$ mBar
• Quadrature Histograms in Maximum Likelihood Quantum State Tomography
• Emulating Quantum Interference with Generalized Ising Machines
• A two-dimensional architecture for fast large-scale trapped-ion quantum computing
• A Rydberg-atom approach to the integer factorization problem
• Mølmer-Sørensen entangling gate for cavity QED systems
• RF-induced heating dynamics of non-crystallized trapped ions
• Realization of Shor's Algorithm at Room Temperature
• Single-photon-added coherent state based measurement transition and its advantages in precision measurement
• Characterizing quantum instruments: from non-demolition measurements to quantum error correction
• Programmable Hamiltonian engineering with quadratic quantum Fourier transform
• Quantum error correction for long chains of trapped ions
• Facets of correlated non-Markovian channels
• Ultra-low Frequency Noise External Cavity Diode Laser Systems for Quantum Applications
• Pitfalls of the sublinear QAOA-based factorization algorithm
• Discrimination of correlated and entangling quantum channels with selective process tomography
• Universal quantum computation using atoms in cross-cavity systems
• Reinforcement learning with learned gadgets to tackle hard quantum problems on real hardware
• Quantum computing hardware in the cloud: Should a computational chemist care?
• Ionic vibration induced transparency and Autler-Townes splitting
• Coherence and entanglement dynamics in Shor's algorithm
• A Computational Workflow for Designing Silicon Donor Qubits
• A quantum algorithm for greatest common divisor problem
• High cooperativity coupling to nuclear spins on a circuit QED architecture
• Supervised binary classification of small-scale digit images and weighted graphs with a trapped-ion quantum processor
• Realizing Quantum Algorithms on Real Quantum Computing Devices
• Experimenting with D-Wave Quantum Annealers on Prime Factorization problems
• Precision magnetometry exploiting excited state quantum phase transitions
• Efficient quantum algorithm for solving structured problems via multi-step quantum computation
• Comparative study of variational quantum circuit and quantum backpropagation multilayer perceptron for COVID-19 outbreak predictions
• Thermal masses and trapped-ion quantum spin models: a self-consistent approach to Yukawa-type interactions in the $\lambda {\varphi }^4$ model
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• A Universal Quantum Computing Virtual Machine
• Ion crystals in anharmonic traps
• Towards a quantum decision tree in a laser pumped four-level system
• Quantum Computation
• Saving resources through repeat-until-success positive-operator-valued-measure measurements in quantum computation
• Quantum Phase Estimation Algorithm with Gaussian Spin States
• Quantum Algorithms in Cybernetics
• Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Quantum Fourier Transform in Oscillating Modes