1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
---
title: "Bernstein-Vazirani algorithm"
firstLetter: "B"
publishDate: 2021-05-01
categories:
- Quantum information
- Algorithms
date: 2021-04-13T10:28:44+02:00
draft: false
markup: pandoc
---
# Bernstein-Vazirani algorithm
In quantum information,
the **Bernstein-Vazirani algorithm** proves
the supremacy of quantum computers
over classical deterministic or probabilistic computers.
It is extremely similar to the
[Deutsch-Jozsa algorithm](/know/concept/deutsch-jozsa-algorithm/),
and even uses the same circuit.
It solves a very artificial problem:
we are given a "black box" function $f(x)$
that takes an $N$-bit $x$ and returns a single bit,
which we are promised is the lowest bit of the bitwise dot product
of $x$ with an unknown $N$-bit string $s$:
$$\begin{aligned}
f(x)
= s \cdot x \:\:(\bmod 2)
= (s_1 x_1 + s_2 x_2 + \:...\: + s_N x_N) \:\:(\bmod 2)
\end{aligned}$$
The goal is to find $s$.
To solve this problem,
a classical computer would need to call $f(x)$ exactly $N$ times
with $x = 2^n$ for $n \in \{ 0, ..., N \!-\! 1\}$.
However, the Bernstein-Vazirani algorithm
allows a quantum computer to do it with only a single query.
It uses the following circuit:
<a href="bernstein-vazirani-circuit.png">
<img src="bernstein-vazirani-circuit.png" style="width:52%;display:block;margin:auto;">
</a>
Where $U_f$ is a phase oracle,
whose action is defined as follows,
where $\ket{x} = \ket{x_1} \cdots \ket{x_N}$:
$$\begin{aligned}
\ket{x}
\quad \to \boxed{U_f} \to \quad
(-1)^{f(x)} \ket{x}
= (-1)^{s \cdot x} \ket{x}
\end{aligned}$$
That is, it introduces a phase flip based on the value of $f(x)$.
For an example implementation of such an oracle,
see the Deutsch-Jozsa algorithm:
its circuit is identical to this one,
but describes $U_f$ in a different (but equivalent) way.
Starting from the state $\ket{0}^{\otimes N}$,
applying the [Hadamard gate](/know/concept/hadamard-gate/) $H$
to all qubits yields:
$$\begin{aligned}
\ket{0}^{\otimes N}
\quad \to \boxed{H^{\otimes N}} \to \quad
\ket{+}^{\otimes N}
= \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} \ket{x}
\end{aligned}$$
This is an equal superposition of all candidates $\ket{x}$,
which we feed to the oracle:
$$\begin{aligned}
\frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} \ket{x}
\quad \to \boxed{U_f} \to \quad
\frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{s \cdot x} \ket{x}
\end{aligned}$$
Then, thanks to the definition of the Hadamard transform,
a final set of $H$-gates leads us to:
$$\begin{aligned}
\frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{s \cdot x} \ket{x}
\quad \to \boxed{H^{\otimes N}} \to \quad
\ket{s}
= \ket{s_1} \cdots \ket{s_N}
\end{aligned}$$
Which, upon measurement, gives us the desired binary representation of $s$.
For comparison, the Deutsch-Jozsa algorithm only cares whether $s = 0$ or $s \neq 0$,
whereas this algorithm is interested in the exact value of $s$.
## References
1. J.S. Neergaard-Nielsen,
*Quantum information: lectures notes*,
2021, unpublished.
2. S. Aaronson,
*Introduction to quantum information science: lecture notes*,
2018, unpublished.
|
