Experimental demonstration of Shor's algorithm with quantum entanglement
arXiv:0705.1398 · doi:10.1103/PhysRevLett.99.250505
Abstract
Shor's powerful quantum algorithm for factoring represents a major challenge in quantum computation and its full realization will have a large impact on modern cryptography. Here we implement a compiled version of Shor's algorithm in a photonic system using single photons and employing the non-linearity induced by measurement. For the first time we demonstrate the core processes, coherent control, and resultant entangled states that are required in a full-scale implementation of Shor's algorithm. Demonstration of these processes is a necessary step on the path towards a full implementation of Shor's algorithm and scalable quantum computing. Our results highlight that the performance of a quantum algorithm is not the same as performance of the underlying quantum circuit, and stress the importance of developing techniques for characterising quantum algorithms.
4 pages, 5 figures + half-page additional online material
References in corpus (20)
- On the Measurement of Qubits
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Simulated Quantum Computation of Molecular Energies
- Experimental One-Way Quantum Computing
- Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
- Experimental entanglement of six photons in graph states
- Distance measures to compare real and ideal quantum processes
- Optical quantum computation using cluster states
- Separability of very noisy mixed states and implications for NMR quantum computing
- Witnessing multipartite entanglement
- Quantum process tomography of a controlled-NOT gate
- Semiclassical Fourier Transform for Quantum Computation
- High-speed linear optics quantum computing using active feed-forward
- Linear Optics C-Phase gate made simple
- Efficient Networks for Quantum Factoring
- Demonstration of a simple entangling optical gate and its use in Bell-state analysis
- Demonstration of an optical quantum controlled-NOT gate without path interference
- Experimental interference of independent photons
- Measuring Controlled-NOT and two-qubit gate operation
- Local Realistic Model for the Dynamics of Bulk-Ensemble NMR Information Processing
Cited by in corpus (120)
- 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
- Towards Quantum Chemistry on a Quantum Computer
- 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
- Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- Experimental demonstration of a hyper-entangled ten-qubit Schrödinger cat state
- Computing prime factors with a Josephson phase qubit quantum processor
- Can One Trust Quantum Simulators?
- 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
- Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- Adding control to arbitrary unknown quantum operations
- Experimental Quantum Computing to Solve Systems of Linear Equations
- Instantaneous Quantum Computation
- Multi-photon quantum interference in a multi-port integrated photonic device
- Large-Alphabet Time-Frequency Entangled Quantum Key Distribution by means of Time-to-Frequency Conversion
- Heralded generation of entangled photon pairs
- A quantum Fredkin gate
- Entangling Bosonic Modes via an Engineered Exchange Interaction
- Phase-controlled integrated photonic quantum circuits
- Statistical Assertions for Validating Patterns and Finding Bugs in Quantum Programs
- Pretending to factor large numbers on a quantum computer
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Quantum Algorithm for Obtaining the Energy Spectrum of Molecular Systems
- Direct characterization of linear-optical networks
- Experimental Blind Quantum Computing for a Classical Client
- Gauss sum factorization with cold atoms
- Experimental quantum coding against photon loss error
- An Experimental Study of Shor's Factoring Algorithm on IBM Q
- Optical Quantum Computation
- Five measurement bases determine pure quantum states on any dimension
- Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
- Benchmarking quantum computers
- Observation of Ten-photon Entanglement Using Thin BiBO Crystals
- Calculating Unknown Eigenvalues with a Quantum Algorithm
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Nonlocal photonic quantum gates over 7.0 km
- Demonstration of Topological Data Analysis on a Quantum Processor
- A proposed testbed for detector tomography
- Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
- Optimising Matrix Product State Simulations of Shor's Algorithm
- Quantum interferometers: principles and applications
- High-visibility nonclassical interference between pure heralded single photons and weak coherent photons
- Faster Quantum Number Factoring via Circuit Synthesis
- Integrated Photonic Sensing
- Digitized Adiabatic Quantum Factorization
- Large-Scale Simulation of Shor's Quantum Factoring Algorithm
- Factoring numbers with a single interferogram
- QDB: From Quantum Algorithms Towards Correct Quantum Programs
- 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
- Factorization of numbers with Gauss sums: I. Mathematical background
- Simple implementation of high fidelity controlled-SWAP gates and quantum circuit exponentiation of non-Hermitian gates
- Transition Role of Entangled Data in Quantum Machine Learning
- Eliminating Spectral Distinguishability in Ultrafast Spontaneous Parametric Down-conversion
- Experimentally generating and tuning robust entanglement between photonic qubits
- Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
- Quantum Simulation Logic, Oracles, and the Quantum Advantage
- Quantum speed-up in solving the maximal clique problem
- Measuring Entanglement in a Photonic Embedding Quantum Simulator
- Efficiency Optimization in Quantum Computing: Balancing Thermodynamics and Computational Performance
- Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
- Quantum optics and frontiers of physics: The third quantum revolution
- Shor's quantum algorithm using electrons in semiconductor nanostructures
- Experimental implementation of quantum algorithm for association rules mining
- Discrimination of thermal baths by single qubit probes
- Quantifying coherence in terms of Fisher information
- Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
- Entangled state generation with an intrinsically pure single-photon source and a weak coherent source
- Implementation of Shor's Algorithm with a Single Photon in 32 Dimensions
- Client-friendly continuous-variable blind and verifiable quantum computing
- A hybrid scheme for prime factorization and its experimental implementation using IBM quantum processor
- State of the art and prospects for quantum computing
- Factoring Safe Semiprimes with a Single Quantum Query
- Odd orders in Shor's factoring algorithm
- Experimental demonstration of teleportation-based programmable quantum gate
- Four-Photon GHZ Entanglement via Collective Two-Photon Coherence in Doppler-Broadened Atoms
- Emulating Quantum Interference with Generalized Ising Machines
- Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
- Markov Chain Monte Carlo Estimation of Quantum States
- Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
- A Rydberg-atom approach to the integer factorization problem
- Dirac formulation for universal quantum gates and Shor's integer factorization in high-frequency electric circuits
- Realization of Shor's Algorithm at Room Temperature
- Photostatistics Reconstruction via Loop Detector Signatures
- Ptychography of pure quantum states
- Multiplexed Pseudo-Deterministic Photon Source with Asymmetric Switching Elements
- On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers
- Remarks on Quantum Modular Exponentiation and Some Experimental Demonstrations of Shor's Algorithm
- Universal quantum computation using atoms in cross-cavity systems
- Bunching Effect and Quantum Statistics of Partially Indistinguishable Photons
- Pitfalls of the sublinear QAOA-based factorization algorithm
- Quantum-Kit: Simulating Shor's Factorization of 24-Bit Number on Desktop
- Complete conversion between one and two photons in nonlinear waveguides with tailored dispersion
- Quantum Annealing for Prime Factorization
- Blindly Factorizing 21 Quantumly
- Quantum resources in Harrow-Hassidim-Lloyd algorithm
- Precision magnetometry exploiting excited state quantum phase transitions
- Synthesizing Quantum Circuits for Simple Periodic Functions
- Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
- Tradeoff between noise and banding in a quantum adder with qudits
- Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
- Verification of entangled states under noisy measurements
- Physics and computer science: quantum computation and other approaches
- Experimental protocol for qubit-environment entanglement detection
- Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
- Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
- Quantum Algorithms in Cybernetics
- Improving adiabatic quantum factorization via chopped random-basis optimization
- Quantum Fourier Transform in Oscillating Modes
- Atom- Photon Entanglement in Double- Lambda Quantum System by using femtosecond Gaussian pulses