Want more efficient simulators? Store time in a quantum superposition
Computer models of systems such as a city's traffic flow or neural firing in the brain tends to use up a lot of memory. But a new approach with quantum simulators could significantly cut that memory use by taking a quantum approach to time. The only cost is a diminished record of the past.
The suggestion comes from researchers Mile Gu and Thomas Elliott in Singapore, who describe their proposal in a paper published 1 March in npj Quantum Information. Gu works at the Centre for Quantum Technologies and Nanyang Technological University (NTU) in Singapore, and Elliott is at NTU.
To perform a simulation, a classical computer must cut time into discrete steps. Gu draws analogy with an ancient way of measuring time: the hourglass. "Zoom in on an hourglass and one can see the individual grains of sand falling one by one. It's a granular flow," says Gu.
Just as the hourglass needs finer sand to make a more precise measurement of time, a computer needs finer time-steps to make more accurate simulations. In fact, the ideal would be to simulate time continuously because, to the best of our observations, time appears to be continuous. But that implies a truly accurate classical simulation would need infinite memory to run such a program.
While that's impossible with a classical computer, quantum effects provide a work-around. "With a quantum simulator, you can avoid the precision versus storage trade-off that you have to suffer with a classical device," explains Elliott.
To explain how it works, imagine you need to catch a bus. If you arrive at the stop just in time to see a bus leaving, you now expect the next bus to take longer to arrive than if you hadn't just seen one leave. That's because the probability of a bus coming isn't always constant, but depends on how long it has been since the last bus.
To simulate similar processes where probability changes over time, a regular computer calculates outcomes at set time intervals. It might, for example, divide the probabilities for bus arrival times into 30 second intervals, updating those probabilities after each interval depending on whether a bus arrived (or didn't). To be more precise about when a bus will come, or to accurately model bigger, more complicated traffic networks, needs smaller time steps and thus more memory.
In this classical approach, one makes predictions by counting how much time has elapsed since the previous bus. This seems logical, and it turns out to be the best classical method. Quantum physics, however, allows a completely different approach.
A quantum simulator can be in many different states at the same time, each with its own probability of being realised. This is a phenomenon known as quantum superposition. Gu and Elliott's proposal is to encode the temporal probability distribution for the event they want to simulate into the probability weighting of the different states. If the superposition is created in a property such as the position of a particle, which can itself evolve continuously, time can then be tracked continuously too. So it is possible to discard some information about the elapsed time – achieving superior memory-efficiency – without sacrificing predictive accuracy.
The gain does come at the expense of losing knowledge of the past. The elapsed time – a record of the past, in other words – cannot be recovered exactly from the superposition, but all forecasting ability is retained nonetheless.
"Ultimately, when making predictions we don't care about what we have already seen. Rather, we care only for what these observations tell us about what we expect to see next. Quantum physics allows us to efficiently isolate this information." says Elliott.
"Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes" npj quantum information 4, 18 (2018) https://www.nature.com/articles/s41534-018-0064-4
Preprint available at https://arxiv.org/abs/1704.04231
Research Assistant Professor, Centre for Quantum Technologies at the National University of Singapore
Assistant Professor, Nanyang Technological University
+65 6516 5627
Research Fellow, Nanyang Technological University
This work was funded by Singapore National Research Foundation Fellowship NRF-NRFF2016-02. Mile Gu is also financially supported by the John Templeton Foundation Grant 53914 "Occam's quantum mechanical razor: Can quantum theory admit the simplest understanding of reality?" and the Foundational Questions Institute.
Related Journal Article