Prime factorization using quantum annealing and computational algebraic geometry

Abstract

We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel scalable algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over $200000$, the largest number factored to date using a quantum processor.

D-Wave stats added, minor fixes

References in corpus (18)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing with more than one hundred qubits
• Quantum Annealing and Analog Quantum Computation
• Realization of a scalable Shor algorithm
• Quantum measurements and the Abelian Stabilizer Problem
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Experimental signature of programmable quantum annealing
• Contextuality in Measurement-based Quantum Computation
• A practical heuristic for finding graph minors
• Pretending to factor large numbers on a quantum computer
• Minimizing Polynomial Functions
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Homology Computation of Large Point Clouds using Quantum Annealing
• Fast clique minor generation in Chimera qubit connectivity graphs
• Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The "deduc-reduc" method and its application to quantum factorization of numbers
• Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing

Cited by in corpus (27)

• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
• Quantum computing cryptography: Finding cryptographic Boolean functions with quantum annealing by a 2000 qubit D-wave quantum computer
• Digitized Adiabatic Quantum Factorization
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• HUBO and QUBO models for Prime factorization
• Heterogeneous Quantum Computing for Satellite Constellation Optimization: Solving the Weighted K-Clique Problem
• Quadratization in discrete optimization and quantum mechanics
• A hybrid scheme for prime factorization and its experimental implementation using IBM quantum processor
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Polynomial Reduction Methods and their Impact on QAOA Circuits
• Combinatorial Optimization by Decomposition on Hybrid CPU--non-CPU Solver Architectures
• Hard instance learning for quantum adiabatic prime factorization
• Experimental Demonstrations of Native Implementation of Boolean Logic Hamiltonian in a Superconducting Quantum Annealer
• Quantum Integer Programming (QuIP) 47-779: Lecture Notes
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Ghost factors in Gauss-sum factorization with transmon qubits
• Mapping State Transition Susceptibility in Quantum Annealing
• Logically Synthesized, Hardware-Accelerated, Restricted Boltzmann Machines for Combinatorial Optimization and Integer Factorization
• Experimenting with D-Wave Quantum Annealers on Prime Factorization problems
• Benchmarking Embedded Chain Breaking in Quantum Annealing
• Experimental Evidence about "A factorisation algorithm in adiabatic quantum computation" by T. D. Kieu
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Resiliency Analysis and Improvement of Variational Quantum Factoring in Superconducting Qubit