Researchers at the Universities of Bristol and Western Australia have demonstrated a practical use of a “primitive” quantum computer, using an algorithm known as “quantum walk.” They showed that a two-qubit photonics quantum processor can outperform classical computers for this type of algorithm, without requiring more sophisticated quantum computers, such as IBM’s five-qubits cloud-based quantum processor (see IBM makes quantum computing available free on IBM Cloud).
Quantum walk is the quantum-mechanical analog of “random-walk” models such as Brownian motion (for example, the random motion of a dust particle in air).
Ref: Efficient quantum walk on a quantum processor. Nature Communications (5 May 2016) | DOI: 10.1038/ncomms11511 | PDF (Open Access)
ABSTRACT
The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.