Analogue simulation a short-cut to faster computing
The “quantum walk” doesn’t deliver a general purpose quantum computer. Instead it delivers a a quantum simulator which the scientists told China’s state-controlled Xinhua news agency can “solve practical problems directly without error correction, and potentially be able to beat the computational power of classical computers in the near future.”
Let’s start with what the researchers showed off, which is published at Science Advances here and can be seen in pre-press at arXiv here.
The Chinese experiment demonstrated “a two-dimensional continuous-time quantum walk” in which photons followed paths in arrays of waveguides. These were constructed as a two-dimensional lattice with 49 x 49 nodes.
In a “classical random walk”, you could imagine someone starting at the centre of a city, and making a random decision at each intersection. In this case, the walker’s position is described by a probability distribution over all the possible positions (kind of like the wear on a stone step is a probability distribution of where feet land).
In the quantum world, superposition (the property of quanta that they may exist in a superposition of multiple states at once until the waveform is collapsed) is added to the mix. In other words, the walker may be superposed over all positions until measured.
For some problems, you could consider this a short-cut to getting a quantum computation, compared to a general-purpose quantum computer. The “analogue quantum simulator” can quickly occupy many possible quantum states, with the act of measurement revealing the answer.
However, the researchers write, most quantum walk demonstrations so far have been single dimensional, which is useful to show that the states can be created, but not for simulation problems. For example, the paper states, “In the spatial search algorithm, a quantum walk outperforms its classical counterparts only when the dimension is higher than one”.
For that, the paper said, a two-dimensional walk was needed, and that’s what the researchers say they achieved.
They claim the scale of their 49 x 49 array should provide a measurable speed-up over classical simulators, for at least that class of problems quantum walks can simulate – for example, predicting the behaviour of randomly-grown networks such as in “simulation of graphene, photosynthesis, or neural network systems”. ®
