Matthew Coudron

According to our database, Matthew Coudron authored at least 15 papers between 2012 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Hamiltonians whose low-energy states require Ω(n) T gates.

Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi

CoRR, 2023

Local Hamiltonians with No Low-Energy Stabilizer States.

Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi

Proceedings of the 18th Conference on the Theory of Quantum Computation, 2023

Quantum Depth in the Random Oracle Model.

Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Quantum Algorithms and the Power of Forgetting.

Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension.

Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, Matthew Coudron

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

2021

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits.

Nolan J. Coble, Matthew Coudron

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.

Nolan J. Coble, Matthew Coudron

CoRR, 2020

Computations with greater quantum depth are strictly more powerful (relative to an oracle).

Matthew Coudron, Sanketh Menda

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision.

Matthew Coudron, William Slofstra

Proceedings of the 34th Computational Complexity Conference, 2019

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion.

Matthew Coudron, Aram W. Harrow

Proceedings of the 34th Computational Complexity Conference, 2019

2017

Entangled protocols and non-local games for testing quantum systems.

Matthew Coudron

PhD thesis, 2017

2015

Interactive Proofs with Approximately Commuting Provers.

Matthew Coudron, Thomas Vidick

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Infinite randomness expansion with a constant number of devices.

Matthew Coudron, Henry Yuen

Proceedings of the Symposium on Theory of Computing, 2014

2013

Robust Randomness Amplifiers: Upper and Lower Bounds.

Matthew Coudron, Thomas Vidick, Henry Yuen

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

On the Sample Complexity of Robust PCA.

Matthew Coudron, Gilad Lerman

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012