Domain Nucleation as a Failure Mode of Adiabatic Quantum Computation*

The bottleneck limiting the runtime of an adiabatic quantum algorithm is generically a quantum phase transition point for the computer's qubits. We show that if the qubits undergo this phase transition simultaneously as in a continuous quantum phase transition in a homogeneous system, then the runtime is only polynomial in the number of qubits. However, we next show that if the qubits have finite range interactions in 3 or fewer dimensions, then it is much more likely that they undergo this phase transition in piecemeal fashion by nucleating domains. The runtime then grows faster than any polynomial, though it often remains subexponential. We show this via a scaling argument based on the Suzuki-Trotter mapping. Our argument extends previous similar ones in that it explicitly shows how domain excitations typically must lead to computational errors as inter-domain couplings typically are insufficient to allow the excitations to reconcile with one another and lead back to a valid solution. We close by remarking on ways to minimize domain nucleation, identifying algorithms with continuous symmetries and/or nearly fully-connected topologies as promising.