Learning Functions of Hamiltonians with Hamiltonian Fourier Features

Several quantum machine learning (QML) tasks demonstrating quantum advantage have been proposed. However, they have been limited to artificial problems such as discrete logarithms, and no quantum advantage has been found in practically useful machine learning tasks. We introduce a QML task that is provably tractable for quantum computers while being conjectured to be intractable for classical ones. The task involves predicting physical quantities of the form Tr[f(H)ρ], where H denotes a Hamiltonian, ρ a quantum state, and f an unknown function. By employing a Fourier-based feature mapping of Hamiltonians combined with linear regression, we theoretically establish the learnability of this task on quantum computers. Furthermore, we prove that the quantum easiness of the proposed problem persists even in the presence of realistic noise. Experimentally, we implement the framework on IBM superconducting quantum processors with up to 40 qubits, demonstrating the learning of f(H)=e^-βH for random Heisenberg Hamiltonians. Despite hardware noise, our results validate the feasibility of the approach on current quantum devices. This work establishes a practically relevant quantum learning task with provable quantum advantage, bridging rigorous theoretical guarantees and near-term experimental realizations.