On random circuits and their uses in compilation
- Earl Campbell, University of Sheffield
I will review work by myself and others in recent years on the use of randomization in quantum circuit optimization. I will present general results showing that any deterministic compiler for an approximate synthesis problem can be lifted to a better random compiler. I will discuss the subtle issue of what "better" means and how it is sensitive to the metric and computation task at hand. I will then review specific randomized algorithms for quantum simulations, including randomized Trotter (Su & Childs) and my group's work on the qDRIFT and SPARSTO algorithms. The qDRIFT algorithm is of particular interest as it gave the first proof that Hamiltonian simulation is possible with a gate complexity that is independent of the number of terms in the Hamiltonian. Since quantum chemistry Hamiltonians have a very large ( ~N^4) number of terms, randomization is especially useful in that setting. I will conclude by commenting on a recent Caltech paper with interesting results on the derandomization of random algorithms! Some of the relevant preprints include:
https://arxiv.org/abs/1910.06255