First-order quantum phase transition in adiabatic quantum computation

We investigate the connection between local minima in the problem Hamiltonian and first-order quantum phase transitions during adiabatic quantum computation. We demonstrate how some properties of the local minima can lead to an extremely small gap that is exponentially sensitive to the Hamiltonian parameters. Using perturbation expansion, we derive an analytical formula that cannot only predict the behavior of the gap, but also provide insight on how to controllably vary the gap size by changing the parameters. We show agreement with numerical calculations for a weighted maximum independent set problem instance.

Figure 1

(Color online) Schematic diagram of crossing global and local minima. At zeroth-order perturbation, levels do not cross (solid lines). Contribution from the second-order perturbation may cause the levels cross if the curvature of the upper level is larger than the lower one (dashed lines).

Figure 2

(Color online) An example graph of WMIS problem. The central six vertices have a weight $w_G$ and the nine outer ones are weighted $w_L$. For $w_L<2w_G$, the six central vertices make the WMIS, while every combination of three vertices each from one triangle is a smaller independent set, altogether making 27 degenerate local minima.

Figure 3

(Color online) (a) The first three energy levels for the example graph of Fig. 2 with $J=2$, $w_G=\Delta =1$, and $w_L=1.8$. (b) Functions $S$ and $M$, as defined in Eq. (8), for the same problem.

Figure 4

(Color online) The (a) position and (b) magnitude of the minimum gap for the graph of Fig. 2 with $J=2$, $w_G=\Delta =1$. The $x$ axis for both figures are the same.