How Quantum Physics Could Make 'The Matrix' More Efficient

Mile Gu of CQT, 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 from Centre for Quantum Technologies (CQT), Singapore and University of Bristol, UK -- implies that a 'The Matrix'-like simulation of reality [1] 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 the quantum theory. The finding is published in Nature Communications dated March 27th, 2012 [2].


Karoline Wiesner of the University of Bristol, UK -->

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 (see Figure 1), 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 modeled as stochastic processes.


















Figure 1: A simulator for a Stochastic Process can be thought of a physical system that stores select information about past outputs, and uses them to generate the require statistics for the future. Ideally, we want to construct a simulator that is as simple as possible, such that the amount of information it requires about the past is minimized.

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. In scientific literature of that field, it is referred to as 'statistical complexity' [3].

Elisabeth Rieper of CQT, Singapore -->

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. This was done by isolating the source of inefficiency within classical simulators. When we attempt to simulate any stochastic process that has a binary property ‘X’ , which affects the future evolution of the process, then the value ‘X’ must be stored. This is unavoidable; even when all future observations of the process do not guarantee that one can deduce the value of ‘X’. The researchers showed that this implied that classical simulators erase information; they contain a source of irreversibly that cannot be removed.

Quantum simulators, however, have greater potential freedom. Instead of allocating a full bit to store the value of ‘X’, one can store the conditions ‘X= 0’ and ‘X=1’ in non-orthogonal states. Consequently, the simulator saves memory, as it was never sure what state the property was in the first place. Nevertheless, Mile et al showed that it is often possible to engineer dynamics such that the simulator can still replicate the dynamics of our desired reality.

Vlatko Vedral of CQT, Singapore

This result has significant implications. Stochastic processes play a ubiquitous role in the modeling of dynamical systems that permeate quantitative science, from climate fluctuations to chemical reaction processes. Classically, the statistical complexity is employed as a measure of how much structure a given process exhibits. The rationale is that the optimal simulator of such a process requires at least this much memory. The fact that this memory can be reduced quantum mechanically implies the counter-intuitive conclusion that quantizing such simulators can reduce their complexity beyond this classical bound, even if the process they're simulating is purely classical. Many organisms and devices operate based on the ability to predict and thus react to the environment around them. The possibility of exploiting quantum dynamics to make identical predictions with less memory implies that such systems need not be as complex as one originally thought.






















Figure 2: 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.

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 2). Could an even more general probability theory -- with even more bizarre correlations -- side-step this restriction?

"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.

Reference
[1] The Matrix (1999 American science fiction action film written and directed by Larry and Andy Wachowski). Wikipedia Page.
[2] Mile Gu, Karoline Wiesner, Elisabeth Rieper and Vlatko Vedral, "Quantum mechanics can reduce the complexity of classical models." Nature Communications 3, 762 (2012). Abstract. arXiv:1102.1994.
[3] Cosma Rohilla Shalizi and James P. Crutchfield, "Computational mechanics: pattern and prediction, structure and simplicity." Journal of Statistical Physics, 104, 817–879 (2001). Abstract.