Efficient Quantum Optimization via Dynamical Simulation

Understand

We provide several quantum algorithms for continuous optimization that do not require gradient estimation.

• Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution.
• We focus on the setting where the objective function can \emph{only} be accessed via a phase oracle.
• Our first two algorithms can find local optima of a differentiable function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian.