Quantum-classical reinforcement learning for decoding noisy classical parity information

Abstract

Learning a hidden parity function from noisy data, known as learning parity with noise (LPN), is an example of intelligent behavior that aims to generalize a concept based on noisy examples. The solution to LPN immediately leads to decoding a random binary linear code in the presence of classification noise. This problem is thought to be intractable classically, but can be solved efficiently if a quantum oracle can be queried. However, in practice, a learner is more likely to receive data from classical oracles. In this work, we show that a naive application of the quantum LPN algorithm to classical data encoded in an equal superposition state requires an exponential sample complexity. We then propose a quantum-classical reinforcement learning algorithm to solve the LPN problem for data generated by a classical oracle and demonstrate a significant reduction in the sample complexity. Simulations with a hidden bit string of length up to 12 show that the quantum-classical reinforcement learning performs better than known classical algorithms when the sample complexity, run time, and robustness to classical noise are collectively considered. Our algorithm is robust to any noise in the quantum circuit that effectively appears as Pauli errors on the final state.

24 pages, 9 figures. Comments welcome!

References in corpus (20)

• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• The theory of variational hybrid quantum-classical algorithms
• Quantum Circuit Learning
• Quantum random access memory
• On the Power of One Bit of Quantum Information
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum generative adversarial networks
• Quantum autoencoders for efficient compression of quantum data
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Architectures for a quantum random access memory
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Reinforcement Learning with Neural Networks for Quantum Feedback
• Demonstration of quantum advantage in machine learning
• Circuit-Based Quantum Random Access Memory for Classical Data
• On the robustness of bucket brigade quantum RAM
• Quantum learning robust to noise
• Learning with Errors is easy with quantum samples
• A Robust Quantum Random Access Memory
• Noise-tolerant parity learning with one quantum bit

Cited by in corpus (1)

• Quantum solvability of noisy linear problems by divide-and-conquer strategy