Information storage

Although many people associate the word ‘complexity’ with the question of how many steps are required to perform an algorithm, it actually goes far beyond that. Here we are concerned with another precious resource in computation, namely memory. In 2012, a surprising discovery was made¹: quantum information processing can reduce the memory needed for the simulation of classical stochastic (that is, partially random) processes. Such processes are used as models for a large variety of systems, including the weather, the stock market, and the decay of atoms. Beyond the practical significance of saving memory in simulations, there are also profound implications on what it means for a system to be simple or complex, which is tied to the memory requirements.

Our group has pioneered experiments in this new and exciting research area called quantum statistical complexity. We have performed the first experiment that demonstrates a quantum advantage in the simulation of classical stochastic processes². This can be seen in the figure above, where the resources using the quantum encoding (blue dots) lie below those using classical encoding (white diamonds) over a range of parameter values of a stochastic process. In ongoing projects, we are moving to increasingly more complex quantum simulators. The quintessentially non-classical feature our simulators rely on is that unlike classical states, two different quantum states can be non-orthogonal, i.e. partially indistinguishable.