In the context of quantum computing, the quantum walk search is a quantum algorithm for finding a marked node in a graph.
The concept of a quantum walk is inspired by classical random walks, in which a walker moves randomly through a graph or lattice. In a classical random walk, the position of the walker can be described using a probability distribution over the different nodes of the graph. In a quantum walk, on the other hand, the walker is represented by a quantum state, which can be in a superposition of several locations simultaneously.
Search algorithms based on quantum walks have the potential to find applications in various fields, including optimization, machine learning, cryptography, and network analysis. The efficiency and probability of success of a quantum walk search depend heavily on the structure of the search space. In general, quantum walk search algorithms offer an asymptotic quadratic speedup similar to that of Grover's algorithm.
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.
Classical problem description
Given a search space and a subset which contains the marked elements, a probabilistic search algorithm samples an element uniformly at random at each step, until it finds a marked element from . If we define as the fraction of marked elements, a procedure of that kind must be repeated times to find a marked element.
If we have information about the structure of we can model it as a graph , where every vertex represents a sample from the search space with , while the edges represent the conditional probability to sample the next element starting from the current sample.
We perform a search by starting from a random vertex and, if it does not belong to , we sample the next vertex among the ones connected to . This procedure is known as random walk search. To have a probability close to to find the marked node, we need to take asymptotically steps on the graph, where the parameter is the spectral gap associated to the stochastic matrix of the graph.
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.
Setup
The setup cost refers to the initialization of the stationary distribution over the vertices of the graph.
Update
The update cost is the cost to simulate a transition on the graph according to the transition probability defined in .
Check
The check cost is the cost to verify if the current element belongs to the set .
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 . The presence of the spectral gap term in the cost formulation can be thought of as the minimum number of steps that the walker must perform to reach the stationary distribution. This quantity is also known as mixing time.
Algorithm description
The quantum walk search algorithm was first proposed by Magniez et al. , also known as MNRS algorithm, and is based on the quantum walk formulation proposed by Mario Szegedy. The walk is performed on the directed edges of the graph so to represent the quantum state associated with the search space we need two quantum registers , which correspond to the edge from to . To easily understand how it works, the algorithm can be explained through its geometric interpretation. We first define as the uniform superposition over the neighbours of . We additionally define the superposition over the marked and non-marked states, often referred to as the good and bad states, as
and
where is the set of marked elements. The uniform superposition over all the edges can be viewed a combination of good and bad states.
with .
The algorithm is composed of the following steps: Initialize the quantum state with , usually it is done by some state preparation routine. Repeat for : Perform a reflection through Perform a reflection through Measure the first quantum register and check if it is marked
Since the way the algorithm finds a marked element is based on the amplitude amplification technique, 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 ). The two reflections through and have the effect to move the quantum state toward the good state, after applications of the reflections the state can be written as and by setting we have that which yields the good state with a high probability.