Efficient method to learn sparse quantum states with optimal samples
Learning Sparse Quantum States
Computational ComplexityData Structures and Algorithms
Summary
Learning the details of complex quantum states is important but very challenging, especially when those states are mostly simple with only a few nonzero parts. The authors developed the first nearly optimal method to figure out these states using a number of samples that grows roughly with how many nonzero parts the state has. Their method also runs quickly compared to previous approaches. This work helps make it easier to understand certain quantum systems and could guide future quantum technology development.
What this means in practice
- •For quantum computing engineers: Improve quantum device calibration by efficiently determining sparse pure and mixed quantum states with fewer samples and faster algorithms.
- •For quantum algorithm developers: Design more scalable quantum algorithms by leveraging better state characterization methods for sparse quantum states.
Authors
Aniruddha Sen
Abstract
We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.