Prime Factorization by Quantum Adiabatic Computation

Erik A. Lucero, R. Barends, Yulin Chen +11 more

Samuel Čarnoký

Jian Hui Lin, Zhengfeng Zhang, Junping Zhang +1 more

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.

Wen-Li Wang, Mei-Huei Tang, Shahid Hussain +1 more

Kebiao Xu, Tianyu Xie, Zhaokai Li +8 more

The adiabatic quantum computation is a universal and robust method of quantum computing. In this architecture, the problem can be solved by adiabatically evolving the quantum processor from the ground state of a simple initial Hamiltonian to that of a final one, which encodes the solution of the problem. Adiabatic quantum computation has been proved to be a compatible candidate for scalable quantum computation. In this Letter, we report on the experimental realization of an adiabatic quantum algorithm on a single solid spin system under ambient conditions. All elements of adiabatic quantum computation, including initial state preparation, adiabatic evolution (simulated by optimal control), and final state read-out, are realized experimentally. As an example, we found the ground state of the problem Hamiltonian S_{z}I_{z} on our adiabatic quantum processor, which can be mapped to the factorization of 35 into its prime factors 5 and 7.

Avinash Dash, Deepankar Sarmah, Bikash K. Behera +1 more

Factoring large integers using a quantum computer is an outstanding research problem that can illustrate true quantum advantage over classical computers. Exponential time order is required in order to find the prime factors of an integer by means of classical computation. However, the order can be drastically reduced by converting the factorization problem to an optimization one and solving it using a quantum computer. Recent works involving both theoretical and experimental approaches use Shor's algorithm, adiabatic quantum computation and quantum annealing principles to factorize integers. However, our work makes use of the generalized Grover's algorithm as proposed by Liu, with an optimal version of classical algorithm/analytic algebra. We utilize the phase-matching property of the above algorithm for only amplitude amplification purposes to avoid an inherent phase factor that prevents perfect implementation of the algorithm. Here we experimentally demonstrate the factorization of two bi-primes, 4088459 and 966887 using IBM's 5- and 16-qubit quantum processors, hence making those the largest numbers that have been factorized on a quantum device. Using the above 5-qubit processor, we also realize the factorization of a tri-prime integer 175, which had not been achieved to date. We observe good agreement between experimental and theoretical results with high fidelities. The difficulty of the factorization experiments has been analyzed and it has been concluded that the solution to this problem depends on the level of simplification chosen, not the size of the number factored. In principle, our results can be extended to factorize any multi-prime integer with minimum quantum resources.