Decomposition and gluing for adiabatic quantum optimization
Micah Blake McCurdy, Jeffrey Egger, Jordan Kyriakidis · Quantum Information and Computation · 2014
Farhi and others~\cite{Farhi} have introduced the notion of solving NP problems using adiabatic quantum computers. We discuss an application of this idea to the problem of integer factorization, together with a technique we call \emph{gluing} which can be used to build adiabatic models of interesting problems. Although adiabatic quantum computers already exist, they are likely to be too small to directly tackle problems of interesting practical sizes for the foreseeable future. Therefore, we discuss techniques for decomposition of large problems, which permits us to fully exploit such hardware as may be available. Numerical results suggest that even simple decomposition techniques may yield acceptable results with subexponential overhead, independent of the performance of the underlying device.