How quantum physics could make 'The Matrix' more efficient

Quantum simulations need to store less information to predict the future than do classical simulations. The finding applies to phenomena described by stochastic processes. Image: Mile Gu / Centre for Quantum Technologies at the National University of Singapore

Researchers have discovered a new way in which computers based on quantum physics could beat the performance of classical computers. The work, by researchers at CQT and in the UK, implies that a Matrix-like simulation of reality would require less memory on a quantum computer than on a classical computer. It also hints at a way to investigate whether a deeper theory lies beneath quantum theory. The finding is published 27 March in Nature Communications.

The finding emerges from fundamental consideration of how much information is needed to predict the future. Mile Gu, Elisabeth Rieper and Vlatko Vedral at CQT, with Karoline Wiesner from the University of Bristol, UK, considered the simulation of 'stochastic' processes, where there are several possible outcomes to a given procedure, each occurring with a calculable probability. Many phenomena, from stock market movements to the diffusion of gases, can be modelled as stochastic processes.

The details of how to simulate such processes have long occupied researchers. The minimum amount of information required to simulate a given stochastic process is a significant topic of study in the field of complexity theory, where it is known in scientific literature as statistical complexity.

Researchers know how to calculate the amount of information transferred inherently in any stochastic process, a quantity known as the excess entropy. Theoretically, this sets the lowest amount of information needed to simulate the process. In reality, however, classical simulations of stochastic processes require more storage than this.

Mile, Karoline, Elisabeth and Vlatko showed that quantum simulators need to store less information than the optimal classical simulators. That is because quantum simulations can encode information about the probabilities in a 'superposition', where one quantum bit of information can represent more than one classical bit.

What surprised the researchers is that the quantum simulations are still not as efficient as they could be: they still have to store more information than the process would seem to need (see figure below).

The researchers calculated the information-storage requirements for a set of stochastic models describing a perturbed coin - a coin that flips at each time step with some probability p. The figure shows how a classical simulation (a) compares to a quantum simulation (b) and the expected ideal (c) for different probabilities p. The quantum model is closer to the ideal than classical, but there's still a gap.

That suggests quantum theory might not yet be optimised. "What's fascinating to us is that there is still a gap. It makes you think, maybe here's a way of thinking about a theory beyond quantum physics," says Vlatko, who is also affiliated with the University of Oxford.

For further details, see "Quantum mechanics can reduce the complexity of classical models" Nature Communications, 3, 762 (2012); arXiv:1102.1994.

You can watch Mile, the paper's first author, give a 12-minute presentation on the work in the video embedded below and read an essay about the findings, which is published on the Foundational Questions Institute (FQXi) website. This story also appears on PhysOrg.