Quantum-classical reinforcement learning for decoding noisy classical parity information

Daniel K. Park, Jonghun Park, June Koo Kevin Rhee

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 likely to obtain classical data. 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 classical data and demonstrate a significant reduction in the sample complexity compared with the naive approach. 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.

Original languageEnglish
JournalQuantum Machine Intelligence
Issue number1
Publication statusPublished - 2020 Jun 1

Bibliographical note

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Software
  • Applied Mathematics
  • Theoretical Computer Science


Dive into the research topics of 'Quantum-classical reinforcement learning for decoding noisy classical parity information'. Together they form a unique fingerprint.

Cite this