  We study a variant of the quantum approximate optimization algorithm [ E.
Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with slightly different
parametrization and 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 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 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 E. Crosson, E. Farhi, C. Yen-Yu Lin, H.-H. Lin, and P. Shor (CFLLS)
[arXiv:1401.7320]. When tested on the full set, the parameters that we find
produce 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.
