Natural Evolution Strategies and Quantum Approximate Optimization
Tianchen Zhao, Giuseppe Carleo, James Stokes, Shravan Veerapaneni
arXiv, 2020 8 citations
Abstract
A notion of quantum natural evolution strategies is introduced, which provides a geometric synthesis of a number of known quantum/classical algorithms for performing classical black-box optimization. Recent work of Gomes et al. [2019] on heuristic combinatorial optimization using neural quantum states is pedagogically reviewed in this context, emphasizing the connection with natural evolution strategies. The algorithmic framework is illustrated for approximate combinatorial optimization problems, and a systematic strategy is found for improving the approximation ratios. In particular it is found that natural evolution strategies can achieve approximation ratios competitive with widely used heuristic algorithms for Max-Cut, at the expense of increased computation time.
Summary
Applies natural evolution strategies to quantum approximate optimization, achieving competitive Max-Cut approximation ratios via neural quantum states.
Key Contributions
- Application of NES to quantum approximate optimization (QAOA) problems
- Systematic strategy for improving approximation ratios in combinatorial optimization
- Competitive Max-Cut results via neural quantum states with NES
Cite this paper if your work involves natural evolution strategies for QAOA, black-box optimization for QAOA, or gradient-free optimization of variational quantum algorithms.
FAQ
- What are natural evolution strategies in the context of quantum optimization?
- Natural evolution strategies (NES) provide a geometric framework for black-box optimization that unifies several known quantum and classical optimization algorithms, leveraging the Fisher information metric for principled parameter updates.
- How does this approach compare to standard QAOA?
- Unlike standard QAOA which uses quantum circuits, this approach uses neural quantum states optimized via NES, achieving competitive Max-Cut approximation ratios through a purely classical simulation with increased computation time.
- Can NES be applied to problems beyond Max-Cut?
- Yes. The framework is general for approximate combinatorial optimization, and the systematic strategy for improving approximation ratios applies to any problem expressible as a quadratic unconstrained binary optimization (QUBO).
- What is the relationship between this paper and the ML:ST journal version?
- This arXiv preprint (2020) was later published in Machine Learning: Science and Technology (2021) under the title "Natural Evolution Strategies and Variational Monte Carlo" with extended content.
Keywords
natural evolution strategies QAOA
quantum approximate optimization natural evolution strategies
gradient-free QAOA
variational quantum algorithms optimization
black-box optimization quantum circuits
Related Papers
BibTeX
@article{zhao2020nes_qaoa,
title={Natural Evolution Strategies and Quantum Approximate Optimization},
author={Zhao, Tianchen and Carleo, Giuseppe and Stokes, James and Veerapaneni, Shravan},
journal={arXiv preprint arXiv:2005.04447},
year={2020}
}
Recommended Citation Contexts
- Black-box optimization of QAOA circuit parameters via natural evolution strategies removes the requirement for analytical gradients (Zhao et al., 2020).