Demonstration of Shor's quantum factoring algorithm using photonic qubits

Abstract

We report an experimental demonstration of a complied version of Shor's algorithm using four photonic qubits. We choose the simplest instance of this algorithm, that is, factorization of N=15 in the case that the period $r=2$ and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semi-classical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents a step toward full realization of Shor's algorithm and scalable linear optics quantum computation.

small changes over v2; to appear in PRL

References in corpus (28)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Experimental quantum teleportation
• Review article: Linear optical quantum computing
• Efficient classical simulation of slightly entangled quantum computations
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Experimental One-Way Quantum Computing
• NMR Techniques for Quantum Control and Computation
• Multi-party entanglement in graph states
• Quantum Networks for Elementary Arithmetic Operations
• Resource-efficient linear optical quantum computation
• Experimental entanglement of six photons in graph states
• On the role of entanglement in quantum computational speed-up
• Optical quantum computation using cluster states
• Separability of very noisy mixed states and implications for NMR quantum computing
• Witnessing multipartite entanglement
• Semiclassical Fourier Transform for Quantum Computation
• High-speed linear optics quantum computing using active feed-forward
• Quantum Computers, Factoring, and Decoherence
• Experimental Analysis of a 4-Qubit Cluster State
• Efficient Networks for Quantum Factoring
• Experimental application of decoherence-free subspaces in a quantum-computing algorithm
• Grover's search algorithm: An optical approach
• Sufficient conditions for three-particle entanglement and their tests in recent experiments
• Experimental Realization of Deutsch's Algorithm in a One-way Quantum Computer
• Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?
• Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers
• Four-photon correction in two-photon Bell experiments
• Effects of frequency correlation in linear optical entangling gate operated with independent photons

Cited by in corpus (99)

• Quantum Computing
• Photonic quantum technologies
• Multi-photon entanglement and interferometry
• The Variational Quantum Eigensolver: a review of methods and best practices
• Boson Sampling on a Photonic Chip
• Photonic quantum information processing: a concise review
• Realization of a scalable Shor algorithm
• Experimental realization of multipartite entanglement of 60 modes of a quantum optical frequency comb
• Shor's quantum factoring algorithm on a photonic chip
• Molecular Spin Qudits for Quantum Algorithms
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Computing prime factors with a Josephson phase qubit quantum processor
• Hybrid Quantum-Classical Convolutional Neural Networks
• On the genesis and evolution of Integrated Quantum Optics
• Perspective: Toward large-scale fault-tolerant universal photonic quantum computing
• Entanglement-Based Machine Learning on a Quantum Computer
• Quantum-Inspired Support Vector Machine
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Adding control to arbitrary unknown quantum operations
• Instantaneous Quantum Computation
• Multi-photon quantum interference in a multi-port integrated photonic device
• Heralded generation of entangled photon pairs
• Experimental Machine Learning of Quantum States
• Pretending to factor large numbers on a quantum computer
• Introduction to topological quantum computation with non-Abelian anyons
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Quantum computing by optical control of electron spins
• Experimental Blind Quantum Computing for a Classical Client
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Experimental quantum coding against photon loss error
• Optical Quantum Computation
• Five measurement bases determine pure quantum states on any dimension
• Reconstruction of a Photonic Qubit State with Reinforcement Learning
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• Spectrally resolved Hong-Ou-Mandel interference between independent sources
• Observation of Ten-photon Entanglement Using Thin BiB${}_3$O${}_6$ Crystals
• Calculating Unknown Eigenvalues with a Quantum Algorithm
• A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
• Demonstration of Topological Data Analysis on a Quantum Processor
• Toward Practical-Scale Quantum Annealing Machine for Prime Factoring
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Toward demonstrating controlled-X operation based on continuous variable four-partite cluster state and quantum teleporters
• Quantum interferometers: principles and applications
• Faster Quantum Number Factoring via Circuit Synthesis
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Digitized Adiabatic Quantum Factorization
• Factoring numbers with a single interferogram
• Experimental Simulation of Larger Quantum Circuits with Fewer Superconducting Qubits
• Quantum Interference between Autonomous Single-Photon Sources from Doppler-Broadened Atomic Ensemble
• NMR implementation of Factoring Large Numbers with GaußSums: Suppression of Ghost Factors
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
• Quantum speed-up in solving the maximal clique problem
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Shor's quantum algorithm using electrons in semiconductor nanostructures
• Measuring Entanglement in a Photonic Embedding Quantum Simulator
• 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
• Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor
• Demonstration of quantum permutation algorithm with a single photon ququart
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
• A hybrid scheme for prime factorization and its experimental implementation using IBM quantum processor
• Implementation of Shor's Algorithm with a Single Photon in 32 Dimensions
• Factoring Safe Semiprimes with a Single Quantum Query
• Programmable coherent linear quantum operations with high-dimensional optical spatial modes
• Experimental demonstration of teleportation-based programmable quantum gate
• Odd orders in Shor's factoring algorithm
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• A Rydberg-atom approach to the integer factorization problem
• Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
• Spin-orbit implementation of Solovay-Kitaev decomposition of single-qubit channels
• Parameter-Parallel Distributed Variational Quantum Algorithm
• Realization of Shor's Algorithm at Room Temperature
• Dirac formulation for universal quantum gates and Shor's integer factorization in high-frequency electric circuits
• Ptychography of pure quantum states
• Integration of highly probabilistic sources into optical quantum architectures: perpetual quantum computation
• Remarks on Quantum Modular Exponentiation and Some Experimental Demonstrations of Shor's Algorithm
• Bunching Effect and Quantum Statistics of Partially Indistinguishable Photons
• Quantum-Kit: Simulating Shor's Factorization of 24-Bit Number on Desktop
• Pitfalls of the sublinear QAOA-based factorization algorithm
• Quantum control of entangled photon-pair generation in electron-atom collisions driven by laser-synthesized free-electron wave packets
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• Quantum Annealing for Prime Factorization
• A quantum algorithm for greatest common divisor problem
• Synthesizing Quantum Circuits for Simple Periodic Functions
• Precision magnetometry exploiting excited state quantum phase transitions
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
• Quantum Algorithms in Cybernetics
• Quantum Search Algorithm for Set Operation
• Computing Shor's algorithmic steps with classical light beams
• Photon Frequency Bears More At Less
• Quantum Fourier Transform in Oscillating Modes
• A Universal Quantum Computing Virtual Machine
• Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Improving adiabatic quantum factorization via chopped random-basis optimization