Reduction of the complete bipartite graph with k edge removal for quantum walks

Introduction: In previous works, systematic dimensionality reduction for Quantum Walks has been studied for optimization of search and transport on particular graphs. The Lanczos Algorithm (LA) has been used to perform the... [ view full abstract ]

Introduction:

In previous works, systematic dimensionality reduction for Quantum Walks has been studied for optimization of search and transport on particular graphs. The Lanczos Algorithm (LA) has been used to perform the reduction on the Complete Graph (CG), CG with symmetry broken, and Complete Multipartite Graphs (CMPG), including the Complete Bipartite Graph (CBG). However, the CBG case with symmetry broken has not been studied in papers we’ve read.

Methods:

Quantum Walk searches on CMPGs take place in four steps: reduction of the original graph’s adjacency matrix, computation of the search matrix, basis change, and determining the correct coupling factor for search optimization. In this work, we focus on the reduction step using the LA. We aim to show that similarly to the CG, the symmetry of the CBG can be broken for the general case and the algorithm can be applied in such a way that allows for its matrix to be reduced.

Results:

We have shown that the LA on the CBG can be generalized to a CBG with broken symmetry, with k links removed and the constraints that no links from nodes connected to the solution node W are removed and at most one link is removed from each node (see Figure 1), resulting in a 5x5 matrix. Furthermore, we have confirmed and clarified the CG with broken symmetry case by performing the algorithm without approximation.

Discussion:

While the CG matrix can be reduced to 3x3, (see Figure 2), the CBG matrix can be reduced to no less than 5x5. This is because unlike in the CG, where there are three types of nodes: W, no edge removed (not affected - NA), and edge removed (affected - A), the CBG contains five types of nodes: W, NA (partition 1), A (partition 1), NA (partition 2), and A (partition 2). This suggests two points of interest that may be further explored. First, whether the CMPG with symmetry broken can be generalized in a similar matter to the CBG for any number of partitions, and second, if it can, how will the matrix dimensions be affected as the number of partitions changes.