Driver Hamiltonians for constrained optimization in quantum annealing

One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.

Figure 1

Magnetization $M_z=\langle {\sum }_i{\sigma }_i^z\rangle$ of the global ground state of the $XY$ driver as a function of the ratio $B/J$ for periodic chains of various sizes. Ground states with negative magnetization $M_z<0$ are attained similarly for negative $B$ values. The inset shows magnetization as a function of the ratio $-E_0/nJ$, where $E_0/n$ is the ground-state energy density.

Figure 2

Required connectivities in the GI problem: an eight-vertex example. Shown on the left are connectivities in the standard approach. On the right is partial removal of connectivities through the use of driver $XY$ Hamiltonians.

Figure 3

Different hopping term types in the graph isomorphism driver: an eight-vertex example. The solid (red) rectangles denote the particles involved in a single hopping term. The dashed (blue) rectangle denotes a hopping term in the case of partial removal of the constraints. (a) An open circle denotes a down spin (or a vacant site), whereas a closed circle denotes an up spin (or an occupied site). A hopping term here consists of four-body terms. (b) An $n\times \lceil {log}_{2}n\rceil$ grid with local hopping terms swapping neighboring rows. (c) An $n$-qudit setup with $n$ levels each. The hopping terms are two-body and local, swapping the modes of neighboring particles.