Showing 2024Show all
2 papers · 1 filter
quant-ph2024
A Criterion for Post-Selected Quantum Advantage
Chaitanya Karamchedu, Matthew Fox, Daniel Gottesman
Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not…
cs.CC2024
A Refinement of the McCreight-Meyer Union Theorem
Matthew Fox, Chaitanya Karamchedu
Using properties of Blum complexity measures and certain complexity class operators, we exhibit a total computable and non-decreasing function such that for all…