-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
236 lines (200 loc) · 20 KB
/
index.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
<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
<h1 align="center"> ECE-592 / CSC-591 PROJECT TOPIC: Combinatorial Optimization </h1>
<h2 align="center"> Subset Sum Problem</h2>
<h3 >Under professor Greg Byrd</h3>
<h3 align="right">Kushal Batra</h3>
<marquee><a href="QC.pdf">Project_v1.pdf</a> ||| <a href="QC2.pdf">Project_v2.pdf</a> ||| <a href="QC3.pdf">Final.pdf</a></marquee>
<a href="SUBSET SUM PROBLEM (B2).pptx">PPT</a><br>
<a href="https://github.com/s0nicboOm/QC/blob/master/Quantum_Subset_Sum_Problem.ipynb">CODE</a>
<h4> What is <b>SUBSET SUM PROBLEM </b>?</h4>
The <b>Subset Sum Problem</b> belongs to category of decision problems. The problem states that given a set (or multiset) of integers, is it possible to construct a non-empty subset whose sum is equal to zero?
<p>For example, given the set { − 40 , − 2 , 1 , 2 , 3 , 4 , 5 , 6 } , the answer is "yes" because the subset { − 2 , 2 } sums to zero.
The <b>Subset Sum Problem</b> belongs to complexity class of NP-complete, meaning it is easier to evaluate whether the final result obtained is correct or not. Also, this checking can be done in polynomial time. The problem itself takes non-deterministic polynomial time to find the solution. The <b>subset sum problem</b> is used in the field of complexity theory and cryptography.
<p>In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty (<i>source : <a href='https://en.wikipedia.org/wiki/NP-completeness'> wikipedia</a></i>).
The <b>Subset Sum Problem</b> can be thought of as a modification to <b>knapsack problem</b> where the limit of the bag is infinite and the assumption that the weight of the elements can ne negative.
<h4>OTHER VARIATIONS OF THE PROBLEM</h4>
<ol>
<li><b>Subset Sum Problem</b> where the sum is equal to some constant. This variation is extenion of the question such that the sum instead of 0 can be any other integer <i>k</i> <br>Example - Suppose the parent set is {− 2 , 0 , 1 , 3}. and we are find subset such that sum equals 2. The answer is "yes" the subset {− 2 , 1 , 3} gives the sum=<i>2</i>.</li><br>
<li><b>Subset Sum Problem</b> where it is posibble to subdivide this set into two strict subsets such that the sum of elements of one set is equal to another set.
<br>Example - Suppose the parent set is {− 2 , 0 , 1 , 3}. The answer is "yes" the subsets are {− 2 , 3} and {0 , 1 } where the sum of elements is <i>1</i></li>.
</ol>
<h4> PROJECT APPROACH </h4>
For our project, we will try to implement the <b>Subset Sum Problem</b> problem using Quantum Computers.So suppose we have 'x' elements in our set and we are supposed to find the subset with 'm' elements such that <i>m<=x</i> and the sum of 'm' elements =0. So, to work with Quantum Circuits we will have 'x' Qubits as our input to the circuit and then the output will be in terms of quibit value {0,1}. If the i<sup>th </sup>line's output is '0' it signifies that the i<sup>th </sup> element is not included in our answer. Similarly, If the i<sup>th </sup>line's output is '1' it signifies that the i<sup>th </sup> element is included in our answer.
<br>
<br>
In our poject, we will be working on both the QAOA algorithm in Qiskit and the Quantum Annealing algorithm in DWAVE system. The objective of our project is to compare the two algorithms and try to compare the results obtained from both the methods and finally create an analysis table about it.<br>
Finally, we will be comparing these two approaches with the existing classical approach.
<h4>Classical Approach</h4>
Using Dynamic programming the best solution is in terms of <b>O(2<sup>n</sup>)</b>. This is an exponential complexity which increases heavily with larger n.
There are various code available online for the following subset sum problem.
<h4>Theory of VQE (Quantum Approximate Optimization Algorithm) and QAOA</h4>
For combinatorial optimization, the Variational-Quantum-Eigensolver (VQE) gives better results than classical algorithms.
The Variational-Quantum-Eigensolver (VQE) [1, 2] is a quantum/classical hybrid algorithm that can be used to find eigenvalues of a (often large) matrix
H. When this algorithm is used in quantum simulations, H is typically the Hamiltonian of some system. In this hybrid algorithm a quantum subroutine is run inside of a classical optimization loop. The quantum subroutine has two fundamental steps:</br>
1 . Prepare the quantum state <b> |Ψ(vec(θ))⟩</b>, often called the ansatz.</br>
2 . Measure the expectation value <b>⟨Ψ(vec(θ))|H|Ψ(vec(θ))⟩</b>.
(<i><a href='https://grove-docs.readthedocs.io/en/latest/vqe.html'>source</a></i>)<p>
So the VQE algorithm works as a subrotine to our QAOA algorithm. This VQE is used to solve minimize/maximize the parameterss for our ising Hamiltonian generated.The heart of the QAOA relies on the use of unitary operators dependent on 2 p angles, where p > 1 is an input integer. These operators are iteratively applied on a state that is an equal-weighted quantum superposition of all the possible states in the computational basis. In each iteration, the state is measured in the computational basis and
<b>C ( z )</b> is calculated. After a sufficient number of repetitions, the value of <b>C ( z )</b> is almost optimal, and the state being measured is close to being optimal as well.
(<i>source : <a href='https://en.wikipedia.org/wiki/Quantum_optimization_algorithms'> wikipedia</a></i>).<p>The QAOA algorithm solves the Combinatorial optimization problems are specified by n bits and m clauses. Each clause is a constraint on a subset of the bits which is satisfied for certain assignments of those bits and unsatisfied for the other assignments. The objective function, defined on n bit strings, is the number of satisfied clauses, <b>C(z) = <span>Σ </span>C<sub>α</sub>(z)</b> where <b>z = z <sub>1</sub>,z <sub>2</sub> ...,z<sub>n</sub></b> is the bit string and <b>C<sub>α</sub>(z) = 1 </b>if z satisfies clause α and 0 otherwise. Typically <b>C<sub>α</sub></b> depends on only a few of the n bits. Satisfiability asks if there is a stringthat satisfies every clause. In the QAOA algorithm our motive is to find Approximate Optimization(To find a string (z) for which <b>C(z)</b> is close to the maximum).
<h4>QAOA (Qiskit) for our problem</h4>
To implement QAOA we will be using Qiskit Aqua as it has well pre-defined libraries to make our task simpler. The Qiskit itself provides implementation examples of TSP problem,Vertex cut problem which act as the foundation for our implementation.The next step in designing the QAOA is to create a cost function for our problem. This will be really helpful because using this we can also design the QUBO for our DWAVE simulation. Also we will be trying to show the results obtained using SPSA optimizers for different circuit depths and different number of trial runs.
<br>
<i>One assumption we have made for our problem is that the sum we are required to find is possible to achieve from our parent set</i> <br>
So let us assume that the cost function for our problem is C. <br><br> <b>C = <span>Σ </span>X<sub>i</sub> a<sub>i</sub></b> for i =1 to number of elements in our set, where <b></span>X<sub>i</sub></b> belongs to {1,0} 1: if that element is taken in our final solution set 0: if not taken in our final solution set and a<sub>i</sub> is the i<sup>th</sup> element in our initial set.
<h4>Challenges with this cost function</h4>
<ol>
<li>The cost function is known but its QUBO formulation is still unknown. </li>
<i><u>Reason</u></i> The above Cost function we have written is not in the form QUBO (2 ising model Hamiltonian ). The QUBO format should be in terms of <b> X<sup>T</sup>QX </b>which is not the case with us. This is essential because in QAOA or any other optimization algorithm, the first step is to generate the QUBO and then try to minimize or maximize it. But the cost function we have is not in that form.<br>
<i><u>Solution 1 :</u></i> Use of Docplex. This is a IBM designed optimization library which takes input in terms of classical function and returns the QUBO form i.e in 2 ising model Hamiltonian form. To obtain the accurate Hamiltonian from Docplex we need to optimize our function and add constraints to our function to obtain te best hamiltonian for our problem. The issue with this is that there are no specific constraints for our problem. So the Hamiltonian we construct is not in the optimized form.
<br><i><u>Solution 2 : </u></i> Use of library PyQubo. This is another alternative to our problem which generates the QUBO (2 ising model Hamiltonian) directly without adding any constraints to our input function.
<br>
<li>Let us for a while assume that the cost function we established is correct. The problem arises is to determine what the minimum energy level will be for the given sum.</li>
<i><u>Reason</u></i> We don't know whether minimizing or maximizing the cost function will yield the lowest energy level or not.
<br><i><u>Solution: </u></i> As now we are able to formulate our problem in terms of Hamiltonian, we now can minimize our energy levels for our correct solution.
</ol>
<b><i><br>Also, in the paper <b>"Quantum Algorithms of the Subset-Sum Problem on a Quantum Computer" </b>by <b>Weng-Long Chang et al</b> the authors discuss the approach of using Nuclear Magnetic resonance(<b>NMR</b>) to solve this problem.As discussed by authors in the paper they have stated that the QUBO implementation for the problem is challenging.<a href="paper.pdf">(link to paper)</a></b></i><p>
So we use the approach of Docplex and Pyqubo to solve our problem. We use PyQubo to generate our Hamiltonian and then we feed it to our docplex for minimiaztion. We could have just skipped the use of Docplex but then it is a better wrapper class for the Qiskit Aqua so we used it.
<p>
<h4>DWave (Quantum Annealing)</h4>
Quantum annealing (QA) is a metaheuristic for finding the global minimum of a given objective function over a given set of candidate states (candidate solutions), by a process using quantum tunneling. Quantum annealing is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground state of a spin glass.This system uses a 128 qubits.D-Wave's architecture differs from traditional quantum computers.<p> It is not known to be polynomially equivalent to a universal quantum computer and, in particular, cannot execute Shor's algorithm because Shor's algorithm is not a hill climbing process. Shor's algorithm requires a universal quantum computer. D-Wave claims only to do quantum annealing.
From the implementation of QAOA we can extract the QUBO and plug it into the DWAVE program.We also have to work out the embedding for our problem
<p>
The QUBO Formulation :
<b>minimize Y=X<sup>T</sup>QX</b><br>
To convert <b>Y</b> into symmetric form we can replace <b> q<sub>ij</sub> </b>by <b>(q<sub>ij</sub>+q<sub>ji</sub>)/2</b> where i is not equal to j.
<br>
This information that we are extracting is from the QAOA . We will be using this QUBO information and then construct the implicit and explicit embedding for it.
<h4>Challenges in DWave</h4>
<ol>
<li>As the number of elements increases or decreases in our problem set the problem of fitting the problem in our 4x4 Bipartite graph changes.<br>
<i><u>Solution:</u></i> We can do is implicit embedding reducing the complexity. But this may reduce the accuracy of our results. </li>
</ol>
<h4>Timeline and individual Contribution</h4>
<table border='2'>
<tr>
<td><b>NAME/WEEK</b></td>
<td><b>ATHARVA GUPTA</b></td>
<td><b>KUSHAL BATRA</b></td>
<td><b>COMMENTS</b></td>
</tr>
<tr>
<td><b>Week 1</b></td>
<td>Understand the problem. Select the algorithm to work on+ maintain project report</td>
<td>Understand the problem. Select the algorithm to work on+ maintain website</td>
<td>---------------------</td>
</tr>
<tr>
<td><b>Oct 28</b></td>
<td> ---------------------</td>
<td>---------------------</td>
<td>Feedback received from professor</td>
</tr>
<tr>
<td><b>Week 2</b></td>
<td>Work on Implementation using D-Wave(Quantum Annealing) + Explore research papers, other examples and then identify the challenges explicitly for our problem</td>
<td>Work on Implementation using Qiskit(QAOA) + Explore research papers, other examples like TSP, Vehivcle routing problems and then identify the challenges explicitly for our problem</td>
<td>discuss challenges and look for alternate solutions</td>
</tr>
<tr>
<td><b>Week 3</b></td>
<td>Figure out the QUBO for Subset Sum Problem + Work on Docplex and PyQubo</td>
<td>Figure out the QUBO for Subset Sum Problem + Work on Docplex and PyQubo</td>
<td>Discuss with TA or professor on how to formulate QUBO for Subset Sum Problem and keep working on special case as a backup </td>
</tr>
<tr>
<td><b>Nov 12</b></td>
<td> ---------------------</td>
<td>---------------------</td>
<td>Feedback received from professor</td>
</tr>
<tr>
<td><b>Week 4</b></td>
<td>Complete the implementation in DWave(Quantum Annealing)</td>
<td>Complete the implementation in Qiskit(QAOA) </td>
<td>Discuss about various assumptions made for our problem</td>
</tr>
<tr>
<td><b>Week 5</b></td>
<td>Do comparison analysis of various algortihms used for our problem</td>
<td>Do comparison analysis of various algortihms used for our problem</td>
<td>Discuss and create final report for our solution</td>
</tr>
</table>
<h4>Results and discussions</h4>
<ol>
<li><b>Analyzing results from DWAVE</b>
<ul>
<li><b>Three elements in the set: Occurrences (correct solution) vs the chain strength</b><p> We ran a simple for loop for 'chain strength' from 0 -> 50 (with an increment of 5) to determine the variations in the occurrence of our chain strength. For this particular example, in our set we had elements {2 , 2 , 4} and the sum to find = k = 4. We observe that for this particular the subset solution we have 2 solutions {2 , 2} and {4}. In the solution, both the solutions have negative energy levels. We observe that the graph has a peak at chain strength = 5. We ran our code for different sets and for different sets of the element. We saw that chain strength = 5 gives best result for sets where the number of sets in the set = 3. With an increase in this cardinality of strength, we get an increase in the chain strength value. <br>
<figure><img src="1.png" width="300" height="200"><figcaption>Fig.1</figcaption>
<img src="2.png" width="300" height="200"><figcaption>Fig.2</figcaption></figure>
<br>The first graph is for 'chain strength' from 0 -> 50 (with increment of 5). The second graph is chain strength from 0->5 (with increment of 0.5) </li>
<li><b>Processing time vs chain strength</b><p>This graph had an interesting pattern. When the chain strength crosses the point of 25 the processing time decrease. There can be two reasons for this. Firstly, as chain strength increases the solution {2,2} chances/occurrences increases (as coupling strength is high). Secondly, it might be possible that till chain strength 20 the servers were busy and hence the high processing time. We ruled out the second scenario by running our solutions 3 times and still obtained somewhat same graph.</li><br><br>
<figure><img src="3.png" width="300" height="200"><figcaption>Fig.1</figcaption></figure>
<figure><img src="4.png" width="300" height="200"><figcaption>Fig.2</figcaption></figure>
<br>
The first graph is for 'chain strength' from 0 -> 50 (with increment of 5). The second graph is chain strength from 0->10 (with increment of 1).</li>
</ul>
<li><b>Analyzing results from QISKIT<p></b>
<ul>
<li><b>3 elements in the set: Processing Time vs the circuit depth</b><p> </li> We initially expected the graph between time vs depth to be exponential but our results show that this dependence of time on depth of the circuit is linear. We were not able to assess the reason for this behaviour. <br>
<figure><img src="5.png" width="300" height="200"><figcaption>Fig.5</figcaption></figure>
</li><br>
<li><b>The Subset-Sum Objective vs depth</b><p></li> As expected from the graph, more depth we add to the circuit more accurate the results we obtain. Subset Sum objective for the correct solution should be zero. So the graph turns out to be a graph in terms of error deviation from 0 with respect to depth of the circuit. <br>
<figure><img src="6.png" width="300" height="200"><figcaption>Fig.6</figcaption></figure>
</li>
<li><b>The Circuit obtained for three elements with depth =5 </b><p>
<figure><img src="7.png" width="600" height="400"><figcaption>Fig.7</figcaption></figure></li>
</ul>
</ol>
<h4>Comparing the results from QISKIT and DWAVE</h4>
<ol>
<li>The solution obtained from DWave takes less time to compute results as compared to Qiskit Aqua (with minimim depth). This information can be extracted by comparing the graphs in fig 1 and fig 5</li>
<li>When n (#no. of elements in the set increases) increases the solution sample also degrades exponentilly in both Dwave and Qiskit. The degardation trend is more prominenet in case of Dwave when compared with Qiskit.</li>
<li>Weakness with Dwave is that as the problem set space increases the number of used qubit also increases and in Dwave the chimera graph is not completely uniform. In case of Qiskit , the number of qubo's are limited with the IBM's quantum achitecture.</li>
</ol>
<h4>Future Work</h4>
<ul>
<li> Try to implement manual embedding for Dwave solution to increase purity of our solution states. This is because when we are dealing with n>=10 our solution sets start giving impure states.</li>
<li>Similarly in QAOA if we are able to generate the Hamiltonian using some other method instead of Docplex or PyQubo we will get better and faster solution. This is because Docplex and Pyqubo are libraries which are operated or executed in classical computer.
</li>
</ul>
<h4>REFERENCE PAPER</h4>
[1] https://en.wikipedia.org/wiki/NP-completeness<br>
[2] Bani-Ahmad, Sulieman. (2015). The Subset-Sum Problem: Revisited with
an Improved Approximated Solution. International Journal of Computer
Applications. 114. 10.5120/20043-7214.<br>
[3] Bernstein, Daniel Jeffery, Stacey Lange, Tanja Meurer, Alexander.
(2013). Quantum Algorithms for the Subset-Sum Problem. 10.1007/978-
3-642-38616-9-2.<br>
[4] Daskin, Ammar. (2017). A Quantum Approach to Subset-Sum and Similar
Problems.<br>
[5] Flaxman, Abraham & Przydatek, Bartosz. (2005). Solving Medium-
Density Subset Sum Problems in Expected Polynomial Time. Lecture
Notes in Computer Science. 3404. 305-314. 10.1007/978-3-540-31856-
9
25.<br>
[6] Zahedinejad, Ehsan & Zaribafiyan, Arman. (2017). Combinatorial Opti-
mization on Gate Model Quantum Computers: A Survey.<br>
[7] Lobe, Elisabeth. (2017). Solving Combinatorial Optimization Problems
via D-Wave’s Quantum Annealer<br>
[8]Dinneen, Michael J; Hua, Richard; Calude, Cristian S
Theoretical Computer Science, Vol. 701, pp. 54 - 69.
<br>[9]A QUBO Model for the Traveling Salesman Problem with Time Windows
by Papalitsas, Christos; Andronikos, Theodore; Giannakis, Konstantinos;
Algorithms, 10/2019, Volume 12, Issue 11
<br>[10]Constraint Embedding for Solving Optimization Problems on Quantum Annealers
by Vyskocil, Tomas; Djidjev, Hristo
2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 05/2019
<br>[11]Quantum algorithms for algebraic problems
by Childs, Andrew M; van Dam, Wim
Reviews of Modern Physics, 01/2010, Volume 82, Issue 1
<br>[12]Quantum Algorithms of the Subset-Sum Problem on a Quantum Computer
by Weng-Long Chang; Ting-Ting Ren; Mang Feng;2009 WASE International Conference on Information Engineering, 07/2009
</ol>
<BR>
------------------------------------------------------------------
</body>
</html>