Learning optimal quantum models is NP-hard
arXiv:1510.02800 · doi:10.1103/PhysRevA.97.020103
Abstract
Physical modeling closes the gap between perception in terms of measurements and abstraction in terms of theoretical models. Physical modeling is a major objective in physics and is generally regarded as a creative process. How good are computers at solving this task? This question is both of philosophical and practical interest because a positive answer would allow an artificial intelligence to understand the physical world. Quantum mechanics is the most fundamental physical theory and there is a deep belief that nature follows the rules of quantum mechanics. Hence, we raise the question whether computers are able to learn optimal quantum models from measured data. Here we show that in the absence of physical heuristics, the inference of optimal quantum models cannot be computed efficiently (unless P = NP). This result illuminates rigorous limits to the extent to which computers can be used to further our understanding of nature.
References in corpus (29)
- Quantum Non-Markovianity: Characterization, Quantification and Detection
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Free randomness can be amplified
- Device-independent tests of classical and quantum dimensions
- Self-Consistent Quantum Process Tomography
- A lower bound on the dimension of a quantum system given measured data
- Robust Calibration of a Universal Single-Qubit Gate-Set via Robust Phase Estimation
- Lifts of convex sets and cone factorizations
- Imperfect measurements settings: implications on quantum state tomography and entanglement witnesses
- Robust Extraction of Tomographic Information via Randomized Benchmarking
- Characterizing Universal Gate Sets via Dihedral Benchmarking
- Robust, self-consistent, closed-form tomography of quantum logic gates on a trapped ion qubit
- Positive semidefinite rank
- Practical, Reliable Error Bars in Quantum Tomography
- Optimization of a solid-state electron spin qubit using Gate Set Tomography
- Self-consistent tomography of the state-measurement Gram matrix
- Extracting dynamical equations from experimental data is NP-hard
- Characterizing finite-dimensional quantum behavior
- Minimum Dimension of a Hilbert Space Needed to Generate a Quantum Correlation
- When quantum tomography goes wrong: drift of quantum sources and other errors
- Detecting correlated errors in SPAM tomography
- Rank-based model selection for multiple ions quantum tomography
- Binary Constraint System Games and Locally Commutative Reductions
- Quantum learning of classical stochastic processes: The Completely-Positive Realization Problem
- Representing probabilistic data via ontological models
- No quantum realization of extremal no-signaling boxes
- Quantum Model Averaging
- Compressibility of positive semidefinite factorizations and quantum models
- Global Completability with Applications to Self-Consistent Quantum Tomography
Cited by in corpus (4)
- Compressibility of positive semidefinite factorizations and quantum models
- Recommender systems inspired by the structure of quantum theory
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Effects of Li Doping on Superconducting Properties of Citrate Gel Prepared Y1-xLixBa2Cu3O7-d Compound