The algorithm for finding solutions to the search problem using a quantum computer finds a solution with a much smaller number of steps than a classical computer.

In the case of a quantum computer, when there is only one solution to the problem and \(N\) elements to search (for example, we want to find a password from \(N\) possible passwords), the number of operations required is \(O(\sqrt{N})\), while for classical computers it is \(O(N)\).
For example, if we have a password consisting of \(6\) characters, the number of which is equal to \(50\), then on a classic computer we would need to check \(50^{6}=15625000000\) possible passwords, whereas on a quantum computer only approximately \(50^{3}=125000\) iterations are needed to find correct password.

Definitions

Suppose we have a space of \(N\) elements that we will search in order to find exactly \(M\) solutions for a given problem, we assume that \(M \in [1 ,N/2]\). Instead of looking for elements we will look for the indexes of these elements in the range from \(0\) do \(N−1\). In addition, we will simplify the situation assuming that \(N =2^{n}\), that is, index is stored in \(n\) bits. The solution of the problem can be described by the function \(f(x)\), which takes the index \(x\) as an argument and returns the value \(1\) if the index matches the solution or \(0\), if the given index is not a solution to the problem.

Let’s start with defining the operation \(O\) as follows:

\(\begin{equation}\left \vert x\right \rangle \left \vert q\right \rangle \overset{O}{ \longrightarrow }\left \vert x\right \rangle \left \vert q \oplus f(x)\right \rangle \end{equation}\)where \( \oplus \) denotes addition modulo \(2\). That is, a single qubit \(\left \vert q\right \rangle \) which is equal to \(\left \vert 0\right \rangle\) or\(\left \vert 1\right \rangle\) will be changed only if \(f(x) =1\), which means that \(x\) is the solution.

Below we will use qubit:

\(\begin{equation}\left \vert q\right \rangle =\frac{1}{\sqrt{2}}(\left \vert 0\right \rangle -\left \vert 1\right \rangle ) \end{equation}\)
which we get from qubit \(\left \vert 0\right \rangle \) after operation \(HX\), where:

\(
\begin{align}X =\left (\begin{array}{cc}0 & 1 \\
1 & 0\end{array}\right ) \\
\end{align}
\)
and

\(
\begin{align}
H =\frac{1}{\sqrt{2}}\left (\begin{array}{cc}1 & 1 \\
1 & -1\end{array}\right )\end{align}
\)
where \(H\) is called the Hadamard operation.

Therefore, \(O\) operation can also be defined as follows:

\(\begin{equation}\left \vert x\right \rangle \left \vert q\right \rangle \overset{O}{ \longrightarrow }( -1)^{f(x)}\left \vert x\right \rangle \left \vert q\right \rangle \end{equation}\)

Algorithm

The goal of the algorithm is to find a solution at the smallest possible amount of the operation of \(O\).

We start from the computer in state \(\left \vert 0\right \rangle ^{ \otimes n}\left \vert 0\right \rangle \) (\(\left \vert 0\right \rangle ^{ \otimes n}\) corresponds to the index \(x=0\)), applying the Hadamard transform \(H^{ \otimes n}\) to state \(\left \vert 0\right \rangle ^{ \otimes n}\) and \(HX\) to last qubit. We get equal superposition state:

\(\begin{equation}\left \vert \psi \right \rangle =\frac{1}{N^{1/2}}\sum \limits _{x =0}^{N -1}\left \vert x\right \rangle \left \vert q\right \rangle \end{equation}\)The quantum algorithm consists of the repeated application of the \(G\) operator, whose single application can be described as follows:

1. Apply \(O\)
2. Apply the Hadamard transform \(H^{ \otimes n}\)
3. Phase change to \(-1\) in each state \(\left \vert x\right \rangle \left \vert q\right \rangle \), except \(\left \vert 0\right \rangle \left \vert q\right \rangle\):\(\begin{equation}\left \vert x\right \rangle \left \vert q\right \rangle \longrightarrow -( -1)^{\delta _{x0}}\left \vert x\right \rangle \left \vert q\right \rangle
   \end{equation}\)
4. Apply the Hadamard transform \(H^{ \otimes n}\)

By combining steps 2, 3 and 4 we get:

\(\begin{equation}H^{ \otimes n}(2\vert 0\rangle \left \vert q\right \rangle \left \langle q\right \vert \left \langle 0\right \vert -I)H^{ \otimes n} =2\left \vert \psi \right \rangle \left \langle \psi \right \vert -I\end{equation}\)Therefore, the \(G\) operator can be expressed by means of a formula \(G =(2\left \vert \psi \right \rangle \left \langle \psi \right \vert -I)O \).
Let’s define two orthonormal states:

\(\begin{align}\left \vert \alpha \right \rangle =\frac{1}{\sqrt{N -M}}\sum _{x}\left \vert x\right \rangle \left \vert q\right \rangle \\\left \vert \beta \right \rangle =\frac{1}{\sqrt{M}}\sum _{y}\left \vert y\right \rangle \left \vert q\right \rangle \end{align}\)
where sum over \(y\) is sum over all indexes which are solutions to the search problem, and sum over \(x\) is sum over all indexes which are not solutions to the search problem. It is easy to show that the following equality occurs:

\(
\begin{equation}\left \vert \psi \right \rangle =\sqrt{\frac{N -M}{N}}\left \vert \alpha \right \rangle +\sqrt{\frac{M}{N}}\left \vert \beta \right \rangle
\end{equation}
\)
By calculating the matrix elements \(G\) in the basis states \(\left \vert \alpha \right \rangle \) and \(\left \vert \beta \right \rangle \) we obtain, that \(G\) is the operator of rotation in the two-dimensional space spanned by these states:

\(
\begin{equation}G =\left (\begin{array}{cc}\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta \end{array}\right )
\end{equation}
\)
where \(\cos \theta =(N -2M)/N\). State \(\left \vert \psi \right \rangle \) can be expressed by \(\theta\) as:

\(
\begin{equation}\left \vert \psi \right \rangle =\cos \frac{\theta }{2}\left \vert \alpha \right \rangle +\sin \frac{\theta }{2}\left \vert \beta \right \rangle
\end{equation}
\)
Applying of \(G\) \(k\) times we obtain:

\(
\begin{equation}G^{k}\left \vert \psi \right \rangle =\cos \left (\frac{2k +1}{2}\theta \right )\left \vert \alpha \right \rangle +\sin \left (\frac{2k +1}{2}\theta \right )\left \vert \beta \right \rangle
\end{equation}
\)
Therefore, by applying the operator \(G\) many times, we turn the state \(\left \vert \psi \right \rangle \) close to the state \(\left \vert \beta \right \rangle \), so observation yields the correct answer with high probability.
Because the initial state has the form \(\left \vert \psi \right \rangle =\sqrt{\frac{N -M}{N}}\left \vert \alpha \right \rangle +\sqrt{\frac{M}{N}}\left \vert \beta \right \rangle\), so in the space of two basis states \(\left \vert \alpha \right \rangle \) and \(\left \vert \beta \right \rangle \) rotation of the initial state by an angle \(\arccos \sqrt{M/N}\) transform it into the state \(\left \vert \beta \right \rangle \). Let \([z]\) be the nearest integer for the real number z. Thus, the number of rotations made by \(G\):

\(
\begin{equation}R =\left [\genfrac{}{}{}{}{\arccos \sqrt{M/N}}{\theta }\right ]\end{equation}
\)
transform the state \(\left \vert \psi \right \rangle\) close to the solution \(\left \vert \beta \right \rangle \). Because \(R\leq [\pi /2\theta ]\), so an upper bound on \(R\) is taken from a lower bound on \(\theta\). Because \(\theta /2 \geq \sin \theta /2 =\sqrt{\frac{M}{N}}\), hence we get the upper bound of the required amount of iteration:

\(
\begin{equation}R \leq \left [\frac{\pi }{4}\sqrt{\frac{N}{M}} \, \right ]
\end{equation}
\)
Finally we get, that \(R =O(\sqrt{N/M})\). Therefore only for one solution, \(M=1\), \(R =O(\sqrt{N})\), in the classic case we would get \(R=O(N)\).

Share: