# Quantum computing ready for chicken and potatoes

Tuesday, May 31 2016

The probability distribution of quantum walk on an example circulant graph. Sampling this probability distribution is generally hard for a classical computer, but simple on a primitive quantum computer. Credit: University of Bristol

Once in a while I step onto some articles and news on (elusive) progress in quantum computer.  They are well understood, offer to solve difficult problems, but they are still very tricky to build.

This time I stepped onto a paper written by researchers at University of Bristol and University of Western Australia on "Efficient quantum walk on a quantum processor".

The problem they are addressing is a very difficult one (although I can understand if you were not intrigued by the problem itself): calculating the browning motion of a particle of dust. If you have a very tiny particle of dust, it will float in the air and as it floats it will bump on gas molecules that are moving in a random way, thus leading to a random motion of the dust particle.

Calculating the "walk" of the particle through a classic computer is very difficult. What the researchers have managed to do is to perform the calculations using a 2 Qbit quantum computer using photonics quantum processors. We have been able to build quantum processors with a few Qbits, up to 5, but using more Qbits has proven difficult because the impossibility, so far, of keeping all Qbits "coherent". There have been some progress using shortcuts but they do not result in a full quantum computation (although for some purposes, like pattern recognition quantum computers like D-Wave 2X works pretty well).

You may want to read the paper to get more details (and if you are new to quantum computers the clip provides a nice introduction to them). What really pushed me to write this post is that something as esoteric as quantum computation and a similarly strange quantum walk algorithm can find down to earth applications.

The issue of simulating the brownian motion of a particle of dust requires the analyses of a circular graph, a set of points that are connected one another and where each point is somehow affecting the behaviour of the others. As the number of points grow the exponential rise of mutual effects blows out the processing capability of a classic computer. Now, circular graphs can be found in many areas, like the problem of what is the most effective way to display products on shelves in a department store.

Ideally, one would like to cluster those products that are likely to be related one another so that a prospective customer when picks up a chicken is immediately drawn to pick up a complement, like potatoes to cook fries along with it.

On the other hand potatoes may fit well along many other products so what is the overall best strategy?

It turns out that a quantum walk approach can provide a solution to this problem. Who would have imagined that Dirac equations eventually will apply to french fries in a supermarket?

Roberto Saracco