The complexity of perfect quantum state classification
Abstract:
The problem of quantum state classification asks how well one can classify a given state when chosen from a known set. We introduce the concept of learning width, which asks what is the minimum number of guesses one must make before being able to guess the state without error. We show that computing the learning width reduces to a matrix decomposition problem known as factor width, and establish that both of these problems are NP-complete. We also show certain variants of this problem can be solved in polynomial time, for example testing if the learning width is below a fixed constant.
Authors:
- Nathaniel Johnston
- Benjamin Lovitz
- Vincent Russo
- Jamie Sikora
Download:
- Preprint from arXiv:2510.20789 [quant-ph]
Cite as:
- N. Johnston, B. Lovitz, V. Russo, and J. Sikora. The complexity of perfect quantum state classification. E-print: arXiv:2510.20789 [quant-ph], 2025.