Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.

On random circuits and their uses in compilation

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

Scientific Areas: 
PIRSA Number: 


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: