2025/10/23 by Nathaniel Johnston, Benjamin Lovitz, Johnston, Nathaniel +5
Computer Science · #Complexity and Algorithms in Graphs #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2510.20789
openalex publication_date 2025/10/23 · openalex created_date 2025/10/25 · openalex updated_date 2026/07/28
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.