  Computer simulation of observable phenomena is an indispensable tool for
engineering new technology, understanding the natural world, and studying human
society. Yet the most interesting systems are often complex, such that
simulating their future behaviour demands storing immense amounts of
information regarding how they have behaved in the past. For increasingly
complex systems, simulation becomes increasingly difficult and is ultimately
constrained by resources such as computer memory. Recent theoretical work shows
quantum theory can reduce this memory requirement beyond ultimate classical
limits (as measured by a process' statistical complexity, C). Here we
experimentally demonstrate this quantum advantage in simulating stochastic
processes. Our quantum implementation observes a memory requirement of C_q =
0.05 $\pm$ 0.01, far below the ultimate classical limit of C = 1. Scaling up
this technique would substantially reduce the memory required in simulation of
more complex systems.
