Error regions in quantum state tomography: computational complexity caused by geometry of quantum states
arXiv:1608.00374 · doi:10.1088/1367-2630/aa7ce9
Abstract
The outcomes of quantum mechanical experiments are inherently random. It is therefore necessary to develop stringent methods for quantifying the degree of statistical uncertainty about the results of quantum experiments. For the particularly relevant task of quantum state estimation, it has been shown that a significant reduction in uncertainty can be achieved by taking the positivity of quantum states into account. However -- the large number of partial results and heuristics notwithstanding -- no efficient general algorithm is known that produces an optimal uncertainty region from experimental data and the prior constraint of positivity. Here, we make this problem precise and show that the general case is NP-hard. Our result leaves room for the existence of efficient approximate solutions, and therefore does not yet imply that the practical task of quantum uncertainty quantification is intractable. However, it does show that there exists a non-trivial trade-off between optimality and computational efficiency for error regions. We prove two versions of the result: One for frequentist and one for Bayesian statistics.
major revision of the presentation and Thiago O. Maciel added as an author, comments very welcome
References in corpus (9)
- Entanglement detection
- Scalable multi-particle entanglement of trapped ions
- Efficient quantum state tomography
- Direct Fidelity Estimation from Few Pauli Measurements
- Measuring measurement
- Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
- Experimental quantum state tomography of a solid state qubit
- Computational Lower Bounds for Sparse PCA
- Robust error bars for quantum tomography
Cited by in corpus (14)
- Experimentally exploring compressed sensing quantum tomography
- Continuous phase-space representations for finite-dimensional quantum states and their tomography
- Wigner tomography of multispin quantum states
- A comparative study of estimation methods in quantum tomography
- Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
- Bound entangled states fit for robust experimental verification
- Numerical study of Wigner negativity in one-dimensional steady-state resonance fluorescence
- Behavior of the maximum likelihood in quantum state tomography
- Efficient Bayesian credible-region certification for quantum-state tomography
- Bayesian error regions in quantum estimation I: analytical reasonings
- Versatile fidelity estimation with confidence
- Probing Bayesian credible regions intrinsically: a feasible error certification for physical systems
- Comparison of confidence regions for quantum state tomography
- Bayesian error regions in quantum estimation II: region accuracy and adaptive methods