Quantum searches on highly symmetric graphs

We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an $M$-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.

Figure 1

A logical circuit (network) that implements a single step of a scattering quantum walk search, which makes use of the quantum oracle $\mathcal{C}{\widehat{V}}_f$. The first input corresponds to a quantum walker originally prepared in the state $\mid {\psi }_{\mathrm{init}}⟩$. The second input represents a vertex state, while the third input represent an ancillary qubit.

Figure 2

An example of a complete graph with $N=7$ vertices out of which $v=2$ are special (white ones). A solution for a scattering-quantum-walk search on such a graph leads to a reduction in dimensionality of the problem to four dimensions.

Figure 3

(Color online) The density plot of the probability $P$, taken for a quantum walk on complete graph with $N=256$ and $v=1$, shows the convergence of the side ridges to the maximum (dark gray) for $\varphi =\pi$ with the probability $P=1$ (blue dots). White areas correspond to the minimal probability of finding the particle on an edge connected to the special vertex. The thick red line represents the optimal number of steps that are to be taken before the measurement so that the search algorithm for the special vertex would require minimal average number of steps.

Figure 4

Average number of walking steps as a function of the phase shift $\varphi$. This plot illustrates the efficiency of algorithms—the classical blind search (dashed), the classical search with memory (dotted), and the quantum search (thick solid). We consider a graph with $N=256$ vertices. We see that the minimal value of the average number of steps is achieved for the quantum search with $\varphi =\pi$.

Figure 5

General bipartite graph having $v_1$ special (black circles) and $p_1$ normal (white circles) vertices in the first set and $v_2$ special and $p_2$ normal vertices in the second set. This problem can be reduced to an eight-dimensional one with a two-dimensional decoupled subspace. The remaining six dimensions can be reduced to three by performing two steps at a time due to the oscillatory behavior of the walk in bipartite graphs.

Figure 6

$M$-partite complete graph consists of $M$ sets of vertices where each set contains $N$ vertices. For every pair of vertices not belonging to the same set there exists an edge, while there is no edge connecting any two vertices within the same set. In one of the sets we consider one vertex to be special.