  The number of parameters describing a quantum state is well known to grow
exponentially with the number of particles. This scaling clearly limits our
ability to do tomography to systems with no more than a few qubits and has been
used to argue against the universal validity of quantum mechanics itself.
However, from a computational learning theory perspective, it can be shown
that, in a probabilistic setting, quantum states can be approximately learned
using only a linear number of measurements. Here we experimentally demonstrate
this linear scaling in optical systems with up to 6 qubits. Our results
highlight the power of computational learning theory to investigate quantum
information, provide the first experimental demonstration that quantum states
can be "probably approximately learned" with access to a number of copies of
the state that scales linearly with the number of qubits, and pave the way to
probing quantum states at new, larger scales.
