Quantum-classical hybrid reinforcement learning algorithm for parity learning with noisy classical samples

Abstract

This work discusses the ability of constructing a quantum machine learning system that can be learned from noisy classical training samples. The learner constructs a hypothesis that is assumed to be the closest to answer from the training samples given in input-output form. This learning system can be formulated in the probably approximately correct (PAC) framework. In PAC learning, import measures of the performance are the sample and time complexity that corresponds to the minimum number of samples required to reach the goal and the run time of the system, respectively. A noisy parity learning (LPN) problem is a well-known example of the PAC problem, which is the problem of learning parity from a uniformly randomly extracted input-output pairs. However, the parity learning problem is more difficult than the general PAC problem because the binary sequence that determines the parity must be exactly correct. Both classical and quantum LPN algorithms can easily solve LPN problems when there is no noise, but only quantum LPN algorithms solve the LPN problem efficiently when there is noise. Quantum LPN algorithms shows strong quantum advantage, such as robustness against errors and exponentially improved time complexity and sample complexity. Quantum LPN algorithms have the quantum advantage in presence of quantum parity oracle that produces all possible input-output pairs in an equal superposition state. However, the assumption of quantum parity oracle is very unrealistic. In this paper, we propose a quantum LPN algorithm learned from a limited number of noisy classical training samples and also retains the quantum advantage. The proposed algorithm uses reinforcement learning system with quantum environment and classical agent. The algorithm introduces a guess quantum parity oracle, that produces all possible input and guessed output pairs. The performance of the algorithm is predicted using the loose mathematical verification and simulation results on classical computer. The proposed quantum LPN algorithm is numerically verified that the sample complexity and time complexity are significantly reduced compared to the classical LPN algorithms. In addition, we confirmed that the proposed algorithm shows the comparable or enhanced performance than the classical LPN algorithms through simulations. In addition, the proposed algorithm is more robust against error than the classical LPN algorithms.