Adiabatic quantum algorithm for factorization with growing minimum energy gap. Issue 1 (24th January 2021) - Yan, Bao; Jiang, Haocong; Gao, Ming; Duan, Qianheng; Wang, Hong; Ma, Zhi
Abstract: We present a new quantum algorithm for factoring integers in the framework of adiabatic quantum computation. For an n bit integer with only one pair of equal bit factors we consider, the qubits needed in our algorithm is less than n, which makes it the most qubit‐saving quantum factoring algorithm to our knowledge. Furthermore, we have numerically studied the scaling law for the minimum energy gap and entanglement entropy acrossing quantum phase transition. We have witnessed an increasing minimum gap scaling law which indicates the potential ability of an exponential quantum speedup with respect to the fastest classical factoring algorithm. In addition, the linear scaling law of the entanglement entropy provides the evidence that the system can provide large amount of entanglement which is the main resource for the quantum speedup.