In the context of quantum computing, the quantum walk search (sometimes regarded as QFS, similar to DFS and BFS) 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 X {\displaystyle X} and a subset M ⊆ X {\displaystyle M\subseteq X} which contains the marked elements, a probabilistic search algorithm samples an element x ∈ X {\displaystyle x\in X} uniformly at random at each step, until it finds a marked element from M {\displaystyle M} . If we define ϵ = | M | / | N | {\displaystyle \epsilon =|M|/|N|} as the fraction of marked elements, a procedure of that kind must be repeated O ( 1 / ϵ ) {\displaystyle O(1/\epsilon )} times to find a marked element. If we have information about the structure of X {\displaystyle X} we can model it as a graph G ( V , E ) {\displaystyle G(V,E)} , where every vertex V = { v 1 , … , v n } {\displaystyle V=\{v_{1},\dots ,v_{n}\}} represents a sample from the search space with | X | = n {\displaystyle |X|=n} , 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 v 1 {\displaystyle v_{1}} and, if it does not belong to M {\displaystyle M} , we sample the next vertex v 2 {\displaystyle v_{2}} among the ones connected to v 1 {\displaystyle v_{1}} . This procedure is known as random walk search. To have a probability close to 1 {\displaystyle 1} to find the marked node, we need to take asymptotically O ( 1 / ϵ δ ) {\displaystyle O(1/\epsilon \delta )} steps on the graph, where the parameter δ {\displaystyle \delta } is the spectral gap associated to the stochastic matrix P {\displaystyle P} 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 S {\displaystyle S} refers to the initialization of the stationary distribution over the vertices of the graph.
Update The update cost U {\displaystyle U} is the cost to simulate a transition on the graph according to the transition probability defined in P {\displaystyle P} .
Check The check cost C {\displaystyle C} is the cost to verify if the current element belongs to the set M {\displaystyle M} . The total cost of a random walk search algorithm is S + 1 ϵ ( 1 δ U + C ) {\displaystyle S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}} . The greedy version of the algorithm, where the check is performed after every step on the graph has a complexity of S + 1 ϵ δ ( U + C ) {\displaystyle S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}} . The presence of the spectral gap term δ {\displaystyle \delta } 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.
… excerpt ends here. Continue reading the full article.
