Hard instance learning for quantum adiabatic prime factorization

Abstract

Prime factorization is a difficult problem with classical computing, whose exponential hardness is the foundation of Rivest-Shamir-Adleman (RSA) cryptography. With programmable quantum devices, adiabatic quantum computing has been proposed as a plausible approach to solve prime factorization, having promising advantage over classical computing. Here, we find there are certain hard instances that are consistently intractable for both classical simulated annealing and un-configured adiabatic quantum computing (AQC). Aiming at an automated architecture for optimal configuration of quantum adiabatic factorization, we apply a deep reinforcement learning (RL) method to configure the AQC algorithm. By setting the success probability of the worst-case problem instances as the reward to RL, we show the AQC performance on the hard instances is dramatically improved by RL configuration. The success probability also becomes more evenly distributed over different problem instances, meaning the configured AQC is more stable as compared to the un-configured case. Through a technique of transfer learning, we find prominent evidence that the framework of AQC configuration is scalable -- the configured AQC as trained on five qubits remains working efficiently on nine qubits with a minimal amount of additional training cost.

arXiv comment10 pages, 6 figures. Comments are welcome

References in corpus (23)

• Quantum Computing in the NISQ era and beyond
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• 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
• Adiabatic Quantum Computing
• Quantum Search by Local Adiabatic Evolution
• Perspectives of quantum annealing: Methods and implementations
• Reinforcement Learning in Different Phases of Quantum Control
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Prime factorization using quantum annealing and computational algebraic geometry
• Reinforcement Learning assisted Quantum Optimization
• Accuracy vs run time in adiabatic quantum search
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• A hybrid scheme for prime factorization and its experimental implementation using IBM quantum processor
• Optimizing Quantum Adiabatic Algorithm
• Quantum Factorization of 143 on a Dipolar-Coupling NMR system
• The quantum annealing gap and quench dynamics in the exact cover problem
• Factoring semi-primes with (quantum) SAT-solvers

Cited by in corpus (3)

• Universal Quantum Optimization with Cold Atoms in an Optical Cavity
• Quantum annealing sampling with a bias field
• Atom Cavity Encoding for NP-Complete Problems