Quantum Walks – Graph-Theoretic Quantum Algorithms

In a classical random walk, a particle or “walker” moves stochastically around a discrete space. Quantum walks are the quantum analog, where the walker is also governed by quantum effects such as superposition, quantum interference, and entanglement.

Quantum walks have attracted broad interest because of a growing range of applications in quantum information processing and quantum simulations. Their markedly distinct properties provide a quantum speedup in solving problems, such as database search and graph isomorphism (GI) that more broadly can be applied to pattern recognition and computer vision, network analysis, and navigation, and website traffic optimization and could find application in the use and analysis of large but imperfect graph states in measurement-based quantum computing.

Applications of quantum walks can depend on the number, exchange symmetry, and indistinguishability of the particles involved, and the underlying graph structures where they move. Here, researchers show that silicon photonics, by exploiting an entanglement-driven scheme, can realize these particles with full control over all these properties in one device.

Read more