A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation

Abstract

We propose an adiabatic quantum algorithm capable of factorizing numbers, using fewer qubits than Shor's algorithm. We implement the algorithm in an NMR quantum information processor and experimentally factorize the number 21. Numerical simulations indicate that the running time grows only quadratically with the number of qubits.

5 pages, 3 figures

References in corpus (13)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum Search by Local Adiabatic Evolution
• Robustness of adiabatic quantum computation
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Experimental implementation of an adiabatic quantum optimization algorithm
• Quantum Phase Transition of Ground-state Entanglement in a Heisenberg Spin Chain Simulated in an NMR Quantum Computer
• Noise resistance of adiabatic quantum computation using random matrix theory
• A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
• Effect of Local Minima on Adiabatic Quantum Optimization
• Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor

Cited by in corpus (59)

• Ising formulations of many NP problems
• Natural and artificial atoms for quantum computation
• p-Bits for Probabilistic Spin Logic
• Quantum Computing with NMR
• Shortcut to adiabaticity for an interacting Bose-Einstein condensate
• Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment
• Superadiabatic Controlled Evolutions and Universal Quantum Computation
• Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
• Experimental realization of quantum algorithm for solving linear systems of equations
• Shortcuts to adiabaticity for trapped ultracold gases
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Ramsey numbers and adiabatic quantum computing
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
• Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Time-efficient implementation of quantum search with qudits
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Quantum Computing: An Overview Across the System Stack
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Experimental Test of Quantum No-Hiding Theorem
• Toward Practical-Scale Quantum Annealing Machine for Prime Factoring
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Digitized Adiabatic Quantum Factorization
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Nonadiabatic quantum state engineering driven by fast quench dynamics
• Energy landscapes of combinatorial optimization in Ising machines
• Efficient generation of many-body entangled states by multilevel oscillations
• Quantum speed-up in solving the maximal clique problem
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Controlling NMR spin systems for quantum computation
• Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor
• A hybrid scheme for prime factorization and its experimental implementation using IBM quantum processor
• Kernel-based quantum regressor models learn non-Markovianity
• Engineering of Quantum State by Time-Dependent Decoherence-Free Subspaces
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• A Rydberg-atom approach to the integer factorization problem
• Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer
• Hard instance learning for quantum adiabatic prime factorization
• Quantum search in many-body interacting system with long-range interaction
• Demonstration of Hardware Efficient Photonic Variational Quantum Algorithm
• Experimental Determination of Electronic States via Digitized Shortcut-to-Adiabaticity and Sequential Digitized Adiabaticity
• Singular-value decomposition using quantum annealing
• Quantum Annealing for Prime Factorization
• Ghost factors in Gauss-sum factorization with transmon qubits
• Accelerating an adiabatic process by nonlinear sweeping
• A quantum algorithm for greatest common divisor problem
• Spintronics for neuromorphic computing
• Validity condition for high-fidelity Digitized Quantum Annealing
• More period finding with adiabatic quantum computation
• Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer
• High-performance Energy Minimization with Applications to Adiabatic Quantum Computing
• Realistic cost for the model of coherent computing
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Experimental implementation of universal holonomic quantum computation on solid-state spins with optimal control