QUASAR weekly seminar talk.

• Date: Friday, October 31, 2025
• Time: 1:00-2:00 PM ET
• Location: STEM Complex
• Speaker: Ben Lovitz
• Affiliation: Concordia University

Abstract

The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of k-learnability, which captures the ability to identify the correct state using at most k guesses, with zero error. We show that deciding whether a given family of states is k-learnable can be solved via semidefinite programming. When there are n states, we present polynomial-time (in n) algorithms for determining k-learnability for two cases: when k is a fixed constant or the dimension of the states is a fixed constant. When both k and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical k-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime. Based on joint work with Nathaniel Johnston, Vincent Russo, and Jamie Sikora (arXiv:2510.20789).