4 papers
Quantum Search with In-Place Queries
Blake Holman, Ronak Ramachandran, Justin Yirka
Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are uni…
A Note on the Complexity of the Spectral Gap Problem
Justin Yirka
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class : polynomial time with access to a logarithmic number of QMA q…
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…
Even quantum advice is unlikely to solve PP
Justin Yirka
We give a corrected proof that if PP BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson 2006 arXiv:cs/0504048]. This recovers the rela…