Preparing the Quantum Register:
-
We start by preparing $n$-qubit to hold states in the set $\{0,1\}^n$ i.e. bit strings of length $n$.
-
Then we need to initialize them to the state $\ket{0}^{\otimes n}=\ket{00..0}$ and apply the Hadamard Transform to the first qubit of $\ket 0^{\otimes n}$to turn it into
$$ \frac{1}{\sqrt{2}} (\ket{0}-\ket{1}) $$
-
We then apply the Hadamard transformation $H^{\otimes n}$ on the initial $\ket{0}^{\otimes n}$ (all of them)
$$ \ket{\psi}=H^{\otimes n} \ket{0}^{\otimes n} =\frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} \ket{x} $$
🗒️ Note: Here we applies the Hadamard separately to the first qubit and then combined for all the other qubits in the registry
Defining the operators:
-
The oracle $O$ is an operator that identifies solutions. It is defined as:
$$ O : \ket{x} \ket{y} \mapsto \ket{x} \ket{y \oplus f(x)} $$
The $\oplus$ operation (XOR) flips $y$ when $f(x)=1$.
-
The Grover $G$ which is defined as follows
$$ G=H^{\otimes n}P_0 H^{\otimes n}O $$
where we have
$$ P_0:\left \{ \begin{aligned} &\ket{0}^{\otimes n} \to -\ket{0}^{\otimes n} \\ &\ket{x}\to\ket{x} \;\text{for} \; x \ne 0^n \end{aligned}\right . \quad \text{or} \quad P_0=2\ket{0}^{\otimes n}\bra{0}^{\otimes n}-I $$
We can rewrite the Grover $G$ as
$$ G=(2\ket{\psi}\bra{\psi} -I)O $$
Algorithm
-
now the oracle $O$ acts for $x\in \{0,1\}^n$ to do
$$ O:\ket{x} \frac{\ket{0}-\ket{1}}{\sqrt{2}} \to(-1)^{f(x)} \ket{x}\frac{\ket{0}-\ket{1}}{\sqrt{2}} $$
The first qubit remains constant in the interaction we thus remove it as it isn't a result
$$ O:\sum_{x\in \{ 0,1 \}^n} \alpha_x \ket{x} \to \sum_{x\in \{ 0,1 \}^n} (-1)^{f(x)}\alpha_x\ket{x} $$
-
We then repeatedly apply $G$ to amplify the amplitude of the solution states until we get our output to a high confidence
We can represent the algorithm like this:
