Showing 2024Show all
2 papers · 1 filter
quant-ph2024
Oracle Separations for the Quantum-Classical Polynomial Hierarchy
Avantika Agarwal, Shalev Ben-David
We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum…
cs.CC2024
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1
The Polynomial-Time Hierarchy () is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…