Quantum walk search

Given a search space $X$ and a subset $M\; \backslash subseteq\; X$ which contains the marked elements, a probabilistic search algorithm samples an element $x\; \backslash in\; X$ uniformly at random at each step, until it finds a marked element from $M$. If we define $\backslash epsilon\; =\; |M|/|N|$ as the fraction of marked elements, a procedure of that kind must be repeated $O(1/\backslash epsilon)$ times to find a marked element.{{Citation |last=Santha |first=Miklos |title=Quantum walk based search algorithms |date=2008 |url=http://link.springer.com/10.1007/978-3-540-79228-4_3 |work=Theory and Applications of Models of Computation |series=Lecture Notes in Computer Science |volume=4978 |pages=31–46 |editor-last=Agrawal |editor-first=Manindra |access-date=2023-07-05 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/978-3-540-79228-4_3 |arxiv=0808.0059 |isbn=978-3-540-79227-7 |s2cid=47163843 |editor2-last=Du |editor2-first=Dingzhu |editor3-last=Duan |editor3-first=Zhenhua |editor4-last=Li |editor4-first=Angsheng}}

If we have information about the structure of $X$ we can model it as a graph $G(V,E)$, where every vertex $V=\backslash \{v\_\{1\},\backslash dots,\; v\_\{n\}\backslash \}$ represents a sample from the search space with $|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\}$and, if it does not belong to $M$, we sample the next vertex $v\_\{2\}$ among the ones connected to $v\_\{1\}$. This procedure is known as random walk search. To have a probability close to $1$ to find the marked node, we need to take asymptotically $O(1/\backslash epsilon\backslash delta\; )$ steps on the graph, where the parameter $\backslash delta$ is the spectral gap associated to the stochastic matrix $P$ of the graph.{{Cite book |last1=Magniez |first1=Frederic |last2=Nayak |first2=Ashwin |last3=Roland |first3=Jeremie |last4=Santha |first4=Miklos |title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |chapter=Search via quantum walk |date=2007-06-11 |chapter-url=https://doi.org/10.1145/1250790.1250874 |series=STOC '07 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=575–584 |doi=10.1145/1250790.1250874 |isbn=978-1-59593-631-8|s2cid=1918990 }}

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$ refers to the initialization of the stationary distribution over the vertices of the graph.

;Update

The update cost $U$ is the cost to simulate a transition on the graph according to the transition probability defined in $P$.

;Check

The check cost $C$ is the cost to verify if the current element belongs to the set $M$.

The total cost of a random walk search algorithm is $S+\backslash frac\{1\}\{\backslash epsilon\}\backslash biggl(\backslash frac\{1\}\{\backslash delta\}U\; +\; C\backslash biggr)$. The greedy version of the algorithm, where the check is performed after every step on the graph has a complexity of $S+\backslash frac\{1\}\{\backslash epsilon\; \backslash delta\}\backslash biggl(U+\; C\backslash biggr)$. The presence of the spectral gap term $\backslash 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.{{Cite book |last1=Levin |first1=David Asher |title=Markov chains and mixing times |last2=Peres |first2=Yuval |publisher=American Mathematical Society |others=Elizabeth L. Wilmer, James G. Propp, David Bruce Wilson, American Mathematical Society |year=2017 |isbn=978-1-4704-2962-1 |edition=Second |location=Providence, Rhode Island |pages=8–15}}

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 $|i\backslash rangle|j\backslash rangle$, which correspond to the edge from $v\_\{i\}$ to $v\_\{j\}$. To easily understand how it works, the algorithm can be explained through its geometric interpretation. We first define $|p\_\{i\}\backslash rangle\; =\; \backslash sum\_\{j\}\; \backslash sqrt\{P\_\{ij\}\}\; |j\backslash rangle$ as the uniform superposition over the neighbours of $|i\backslash rangle$. We additionally define the superposition over the marked and non-marked states, often referred to as the good and bad states, as

$|G\backslash rangle=\backslash frac\{1\}\{\backslash sqrt$

where $M$ is the set of marked elements. The uniform superposition over all the edges $U$ can be viewed a combination of good and bad states.

$|U\backslash rangle=\backslash frac\{1\}\{\backslash sqrt\{X\}\}\backslash sum\_\{i\; \backslash in\; X\}|i\backslash rangle\; |p\_\{i\}\backslash rangle\; =\; \backslash sin(\backslash theta)|G\backslash rangle\; +$

\cos(\theta)|B\rangle with $\backslash theta\; =\; \backslash arcsin(\backslash sqrt\{\backslash epsilon\})$.{{Cite arXiv|last=de Wolf |first=Ronald |date=2019 |title=Quantum Computing: Lecture Notes |class=quant-ph |eprint=1907.09415}}

File:Schematic view of quantum phase estimation on walk operator.png

The algorithm is composed of the following steps:

1. Initialize the quantum state with $|U\backslash rangle$, usually it is done by some state preparation routine.
2. Repeat for $O(1/\backslash sqrt\{\backslash epsilon\})$:
3. * Perform a reflection through $|B\backslash rangle$
4. * Perform a reflection through $|U\backslash rangle$
5. 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,{{Citation |last1=Brassard |first1=Gilles |chapter=Quantum Amplitude Amplification and Estimation |date=2002 |volume=305 |pages=53–74 |last2=Hoyer |first2=Peter |last3=Mosca |first3=Michele |last4=Tapp |first4=Alain|title=Quantum Computation and Information |series=Contemporary Mathematics |doi=10.1090/conm/305/05215 |arxiv=quant-ph/0005055 |isbn=9780821821404 |s2cid=54753 }} 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 $|U\backslash rangle$ and $|B\backslash rangle$ exhibit the effect of moving the quantum state toward the good state. After $k$ applications of the reflections the state can be written as $\backslash sin((2k+1)\backslash theta)|G\backslash rangle\; +\; \backslash cos((2k+1)\backslash theta)|B\backslash rangle$, and by setting $k\backslash thickapprox\; \backslash frac\{\backslash pi\}\{4\backslash theta\}\; =\; O(1/\backslash sqrt\{\backslash epsilon\})$ we have that $\backslash sin((2k+1)\backslash theta)\; \backslash thickapprox\; 1$ which yields the good state with a high probability.

;First reflection

The first reflection has the effect of checking if the current vertex is marked and applying a phase shift equal to $-1$ if it is so. 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 $|i\backslash rangle\; \backslash in\; M$.

;Second reflection

The second reflection is implemented with a quantum phase estimation over the walk operator $W$ which must reflect the structure of the graph we are exploring. The walk operator can be defined as $W=ref(\backslash mathcal\{B\})ref(\backslash mathcal\{A\})$ where $ref(\backslash mathcal\{B\})$ and $ref(\backslash mathcal\{A\})$ are two reflections through the subspaces $\backslash mathcal\{A\}=span\backslash \{|i\backslash rangle,\; |p\_\{i\}\backslash rangle\backslash \}$ and $\backslash mathcal\{B\}=span\backslash \{|p\_\{j\}\backslash rangle,\; |j\backslash rangle\backslash \}$. Since the eigenvalues of $W$ are on the form $e^\{\backslash pm2i\backslash theta\}$and the operator has a unique eigenvalue equal to $1$ corresponding to $|U\; \backslash rangle$ given by $\backslash theta\; =\; 0$, we can perform a phase estimation with precision $O(1/\backslash sqrt\{\backslash delta\})$ to find the unique eigenvalue. The precision of the reflection depends on the number of qubits used to estimate the phase.

;Complexity

With the same formalism used to estimate the cost of the classical random walk algorithm, the quantum costs can be summarised with:

• S: is the cost to initialize the superposition $|U\backslash rangle$
• U: is the cost perform a step on the graph in superposition i.e. reflection through $|U\backslash rangle$
• C: is the cost to implement the quantum oracle i.e. reflection through $|B\backslash rangle$

The total cost of the quantum walk search is $S+\backslash frac\{1\}\{\backslash sqrt\{\backslash epsilon\}\}\backslash biggl(\backslash frac\{1\}\{\backslash sqrt\{\backslash delta\}\}U\; +\; C\backslash biggr)$, 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.{{Cite thesis |title=Quantum Cost Models for Cryptanalysis of Isogenies |url=https://uwspace.uwaterloo.ca/handle/10012/14612 |publisher=University of Waterloo |date=2019-05-01 |degree=Master Thesis |language=en |first=Samuel |last=Jaques}}p 67-68.

This is an example of how to apply the quantum walk search on a hypercube graph.{{Cite web |title=Quantum Walk Search Algorithm |url=https://learn.qiskit.org/ |access-date=2023-07-05 |website=learn.qiskit.org |language=en}}

File:Hypercubestar binary.svg

Although in the original description Szegedy quantum walks are used, for this example we show the use of coined quantum walk as it is more intuitive to understand. In any case, the two formalizations turn out to be equivalent under specific assumptions.{{Cite journal |last=Wong |first=Thomas G. |date=2017 |title=Equivalence of Szegedy's and Coined Quantum Walks |journal=Quantum Information Processing |volume=16 |issue=9 |pages=215 |doi=10.1007/s11128-017-1667-y |arxiv=1611.02238 |bibcode=2017QuIP...16..215W |s2cid=254985379 |issn=1570-0755}}

The search space is a $n$-hypercube with $n=4$, it has $|V|=2^\{4\}$ vertices and it has a degree equal to $4$. Each node $v\_\{i\}$ can be labeled with a binary string of $4$ bits and two nodes are connected by an edge if their Hamming distance is $1$. To set up the quantum walk search we need a coin register of dimension $\backslash mathcal\{H\}^\{n\}$ to encode all the possible directions which a walker can choose and a vertex register of dimension $\backslash mathcal\{H\}^\{2^\{n\}\}$to represent the vertices.

The computational basis is $|d\backslash rangle\; |v\backslash rangle$ with$\backslash \{d\; \backslash in\; D=\backslash \{00,01,10,11\backslash \},v\; \backslash in\; V=\backslash \{0000,0001,\; \backslash dots\; ,1111\backslash \}\backslash \}$.

The walk is performed by two operators:

• Coin operator $C$ is used to create the superposition over the possible directions
• Shift operator $S$ is used to take a step in the graph according to one direction

Thus, the walk operator is $W=SC$.

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. The shift operator can be written as:

$S=\backslash sum\_\{d=1\}^\{n\}\backslash sum\_\{v=1\}^\{n\}|d\backslash rangle|v\; \backslash oplus\; e\_\{d\}\; \backslash rangle\; \backslash langle\; d\; |\; \backslash langle\; v|$

where $e\_\{d\}$ is the $d$-basis for the hypercube ( if $n=4$ the basis are $\backslash \{0001,0010,0100,1000\backslash \}$). For the coin there are multiple choices such as the Grover coin or the Fourier coin, one can choose the Grover coin to have an equal superposition over all the directions.

The algorithm works as follows:

1. Repeat for $O(1/\backslash sqrt\{\backslash epsilon\})$
2. * Initialise the counting register for the phase in superposition
3. * Perform a phase estimation on $W$ with $O(1/\backslash sqrt\{\backslash delta\})$ precision
4. * Mark an auxiliary qubit if the estimated phase is $\backslash tilde\{\backslash theta\}=0$
5. * Un-compute auxiliary data structure
6. Measure the vertex register

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.{{Cite arXiv|last1=Douglas |first1=B. L. |last2=Wang |first2=J. B. |date=2007 |title=Efficient quantum circuit implementation of quantum walks |class=quant-ph |eprint=0706.0304 }}

The following applications are based on quantum walk on Johnson graph $J(n,k)$.{{Cite journal |last1=Agong |first1=Louis Anthony |last2=Amarra |first2=Carmen |last3=Caughman |first3=John S. |last4=Herman |first4=Ari J. |last5=Terada |first5=Taiyo S. |date=2018-01-01 |title=On the girth and diameter of generalized Johnson graphs |journal=Discrete Mathematics |language=en |volume=341 |issue=1 |pages=138–142 |doi=10.1016/j.disc.2017.08.022 |s2cid=257985351 |issn=0012-365X|doi-access=free |arxiv=2304.02864 }}

;Element distinctness

Given a function $f$ defined on $\backslash \{n\backslash \}$, it asks to find two distinct elements $i,j\; \backslash in\; \backslash \{n\backslash \}$ such that $f(i)=f(j)$ if there exist such a pair.{{Cite journal |last=Ambainis |first=Andris |date=2007 |title=Quantum Walk Algorithm for Element Distinctness |url=http://epubs.siam.org/doi/10.1137/S0097539705447311 |journal=SIAM Journal on Computing |language=en |volume=37 |issue=1 |pages=210–239 |doi=10.1137/S0097539705447311 |issn=0097-5397|citeseerx=10.1.1.251.5460 }}

;Matrix product verification

Given three $n\backslash times\; n$ matrices $A,B$ and $C$, the problem asks to verify if $AB=C$ or otherwise find the indices $i,j$ such that $(AB)\_\{i,j\}\; \backslash neq\; C\_\{i,j\}$.

;Triangle

A triangle is a complete subgraph on three vertices part of an undirected graph $G$. Given the adjacent matrix of a graph the problem asks to find a triangle if there is any.

• Grover's algorithm
• Quantum phase estimation
• Quantum walk
• Random walk

• {{Cite book |last1=Nielsen |first1=Michael A. |title=Quantum computation and quantum information |last2=Chuang |first2=Isaac L. |date=2010 |publisher=Cambridge university press |isbn=978-1-107-00217-3 |edition=10th anniversary |location=Cambridge}}
• {{Cite book |last1=Lawler |first1=Gregory F. |url=https://www.cambridge.org/core/books/random-walk-a-modern-introduction/7DA2A372B5FE450BB47C5DBD43D460D2 |title=Random Walk: A Modern Introduction |last2=Limic |first2=Vlada |date=2010 |publisher=Cambridge University Press |isbn=978-0-521-51918-2 |series=Cambridge Studies in Advanced Mathematics |location=Cambridge |doi=10.1017/cbo9780511750854}}
• {{Cite book |last=Hidary |first=Jack D. |title=Quantum computing: an applied approach |date=2019 |publisher=Springer |isbn=978-3-030-23921-3 |location=Cham, Switzerland}}

• [https://medium.com/@qcgiitr/quantum-walk-9acb8ae2a20a Quantum Walk]
• [https://github.com/qiskit-community/qiskit-community-tutorials/blob/master/terra/qis_adv/quantum_walk.ipynb Implementation of quantum walk on cycle graph]
• [https://medium.com/qiskit/studying-quantum-walks-on-near-term-quantum-computers-f60fd2395f04 Studying quantum walks on near term quantum computers]

{{Quantum information}}

Category:Quantum algorithms