Quantum Polynomial Hierarchies: Karp-Lipton and Lower Bounds

CS/Math Seminar - Avantika Agarwal, IQC 1201 IN PERSON + ZOOM

The Polynomial-Time Hierarchy (PH) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, even though at least four definitions of quantum PH exist, it has been challenging to prove analogues for these or even basic facts from PH. This work studies three quantum-verifier based generalizations of PH, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings (QCPH) and quantum mixed states (QPH) as proofs, and one of which is new to this work, utilizing quantum pure states (pureQPH) as proofs. We first talk about solutions to open problems from GSSSY22 which include a collapse theorem for QCPH and a quantum-classical Karp-Lipton. We then talk about our results for pureQPH, including lower bounds relating QCPH to pureQPH, and finally discuss some interesting open problems related to QCPH. This talk is based on https://arxiv.org/abs/2401.01633, a joint work with Sevag Gharibian, Venkata Koppula and Dorian Rudolph.

Join Zoom Meeting
https://uwaterloo.zoom.us/j/96245159834?pwd=SndYUkxDdGVvYWNab1pVYmRLaHVjQT09

Meeting ID: 962 4515 9834
Passcode: 941574

Add event to calendar