Matthew Coudron


Research Scientist, NIST, Applied and Computational Mathematics Division.

Fellow, Joint Center for Quantum Information and Computer Science (QuICS).

Adjunct Assistant Professor, University of Maryland, Department of Computer Science.


Before moving to NIST/UMD I was a postdoc in the Institute for Quantum Computing (IQC) at the University of Waterloo. Before that I completed my PhD in the Theory of Computation group at MIT, where I was advised by Peter Shor.

Along the way I also dabbled in industry, interning in the Google Quantum AI group, and later working as a Quantum Algorithms Researcher at QCWare.

Research Interests

I am broadly interested in Theoretical Computer Science. I explore Quantum Algorithms and Complexity, including topics of relevance to near-term quantum computing, and to verifying the behavior of quantum devices. I have additional interests in machine learning, and protein structure prediction. You can find out more about my interests by looking at my publications.

Here are a few things I've done recently:

  • Quantum Depth in the Random Oracle Model. [pdf]
    With Atul Singh Arora, Andrea Coladangelo, Alexandru Gheorghiu, Uttam Singh, and Hendrik Waldner.
    Symposium on the Theory of Computing (STOC), 2023

  • Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits. [pdf]
    With Nolan Coble.
    Symposium on Foundations of Computer Science (FOCS), 2021

    Conference on Quantum Information Processing (QIP), 2021

  • Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle). [pdf]
    With Sanketh Menda.
    Symposium on the Theory of Computing (STOC), 2020