Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors

Abstract

We report a proof-of-concept demonstration of a quantum order-finding algorithm for factoring the integer 21. Our demonstration involves the use of a compiled version of the quantum phase estimation routine, and builds upon a previous demonstration by Martín-López et al. in Nature Photonics 6, 773 (2012). We go beyond this work by using a configuration of approximate Toffoli gates with residual phase shifts, which preserves the functional correctness and allows us to achieve a complete factoring of N=21. We implemented the algorithm on IBM quantum processors using only 5 qubits and successfully verified the presence of entanglement between the control and work register qubits, which is a necessary condition for the algorithm's speedup in general. The techniques we employ may be useful in carrying out Shor's algorithm for larger integers, or other algorithms in systems with a limited number of noisy qubits.

arXiv comment11 pages, 10 figures, appendix

References in corpus (25)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Efficient classical simulation of slightly entangled quantum computations
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum state tomography via compressed sensing
• On the role of entanglement in quantum computational speed-up
• Separability of very noisy mixed states and implications for NMR quantum computing
• Witnessing multipartite entanglement
• 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
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Computing prime factors with a Josephson phase qubit quantum processor
• Entanglement Detection in the Stabilizer Formalism
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Efficient Networks for Quantum Factoring
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Approximate Quantum Fourier Transform and Decoherence
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• QUBIT4MATLAB V3.0: A program package for quantum information science and quantum optics for MATLAB
• Pure State Tomography with Pauli Measurements
• Multipartite entanglement detection with minimal effort
• Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor

Cited by in corpus (15)

• Digitized Adiabatic Quantum Factorization
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• A Rydberg-atom approach to the integer factorization problem
• Pulse shape effects in qubit dynamics demonstrated on an IBM quantum computer
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Demonstration of Hardware Efficient Photonic Variational Quantum Algorithm
• Ghost factors in Gauss-sum factorization with transmon qubits
• Measurement-based interleaved randomised benchmarking using IBM processors
• Adaptively partitioned analog quantum simulation on near-term quantum computers: The nonclassical free-induction decay of NV centers in diamond
• Quantum Software Ecosystem Design
• Implementation of single-qubit measurement-based t-designs using IBM processors
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• On The Stabilizer Formalism And Its Generalization
• Using linear and nonlinear entanglement witnesses to generate and detect bound entangled states on an IBM quantum processor