37 citations · 65 across the 8 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.CC2024★ 1 cited
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…
quant-ph2024★ 1 cited
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…
quant-ph2024★ 1 cited
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…