$$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$$
$$\newcommand{\bra}[1]{\left\langle{#1}\right|}$$
$$\newcommand{\braket}[2]{\left\langle{#1}\middle|{#2}\right\rangle}$$

## Search on a cube cloud
The SKW search algorithm is based on discrete quantum walk on a hypercube and it is a convenient algorithm for searching a disordered database. In this algorithm, walk is performed on an n-dimensional hypercube and the number of data problem is $N = 2^n$.
We place the specified $N$ data on the vertices of the cube cloud and represent each vertex with an n-bit string. The two vertices x and y are connected only if the Hamming weight difference is one, i.e. 

\begin{equation}
    |\bar{x} - \bar{y}| = 1.
\end{equation}

Figure 3.1 The data mapping on the hypercube grid is displayed in $d = 3$. Three-component bit strings represent the vertices, and the edges are labeled based on which bit must be flipped to reach the adjacent vertex. For the $n$ qubit string $\textbf{x} = (0010000010) $, Hamming weight is defined as follows [[S07]](https://arxiv.org/abs/0712.0625):
\begin{equation}
    |x = \sum_{i=1}^n x_i|.
\end{equation}

Since the cube cloud is symmetric and each vertex is connected to n edges, a quantum walk is done with the n-dimensional coin. Hilbert space and system state are defined as $H = H^n \otimes H^{2n}$ and $\ket{d,\bar{x}}$ respectively, where $d$ denotes the state of the coin. The conditional displacement operator also maps the state $\ket{d,\bar{x}}$ to the state $\ket{d,\bar{x} \oplus \bar{e}_d}$, representing the -th vector of the base of the hypercube (a vector whose all components are zero except the n-th component. Therefore, the unitary displacement operator is defined as follows [[S08]](https://arxiv.org/abs/quant-ph/0205083):

\begin{equation}
    S = \sum_{d,\bar{x}}^{n-1} \ket{d,\bar{x} \oplus \bar{e}_d} \bra{d,\bar{x}}
\end{equation}

According to this equation, the point's position will move to an adjacent vertex in the direction of the edge $d$, and the coin operator must be unitary transformation. In standard quantum spinning, only one coin operator is used, which is applied to all vertices of the graph (i.e., the coin operator does not change from one vertex to another), so the coin operator can be written as a separable:

\begin{equation}
    C = C. \otimes I
\end{equation}

Choosing the suitable coin operator is important in advancing the algorithm, since we tend to consider all the edges leading to the vertex of the target to be of equal value, so the probability of the point remaining in the current state $\ket{d,\bar{x}}$ for all values $d$ must be the same. Also, for all $d$ the range of transitions from $\ket{d,\bar{x}}$ to $\ket{d^{'},\bar{x}}$ must be the same. The only unit matrices that satisfy these conditions are: G, -G, I, -I. An appropriate and efficient choice is the Grover diffusion operator, which is a suitable unitary operator, and with this choice, the amplitudes of probability are propagated by quantum walk at the maximum possible speed [[S09]](http://stephanhoyer.com/pubs/thesis.pdf). This operator is defined as follows:

\begin{equation}
    C. = G = -I_n + \ket{s^c} \bra{s^c},
\end{equation}


Fig. 2) Quantum walk mapping on a cube cloud for one-dimensional walk, in n = 3.

Or in the matrix form:

\begin{equation}
    G = \begin{pmatrix}
\frac{2}{n} - 1 & ... & \frac{2}{n}\\
: & ... & : \\
\frac{2}{n} & ... & \frac{2}{n} -1
\end{pmatrix},
\end{equation}

In which

\begin{equation}
    \ket{s^c} = \frac{1}{\sqrt{n}} \sum_{d=1}^n \ket{d},
\end{equation}

where $\sum_{d=1}^n \ket{d}\bra{d} = I_n$.

A classical walk on a Hypercube has excellent symmetry. For example, if we start from the vertex, all vertices with the same Hamming weight can be moved together without correcting the quantum walk. This permutation applies to other vertices with the same Hamming weight. Slowly This symmetry requires that all vertices with the same Hamming weight in the probability distribution fall.

Classically, they have the same weight, so we can add vertices of the same weight at the same vertex and reduce the random walk on the cube to a balanced spin on the line [[S10]](https://arxiv.org/abs/quant-ph/0303081). The probability of transition from vertex $i$ to vertex $i+1$ is equal to $P_{i,i+1} = \frac{d - i}{d}$. In addition to being uniform and highly diffused, the Graver coin also maintains permutation symmetry. The Gravure coin is inaccurate concerning the simultaneous permutation of rows and columns. In addition, it is not a balanced coin, meaning that the probability that the coin will not change direction is not equal to the probability that the coin will change direction [[S10]](https://arxiv.org/abs/quant-ph/0303081). To analyze the dynamics of the quantum walk, we need to consider the transformation operator: $U = S.(C.\otimes I)$. For this purpose, the general state of the system after  steps can be written as follows,

\begin{equation}
    \ket{\psi (t)} = \sum_{d=1}^n \sum_{\bar{x} = 1}^{2^n - 1} \psi_{d,\bar{x}} (t) \ket{d,\bar{x}},
\end{equation}

where $\psi_{d,\bar{x}} (t)$ is the probability of amplitude and normal condition would be accrue. In general, this equation is very difficult to solve, but the same efficient Fourier transform method can be used to diagonalize this operator. In computational foundations, the discrete Fourier transform on space is as follows:

\begin{equation}
    \ket{\bar{k}} = \frac{1}{\sqrt{2^n}} \sum_{\bar{x} = 1}^{2^n - 1} (-1)^{\bar{K},\bar{x}} \ket{\bar{x}},
\end{equation}

Where $\ket{\bar{k}}$ comes from Fourie transformation. Now, by diagonalizing the transformation operator, the following equation can be obtained,

\begin{equation}
    e^{\pm i \omega_k} = 1 - \frac{2k}{n} \pm 2i \sqrt{\frac{k}{n} (1 - (k/n))}.
\end{equation}

Therefore, the specifics of normal transformations vector operators can be written as follows

\begin{equation}
    \ket{v_k},\ket{v_k}^* = \sum_{\bar{x},d} (-1)^{\bar{k}.\bar{x}} \frac{2^{-\frac{n}{2}}}{\sqrt{2}} \ket{d,\bar{x}} \times \begin{matrix}
1/\sqrt{k} && k_d = 1 \\
\mp i / \sqrt{n -  k} && k_d = 0
\end{matrix} 
\end{equation}

Because of the symmetry in the hypercube, vertices can be labeled so that the vertex is always marked $\bar{x}_{tg} = \bar{0}$, so without diminishing the totality of the problem, we always assume that the vertex sought is $\bar{0}$. Therefore, the location of this vertex is not important. As a result, the disturbance in the coin operator, which indicates the spatial dependence of the new operator, is described as follows


\begin{equation}
     C^{'} = C.\otimes (I_{2^n} - \ket{\bar{x}_{tg}} \bra{\bar{x}_{tg}} + C_1 \otimes \ket{\bar{x}_{tg}} \bra{\bar{x}_{tg}}),
\end{equation}

In this phrase, the first sentence, the coin $C_0$, is applied to all vertices except the vertex of the target. With these descriptions, the unit transformation operator is disrupted as follows

\begin{align*}
    U^{'} &= S.C^{'} \\
    &= S.(G \otimes I - (G - I) \otimes \ket{\textbf{0}}\bra{\textbf{0}})\\
    &= U - 2S.(\ket{s^C}\bra{s^C} \otimes \ket{\textbf{0}}\bra{\textbf{0}})
\end{align*}

Analysis of the effect of this disorder will lead to the definition of a quantum walk search algorithm. The conditions are created for the particle that initially starts from a uniform distribution in the whole space to eventually converge to the vertex of the search by applying a small perturbation. This process is contrary to the standard quantum walk, in which the particle starts moving from a point and spreads throughout space.




Fig. 3) Simulation of the search algorithm on a cube, in n = 2 mode, when the searched vertex is $\ket{0}$ [[S09]](http://stephanhoyer.com/pubs/thesis.pdf).




Fig. 4) Quantum circuit of quantum spin search algorithm on n-dimensional transduce network.

2d186ca0df2fb72ea867833310ab49456f5e47ee
ipynb
Jupyter Notebook
.ipynb_checkpoints/Search on a cube cloud-checkpoint.ipynb
Spintronic6889/Introduction-of-Quantum-walk-its-application-on-search-and-decision-making
a7cae6ee6a532a1d8a2f22cb25c5d4502a4ef493
Apache-2.0
2022-01-20T12:42:19.000Z
2022-01-20T12:42:19.000Z
.ipynb_checkpoints/Search on a cube cloud-checkpoint.ipynb
Spintronic6889/Introduction-of-Quantum-walk-its-application-on-search-and-decision-making
a7cae6ee6a532a1d8a2f22cb25c5d4502a4ef493
Apache-2.0
.ipynb_checkpoints/Search on a cube cloud-checkpoint.ipynb
Spintronic6889/Introduction-of-Quantum-walk-its-application-on-search-and-decision-making
a7cae6ee6a532a1d8a2f22cb25c5d4502a4ef493
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES