37 citations · 65 across the 8 of their papers we have counts for
9 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…
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…
The Entangled Quantum Polynomial Hierarchy Collapses
Sabee Grewal, Justin Yirka
We introduce the entangled quantum polynomial hierarchy as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entang…
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…
Qubit-efficient entanglement spectroscopy using qubit resets
Justin Yirka, Yigit Subasi
One strategy to fit larger problems on NISQ devices is to exploit a tradeoff between circuit width and circuit depth. Unfortunately, this tradeoff still limits the size of tractabl…
Oracle complexity classes and local measurements on physical Hamiltonians
Sevag Gharibian, Stephen Piddock, Justin Yirka
The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of estimating ground state energies of local Hamiltonians. Perhaps surprisingly, [Ambainis, CCC 2014] showed…
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Sevag Gharibian, Miklos Santha, Jamie Sikora +2
The polynomial-time hierarchy () has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as $\m…
The complexity of simulating local measurements on quantum systems
Sevag Gharibian, Justin Yirka
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class P^QM…