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 (2)

• A practical heuristic for finding graph minors
• 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