Publications  —  Matthew Coudron

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
  

• 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
  

• Trading locality for time: certifiable randomness from low-depth circuits. [pdf]
  With Jalex Stark and Thomas Vidick.
  Communications in Mathematical Physics, 2021
  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

• Testing Untrusted Devices via Quantum Mechanics
  

  • Charles River Science of Information Day, 2014
    

  • Astronaut Scholars Technical Conference, 2014
    

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