25 citations · 92 across the 16 of their papers we have counts for
18 papers
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Matthew Coudron, Michael J. Gullans, Jon Nelson +2
We give a deterministic classical algorithm that estimates to additive error in time, where is a co…
A quantum lower bound for path finding in welded trees
Joseph Carolan, Andrew M. Childs, Matthew Coudron +1
In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk…
Provably Overwhelming Transformer Models with Designed Inputs
Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron
We develop an algorithm which, given a trained transformer model as input, as well as a string of tokens of length and an integer , can genera…
Hamiltonians whose low-energy states require T gates
Nolan J. Coble, Matthew Coudron, Jon Nelson +1
The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Ev…
Local Hamiltonians with no low-energy stabilizer states
Nolan J. Coble, Matthew Coudron, Jon Nelson +1
The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of lo…
Quantum algorithms and the power of forgetting
Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the na…