Hard-instance learning for quantum adiabatic prime factorization

Prime factorization is a difficult problem with classical computing, whose exponential hardness is the foundation of Rivest-Shamir-Adleman cryptography. With programable 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 unconfigured 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 unconfigured 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.

Figure 1

Schematic illustration of hard instance learning architecture for quantum adiabatic prime factorization. In phase 1, we map the factorization problem to the quadratic unconstrained binary optimization (QUBO) problem and transfer it into an equivalent Ising type Hamiltonian (see Appendix pp1). We generate instances that need the same number of qubits to factorize. Then, we separate factorization instances into two groups according to their performance in AQC and load the intractable instances under the unconfigured AQC schedule into the RL optimization process. In phase 2, we show the RL structure. We combine the Hamiltonian schedule [all the $b_m$ in Eq. (4)] and DoubleOneHot Encoder as the input state to the neural networks. The critic neural network supervises the actor neural network to take actions on the Hamiltonian schedule. A quantum adiabatic computer works under the configured schedule and provides the success probability as feedback to the RL framework.

Figure 2

Easy and hard factorization instances with simulated annealing and adiabatic quantum computing. We separate the problem instances into two groups according to their performances. In (a), blue data show the $j_0^{*}$ obtained in 500 parallel runs of simulated annealing (see main text). Red data show the failure probability of unconfigured AQC (see main text) with a total evolution time $T=6964$. The red dashed line denotes the average failure probability of all the problem instances. It reaches the threshold of failure probability which we set to be 0.9. The problem instances that are hard with SA which have a high value of $j_0^{*}$ remain hard for the unconfigured AQC as it yields a considerably higher failure probability compared to other problem instances. In (b), we show the performances of different instances with the increasing total evolution time $T$. We find the success probabilities of several instances increase more slowly than others and are under the average value at the end. We separate them into two groups with the threshold (see main text). In these plots, we choose numbers to factorize that are encoded by seven spins.

Figure 3

Performance of SAC configured AQC with different reward settings. The success probabilities on all the hard factorization instances are obtained by using the best Hamiltonian schedule that is trained under the different reward settings within the same number of training steps. We test the different reward types including Reward1, $min[log$(success probability)], Reward2, ave[$log$(success probability)], Reward3, $min$(success probability), Reward4, ave(success probability), and Reward5, ave(energy). The reward settings giving more weights to the worst-case problem instances such as Reward1 and Reward3 produce success probabilities more narrowly distributed. The averaging type of reward settings such as Reward2 and Reward4 yield a larger mean value of success probability but the distribution is much broader compared to Reward1 and Reward3. The energy type reward produces relatively lower success probability overall.

Figure 4

Training process of SAC configuration on AQC-based prime factorization in the different system sizes with the qubit number of 5, 6, 7, 8, 9, 10, 11. We record the reward of $min[log$(success probability)], which corresponds to the performance of the hardest factorizing instance in each system size during the training. The bold lines denote the results of smoothing over 80 nearby date points. We observe that the SAC improves the performance of the hardest instances and all the cases of rewards converge within 1600 measurement steps.

Figure 5

Evolution of $\mathbf{b}$ during the SAC training process in the seven-qubit system. (a) The $\mathbf{b}$ values converge after 200 training episodes. For each episode, there are four measurement steps (see more details in Appendix pp2). (b) The representative RL-configured Hamiltonian schedule and the performance comparison of different schedules. We observe the RL-configured schedule has a large flattened region at the beginning. The corresponding performance of different schedules are shown in the inset. The success probabilities of the RL-configured schedule which is trained from a linear one are dramatically improved. The power-law schedule $\lambda \sim {(\tau /T)}^7$ has a slightly lower success probability compared with the RL-configured one.

Figure 6

Transferring methods in hard instance learning. The reward evolution during the learning process is shown in this plot. The bold lines denote the results of smoothing over 50 nearby date points. (a) Comparison of different transfer protocols on the seven-qubit system. We transfer the network data trained on five-qubit AQC to seven qubit here. The learning process of a direct retraining on the seven-qubit system is shown as a baseline (“purple dashed” line). The different protocols of transferring actor weights, critic weights, all network weights, and Hamiltonian schedule are presented by “blue dashed dotted,” “red solid,” “green dash dotted,” and “black dotted” lines, respectively, in this plot. (b) Training curves of transferring the weights of actor and critic networks trained on five-, six-, and seven-qubit systems to a nine-qubit system. All the transfer learning processes reach an almost optimal reward within only a few measurement steps, much less than the direct training.