IQC Student seminar featuring Avantika Agarwal

Quantum Polynomial Hierarchies

by Avantika Agarwal

The Polynomial-Time Hierarchy (PH) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds. Quantumly, however, even though at least four definitions of quantum PH exist, it has been challenging to prove analogues for these of even basic facts from PH. We first motivate the study of quantum PH and survey what is already known about it, and finally discuss some interesting open problems related to QCPH and QPH.

This talk is based partly on Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds, a joint work with Sevag Gharibian, Venkata Koppula and Dorian Rudolph.

Location

QNC 1201