## 2 Quantum Random Walk Search with an Alternative Walk Coin  
### Quantum Random Walk Search Algorithm  
Quantum random walk search is a quantum algorithm designed for searching an unsorted database with arbitrary topology. Because of the faster traversing of structures by the quantum random walk, QRWS is quadratically faster than its classical counterpart. The algorithm is probabilistic with the probability to find a solution depending on the node register size [13], topology of the searched structure [4; 16], modification of the algorithm [16], and the number and position of the solutions [52; 53]. The quantum circuit of the QRWS algorithm in the case of qudits is shown in Figure 1.  
The algorithm begins with preparing the initial states of node (\(|x_{init}\rangle\)) and edge (\(|c_{init}\rangle\)) registers in equal weight superposition and the control register qubit is in state \(|0\rangle\). Such superposition can be achieved by applying the Discrete Fourier Transform operator on the coin and node registers when each of them is in state \(|0\rangle\). In Figure 1, those operators are denoted by \(F_{m}\) and \(F_{n}\). \[|c_{init}\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^{m}|i\rangle \tag{1}\]  
\[|x_{init}\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle \tag{2}\]  
The dimensions of control, node, and coin registers are 2, \(n\) and \(m\), accordingly. The initial state of the whole algorithm has dimension \(2 mn\) and can be written as follows:  
\[|\psi_{0}\rangle=|x_{init}\rangle\otimes|c_{init}\rangle\otimes|0\rangle \tag{3}\]  
In the case of hypercube \(n=2^{m}\), so the dimension of the initial state is \(m2^{m+1}\). The algorithm continues by applying the algorithm's iteration a fixed number of times. The probability to find a solution is a periodic function of the number of iterations. Each iteration consists of the following steps:  
First, an Oracle (\(O\)) is applied. Its goal is to recognize a solution and mark it, to ensure that the first coin \(C_{0}\) (traversing coin) is applied to all non-solutions and the second coin \(C_{1}\) (marking coin) is applied to all solutions. We have the following elements that are solutions \(h_{1},\ldots,h_{\lambda}\). The Oracle has dimension \(2n\) (in the case of hypercube \(2^{m+1}\)) and the following matrix form:  
\[O=\hat{I}_{2n}-\sum_{i=1}^{\lambda}[h_{i},h_{i}]-\sum_{i=1}^{ \lambda}[h_{i}-n,h_{i}-n]+\] \[\sum_{i=1}^{\lambda}[h_{i},h_{i}-n]+\sum_{i=1}^{\lambda}[h_{i}-n, h_{i}] \tag{4}\]  
Here, \(\hat{I}_{2n}\) is the identity operator with dimension \(2n\), and \([r,c]\) denotes matrix element with value \"1\" positioned on the r-th row and c-th column. In this way, all register elements that are not solutions continue to stay in the second half of the register and all that are solutions are separated by moving them in the first half. Traversing \(C_{0}\) and marking coins \(C_{1}\) are applied using controlled gates. Both controlled gates have block diagonal matrix representation and can be written as:  
\[\mathcal{C}_{0}= \begin{pmatrix}\hat{I}_{m\
eq n}&0_{m\
eq n}\\ \hat{0}_{m\
eq n}&C_{0}\otimes\hat{I}_{n}\end{pmatrix}  \tag{5}\]  
Figure 1: (Color online) Circuit of quantum random walk search algorithm. \[\mathcal{C}_{1}= \begin{pmatrix}C_{1}\otimes\hat{I}_{n}&0_{m*n}\\ \hat{0}_{m*n}&\hat{I}_{m*n}\end{pmatrix}  \tag{6}\]  
where \(0_{mn}\) is a matrix with dimension \(m*n\) with all elements equal to zero. Hence, the simultaneous action of both controlled coins can be written as sequential applying of both operators:  
\[\mathcal{C}^{\prime}=\mathcal{C}_{0}\cdot\mathcal{C}_{1} \tag{7}\]  
The operator \(\mathcal{C}^{\prime}\) acts on the node, coin, and control registers. This ensures applying the right coin on the nodes. However, after acting with the coin operators, the whole circuit's register has to be returned to its initial form to ensure that the shift operator will make the desired walk. This should be performed by applying the inverse matrix of the Oracle. However, the Oracle is the inverse matrix of itself.