Searching via walking: How to find a marked clique of a complete graph using quantum walks

We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has $N$ vertices and the subgraph has $K$ vertices, the particle becomes localized on the subgraph in $O(N/K)$ steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches—the number of oracle calls.

Figure 1

An example of a complete graph with $N=7$ vertices out of which $v=3$ are special (white ones). The edge between two such vertices is considered to be special and it performs a phase shift for the particle either entering or leaving it (gray bars).

Figure 2

A quantum circuit (network) that implements a single step of scattering quantum walk search, which makes use of the quantum oracle $\mathcal{C}{\mathrm{Û}}_f$. The first input corresponds to a quantum walker originally prepared in the state $|{\psi }_{\mathrm{init}}\rangle$. The second and third inputs represent the end vertices of the walker’s edge state, while the fourth input represents an ancillary processing subsystem prepared in the state $|\mu \rangle$ given by Eq. (5).