25 citations · 92 across the 16 of their papers we have counts for
17 papers · 1 filter
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…
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…
Quantum Depth in the Random Oracle Model
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron +3
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, w…