The Algorithmic Cookbook of Quantum Science: Quantum and Classical Recipes for Computation

Abstract

Since the dawn of science, computation and physics have evolved alongside each other, both driven by a shared quest to solve problems and calculate properties of the natural world. Today, this symbiotic relationship is epitomized in quantum information science, which proposes to use quantum mechanics to solve hard computational problems and develop new paradigms of communication and cryptography. Yet often absent from these developments is a clear, human-interpretable understanding, with many quantum protocols built from inherently quantum concepts (e.g., entanglement, superposition) that defy our classical line of thought and muddle the search for efficient quantum algorithms. Here we show that this search need not be so opaque: simple mathematical tools, namely polynomials and their fundamental theorems, in unison with concepts from classical computing, provide a powerful framework for the design of quantum algorithms. We develop this framework and use it to construct an assortment of quantum algorithms, including methods for quantum simulation, parallel computing, randomized algorithms, and continuousvariable quantum hardware. In illuminating this framework, we find a striking bidirectional flow: just as classical concepts inspire new quantum algorithms, so too can quantum mechanical insights bring about novel methods of classical computing. In this reverse direction, we adopt inherently quantum concepts, such as random compilation and bosonic symmetry, to develop new classical methods, with applications in simulating quantum systems and designing robust neural networks. In aggregate, this thesis provides a compendium of algorithmic techniques for probing quantum systems and solving hard problems, using both quantum and classical tools—an “algorithmic cookbook”—predicated on deep connections between these two domains. The recipes presented here aim to demystify black boxes of quantum information science, and provide a valuable resource for future developments.