Team 8 Alex Khan, Theo Cleland, Henry Makhanov, Ehsan Torabizadeh, Darshit Mehta

In this project we are going to demonstrate the amazing power of classical and quantum annealers. Throughout a series of tasks we will demonstrate the existing annealing techniques to solving a variety of problems. Crucially, we will show a solution to the unit-disk maximum independent set (UD-MIS) problem using both a simulated classical annealer with different schedules and a quantum annealer. For the third task, we have also solved the Gotham City Cell Tower problem using both classical annealer and quantum annealer. Finally, we have mapped a real-world protein redundancy problem to the UD-MIS problem and found very promising results that will serve as a founding block for our business proposal.

1. Simulating the UD-MIS Problem Using Classical Simulated Annealing
2. Finding a Better Annealing Schedule
3. Simulating the Same Problem but Using Quantum Annealing
4. Comparing the Classical and Quantum Methods
5. Gotham City Problem
6. Finding Non-Redundant Protein Sequences
7. Business Application
8. Project Resources

Please view this notebook for the code used to solve this section.

We simulate the UD-MIS using classical simulated annealing for the following abstract graph (truncated to 2 decimal places). Edges are created whenever a node is closer than a unit distance of 1.

Table Representation of Graph	Visual Representation of Graph
X Coordinate Y Coordinate 0.35 1.50 0.63 2.58 1.39 2.16 0.66 0.67 0.87 3.39 1.16 1.08

Next we simulate annealing to solve the ground state of the following Hamiltonian:

With the following annealing schedule:

We find a ground state energy level of -3 after about 4000 iterations. We plot in the following corresponding occupations in green which yield the ground state:

Please view this notebook for the code used to solve this section.

We test 3 different annealing temperatures summarized by the following table (left) and visualized in the follow plot (right):

Table of Different Annealing Schedules	Plots of Each Annealing Schedule
Annealing Schedule Name exponential ~x (benchmark) exponential ~2x exponential ~4x

To test the speed of convergence, we consider a "stable" solution one where the energy has not changed after 100 iterations. After simulating the annealing for each schedule, we plot the energy versus the number iterations in the following table:

We see clearly that the exponential ~4x schedule converges the fastest, and is more than 3x faster than the benchmark provided in the sample code. These results are further summarized in the following table:

Annealing Schedule	Iterations to Stable Solution	Time to Stable Solution (seconds)
	3676	0.61
	2007	0.34
	1044	0.17

Please view this notebook for the code used to solve this section.

We simulate the UD-MIS using simulated quantum annealing for the following abstract graph (truncated to 2 decimal places). Edges are created whenever a node is closer than a unit distance of 1.This graph will look a bit different from the one used in the previous section because we are using a different programming language (Julia) and because we use a different plotting package(GraphPlots.jl).

Table Representation of Graph	Visual Representation of Graph
X Coordinate Y Coordinate 0.35 1.50 0.63 2.58 1.39 2.16 0.66 0.67 0.87 3.39 1.16 1.08

In the instructions we were tasked with applying quantum annealing to solve the UD-MIS problem. Our approach will be different from the classical annealing as we will be considering a time-dependent Hamiltonian:

Mathematically and algorithmically, Quantum Annealing looks like the following

where is the time-evolution operator

We can see the top five solutions and their frequency on the following graph. Additonally you can look at the file with all the available solutions

We can see that simulated quantum annealing found several suitable solutions. Most notably, the top 3 solutions are very close to each other. We have made the corresponding frequency distribution and graph that maps the top 5 solutions:

Solutions	Solutions on the Graph
Solution Frequency 010101 28581 011100 28457 110100 28204 111100 3052 011101 2953

Additionally we have run the simulated quantum annealer on a more complicated graph with 11 nodes, where top 5 solutions are much more evenly distributed. We suspect it was due to inherently different structure of the graphs.

Solutions	Solutions on the Graph
Solution Frequency 01111001100 6827 11011011000 6774 01111011000 6713 11011001100 6709 11011001001 6682

Simulated quantum annealing presents a promising option for solving the UD-MIS problem, but perhaps it would be more interesting how will the real quantum hardware perform.

Please view this notebook for the code used to solve this section.

We will be comparing classical and quantum solutions to the UD-MIS problem. D-Wave will be our quantum hardware of choice for this task. Our experiment will consist of running UD-MIS algorithm until there is no change in energy, during our experiments we found that this occurs after roughly 300 steps. For our experiments we tried different size graphs of the UD-MIS formulation and also tracked the lowest energy found with both the classical UD-MIS solver and the D-Wave quantum annealer. We have used both D-Wave 2000Q and D-Wave Advantage in our comparison to classical annealing. With D-Wave 2000Q we were only able to go up to a maximum node size of 70, and in the case of D-Wave Advantage we have increased the number of nodes to 100.

Through experimentation we determined that these were the optimal parameters:

chain_strength = 1.7

annealing_time = 30

number_of_runs = number_of_nodes * 20

Here are the results of our time to execute experiment:

D-Wave 2000Q vs Classical	D-Wave Advantage vs Classical

Here are the results of our lowest energy experiment:

D-Wave 2000Q vs Classical	D-Wave Advantage vs Classical

We can see that both D-Wave machines can't find the lowest energy solution. Despite a large amount of sampling both quantum machines found very few results in the lower values, as can be seen in the following graphs:

40 Nodes	100 Nodes

While it is true that current quantum machines fail to find the solutions with the lowest value, we can clearly see that they perform much faster than classical methods. We expect that with general quantum hardware improvements, quantum methods will become better at finding the lowest energy solutions for the UD-MIS problem, whilst keeping their speed advantage.

This work was generated from this notebook. The goal was to map the UD-MIS problem to a real world problem relating to finding optimal placements for cell phone towers in the city of Gotham.

We are given the follow nodes representing the potential position of cell phone towers in Gotham (edges in the graph represent towers whose signals overlap):

Table Representation of Graph	Visual Representation of Graph
X Coordinate Y Coordinate 1.19 4.25 2.71 3.48 1.19 3.51 2.00 3.38 1.12 2.86 1.70 2.42 2.36 2.54 1.52 1.48 2.15 1.54 2.14 1.87 1.72 0.86 2.29 0.87

Our goal is to optimize the cell locations of each tower to best cover Gotham City, while only purchasing the required number of towers such that the tower signals do not overlap and as much of Gotham City is within signal range.

The requirements of the problem to maximize the tower coverage (use as many nodes as possible) and that the signal range not overlap (penalize node pairs with some condition) fits the UD-MIS formulation:

We solve this problem in four ways using a simulated classical annealing approach, a quantum annealing algorithm as well as on real quantum hardware using Microsoft QIO and D-Wave.

Running the algorithm on a simulated classical annealing algorithm yields a lowest energy level of -5. This ground state has 5 nodes (indicated in green). We reached convergance after about 3700 iterations using the default cooling schedule . We plot one solution in the figure below, where the green nodes indicate cell phone towers and the yellow nodes are potential locations that are not ideal:

We have used a time-dependent Hamiltonian to reach the ground state. We have placed the coordinates into the quantum annealer, run for 100000 nshots and got the following solutions:

Gotham Solutions	Gotham Solutions Graph
Solution Frequency 100001010011 17686 010001010011 17443 101000010011 12414 011000010011 12403 000011010011 9648

Repeated runs on Microsoft QIO gave the same answer as the simulated quantum annealing approach.

This solver (similar to most simulated annealing solvers) seems to give only one answer. It did not appear to be probabilistic and so, we did not see the value in proceeding any further with this algorithm.

We also solve this problem on real quantum hardware using D-Wave. Here, we found multiple potential solutions with the same lowest energy of -5. We display the top potential solutions found in the left, along with an awesome GIF displaying some of them on the right (green nodes are occupied, edges represent signals that overlap).

D-Wave Solutions for Gotham Problem	GIF of the Multiple Best Solutions Found

However, one of Bruce's conditions is that the signals must not overlap. Therefore, we must exclude some of the ground states because they overlap (indicated by green nodes with connected edges). With this in mind, we show three non-overlapping solutions for breivity:

We also show the graph representation of the problem in D-Wave (left), the actual embedding on D-Wave 2000Q (middle) along with the energies sampled from Dwave (right).

Graph Representation on D-Wave	Embeddings on D-Wave	Energies Sampled on D-Wave

It depends on if Bruce can tolerate some overlap between the tower signals.

• If Bruce insists that there cannot be any signal overlap: he should not purchase more towers.
• If Bruce can tolerate some overlap: he should purchase more towers.

Let's examine this in more detail...

For the case where Bruce can not afford any signal overlap, we already found a handful of optimal solutions with 5 towers and a ground state energy of -5. These are shown again here for convenience. We notice that no two green node is connected - indicating no overlap.

However, if Bruce allowed some overlap, he should purchase an extra tower (total of 6 towers). We found a handful of ground states (energy -5) with 6 occupied nodes. These states indicate some of the best coverage with a little bit of signal overlap. We believe that the trade off between overlap and city-wide coverage is worth it, and insist that Bruce purchase the extra tower! We display some of these solutions below:

We could push this even further. If Bruce would consider even a little bit more overlap, he could purchase a second tower (for a total of 7 towers!). We justify this descision because we found 2 ground state solutions with 7 nodes! With this combination, he will be covering the most amount of Gotham - the only tradeoff is that he will have to make peace with a little bit more overlap. We display the solutions below:

The only issue with the above solution is that it does not determine which of the solutions for either the 6 towers of 7 towers solution is the best. This is due to the formulation of the UD-MIS problem which basically "bins" the amount of overlap between two nodes into a simple "yes" or "no". For example, two nodes that are 0.99 units away will be penalized in the same way as two nodes that are 0.1 units away. To solve this after the fact is trivial, we simply need to compute the amount of overlap between the solution set and determine the solution that minimizes it. However, we try to re-formulate the problem in such a way where that comes out naturally.

Ideal method to find the appropriate overlap would be using the inverse square law for transmission of signals or calculating overlaping areas using a RELU type method. We use a 1/distance equation rather than 1/distance^2. This formulation is an extra exercise to evaluate incremental differences in energy that are not possible using the UD-MIS method. The solution from this method is base on the new formulation and not on the expected UD-MIS.

The UD-MIS formulation where the range overlap is descretized does not give solutions that would indicate the optimum solution since a large overlap and a small overlap both have the same penalty (higher energy of 1).

Thus a modified solution is found with a different solver (D-Wave) which uses the equation:

Where and the energy of each tower is -3.

As can be seen, in this solver the coefficient can be used to indicate higher penalty for higher overlap.

Using this formula and the execution below, we get the following best energy solution of -9.513712 using D-Wave. Although, note that this solution was only found 1 time with 100 samples. We notice that even with the new formulation, only 5 towers are needed.

With this formulation, we get a sampling given by the following two figures. On the left, we show the sampling from D-Wave and on the right, a similar GIF as above displaying the various solutions.

D-Wave Solutions for Modified Gotham Problem	GIF of the Multiple Best Solutions Found

From D-Wave, we also show the resulting qubit graph (left), embedding (center) and energy spectrum (right):

Graph Representation on D-Wave	Embeddings on D-Wave	Energies Sampled on D-Wave

We take this project one step further by solidifying our business case with a real application: finding the least redundant set of proteins from real data! See this notebook for the implementation.

Qamino strives in finding non-redundant protein sets to enable our customers to efficiently produce drugs without having to waste time experimenting with proteins that have already been tested. We test our algorithm on data found from the Dali Protein Structure Comparison Server. Our data is a matrix of the "similarity" scores between 59 different protein sequences. Here are the following protein sequences we investigate:

1bksA, 3f2bA, 2yb1A, 3e38A, 2anuA, 3qy6A, 1v77A, 3dcpA, 3au2A, 1m65A, 2a3lA, 2qpxA, 3iacA, 1j5sA, 1itqA, 4mupB, 4dlfA, 2ffiA, 3irsA, 3cjpA, 4dziC, 2gwgA, 4ofcA, 4hk5D, 4qrnA, 2dvtA, 3gg7A, 2y1hB, 2vc5A, 2ob3A, 3k2gB, 1bf6A, 1a4mA, 2ogjA, 1a5kC, 1yrrB, 3nqbA, 2vunA, 1onxA, 3pnuA, 3giqA, 3griA, 3e74A, 4b3zD, 1gkpA, 2imrA, 3ooqA, 3icjA, 2oofA, 4c5yA, 3mtwA, 3mkvA, 4cqbA, 1k6wA, 4rdvB, 2uz9A, 2pajA, 3ls9A, 1j6pA

To formulate this problem as a UD-MIS problem, we simply need to construct the edge matrix based on the similarity values from the Dali Protein Structure Comparison Server. To do so, we must choose a good threshold to consider an edge. We use the following histogram to arbitrarily determine the best threshold. We chose a threshold of 25 indicated by the red dotted line on the histogram. On the right, we show the graph created (node positions are randomly assigned).

Histogtam of Similarity Values	Graph Visualization

We then solve the UD-MIS problem using a clasical simulated annealing schedule T_i * (T_f/T_i)^(t/N) where T_i = 100 and T_f = 0. We find a ground state for an energy level of -28. We plot the corresponding energies per iteration (left) and the graph solution in green (right) in the following figures:

Energy Values	Graph Visualization

The solution set yielded from the classical simulation found 28 non-redundant proteins at a ground state energy of -28:

1bksA, 3f2bA, 2yb1A, 3e38A, 2anuA, 3qy6A, 1v77A, 3dcpA, 3au2A, 2a3lA, 2qpxA, 3iacA, 1itqA, 2ffiA, 3irsA, 3cjpA, 4dziC, 2gwgA, 2y1hB, 2vc5A, 1a4mA, 2ogjA, 1a5kC, 1yrrB, 3pnuA, 2imrA, 3ooqA, 3icj

Since our company name is Qamino (standing for Quantum Amino), we needed a solution using real quantum hardware as well! Thus we tested this out using D-Wave. We were able to find the -28 energy ground state (although it was only sampled once out of 100 samples). We display graph representation of the problem in D-Wave (left), the actual embedding on D-Wave 2000Q (middle) along with the energies sampled from Dwave (right).

Graph Representation on D-Wave	Embeddings on D-Wave	Energies Sampled on D-Wave

For more details refer to the Business Application found here

• Notebook for task 1
• Notebook for task 2
• Notebook for task 3 (Gotham city) running on real quantum hardware
• Notebook for extra challenge: Finding the least redundant set of protein sequences
• Notebook used for benchmarking
• Business Application
• Business Pitch Video