Quantum-enhanced learning of rotations about an unknown direction

Abstract

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(mathrm{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.