  We design machines that learn how to rotate a quantum bit about an initially
unknown direction, encoded in the state of a spin-j particle. We show that a
machine equipped with a quantum memory of O(log j) qubits can outperform all
machines with purely classical memory, even if the size of their memory is
arbitrarily large. The advantage is present for every finite j and persists as
long as the quantum memory is accessed for no more than O(j) times. We
establish these results by deriving the ultimate performance achievable with
purely classical memories, thus providing a benchmark that can be used to
experimentally demonstrate the implementation of quantum-enhanced learning.
