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

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.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Physics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Martyn, John Michael

Advisor dc:contributor.advisor

• Chuang, Isaac L.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/164167

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/164167