Nengkun Yu (Stony Brook): A Tale of Quantum State Complexity and Learning Complexity

Testing the properties of unknown quantum states is fundamental to understanding quantum devices. For a general unknown state, an exponential number of copies is needed. In the low-complexity region, we establish the connection between the state's complexity and the sample complexity of learning it. Furthermore, we show that one can learn nontrivial information from a single copy if the state has low complexity. We derive the optimal learning strategy for quantum Markov states.