-
Notifications
You must be signed in to change notification settings - Fork 39
/
main.tex
229 lines (202 loc) · 9.74 KB
/
main.tex
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
\documentclass[aspectratio=43]{beamer}
\usepackage[utf8]{inputenc}
%%%%%%%%%%%%%%%%%%%%%%%% THEME
\usetheme{material}
\useLightTheme
\usePrimaryAmber
\useAccentDeepOrange
\usepackage{macros} % must come after theme
\title{\q Search}
\keywords{\qc, \q Search, Grover's algorithm}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}{Table of contents}
\begin{card}
\tableofcontents
\end{card}
\end{frame}
\section{Introduction}
\begin{frame}{Introduction}
\begin{card}
This week we will be studying a famous and pragmatic quantum algorithm to perform a search, the \textbf{\gvsa}. We will look through its purpose, how it compares with classical search strategies that solve the same problems. The algorithm will be studied from a more abstract point of view, namely in understanding \textbf{\aamp} (\textbf{\phiv} + \textbf{\iatm}). This week's exercises will focus more on the implementation details.
\end{card}
\pagenumber
\end{frame}
\section{The Search Problem}
\begin{frame}{The Search Problem}
\begin{cardTiny}
Let us assume we have a function $f$:
\begin{equation*}
f : \{0, 1, ..., N-1\} \rightarrow \{0,1\}
\end{equation*}
And we want to find those values of $x$ for which $f(x)=1$. To simplify, and also to make the problem harder, let us assume there is only one such $x$:
\begin{center}
\includegraphics[width=0.45\textwidth]{haystack}
\end{center}
\end{cardTiny}
\pagenumber
\end{frame}
\begin{frame}{The Search Problem}
\begin{card}
How would a classical programmer tackle this problem?
\begin{itemize}
\item Sequential search through $x \in [0, N[$ until $f(x)=1$
\item Random search with $x \in [0, N[$ until $f(x)=1$
\item ...
\end{itemize}
As you can see, this is quite straightforward, and yields a worst-case scenario of $N$ searches and average $\frac{N}{2}$ (assuming no bias in $f$).
\end{card}
\pagenumber
\end{frame}
\section{SAT Problem}
\begin{frame}{SAT Problem}
\begin{card}
\small{Besides the most obvious problems, we should also know about the \textbf{SAT problem} (sometimes Boolean satisfiability problem). This problem is about determining values for Boolean variables so that the \textbf{Boolean expression} associated \textbf{evaluates to true}. This is a computationally expensive problem and falls into the \np (actually \href{https://en.wikipedia.org/wiki/NP-completeness}{NP-complete}) category. Many problems, like scheduling, can be converted into a SAT formulation, making use of existing SAT solvers to easily find solutions for novel problems.}
\end{card}
\begin{card}
\small{As such, SAT can be seen as a \textbf{search problem}, where we need to find the precise combination of Boolean values that \textbf{yields true}.}
\end{card}
\pagenumber
\end{frame}
\section{\gvsa} % overview of steps, comparison of bigO
\begin{frame}{\gvsa}
\begin{card}
Luckily for the world, Dr. \href{https://en.wikipedia.org/wiki/Lov_Grover}{Lov Grover} devised an algorithm that, instead of $N$ steps to find a solution, requires $\sqrt{N}$. This is \href{https://arxiv.org/abs/quant-ph/9711070}{optimal} (no better speed up is possible for this problem).
\end{card}
\begin{card}
The algorithm makes use of two very important phenomena that can be implemented in a quantum computer:\begin{itemize}
\item \textbf{Phase inversion}
\item \textbf{Inversion about the mean} (average)
\item An oracle for our $f$ function
\end{itemize}
\end{card}
\pagenumber
\end{frame}
\section{Phase Inversion}
\begin{frame}{Phase Inversion}
\begin{card}
The first phenomena is that of \phiv and will help in finding $x'$ so that $f(x')=1$. Let us imagine a quantum superposition over all possible $x$ values:
\begin{equation*}
\sum_x\alpha_x \ket{x}
\end{equation*}
To which we can, through the use of our oracle, obtain:
\begin{equation*}
\sum_{x\neq x'}\alpha_x \ket{x} - \alpha_{x'}\ket{x'}
\end{equation*}
\end{card}
\pagenumber
\end{frame}
\begin{frame}{Phase Inversion}
\begin{cardTiny}
This will mean that, if we plot $\alpha_x$ for each $x$ value, we will get something like the following abstract diagram - in which the correct value has been inverted (even though we do not know its value)
\begin{multicols}{2}
\begin{center}
\includegraphics[width=0.5\textwidth]{phiv_before}
\end{center}
\begin{center}
\includegraphics[width=0.5\textwidth]{phiv}
\end{center}
\end{multicols}
\end{cardTiny}
\pagenumber
\end{frame}
\section{Inversion about the Mean}
\begin{frame}{Inversion about the Mean}
\begin{cardTiny}
The next phase of the algorithm is to take that very distribution of weight and mirror it to the other side of the mean. This can be done in a quantum circuit (more on the exercises). The following is a representation of this transformation (either function is the \iatm of the other):
\begin{center}
\includegraphics[width=0.5\textwidth]{iatm}
\end{center}
\end{cardTiny}
\pagenumber
\end{frame}
\begin{frame}{Inversion about the Mean}
\begin{cardTiny}
Why do we do this, you may ask. To answer this, consider the two steps taken so far: \phiv and then \iatm. The first one, sets our solution to be a bit more recognizable and the second operation further segregates our result from the rest of the possible states.
\end{cardTiny}
\begin{cardTiny}
If we keep on doing this two steps, we will segregate the correct answer from the others further and further. The number of times we need to do it to have a guaranteed high probability of having the right answer is $\sqrt{N}$!
\end{cardTiny}
\pagenumber
\end{frame}
\section{Why $\sqrt{N}$?}
\begin{frame}{\gvsa (why $\sqrt{N}$?) }
\begin{cardTiny}
Let us assume, we initialize our $n$ qubits to $\ket{0}$, each qubit can be compared to a Boolean value on the n-bit solution we are looking for. We then create a superposition that sets them in a \textbf{uniform superposition} (each state has equal probability):
\begin{equation*}
\sum_{x \in {0,1}^n} \frac{1}{\sqrt{N}}\ket{x}
\end{equation*}
\begin{center}
\includegraphics[width=1\textwidth]{grover_start}
\end{center}
\end{cardTiny}
\pagenumber
\end{frame}
\begin{frame}{\gvsa (why $\sqrt{N}$?)}
\begin{cardTiny}
We then create a quantum oracle $O_f$ that will flip the qubits if the result is 1, and apply this gate, this effectively applies a phase inversion:
\begin{center}
\includegraphics[width=1\textwidth]{grover_phiv}
\end{center}
\end{cardTiny}
\pagenumber
\end{frame}
\begin{frame}{\gvsa (why $\sqrt{N}$?)}
\begin{cardTiny}
Finally, we will apply the \iatm ($\mu = \frac{1}{N}\sum_x \alpha_x \ket{x}$):
\begin{equation*}
\sum_x \alpha_x \ket{x} \rightarrow \sum_x (2\mu - \alpha_x) \ket{x}
\end{equation*}
\begin{center}
\includegraphics[width=1\textwidth]{grover_iotm}
\end{center}
\end{cardTiny}
\pagenumber
\end{frame}
\newcommand{\amp}[2]{\frac{#1}{\sqrt{#2}}}
\begin{frame}{\gvsa ($\sqrt{N}$ because...)}
\begin{card}
If you repeat this mechanism, you will notice the amplitude improves (per step) $\amp{\sqrt{2}}{N}$ every iteration:
\begin{equation*}
\amp{1}{N}, \amp{3}{N}, \amp{5}{N}, ... \amp{1}{2}
\end{equation*}
At the point of $\amp{1}{2}$ we have a guaranteed high probability of the measurement resulting in the solution! How long until we get there?
\begin{equation*}
\frac{\amp{1}{2}}{\amp{\sqrt{2}}{N}} = \frac{\sqrt{N}}{2} = O(\sqrt{N})
\end{equation*}
\end{card}
\pagenumber
\end{frame}
\section{\aamp}
\begin{frame}{\aamp}
\begin{cardTiny}
This combination of \phiv and \iatm is called \textbf{\aamp}!
\end{cardTiny}
\begin{cardTiny}
\small{
It should be noted that the amplitude \textbf{cannot increase forever} and will eventually be so large that the mean becomes negative (after \phiv) and the \iatm step is actually \textbf{harming our result}. That is why one should know when to stop (how many iterations guarantee the minimum desired amplitude).}
\end{cardTiny}
\begin{cardTiny}
There you have it, by executing the \aamp iteration we can solve a classical problem that had a complexity of $O(N)$ in $O(\sqrt{N})$, it is not an exponential growth (as some quantum algorithms are able to do), but in this case that would have some \href{https://en.wikipedia.org/wiki/P_versus_NP_problem}{very disruptive consequences}.
\end{cardTiny}
\pagenumber
\end{frame}
\section{Hands-on}
\begin{frame}{Hands-on}
\begin{card}
This week's exercises will focus more on understanding the logic at the quantum circuit level, and are based on a Jupyter notebook available at the official \href{https://github.com/Qiskit/qiskit-tutorial}{\qk tutorial repository}. You will get to solve a real SAT problem, of dimension 3, in a real quantum device!
\end{card}
\pagenumber
\end{frame}
\section{Where to learn more?}
\begin{frame}{Where to learn more?}
\begin{card}
\begin{itemize}
\item \href{https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/070-Grover's_Algorithm.html}{\ibmqe Documentation on \gv} includes circuitry and interesting diagrams.
\item \href{https://arxiv.org/abs/1708.03684}{An Introduction to Quantum Computing, Without the Physics} good paper for understanding more on \gvsa
\end{itemize}
\end{card}
\end{frame}
\end{document}