-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathcombinatorial_optim_applic.html
214 lines (193 loc) · 12.9 KB
/
combinatorial_optim_applic.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
<!DOCTYPE html>
<html class="writer-html5" lang="en" data-content_root="./">
<head>
<meta charset="utf-8" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Combinatorial optimization — myQLM documentation documentation</title>
<link rel="stylesheet" type="text/css" href="static/pygments.css?v=03e43079" />
<link rel="stylesheet" type="text/css" href="static/css/theme.css?v=e59714d7" />
<link rel="stylesheet" type="text/css" href="static/css/custom.css?v=ccfc9eea" />
<link rel="stylesheet" type="text/css" href="static/sphinx-design.min.css?v=95c83b7e" />
<link rel="shortcut icon" href="static/favicon.png"/>
<script src="static/jquery.js?v=5d32c60e"></script>
<script src="static/_sphinx_javascript_frameworks_compat.js?v=2cd50e6c"></script>
<script src="static/documentation_options.js?v=8a448e45"></script>
<script src="static/doctools.js?v=9bcbadda"></script>
<script src="static/sphinx_highlight.js?v=dc90522c"></script>
<script src="static/design-tabs.js?v=f930bc37"></script>
<script crossorigin="anonymous" integrity="sha256-Ae2Vz/4ePdIu6ZyI/5ZGsYnb+m0JlOmKPjt6XZ9JJkA=" src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.4/require.min.js"></script>
<script>window.MathJax = {"tex": {"inlineMath": [["$", "$"], ["\\(", "\\)"]], "processEscapes": true}, "options": {"ignoreHtmlClass": "tex2jax_ignore|mathjax_ignore|document", "processHtmlClass": "tex2jax_process|mathjax_process|math|output_area"}}</script>
<script defer="defer" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="static/js/theme.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="NP-hard problems" href="combinatorial_optim_applic/01_np_probs_for_annealing.html" />
<link rel="prev" title="Migrating code based on deprecated library qat.dqs" href="fermion/04_migrating.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="index.html" class="icon icon-home">
myQLM documentation
<img src="static/myqlm-doc-logo.png" class="logo" alt="Logo"/>
</a>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
<input type="text" name="q" placeholder="Search docs" aria-label="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<ul>
<li class="toctree-l1"><a class="reference internal" href="01_getting_started.html">Getting started</a></li>
</ul>
<ul class="current">
<li class="toctree-l1 current"><a class="reference internal" href="02_user_guide.html">User guide</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="02_user_guide/01_write.html">Writing quantum programs</a></li>
<li class="toctree-l2"><a class="reference internal" href="02_user_guide/02_execute.html">Executing / Simulating quantum programs</a></li>
<li class="toctree-l2"><a class="reference internal" href="02_user_guide/03_compile.html">Compiling and rewriting quantum circuits</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="02_user_guide.html#libraries-built-upon-qaptiva">Libraries built upon Qaptiva</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="fermion.html">Spin and fermionic systems</a></li>
<li class="toctree-l3 current"><a class="current reference internal" href="#">Combinatorial optimization</a><ul>
<li class="toctree-l4"><a class="reference internal" href="combinatorial_optim_applic/01_np_probs_for_annealing.html">NP-hard problems</a></li>
<li class="toctree-l4"><a class="reference internal" href="combinatorial_optim_applic/02_qaoa.html">Quantum Approximate Optimization Algorithm (QAOA)</a></li>
<li class="toctree-l4"><a class="reference internal" href="combinatorial_optim_applic/03_aqo.html">Adiabatic Quantum Optimization (AQO)</a></li>
<li class="toctree-l4"><a class="reference internal" href="combinatorial_optim_applic/04_crossing_lattice.html">Crossing lattice</a></li>
<li class="toctree-l4"><a class="reference internal" href="combinatorial_optim_applic/05_np_problem_generators.html">Problem generators</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="%3Amyqlm%3Ainteroperability.html">Interoperability with gate-based framework</a></li>
<li class="toctree-l3"><a class="reference internal" href="interoperability_annealing.html">Interoperability with annealing framework</a></li>
</ul>
</li>
</ul>
</li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="04_api_reference.html">API reference</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="05_demos.html">Demos</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="%3Amyqlm%3A06_support.html">Contributing to myQLM</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="07_release_notes.html">Release notes</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="index.html">myQLM documentation</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html" class="icon icon-home" aria-label="Home"></a></li>
<li class="breadcrumb-item"><a href="02_user_guide.html">User guide</a></li>
<li class="breadcrumb-item active">Combinatorial optimization</li>
<li class="wy-breadcrumbs-aside">
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<section id="combinatorial-optimization">
<span id="id1"></span><h1>Combinatorial optimization<a class="headerlink" href="#combinatorial-optimization" title="Link to this heading"></a></h1>
<p>As we hinted in the <a class="reference internal" href="02_user_guide/01_write/03_annealing_problems.html#annealing-programming"><span class="std std-ref">Annealing programming</span></a> section, many problems with actual practical applications are combinatorial and can be represented as minimization or maximization ones. Here we will use the <a class="reference internal" href="02_user_guide/01_write/03_annealing_problems.html#annealing-programming"><span class="std std-ref">quantum formulations</span></a> of such problems to encode and solve some of the most famous <a class="reference internal" href="combinatorial_optim_applic/01_np_probs_for_annealing.html#np-problems-annealing"><span class="std std-ref">NP-hard problems</span></a>.</p>
<div class="toctree-wrapper compound">
</div>
<div class="sd-container-fluid sd-sphinx-override sd-mb-4 docutils">
<div class="sd-row sd-row-cols-1 sd-row-cols-xs-1 sd-row-cols-sm-2 sd-row-cols-md-2 sd-row-cols-lg-2 docutils">
<div class="sd-col sd-d-flex-row docutils">
<div class="sd-card sd-sphinx-override sd-w-100 sd-shadow-sm sd-card-hover docutils">
<div class="sd-card-body docutils">
<div class="sd-card-title sd-font-weight-bold docutils">
NP-hard problems for Simulated Annealing</div>
</div>
<a class="sd-stretched-link sd-hide-link-text reference internal" href="combinatorial_optim_applic/01_np_probs_for_annealing.html"><span class="doc">combinatorial_optim_applic/01_np_probs_for_annealing.rst</span></a></div>
</div>
</div>
</div>
<p>However, it is not only annealing that allows us to encode and tackle such minimization or maximization problems. In fact, one can also use the
<a class="reference internal" href="02_user_guide/01_write/01_digital_circuit.html#circuit"><span class="std std-ref">gate-based</span></a> and <a class="reference internal" href="02_user_guide/01_write/02_analog_schedule.html#schedules-section"><span class="std std-ref">analog computing</span></a> approaches to create custom circuits or custom schedules, which, when
executed, should also give us the desired lowest energy, hence best answer. myQLM provides:</p>
<blockquote>
<div><ul class="simple">
<li><p>Quantum Approximate Optimization Algorithm (<a class="reference internal" href="combinatorial_optim_applic/02_qaoa.html#qaoa"><span class="std std-ref">QAOA</span></a>) relying on gate-based computation</p></li>
<li><p>Adiabatic Quantum Optimization (<a class="reference internal" href="combinatorial_optim_applic/03_aqo.html#aqo-sec"><span class="std std-ref">AQO</span></a>) relying on analog computation</p></li>
<li><p>Adiabatic Quantum Optimization for Rydberg quantum devices (<a class="reference internal" href="combinatorial_optim_applic/04_crossing_lattice.html#crossing-lattice"><span class="std std-ref">RYD</span></a>), relying on the Crossing Lattice
embedding technique to target Rydberg atom devices</p></li>
</ul>
</div></blockquote>
<div class="sd-container-fluid sd-sphinx-override sd-mb-4 docutils">
<div class="sd-row sd-row-cols-1 sd-row-cols-xs-1 sd-row-cols-sm-2 sd-row-cols-md-2 sd-row-cols-lg-3 sd-g-4 sd-g-xs-4 sd-g-sm-4 sd-g-md-4 sd-g-lg-4 docutils">
<div class="sd-col sd-d-flex-row docutils">
<div class="sd-card sd-sphinx-override sd-w-100 sd-shadow-sm sd-card-hover docutils">
<div class="sd-card-body docutils">
<div class="sd-card-title sd-font-weight-bold docutils">
Gate-Based simulation - QAOA</div>
</div>
<a class="sd-stretched-link sd-hide-link-text reference internal" href="combinatorial_optim_applic/02_qaoa.html"><span class="doc">combinatorial_optim_applic/02_qaoa.rst</span></a></div>
</div>
<div class="sd-col sd-d-flex-row docutils">
<div class="sd-card sd-sphinx-override sd-w-100 sd-shadow-sm sd-card-hover docutils">
<div class="sd-card-body docutils">
<div class="sd-card-title sd-font-weight-bold docutils">
Analog simulation - AQO</div>
</div>
<a class="sd-stretched-link sd-hide-link-text reference internal" href="combinatorial_optim_applic/03_aqo.html"><span class="doc">combinatorial_optim_applic/03_aqo.rst</span></a></div>
</div>
<div class="sd-col sd-d-flex-row docutils">
<div class="sd-card sd-sphinx-override sd-w-100 sd-shadow-sm sd-card-hover docutils">
<div class="sd-card-body docutils">
<div class="sd-card-title sd-font-weight-bold docutils">
Analog simulation for Rydberg QPU - RYD</div>
</div>
<a class="sd-stretched-link sd-hide-link-text reference internal" href="combinatorial_optim_applic/04_crossing_lattice.html"><span class="doc">combinatorial_optim_applic/04_crossing_lattice.rst</span></a></div>
</div>
</div>
</div>
<p>Since using all the three quantum computation paradigmes above leads to solving the same general task, the NP-hard problems representations were abstracted to allow a seamless shift in generating such gate-based, analog or annealing problems - the so-called <em>NP-hard problems generators</em>.</p>
<div class="sd-container-fluid sd-sphinx-override sd-mb-4 docutils">
<div class="sd-row sd-row-cols-1 sd-row-cols-xs-1 sd-row-cols-sm-2 sd-row-cols-md-2 sd-row-cols-lg-2 docutils">
<div class="sd-col sd-d-flex-row docutils">
<div class="sd-card sd-sphinx-override sd-w-100 sd-shadow-sm sd-card-hover docutils">
<div class="sd-card-body docutils">
<div class="sd-card-title sd-font-weight-bold docutils">
NP-hard problems for the 3 types of quantum computation</div>
</div>
<a class="sd-stretched-link sd-hide-link-text reference internal" href="combinatorial_optim_applic/05_np_problem_generators.html"><span class="doc">combinatorial_optim_applic/05_np_problem_generators.rst</span></a></div>
</div>
</div>
</div>
</section>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="fermion/04_migrating.html" class="btn btn-neutral float-left" title="Migrating code based on deprecated library qat.dqs" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="combinatorial_optim_applic/01_np_probs_for_annealing.html" class="btn btn-neutral float-right" title="NP-hard problems" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>© Copyright Eviden 2016-2025.</p>
</div>
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>