The Learnability of Unknown Quantum Measurements
arXiv:1501.00559
Abstract
Quantum machine learning has received significant attention in recent years, and promising progress has been made in the development of quantum algorithms to speed up traditional machine learning tasks. In this work, however, we focus on investigating the information-theoretic upper bounds of sample complexity - how many training samples are sufficient to predict the future behaviour of an unknown target function. This kind of problem is, arguably, one of the most fundamental problems in statistical learning theory and the bounds for practical settings can be completely characterised by a simple measure of complexity. Our main result in the paper is that, for learning an unknown quantum measurement, the upper bound, given by the fat-shattering dimension, is linearly proportional to the dimension of the underlying Hilbert space. Learning an unknown quantum state becomes a dual problem to ours, and as a byproduct, we can recover Aaronson's famous result [Proc. R. Soc. A 463:3089-3144 (2007)] solely using a classical machine learning technique. In addition, other famous complexity measures like covering numbers and Rademacher complexities are derived explicitly. We are able to connect measures of sample complexity with various areas in quantum information science, e.g. quantum state/measurement tomography, quantum state discrimination and quantum random access codes, which may be of independent interest. Lastly, with the assistance of general Bloch-sphere representation, we show that learning quantum measurements/states can be mathematically formulated as a neural network. Consequently, classical ML algorithms can be applied to efficiently accomplish the two quantum learning tasks.
References in corpus (32)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- Quantum state tomography via compressed sensing
- Quantum random access memory
- The quest for a Quantum Neural Network
- Quantum Data Fitting
- Quantum algorithms for supervised and unsupervised machine learning
- Correcting Quantum Errors with Entanglement
- Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
- Quantum states and generalized observables: a simple proof of Gleason's theorem
- Optimal quantum learning of a unitary transformation
- Quantum Algorithm for Linear Regression
- Entanglement-Assisted Capacity of Quantum Multiple-Access Channels
- Catalytic quantum error correction
- Entanglement-assisted communication of classical and quantum information
- Quantum learning robust to noise
- Quantum POMDPs
- High performance entanglement-assisted quantum LDPC codes need little entanglement
- Improved Bounds on Quantum Learning Algorithms
- (4,1)-Quantum Random Access Coding Does Not Exist
- One-shot entanglement-assisted quantum and classical communication
- When do Local Operations and Classical Communication Suffice for Two-Qubit State Discrimination?
- Hidden Quantum Markov Models and non-adaptive read-out of many-body states
- Quantum learning of coherent states
- Quantum learning algorithms for quantum measurements
- Quantum learning of classical stochastic processes: The Completely-Positive Realization Problem
- Quantum algorithms for topological and geometric analysis of big data
- Quantum computing for pattern classification
- Quantum versus Classical Learnability
- On Learnability, Complexity and Stability
- Robust optimal quantum learning without quantum memory