Compilation of product-formula Hamiltonian simulation via reinforcement
  learning
Lea M. Trenkwalder Eleanor Scerri Thomas E. O'Brien Vedran Dunjko
Hamiltonian simulation is believed to be one of the first tasks where quantum
computers can yield a quantum advantage. One of the most popular methods of
Hamiltonian simulation is Trotterization, which makes use of the approximation
$e^{i\sum_jA_j}\sim \prod_je^{iA_j}$ and higher-order corrections thereto.
However, this leaves open the question of the order of operations (i.e. the
order of the product over $j$, which is known to affect the quality of
approximation). In some cases this order is fixed by the desire to minimise the
error of approximation; when it is not the case, we propose that the order can
be chosen to optimize compilation to a native quantum architecture. This
presents a new compilation problem -- order-agnostic quantum circuit
compilation -- which we prove is NP-hard in the worst case. In lieu of an
easily-computable exact solution, we turn to methods of heuristic optimization
of compilation. We focus on reinforcement learning due to the sequential nature
of the compilation task, comparing it to simulated annealing and Monte Carlo
tree search. While two of the methods outperform a naive heuristic,
reinforcement learning clearly outperforms all others, with a gain of around
12% with respect to the second-best method and of around 50% compared to the
naive heuristic in terms of the gate count. We further test the ability of RL
to generalize across instances of the compilation problem, and find that a
single learner is able to solve entire problem families. This demonstrates the
ability of machine learning techniques to provide assistance in an
order-agnostic quantum compilation task.