Title: Stabiliser states are efficiently PAC-learnable,
Abstract: The exponential scaling of the wave function is a fundamental property of
quantum systems with far reaching implications in our ability to process
quantum information. A problem where these are particularly relevant is quantum
state tomography. State tomography, whose objective is to obtain a full
description of a quantum system, can be analysed in the framework of
computational learning theory. In this model, quantum states have been shown to
be Probably Approximately Correct (PAC)-learnable with sample complexity linear
in the number of qubits. However, it is conjectured that in general quantum
states require an exponential amount of computation to be learned. Here, using
results from the literature on the efficient classical simulation of quantum
systems, we show that stabiliser states are efficiently PAC-learnable. Our
results solve an open problem formulated by Aaronson [Proc. R. Soc. A, 2088,
(2007)] and propose learning theory as a tool for exploring the power of
quantum computation.