Researchers have discovered a new way in which computers based on quantum physics could beat the performance of classical computers. The work 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 emerges from fundamental consideration of how much information is needed to predict the future. Researchers know how to calculate the amount of information transferred inherently in any stochastic process. 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.
Gu, Wiesner, Rieper and Vedral 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.