Matthew Coudron


About Me

I am a postdoc at the Institute for Quantum Computing at the University of Waterloo. I completed my PhD in the Theory of Computation group at MIT, where I was advised by Peter Shor. Before coming to MIT I was a student at the University of Minnesota, where I obtained my BS in Mathematics. 

Research Interests

I am broadly interested in Theoretical Computer Science. I study 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 semi-definite programming. 



  • Complexity lower bounds for approximating entangled games to high precision.
    Matthew Coudron, William Slofstra. 
    Computational Complexity Conference (CCC), 2019 - To Appear


  • The Communication Cost of State Conversion, with application to Entanglement-Assisted Communication Complexity.
    Matthew Coudron, Aram Harrow.
    Computational Complexity Conference (CCC), 2019 - To Appear
    Conference on Quantum Information Processing (QIP), 2019

  • Trading locality for time: certifiable randomness from low-depth circuits.[pdf]
    Matthew Coudron, Jalex Stark, Thomas Vidick. 
    Conference on Quantum Information Processing (QIP), 2019

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

  • Interactive Proofs with Approximately Commuting Provers. [pdf] 
    Matthew Coudron, Thomas Vidick. 
    International Colloquium on Automata, Languages, and Programming (ICALP), 2015
    Conference on Quantum Information Processing (QIP), 2016 

  • Infinite Randomness Expansion with a Constant Number of Devices. [pdf] 
    Matthew Coudron, Henry Yuen. 
    Symposium on the Theory of Computing (STOC), 2014 
    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] 
    Matthew Coudron, Thomas Vidick, Henry Yuen. 

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

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

Other Presentations

  • Testing Untrusted Devices via Quantum Mechanics. 

    • Astronaut Scholars Technical Conference, 2014 

  • Introduction to Quantum Error Correcting Codes. 

    • Astronaut Scholars Technical Conference, 2012 

Page generated 2016-10-11 00:55:55 EDT, by jemdoc