Efficient Quantum Circuit Architecture for Coined Quantum Walks on many Bipartite Graphs (en)

Efficient Quantum Circuit Architecture for Coined Quantum Walks on many Bipartite Graphs

Abstract:

Quantum walks, a quantum analog of classical random walks, have emerged as a powerful paradigm in quantum computation and simulation. While classical random walks rely on stochastic processes to explore systems, quantum walks leverage the unique properties of quantum mechanics to perform these tasks more efficiently. In particular, discrete-time quantum walks (DTQWs) have been studied extensively for their applications in graph theory, such as graph isomorphism, graph connectivity, and graph-based search problems. Despite their potential, implementing DTQWs on near-term quantum devices remains challenging. While previous works have focused on quantum circuit implementations for DTQWs with uniform coin operators, implementing non-homogeneous coin sets is a complex task that requires new approaches. This thesis presents an efficient quantum circuit architecture for implementing coined DTQWs with non-homogeneous, position-dependent coin sets on a large subset of bipartite graphs. A novel edge labeling scheme, Gray Code Directed Edges encoding, is introduced, taking advantage of Gray code for position encoding and the bipartite structure of the underlying graph to minimize the complexity of the quantum circuits representing coin and shift operators. This optimization leads to fewer gate operations, reducing the impact of noise and errors in near-term quantum devices. A labeling scheme is developed for various graph topologies, including cycle graphs, chained cylinder graphs, and square grid graphs, which are especially relevant for reinforcement learning applications. These findings offer a new perspective on the implementation of coined quantum walks and lay a foundation for future research on quantum walks with non-homogeneous coin sets.

Author:

Viktoryia Patapovich

Advisors:

Jonas Stein, Michael Kölle, Maximilian-Balthasar Mansky, Claudia Linnhoff-Popien

Student Thesis | Published July 2023 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors