6 papers
On State Distinguishing Without Inverse Queries
Emma Wang, Joseph Carolan, Andrew M. Childs
In the quantum state distinguishing problem, an algorithm is given copies of a state or separated by trace distance , and tasked with deciding…
Optimal Quantum Algorithms for Ordered Search
Joseph Carolan, Andrew M. Childs
Ordered search is the problem of locating a target element in a sorted list of size using comparison queries. Classically, binary search requires querie…
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…
Quantum lower bounds for simulating fluid dynamics
Abtin Ameri, Joseph Carolan, Andrew M. Childs +1
Developing quantum algorithms to simulate fluid dynamics has become an active area of research, as accelerating fluid simulations could have significant impact in both industry and…
Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak +1
Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses $\lceil \log_{2}{n}\…
Succinct Fermion Data Structures
Joseph Carolan, Luke Schaeffer
Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of im…