Abstract
Controlling quantum systems is crucial for quantum computation and a variety of new quantum technologies. The control is typically achieved by breaking down the target dynamics into a sequence of elementary gates,whose description can be stored into the memory of a classical computer. Here we explore a different approach, initiated by Nielsen and Chuang, where the target dynamics is encoded in the state of a quantum system, regarded as a "quantum program". We show that quantum strategies based on coherent interactions between the quantum program and the target system offer an advantage over all classical strategies that measure the program and conditionally operate on the system. To certify the advantage, we provide a benchmark that guarantees the successful demonstration of quantum-enhanced programming in realistic experiments.