Nathaniel Johnston, Benjamin Lovitz, Vincent Russo, Jamie Sikora (Oct 24 2025).
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.
