On random circuits and their uses in compilation

October 28, 2020 PIRSA:20100062 Scientific Series Quantum Information

DOI10.48660/20100062

Series: Perimeter Institute Quantum Discussions

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}}
}

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