Quantum learning robust to noise

Abstract

Noise is often regarded as anathema to quantum computation, but in some settings it can be an unlikely ally. We consider the problem of learning the class of $n$-bit parity functions by making queries to a quantum example oracle. In the absence of noise, quantum and classical parity learning are easy and almost equally powerful, both information-theoretically and computationally. We show that in the presence of noise this story changes dramatically. Indeed, the classical learning problem is believed to be intractable, while the quantum version remains efficient. Depolarizing the qubits at the oracle's output at any constant nonzero rate does not increase the computational (or query) complexity of quantum learning more than logarithmically. However, the problem of learning from corresponding classical examples is the Learning Parity with Noise (LPN) problem, for which the best known algorithms have superpolynomial complexity. This creates the possibility of observing a quantum advantage with a few hundred noisy qubits. The presence of noise is essential for creating this quantum-classical separation.

5 pages, 1 figure

References in corpus (3)

• Quantum support vector machine for big data classification
• Quantum algorithms for supervised and unsupervised machine learning
• Improved Bounds on Quantum Learning Algorithms

Cited by in corpus (34)

• Quantum machine learning: a classical perspective
• Demonstration of quantum advantage in machine learning
• Circuit-Based Quantum Random Access Memory for Classical Data
• Quantum Software Engineering: Landscapes and Horizons
• On the Quantum versus Classical Learnability of Discrete Distributions
• Vulnerability of quantum classification to adversarial perturbations
• Learning with Errors is easy with quantum samples
• A hybrid quantum-classical approach to mitigating measurement errors
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Machine learning \& artificial intelligence in the quantum domain
• Transport Implementation of the Bernstein-Vazirani Algorithm with Ion Qubits
• Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers
• Efficient and Effective Quantum Compiling for Entanglement-based Machine Learning on IBM Q Devices
• A super-polynomial quantum-classical separation for density modelling
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• Quantum advantage for noisy channel discrimination
• On the Hardness of PAC-learning Stabilizer States with Noise
• Noise-tolerant parity learning with one quantum bit
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Binary Classification with Classical Instances and Quantum Labels
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Quantum Learning Boolean Linear Functions w.r.t. Product Distributions
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• A Quantum Algorithm for the Classification of Patterns of Boolean Functions
• Quantum-classical reinforcement learning for decoding noisy classical parity information
• The Learnability of Unknown Quantum Measurements
• Probabilistic Links Between Quantum Classification of Patterns of Boolean Functions and Hamming Distance
• Quantum Learning Based Nonrandom Superimposed Coding for Secure Wireless Access in 5G URLLC
• Sample-size-reduction of quantum states for the noisy linear problem
• Optimizing Circuit Reusing and its Application in Randomized Benchmarking
• Assessing the feasibility of quantum learning algorithms for noisy linear problems
• Quantum Learning Algorithms and Post-Quantum Cryptography