On random circuits and their uses in compilation

          @misc{ scivideos_PIRSA:20100062,
            doi = {10.48660/20100062},
            url = {https://pirsa.org/20100062},
            author = {Campbell, Earl},
            keywords = {Quantum Information},
            language = {en},
            title = {On random circuits and their uses in compilation},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2020},
            month = {oct},
            note = {PIRSA:20100062 see, \url{https://scivideos.org/pirsa/20100062}}
          }
          

Abstract

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

https://arxiv.org/abs/1811.08017

https://arxiv.org/abs/1612.02689