Experimental realisation of Shor's quantum factoring algorithm using qubit recycling

Abstract

Quantum computational algorithms exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum algorithm for fast number factoring is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the substantial resource requirement, to date, there have been only four small-scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which the n qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N=21. The algorithmic output is distinguishable from noise, in contrast to previous demonstrations. These results point to larger-scale implementations of Shor's algorithm by harnessing scalable resource reductions applicable to all physical architectures.

7 pages, 3 figures

References in corpus (19)

• Quantum Computing
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Simulated Quantum Computation of Molecular Energies
• Ultra-bright source of polarization-entangled photons
• Towards Quantum Chemistry on a Quantum Computer
• Quantum process tomography of a controlled-NOT gate
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Shor's quantum factoring algorithm on a photonic chip
• Semiclassical Fourier Transform for Quantum Computation
• High-speed linear optics quantum computing using active feed-forward
• Linear Optical CNOT Gate in the Coincidence Basis
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Efficient Networks for Quantum Factoring
• Quantum phase gate for photonic qubits using only beam splitters and post-selection
• Adding control to arbitrary unknown quantum operations
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
• Quantum computing applied to calculations of molecular energies: CH2 benchmark

Cited by in corpus (102)

• Quantum algorithms: an overview
• The Variational Quantum Eigensolver: a review of methods and best practices
• Demonstration of a small programmable quantum computer with atomic qubits
• Photonic quantum information processing: a concise review
• Building logical qubits in a superconducting quantum computing system
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Realization of a scalable Shor algorithm
• Molecular Spin Qudits for Quantum Algorithms
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• A quantum information processor with trapped ions
• Experimental Superposition of Orders of Quantum Gates
• Integrated spatial multiplexing of heralded single photon sources
• Spontaneous parametric down-conversion
• Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Large-Alphabet Time-Frequency Entangled Quantum Key Distribution by means of Time-to-Frequency Conversion
• A quantum Fredkin gate
• Quantum Algorithm Implementations for Beginners
• Pretending to factor large numbers on a quantum computer
• Solving systems of linear equations on a quantum computer
• Enhancing quantum cryptography with quantum dot single-photon sources
• Towards High-Fidelity Quantum Computation and Simulation on a Programmable Photonic Integrated Circuit
• Direct high-resolution characterization of quantum correlations via classical measurements
• Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
• Prime factorization using quantum annealing and computational algebraic geometry
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Simulating the performance of a distance-3 surface code in a linear ion trap
• Experimental quantum e-commerce
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• Coherent controlization using superconducting qubits
• Entanglement universality of two-qubit X-states
• A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
• A logical qubit in a linear array of semiconductor quantum dots
• Approaching the theoretical limit in quantum gate decomposition
• Demonstration of quantum-digital payments
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• Resonator reset in circuit QED by optimal control for large open quantum systems
• Bayesian Quantum Multiphase Estimation Algorithm
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Digitized Adiabatic Quantum Factorization
• Photonic implementation of quantum information masking
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Experimental implementation of a fully controllable depolarizing quantum operation
• Wire Recycling for Quantum Circuit Optimization
• Simple implementation of high fidelity controlled-$i$SWAP gates and quantum circuit exponentiation of non-Hermitian gates
• Generating polarization-entangled photon pairs using cross-spliced birefringent fibers
• Witnessing quantum resource conversion within deterministic quantum computation using one pure superconducting qubit
• Experimental quantum phase discrimination enhanced by controllable indistinguishability-based coherence
• 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
• Experimental implementation of quantum algorithm for association rules mining
• Simple, robust and on-demand generation of single and correlated photons
• Variational quantum iterative power algorithms for global optimization
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
• A certification scheme for the boson sampler
• Robust excitation of C-band quantum dots for quantum communication
• State of the art and prospects for quantum computing
• Probing phases of quantum matter with an ion-trap tensor-network quantum eigensolver
• Genuinely multi-point temporal quantum correlations and universal measurement-based quantum computing
• Factoring Safe Semiprimes with a Single Quantum Query
• Odd orders in Shor's factoring algorithm
• Reachability Analysis of Quantum Markov Decision Processes
• Complexity Classification of Conjugated Clifford Circuits
• Shor's Factoring Algorithm and Modular Exponentiation Operators
• Dirac formulation for universal quantum gates and Shor's integer factorization in high-frequency electric circuits
• Realization of Shor's Algorithm at Room Temperature
• Experimental characterization of quantum polarization of three-photon states
• Error-Resilient Floquet Geometric Quantum Computation
• Bunching Effect and Quantum Statistics of Partially Indistinguishable Photons
• Pitfalls of the sublinear QAOA-based factorization algorithm
• Universal quantum computation using atoms in cross-cavity systems
• Quantum-Kit: Simulating Shor's Factorization of 24-Bit Number on Desktop
• Floquet geometric entangling gates in ground-state manifolds of Rydberg atoms
• Ghost factors in Gauss-sum factorization with transmon qubits
• Blindly Factorizing 21 Quantumly
• Quantum Annealing for Prime Factorization
• Conical Designs and Categorical Jordan Algebraic Post-Quantum Theories
• Experimenting with D-Wave Quantum Annealers on Prime Factorization problems
• Precision magnetometry exploiting excited state quantum phase transitions
• Non-stabilizerness and entanglement from cat-state injection
• Synthesizing Quantum Circuits for Simple Periodic Functions
• Gates for Adiabatic Quantum Computing
• Factoring an integer with three oscillators and a qubit
• On completely factoring any integer efficiently in a single run of an order finding algorithm
• 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
• Information-theoretically secure quantum timestamping with one-time universal hashing
• Linear-optical generation of eigenstates of the two-site XY model
• More period finding with adiabatic quantum computation
• Consideration of the Need for Quantum Grid Computing
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
• Quantum Phase Estimation Algorithm with Gaussian Spin States
• Achievability of two qubit gates using linear optical elements and post-selection
• Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Implementation of a quantum controlled-SWAP gate with photonic circuits
• Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies
• Exploring the Impact of Affine Loop Transformations in Qubit Allocation
• Optimizing the Phase Estimation Algorithm Applied to the Quantum Simulation of Heisenberg-Type Hamiltonians
• The Computational Power of Non-interacting Particles
• Computing Shor's algorithmic steps with classical light beams
• Signing Information in the Quantum Era
• Quantum Algorithms in Cybernetics