Inductive Supervised Quantum Learning

In supervised learning, an inductive learning algorithm extracts general rules from observed training instances, then the rules are applied to test instances. We show that this splitting of training and application arises naturally, in the classical setting, from a simple independence requirement with a physical interpretation of being nonsignaling. Thus, two seemingly different definitions of inductive learning happen to coincide. This follows from the properties of classical information that break down in the quantum setup. We prove a quantum de Finetti theorem for quantum channels, which shows that in the quantum case, the equivalence holds in the asymptotic setting, that is, for large numbers of test instances. This reveals a natural analogy between classical learning protocols and their quantum counterparts, justifying a similar treatment, and allowing us to inquire about standard elements in computational learning theory, such as structural risk minimization and sample complexity.

Figure 1

Diagrammatic representation of a generic quantum learning protocol $\mathbb{Q}$ (gray box), as per Definition 1, which is approximated by $\tilde{\mathbb{Q}}$, given in Eq. (3). Both setups take training and test instances ${\rho }_A$ and ${\rho }_{X{Y}^{\prime }}^{\otimes n}$ as inputs. We distinguish two agents in the diagrams: the performer of the learning protocol or “learner,” placed above the dashed horizontal line, and the “referee,” placed below. The learner sends the output registers $Y_{1:n}$ of the learning channel to the referee, who contrasts them with the registers $Y_{1:n}^{\prime }$ and evaluates the average risk of the channel $\overline{S}$ (see Definition 2). This referee plays a role similar to the classical tester in the final phase of quantum-enhanced reinforcement learning [19]. While the most general approach (a collective quantum channel $\mathbb{Q}$) in principle acts globally on all its inputs, its approximation $\tilde{\mathbb{Q}}$ comprises two separate phases: first (training phase) a measurement $\mathcal{M}$ is performed on the training set ${\rho }_A$, and second (test phase) the classical information $g$ obtained from the measurement is distributed among all test instances, and corresponding quantum channels ${\mathrm{\Phi }}_g$ are applied locally to each one of them.