Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds

Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1

The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…