Quantum-classical reinforcement algorithm for learning parity with noisy classical data and a noisy quantum machine

Abstract

An intelligent behavior of interest in this work is the ability to learn a general concept from particular examples that contain errors. This problem can be formulated in the probably approximately correct (PAC) framework in which a learner is to construct a hypothesis h with high probability based on a training set of input-output pairs such that the h(x) agrees with f(x) on a large fraction of the inputs. In PAC learning, important measures of the performance are the sample and time complexity that correspond to the minimum number of examples required to reach the goal and the run time of the algorithm, respectively.