summaryrefslogtreecommitdiff
path: root/source/know/concept/bernstein-vazirani-algorithm/index.md
blob: 4f36d3c8c565f5cd48e4acbe128ea99c51e21739 (plain)
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
---
title: "Bernstein-Vazirani algorithm"
sort_title: "Bernstein-Vazirani algorithm"
date: 2021-05-01
categories:
- Quantum information
- Algorithms
layout: "concept"
---

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)
    \equiv 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:

{% include image.html file="bernstein-vazirani-circuit.png" width="52%"
    alt="Bernstein-Vazirani circuit" %}

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/quantum-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, using the definition of the Hadamard transform
and the fact that it is its own inverse,
one 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.