-
Notifications
You must be signed in to change notification settings - Fork 0
/
2020-12-06.html
executable file
·245 lines (184 loc) · 13.5 KB
/
2020-12-06.html
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
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=Edge">
<meta name="description" content="">
<meta name="keywords" content="">
<meta name="author" content="">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<title>Quantum computing 4</title>
<!--
Template 2085 Neuron
http://www.tooplate.com/view/2085-neuron
-->
<link rel="stylesheet" href="css/bootstrap.min.css">
<link rel="stylesheet" href="css/all.css">
<link rel="stylesheet" href="css/magnific-popup.css">
<!-- Main css -->
<link rel="stylesheet" href="css/style.css">
<link href="https://fonts.googleapis.com/css?family=Lora|Merriweather:300,400" rel="stylesheet">
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-108246943-1"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-108246943-1');
</script>
<!-- Google AdSense -->
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-8299683413193339" crossorigin="anonymous"></script>
<!--<script async src="https://fundingchoicesmessages.google.com/i/pub-8299683413193339?ers=1" nonce="AuY4vKpDElA9N7YwmFfMjg"></script>
<script nonce="AuY4vKpDElA9N7YwmFfMjg">(function() {function signalGooglefcPresent() {if (!window.frames['googlefcPresent']) {if (document.body) {const iframe = document.createElement('iframe'); iframe.style = 'width: 0; height: 0; border: none; z-index: -1000; left: -1000px; top: -1000px;'; iframe.style.display = 'none'; iframe.name = 'googlefcPresent'; document.body.appendChild(iframe);} else {setTimeout(signalGooglefcPresent, 0);}}}signalGooglefcPresent();})();</script>-->
</head>
<body>
<!-- Tikz for mathjax -->
<link rel="stylesheet" type="text/css" href="https://tikzjax.com/v1/fonts.css">
<script src="https://tikzjax.com/v1/tikzjax.js"></script>
<!-- PRE LOADER -->
<div class="preloader">
<div class="sk-spinner sk-spinner-wordpress">
<span class="sk-inner-circle"></span>
</div>
</div>
<!-- Navigation section -->
<div class="navbar navbar-default navbar-static-top" role="navigation">
<div class="container">
<div class="navbar-header">
<button class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse">
<span class="icon icon-bar"></span>
<span class="icon icon-bar"></span>
<span class="icon icon-bar"></span>
</button>
<a href="index.html" class="navbar-brand">H. Montanelli</a>
</div>
<div class="collapse navbar-collapse">
<ul class="nav navbar-nav navbar-right">
<li><a href="about.html">About</a></li>
<li><a href="blog.html">Blog</a></li>
<li><a href="publications.html">Publications</a></li>
<li><a href="research.html">Research</a></li>
<li><a href="students.html">Students</a></li>
<li><a href="talks.html">Talks</a></li>
<li><a href="teaching.html">Teaching</a></li>
<li><a href="https://www.paypal.com/donate/?hosted_button_id=UCLCSJLFL433E"><b>Donate</b></a></li>
</ul>
</div>
</div>
</div>
<!-- Home Section -->
<section id="home" class="main-about parallax-section">
<div class="overlay"></div>
<div class="container">
<div class="row">
<div class="col-md-12 col-sm-12">
<h1>Quantum computing 4</h1>
</div>
</div>
</div>
</section>
<!-- Blog Single Post Section -->
<section id="about">
<div class="container">
<div class="row">
<div class="col-md-offset-1 col-md-10 col-sm-12">
<p><i>December 6, 2020 — Support my next blog post, <a href="https://www.paypal.com/donate/?hosted_button_id=UCLCSJLFL433E">buy me a coffee</a> ☕.</i></p>
<p>In this post, I talk about quantum computing for <a href='https://en.wikipedia.org/wiki/Supervised_learning'>supervised learning</a>. Marcello Benedetti and his colleagues wrote a very nice <a href='https://iopscience.iop.org/article/10.1088/2058-9565/ab4eb5/pdf'>review</a> last year, which I highly recommend. The main ideas are similar to those described in my previous post about quantum computing for ODEs:</p>
<ul>
<li>reformulate the problem as an <a href='https://en.wikipedia.org/wiki/Mathematical_optimization'>optimization</a> one;
<li>use hybrid systems of quantum and classical computers to solve it.
</ul></p>
<h2>Setup</h2>
<p>The core idea in supervised learning goes like this. We consider data \(\mathcal{X}\subseteq\mathbb{R}^d\), labels \(\mathcal{Y}\subseteq\mathbb{R}\) and a classifier \(f:\mathcal{X}\mapsto\mathcal{Y}\). We want to approximate \(f\) by \(\widehat{f}\) using \(n\) labeled data \((\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_n,y_n)\in\mathcal{X}\times\mathcal{Y}\). The approximate classifier \(\widehat{f}\) is often parametrized by a vector of parameters \(\boldsymbol{\theta}\), and the training process consists in minimizing some <a href='https://en.wikipedia.org/wiki/Loss_function'>cost function</a> \(J(\boldsymbol{\theta})\).</p>
<p>They review two methods for quantum supervised machine learning, <i>quantum kernel estimator</i> (QKE) and <i>variational quantum model</i> (VQM). In both methods, the training set is mapped to <a href='https://en.wikipedia.org/wiki/Feature_(machine_learning)'>feature space</a> with a used-defined map \(\phi\) during the pre-processing stage.</p>
<h2>Method 1 (QKE)</h2>
<p>First, the data \(\phi(\boldsymbol{x}_i)\) is encoded in a quantum circuit by applying some operator \(U_{\phi(\boldsymbol{x}_i)}\).</p>
<p>Second, a <a href='https://en.wikipedia.org/wiki/Swap_test'>SWAP test</a> is used to evaluate the kernel.</p>
<p>Third, the evaluation of \(J(\boldsymbol{\theta})\) and the optimization over the parameters \(\boldsymbol{\theta}\) are carried out on a classical computer. A typical example of such a \(J(\boldsymbol{\theta})\) would be the following quantum <a href='https://en.wikipedia.org/wiki/Support_vector_machine'>support-vector machines</a> cost function,
$$
J(\boldsymbol{\theta}) = \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\theta_i\theta_jy_iy_j\langle K(\boldsymbol{x}_j,\boldsymbol{x}_i)\rangle-\sum_{i=1}^n\theta_i.
$$
</p>
<center>
<img src="/blog/QKE.jpg" class="img-responsive">
</center>
<h2>Method 2 (VQM)</h2>
<p>The first step is the same as in QKE.</p>
<p>Second, a variational circuit \(U(\boldsymbol{\theta})\) implements the forecasting model. This yields state \(\vert\psi_J(\boldsymbol{\theta})\rangle\) for which it is possible to measure a quantity \(\langle M_J(\boldsymbol{\theta})\rangle\) that is directly related to the forecast.</p>
<p>Third, the evaluation of both the forecast \(\widehat{f}(\boldsymbol{x}_i;\langle M_J(\boldsymbol{\theta})\rangle)\) and \(J(\boldsymbol{\theta})\), which measures the forecasting error, as well as the optimization over \(\boldsymbol{\theta}\) are carried out on a classical computer. An example of a cost function \(J(\boldsymbol{\theta})\) would be
$$
J(\boldsymbol{\theta}) = \frac{1}{n}\sum_{i=1}^n\left(\widehat{f}(\boldsymbol{x}_i;\langle M_J(\boldsymbol{\theta})\rangle)-y_i\right)^2.
$$
</p>
<center>
<img src="/blog/VQM.jpg" class="img-responsive">
</center>
<h2>Encoder circuit</h2>
<p>The encoder circuit \(U_{\phi(\boldsymbol{x})}\) can be seen as an extra layer of feature-mapping, where the inner product defines a kernel
$$
K(\boldsymbol{x}_i,\boldsymbol{x}_j)=\vert\langle\boldsymbol{0}\vert U^{*}_{\phi(\boldsymbol{x}_j)}U_{\phi(\boldsymbol{x}_i)}\vert\boldsymbol{0}\rangle\vert^2.
$$
As I mentioned above, the SWAP test can then be used to estimate \(\langle K(\boldsymbol{x}_i,\boldsymbol{x}_j)\rangle\).</p>
<h2>Variational circuit</h2>
<p>In practice, the gate structure is fixed; only the gate parameters vary. A simple example of gate parametrization is given by
$$
U(\boldsymbol{\theta}) = \prod_{\ell=1}^L\exp\left(-\frac{i}{2}\theta_\ell P_\ell\right),
$$
where \(P_\ell\in\{I,Z,X,Y\}^{\otimes n}\) is a tensor of \(n\) <a href='https://en.wikipedia.org/wiki/Pauli_matrices'>Pauli matrices</a>.</p>
<p>It is crucial to efficiently encode the variational circuit. A fixed gate structure allows for the number of gate parameters to grow polynomially in \(n\).</p>
<p>They emphasize on two key differences between variational circuits and neural networks. The first one is that quantum circuit operations are linear, as opposed to the nonlinear <a href='https://en.wikipedia.org/wiki/Activation_function'>activation functions</a> used in <a href='https://en.wikipedia.org/wiki/Artificial_neural_network'>neural networks</a>. The second one is that it is not possible to access the quantum state during the computation, which makes it hard to design a quantum analog of <a href='https://en.wikipedia.org/wiki/Backpropagation'>backpropagation</a>.</p>
<h2>Circuit learning</h2>
<p>Circuit learning relies on standard optimization procedures, which are carried out on the classical computer. For simple gates such as the Pauli gates presented above, it is possible to derive a closed-form expression for the <a href='https://en.wikipedia.org/wiki/Gradient'>gradient</a> with respect to \(\boldsymbol{\theta}\).</p>
<hr>
<h4>Blog posts about quantum computing</h4>
<p>2020 <a href="2020-12-06.html">Quantum computing 4</a></p>
<p>2020 <a href="2020-11-28.html">Quantum computing 3</a></p>
<p>2020 <a href="2020-11-17.html">Quantum computing 2</a></p>
<p>2020 <a href="2020-11-11.html">Quantum computing 1</a></p>
</div>
</div>
</div>
</section>
<!-- Footer Section -->
<footer>
<div class="container">
<div class="row">
<div class="col-md-4 col-md-offset-1 col-sm-6">
<h3>Contact</h3>
<p style="color:white"><i class="fa fa-send-o"></i>[email protected]</p><br>
<a href="https://www.inria.fr/en"><img src="/images/inria.png" class="img-responsive"></a>
</div>
<div class="col-md-4 col-md-offset-1 col-sm-6">
<h3 style="opacity:0;">Contact</h3>
<p style="color:white">Copyright © 2024 Hadrien Montanelli</p><br>
<a href="https://www.ip-paris.fr/en"><img src="/images/polytechnique.png" class="img-responsive"></a>
</div>
<div class="clearfix col-md-12 col-sm-12">
<hr style="color:white;">
</div>
<div class="col-md-12 col-sm-12">
<ul class="social-icon">
<li><a href="https://github.com/Hadrien-Montanelli" class="fa-brands fa-github" style="font-size:30px;color:white"></a></li>
<li><a href="https://scholar.google.com/citations?user=Bjmkfe8AAAAJ&hl=en&oi=sra/" class="fa-brands fa-google" style="font-size:30px;color:white"></a></li>
<li><a href="https://www.linkedin.com/in/hadrien-montanelli/" class="fa-brands fa-linkedin" style="font-size:30px;color:white"></a></li>
<li><a href="https://orcid.org/0009-0005-1742-9828" class="fa-brands fa-orcid" style="font-size:30px;color:white"></a></li>
<li><a href="https://twitter.com/drmontanelli" class="fa-brands fa-x-twitter" style="font-size:30px;color:white;"></a></li>
</ul>
</div>
</div>
</div>
</footer>
<!-- Back top -->
<a href="#back-top" class="go-top"><i class="fa fa-angle-up"></i></a>
<!-- SCRIPTS -->
<script src="js/jquery.js"></script>
<script src="js/bootstrap.min.js"></script>
<script src="js/particles.min.js"></script>
<script src="js/app.js"></script>
<script src="js/jquery.parallax.js"></script>
<script src="js/smoothscroll.js"></script>
<script src="js/custom.js"></script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
</body>
</html>