# Hard instance learning for quantum adiabatic prime factorization

arXiv: https://arxiv.org/abs/2110.04782 · HTML: https://mlsanity.com/paper/2110.04782/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 35 references that are in the map.
- First posted on arXiv 10 Oct 2021.

## Builds on (most cited first, 6 of 6)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis](https://mlsanity.com/paper/1705.09844/) (2017)
- [Goldbach's Function Approximation Using Deep Learning](https://mlsanity.com/paper/1803.09237/) (2018)
- [Factoring semi-primes with (quantum) SAT-solvers](https://mlsanity.com/paper/1902.01448/) (2019)
- [Prime factorization using quantum annealing and computational algebraic geometry](https://mlsanity.com/paper/1604.05796/) (2016)
- [Integer Factorization with a Neuromorphic Sieve](https://mlsanity.com/paper/1703.03768/) (2017)

## Abstract (arXiv)

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.