Training a quantum optimizer
Open Access
- 10 August 2016
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 94 (2), 022309
- https://doi.org/10.1103/physreva.94.022309
Abstract
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.Keywords
Funding Information
- Aspen Center for Physics
- National Science Foundation (PHY-1066293)
This publication has 14 references indexed in Scilit:
- Tunneling and Speedup in Quantum Optimization for Permutation-Symmetric ProblemsPhysical Review X, 2016
- Heavy Tails in the Distribution of Time to Solution for Classical and Quantum AnnealingPhysical Review Letters, 2015
- Progress towards practical quantum variational algorithmsPhysical Review A, 2015
- Experimental signature of programmable quantum annealingNature Communications, 2013
- Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problemsPhysical Review E, 2011
- Anderson localization makes adiabatic quantum optimization failProceedings of the National Academy of Sciences of the United States of America, 2010
- First-Order Phase Transition in the Quantum Adiabatic AlgorithmPhysical Review Letters, 2010
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- An efficient method for finding the minimum of a function of several variables without calculating derivativesThe Computer Journal, 1964