Building Better Quantum Algorithms with Physics

  • Gaung-Hao Low | Massachusetts Institute of Technology

The potential for meaningful experimental realizations of quantum algorithms is the source of much excitement in this dawning era of the small digital quantum computer. As such, attention is increasingly focused upon practical concerns regarding constant factors in space and gate complexities, in contrast to the traditional asymptotic analyses. One predominant approach to compiling quantum algorithms into the fewest qubits and quantum gates revolves around sophisticated mathematical optimization, and the translation of digital classical circuits into reversible quantum logic. Thus, it would be surprising if physical intuition were at all relevant to this abstract task. In contrary, I demonstrate with a few diverse but accessible motivating examples of how a rigorous understanding of the simplest physics — rotations on a sphere — leads to an unexpected and highly efficient form of quantum compilation. This culminates in a quantum algorithm for Hamiltonian simulation with a query complexity optimal in all parameters, in both asymptotic and non-asymptotic limits, and an extraordinarily small overhead.

Series: Microsoft Research Talks