5 papers · 1 filter
Learning Gaussian optical states with quantum computers
Spencer Dimitroff, John Kallaugher, Ashe Miller +1
Recent results have established dramatic advantages in learning properties of quantum states when a quantum computer is available to process or jointly measure multiple copies of t…
Hamiltonian Locality Testing via Trotterized Postselection
John Kallaugher, Daniel Liang
The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian is -close to being -local (…
How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
John Kallaugher, Ojas Parekh, Nadezhda Voronova
A series of work [GKK+08, Kal22, KPV24] has shown that asymptotic advantages in space complexity are possible for quantum algorithms over their classical counterparts in the stream…
Complexity Classification of Product State Problems for Local Hamiltonians
John Kallaugher, Ojas Parekh, Kevin Thompson +2
Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A…
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh, Nadezhda Voronova
While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work…