Algorithmic approach to adiabatic quantum optimization

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^5$ and ${10}^6$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\sim$10 iterations.

Figure 1

$A\left(s\right)$, the energy scale of $H_B$, and $B\left(s\right)$, the energy scale of $H_P$.

Figure 2

Visualization of perturbative crossings eliminated in four iterations. Each horizontal strip plots the ground-state expectation $\langle {\sigma }_z^{\left(i\right)}\rangle$, for the $i$th qubit, as a function of $s$. There are 64 strips in each plot corresponding to the 64 qubits. All qubits begin in a uniform superposition, so $\langle {\sigma }_z^{\left(i\right)}\rangle =0$ (gray) at $s=0$ on the left. The final ground state represents the MIS, with $+1$ (white) for nodes in the set, and $-1$ (black) for nodes not in the set. As $s$ increases from 0 to 1, the system localizes into low-energy minima (gray moving toward white or black). If it localizes into the global minimum, like the smooth transition in iteration 4, there is no perturbative crossing. However, if it localizes into any local minima, there is at least one crossing, which will be visible as a sudden change in many qubits, as seen in iterations 0–3. Each iteration penalizes the path to the local minima into which the ground state localized, until no crossings remain. The penalization is strong enough that different local minima are found on each iteration.

Figure 3

Number of “unsolved” problem instances as a function of the number of iterations. None of the 50 instances were solved without iteration, and all instances were solved within 13 iterations.