Source-linked AI summary
A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
Xinhua Peng, Zeyang Liao, Nanyang Xu, Gan Qin, Xianyi Zhou, Dieter Suter, Jiangfeng Du
TL;DR
The paper presents an adiabatic quantum algorithm for integer factorization, motivated by hard optimization problems. Its NMR implementation encodes factors 3 and 7 in the final state, while simulations suggest quadratic runtime growth.
Problem
Many numerical problems can be formulated as hard optimization problems, motivating quantum adiabatic computation as a possible solution approach.
Source: p. 1Method
The algorithm uses adiabatic evolution from a known-ground-state initial Hamiltonian to a problem Hamiltonian encoding the factorization solution, implemented with nuclear spin qubits.
Source: p. 1Results
The final state had high occupation probability on |111>, encoding p=3 and q=7; simulations suggest runtime grows quadratically with problem size.
Source: pp. 3–4Takeaways & Limitations
The method uses significantly fewer qubits than Shor’s algorithm, and simulations indicate it may be efficient through 16-bit integers.
Source: p. 4
Abstract
from arXiv · showhide
We propose an adiabatic quantum algorithm capable of factorizing numbers, using fewer qubits than Shor's algorithm. We implement the algorithm in an NMR quantum information processor and experimentally factorize the number 21. Numerical simulations indicate that the running time grows only quadratically with the number of qubits.