8 Bernstein-Vazirani Algorithm
With all the quantum basics from the previous chapters, we now can start with the first quantum algorithm. This algorithm is called the Bernstein-Vazirani algorithm.
This algorithm tackles the following problem: Given a secret \(s \in \{0,1\}^n\) and the function \(f: \{0,1\}^n \rightarrow \{0,1\}\), defined as \(f(x):=x \cdot s\). \(\cdot\) denotes the inner product of two bitstrings here. This means that for bitstrings \(x\) and \(y\) of length \(n\), the inner product is \(x\cdot y = x_1y_1 + \dots + x_ny_n \bmod 2\).
The goal is to find the secret \(s\) using as little queries of \(f\) as possible. By “query” we mean an evaluation of \(f\). The word query stems from the fact that we often think of the algorithm having access to a so-called “oracle” which we can “query” to get \(f(x)\).
Classically we will need at least \(n\) queries to \(f\) to get \(s\) definitely. A classical algorithm with only \(m \leq n\) queries will get \(s\) with a probability of \(2^{m-n}\) if \(s\) is uniformly random.
We will now look at a quantum algorithm which will find \(s\) with only one evaluation of \(f\). This algorithm is sketched in the following circuit:
Note that \(U_f\) is defined with the explanation below.
We start with \(n\) qubits on the top wire. All of these qubits are in the state \(\ket{0}\), which we write \(\ket{0}^n = \ket{0} \otimes \dots \otimes \ket{0}\). The bottom wire is in the state \(\ket{1}\). Both wires composed together can be written as \(\psi_1 = \ket{0}^n \otimes \ket{1}\), which is the overall starting state of our algorithm (the state at slice 1). We now perform the following steps
First we apply a Hadamard gate on all qubits. This is denoted for the first \(n\) qubits by the \(H^{\otimes n}\) gate and for the last qubit by the \(H\) gate on the bottom wire. The resulting quantum state is calculated as follows: \[ \begin{aligned} \psi_2&= \left(H^{\otimes n} \otimes H\right) \left(\ket{0}^n \otimes \ket{1}\right)\\ &=\left(H^{\otimes n}\ket{0}^n\right) \otimes H\ket{1}\\ &=\left(\ket{+}\right)^{\otimes n} \otimes \ket{-}\\ &=\left(\frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1} \right)^{\otimes n} \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} \ket{x} \otimes \ket{-} \end{aligned} \] Roughly speaking, we are now in the superposition over all classical possibilities on the top wire and in \(\ket{-}\) on the bottom wire at slice 2.
Next, we apply the unitary \(U_f\) on both wires. This unitary is defined as \[ U_f\,\ket{x,y} = \ket{x,y \oplus f(x)} \] This unitary represents the function \(f\) and combines the output of \(f(x)\) with the bottom wire \(y\). For our quantum states, this means that the state after \(U_f\) at slice 3 can be calculated as follows: \[ \begin{aligned} \psi_3&=U_f\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} \ket{x} \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} U_f\Bigl (\ket{x} \otimes \ket{-}\Bigr) \\ &\stackrel{*}{=}\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} (-1)^{f(x)}\ket{x} \otimes \ket{-} \\ &=\left(\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} (-1)^{f(x)}\ket{x} \right) \otimes \ket{-} \end{aligned} \] Note that the \(*\) holds since we can rewrite \(U_f(\ket{x}\otimes\ket{-})\) as \[ \begin{aligned} &U_f\Bigl(\ket{x}\otimes\ket{-}\Bigr)\\ &= \frac{1}{\sqrt{2}} U_f\ket{x,0} - \frac{1}{\sqrt{2}} \ket{x,1}\\ &= \frac{1}{\sqrt{2}} \ket{x,f(x)} - \frac{1}{\sqrt{2}} \ket{x,\overline{f(x)}}\\ &= \begin{cases} \frac{1}{\sqrt{2}} \ket{x,0} - \frac{1}{\sqrt{2}} \ket{x,1} & f(x)=0\\ \frac{1}{\sqrt{2}} \ket{x,1} - \frac{1}{\sqrt{2}} \ket{x,0} & f(x)=1 \end{cases}\\ &= \begin{cases} \ket{x} \otimes \ket{-} & f(x)=0\\ -\ket{x} \otimes \ket{-} & f(x)=1 \end{cases}\\ &= (-1)^{f(x)} \ket{x} \otimes \ket{-} \end{aligned} \] The bottom wire has not changed and is still \(\ket{-}\). But on the top wire, we now have \(f(x)\) somehow encoded into our quantum state. The phenomenon that the output of \(f\) is encoded as a \(-1\) in the input register is called phase kickback. Measuring this quantum state would not give us any advantage, since we would just get one random \(x\). We therefore perform one final step before measuring.
As the final unitary, we perform another \(H^{\otimes n}\) on the top wire. We hope that the result of this unitary transformation is the state \(\ket{s}\). To check, whether our hopes become reality, we can calculate \(\left(H^{\otimes n}\right)^\dagger \ket{s} \otimes \ket{-}\) and check if it is equal to \(\psi_3\). We do it in this direction, since these calculations are a bit simpler: \[ \begin{aligned} \left( H^{\otimes n}\right )^\dagger \ket{s}\otimes \ket{-} &= H^{\otimes n} \ket{s}\otimes \ket{-} \\ &= H^{\otimes n} (\ket{s_1} \otimes \dots \otimes \ket{s_n})\otimes \ket{-}\\ &= H\ket{s_1} \otimes \dots \otimes H\ket{s_n}\otimes \ket{-}\\ &= \bigotimes_{i=1}^n \left(\frac{1}{\sqrt{2}} \ket{0} + (-1)^{s_i}\frac{1}{\sqrt{2}} \ket{1}\right) \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\bigotimes_{i=1}^n \Bigl( \ket{0} + (-1)^{s_i}\ket{1}\Bigr) \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n} \Bigl( (-1)^{x_1s_1}(-1)^{x_2s_2}\dots(-1)^{x_ns_n}\ket{x}\Bigr) \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n} \left( (-1)^{\sum_i x_is_i \bmod 2}\ket{x}\right) \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n} (-1)^{s\cdot x}\ket{x} \otimes \ket{-}\\ &=\frac{1}{\sqrt{2^{n}}}\sum_{x\in \{0,1\}^n} (-1)^{f(x)}\ket{x} \otimes \ket{-}\\ &= \psi_3 \end{aligned} \] This calculation shows that we have the quantum state \(\ket{s} \otimes \ket{-}\) at slice 4.
We now perform a measurement on the top wire and measure \(s\) as a result.
This concludes the Bernstein-Vazirani algorithm.