How much information do we need to communicate?
For some tasks, quantum science offers an advantage over anything that can be achieved with conventional, classical tools. Two of the tasks that can benefit from nonclassical resources in this way are the storage and communication of information, and these are studied in the research field of quantum complexity.
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 made1: 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 processes2. 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.
In contrast to the above focus on memory, in quantum communication complexity we look at communication (for example the number of bits sent) as the resource to be minimised. Here we deal with so-called distributed information-processing tasks. These arise in situations where there are several parties, say, Alice and Bob, who each have some information. They need to jointly perform a calculation that requires information from both, and the point is to do so with as little communication as possible. One example is where Alice and Bob each have a message (a bit string), and they need to decide whether the two messages are the same or different. Quantum resources can serve to decrease the amount of communication required for these types of tasks.
1. M. Gu, K. Wiesner, E. Rieper and V Vedral, Nat. Commun. 3, 762 (2012).
2. M. S. Palsson, M. Gu J. Ho, H. M. Wiseman and G. J. Pryde, Science Advances 3, e1601302 (2017).