Training a quantum optimizer

We study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a “training set” of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.

Figure 1

Dashed curves show ${\theta }^X$ and solid curves show ${\theta }^Z$. Four different learned schedules are shown; the format such as $X621\_3.64$ indicates that this curve is ${\theta }^X$, for a schedule started using initial schedule 6; the 21 indicate the particular training set and run (these numbers are not important, as they are just keys to a random number generator but they differentiate the three different curves that use initial schedule 3); the $3.64$ indicates the average improvement for that schedule. The $Xavg,Zavg$ curves show the parameters averaged over those four schedules.

Figure 2

$x$ axis labels different instances. $y$ axis shows overlap. Dashed curve is from learned schedule while solid curve is for optimized anneal. Instance numbers differ from CFLLS because instances are sorted by overlap for optimized anneal.

Figure 3

Ratio of averages for eight different subsets of the MAX-2-SAT instances with $N=20$, chosen by binning by hardness for $L(80,1,1)$. We compare various schedules to $L(10,1,1)$. Different colors label different schedules. On hardest instances (those on the left side of the graph), 154 has highest ratio (i.e., 154 is uppermost of curves on left side of graph), followed by $L(20,1,1),L(30,1,1),L(10,1,1),L(40,1,1),L(80,1,1)$ in sequence.

Figure 4

Ratio of averages for eight different subsets of the MAX-3-SAT instances with $N=20$, chosen by binning by hardness for $L(80,1,1)$. We compare various schedules to $L(10,1,1)$. 154 and 157 are both learned schedules. Different colors label different schedules. On hardest instances, 157 has highest ratio, followed by $154,L(20,1,1),L(10,1,1),L(40,1,1),L(80,1,1)$ in sequence.

Figure 5

Graph of the toy model considered for the case of $K=6$ with $N=12$ spins. The edges indicate ferromagnetic couplings between spins. All but one spin of the inner ring has positive magnetic fields (indicated by $+$ symbols), while all the outer spins have negative fields (indicated by $-$) symbols applied in the $z$ direction.