The Incredible Shrinking Quantum Circuit

  • Alex Bocharov | Microsoft

This is a story of breakthroughs in quantum circuit synthesis, that brought down the cost of the resulting circuits by 5 orders of magnitude in short 9 months of 2012, and provided specific theoretical guarantees of the cost that are linear in log precision instead of being roughly quartic in log precision.

The story is rife with results, conjectures and open problems in the fields of group theory, algebra and number theory. Lie algebras, quaternions, algebraic numbers, integer lattices, Diophantine equations were just some means to the end to achieve the year end 2012 results. The road ahead is likely to require more of the same – but in progressively higher dimensions.

Series: Microsoft Research Talks