  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.
