Quantum walk search

In a classical random walk, the position of the walker can be described using a probability distribution over the different nodes of the graph.

[1] Search algorithms based on quantum walks have the potential to find applications in various fields, including optimization, machine learning, cryptography, and network analysis.

[3][4] One of the first works on the application of quantum walk to search problems was proposed by Neil Shenvi, Julia Kempe, and K. Birgitta Whaley.

uniformly at random at each step, until it finds a marked element from

as the fraction of marked elements, a procedure of that kind must be repeated

[7] To assess the computational cost of a random walk algorithm, one usually divides the procedure into three sub-phases such as Setup, Check, and Update, and analyses their cost.

refers to the initialization of the stationary distribution over the vertices of the graph.

is the cost to verify if the current element belongs to the set

[6] The total cost of a random walk search algorithm is

The greedy version of the algorithm, where the check is performed after every step on the graph has a complexity of

in the cost formulation can be thought of as the minimum number of steps that the walker must perform to reach the stationary distribution.

[8] The quantum walk search algorithm was first proposed by Magniez et al.,[7] also known as MNRS algorithm, and is based on the quantum walk formulation proposed by Mario Szegedy.

To easily understand how it works, the algorithm can be explained through its geometric interpretation.

[9] The algorithm is composed of the following steps: Since the way the algorithm finds a marked element is based on the amplitude amplification technique,[10] the proof of correctness is similar to the one of Grover's algorithm (which can also be viewed as a special case of a quantum walk on a fully connected graph ).

[9] The first reflection has the effect of checking if the current vertex is marked and applying a phase shift equal to

This is a common procedure in many quantum algorithms based on amplitude amplification and can be realized through a quantum oracle function that verifies the condition

[9] The second reflection is implemented with a quantum phase estimation over the walk operator

The precision of the reflection depends on the number of qubits used to estimate the phase.

, which results in a quadratic speedup compared to the classical version.

Compared to Grover's algorithm quantum walks become advantageous in the presence of large data structures associated with each quantum state, since in the first case they are entirely rebuilt at each iteration while in walks they are only partially updated in each step.

[11] This is an example of how to apply the quantum walk search on a hypercube graph.

In any case, the two formalizations turn out to be equivalent under specific assumptions.

bits and two nodes are connected by an edge if their Hamming distance is

To set up the quantum walk search we need a coin register of dimension

to encode all the possible directions which a walker can choose and a vertex register of dimension

[12] In the case of the hypercube graph, we can leverage the fact that the binary encoding of the vertices differ by only one bit for any couple of adjacent nodes to construct an efficient shift operator.

[12] The algorithm works as follows: The shift operator is a key factor to the implementation on an efficient quantum walk, while for certain families of graph such as toroids and lattices, the shift is known, for non-regular graph the design of an effective shift operator is still an open challenge.

[14] The following applications are based on quantum walk on Johnson graph

[6] A triangle is a complete subgraph on three vertices part of an undirected graph

Given the adjacent matrix of a graph the problem asks to find a triangle if there is any.