Quantum Walks – Graph-Theoretic Quantum Algorithms

A particle or “walker” moves stochastically around a discrete space in a classical random walk. 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 simulations. Their markedly distinct properties provide a quantum speedup in solving problems, such as database search and graph isomorphism (GI), that can be broadly applied to pattern recognition and computer vision, network analysis, navigation, and website traffic optimization. They could find applications in using and analyzing 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 by exploiting an entanglement-driven scheme, silicon photonics can realize these particles with full control over all these properties in one device.

With the full programmability of the device and the inherent subwavelength stability of its monolithic integration, researchers were able to experimentally implement quantum walk–based algorithms of hundreds of graph configurations on a single device—they search for marked vertices in graphs and distinguish nonisomorphic graph pairs. These demonstrations physically explore the suitability of simulating quantum walk phenomena and applications in silicon photonics as the scale and capability of the technology grow.

Read more

Related Content: Quantum Key Distribution – Photonic Chip