Publications  —  Matthew Coudron

Manuscripts

  • Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard. [pdf]
    With Joseph Carolan, Andrew Childs, Amin Shiraz Gilani, David Miloschewsky, and Supartha Podder.
    (Subsumes arXiv:2609.26712)
    In submission


  • AlphaFold reveals but sometimes distorts an organizational principle of protein folding. [pdf]
    With Madeleine F. Clore, Joseph F. Thole, Suchetan Dontha, Pramesh Sharma, Naomi Greenberg, Marie-Paule Strub, Mary Starich, Carolyn Ott, Davin Jensen, Brian F. Volkman, and Lauren L. Porter.
    In submission


  • Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits. [pdf]
    With Michael J. Gullans, Jon Nelson, Joel Rajakumar, and Shi Jie Samuel Tan.
    In submission


  • Provably Overwhelming Transformer Models with Designed Inputs. [pdf]
    With Lev Stambler and Seyed Sajjad Nezhadi.
    In submission


  • Hamiltonians whose low-energy states require Ω(n) T gates. [pdf]
    With Nolan J. Coble, Jon Nelson, and Seyed Sajjad Nezhadi.
    In submission


Publications

  • 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


  • Quantum Algorithms and the Power of Forgetting. [pdf]
    With Andrew Childs and Amin Shiraz Gilani.
    Innovations in Theoretical Computer Science Conference (ITCS), 2023


  • Local Hamiltonians with no low-energy stabilizer states. [pdf]
    With Nolan J. Coble, Jon Nelson, and Seyed Sajjad Nezhadi.
    Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), 2023


  • Approximating Output Probabilities of Shallow Quantum Circuits which are Geometrically-local in any Fixed Dimension. [pdf]
    With Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, and Sangheon Choi.
    Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), 2022


  • 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


  • Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision. [pdf]
    With William Slofstra.
    Computational Complexity Conference (CCC), 2019


  • The Communication Cost of State Conversion, with application to Entanglement-Assisted Communication Complexity. [pdf]
    With Aram Harrow.
    Computational Complexity Conference (CCC), 2019
    Conference on Quantum Information Processing (QIP), 2019



  • The Parallel-Repeated Magic Square Game is Rigid. [pdf]
    With Anand Natarajan
    Conference on Quantum Information Processing (QIP), 2017


  • Interactive Proofs with Approximately Commuting Provers. [pdf]
    With Thomas Vidick
    International Colloquium on Automata, Languages, and Programming (ICALP), 2015 (to appear)


  • Infinite Randomness Expansion with a Constant Number of Devices. [pdf]
    With Henry Yuen
    ACM Symposium on the Theory of Computing (STOC), 2014

    • Also presented at the XVII Conference on Quantum Information Processing (QIP), 2014

    • In his American Scientist article Scott Aaronson gives a great discussion of this problem, and the whole field of randomness expansion.


  • Robust Randomness Amplifiers: Upper and Lower Bounds. [pdf]
    With Thomas Vidick, and Henry Yuen
    APPROX-RANDOM 2013


  • On the Sample Complexity of Robust PCA. [pdf]
    With Gilad Lerman
    Advances in Neural Information Processing Systems (NeurIPS), 2012


Other Presentations


  • Unfrustration Condition and Degeneracy of Qudits on Trees [pdf]
    Matthew Coudron, Ramis Movassagh
    XVI Conference on Quantum Information Processing (QIP) 2013 - Poster