Natural evolution strategies and variational Monte Carlo
This work provides a theoretical synthesis for optimization methods, with potential applications in combinatorial problems like Max-Cut, but it is incremental as it builds on existing algorithms.
The paper introduces quantum natural evolution strategies as a geometric framework that unifies various quantum and classical black-box optimization algorithms, and demonstrates that this approach can achieve competitive approximation ratios for Max-Cut compared to standard heuristics, though with higher computational cost.
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.