PIRSA:20100062

On random circuits and their uses in compilation

Campbell, E. (2020). On random circuits and their uses in compilation. Perimeter Institute. https://pirsa.org/20100062

Campbell, Earl. On random circuits and their uses in compilation. Perimeter Institute, Oct. 28, 2020, https://pirsa.org/20100062 

          @misc{ pirsa_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},
            year = {2020},
            month = {oct},
            note = {PIRSA:20100062 see, \url{https://pirsa.org}}
          }

Earl Campbell

University of Sheffield

Talk number
PIRSA:20100062
Collection
Talk Type
Subject
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