[GS_C_QI] Quantum Testing, Learning, and Estimation: Sample and Query Complexity
ABSTRACT
I will present some of my recent work on quantum testing, learning, and estimation. For learning, we initiate the study of quantum junta states, the quantum analogues of classical junta distributions. As a corollary, our junta-state learning algorithm yields an improved algorithm for learning (QAC^0) circuits, a canonical class of constant-depth quantum circuits. For completeness, we also present an algorithm for tolerant testing of quantum junta states. This algorithm is optimal up to polylogarithmic factors when the junta size is constant. For estimation, we provide a new algorithm for estimating a parameterized Tsallis relative entropy, which reduces to the Hellinger distance in a particular parameter regime. Within the talk, I will briefly discuss the relationships among testing, learning, and estimation, as well as conversions between the query-access and sample-access models.
