iQuHacks 2023 Quantinuum Challenge

Our Experience At iQuHack!

Authors: Jaydin Freeman, and David Glover

This weekend our group: Jaydin Freeman, David Glover,  Ken, Jack, and Eimaan had the wonderful opportunity to attend iQuHack held at Massachusetts Institute of Technology. At this event we attended workshops, networking sessions, and connected with peers. It was truly a great experience.

Quantinuum's Challenge

Quantinuum provided five challenges to its participants. The one we chose was the following:

This QAOA (Quantum Approximate Optimisation algorithm) implementation uses the most naive possible classical optimisation strategy. Parameters are sampled from a uniform distribution and if a list of parameters increases the value of the cost function these values are stored as the best guess so far. Can you improve on this using a more sophisticated optimisation strategy? 

In layman's terms, we were tasked with coming up with a more efficient way to solve the Max Cut Problem using quantum algorithms. Imagine you have a big picture with lots of dots (nodes) and lines (edges) connecting some of the dots. We want to color some of the dots red and the rest blue in a way that there are as many lines as possible connecting dots of different colors.

At first glance, this came off as extremely difficult, seeing as no one in our group had experience working with quantum computers before today. As soon as we got the challenge, we broke off from the larger group and started working on getting collaboration tools set up and learning the basics of project management. This took a lot longer than we initially thought, with us finishing setting up our repo three hours after the challenge started, but we created memories that we will carry for the rest of our lives. After we got our repository and environments set up, we moved on to delegating tasks to each team member and attacking those right away. We got off to a rocky start learning the basics of quantum computing and genuinely trying to wrap our heads around the challenge. Thankfully, with Callum’s help, we were put back on the right track, and off we went. Around this mark, we started to dig deep into the challenge of looking for more efficient alternatives to the algorithm supplied. 

That’s when Jaydin Freeman found two global optimization techniques that piqued the group’s interest: the Basin Hopping Technique and the Nelder-Mead Method. He first looked at the Basin Hopping Technique, which we’ll describe through analogy. The basin hopping technique is a way to help solve the Max-Cut problem by pretending that the group of things is in a big basin (like a bowl) and then shaking the basin to move the items around. The goal is to find the best way to divide things into two groups by shaking the basin differently and seeing which orientation gives the most even split. I chose this technique because it’s a form of the global optimization algorithm previously mentioned in the challenge description. I went about implementing this by researching public repositories and looking for pre-existing libraries with implementations of this technique. I stumbled upon the scipy library, which had the basin hopping function with arguments that matched up with the outline of the problem given to us. After strenuous trial and error, I ended up getting a result that matched the given algorithm. I then compared my implementation of this technique to the baseline supplied by the given algorithm. Although completing this algorithm gave me my second wind, I only saw a noticeable improvement in larger datasets (i.e., more nodes and edges) which wasn’t enough for me. I met with my team and discussed the following steps, and we decided it was best to continue. Researching and using my implementation as another baseline to compare future models too. 

Next, I studied Nelder-Mead, which is also a global optimization technique that is best described using an apology. Imagine you are trying to cut a big piece of paper into two parts, and you want to make sure that you miss it in a way that makes one piece as big as possible. The Nelder-Mead method is like a set of instructions that helps you figure out the best way to cut the paper. It starts by looking at a few different places you could miss. Then it makes minor adjustments to the amount until it finds the best one. Think of it like a treasure hunt game where you start at a point and try different directions until you find the treasure. After understanding this algorithm’s approach, I looked for pre-existing libraries or repositories that may have implemented this technique in the past to avoid reinventing the wheel. I started using the supplied algorithms outline and a cost function and went from there. Next, we guess an angle for n iterations, then apply Nelder-Mead’s optimization method using the pre-existing minimize function in the scipy library. We then compare the inverse of the result to the highest energy, and if it’s more, we update the highest energy else. We restart this loop. This process took me around another 3 hours of trying different pre-existing implementations of this technique and troubleshooting more minor errors. Still, we prevailed with around 12 hours left in the Hackathon. With this extra time, I felt like the results of this function were lackluster, only seeing minimal improvement to the original function. Although this was a time-staking process, it produced results. The Nelder-Mead method was able to provide an 8.1% increase in the highest energy and a 4.0% increase in average success rate. 

David Glover then found a method that targeted the cost Hamiltonian H_C and mixing Hamiltonian H_M. This method was the gradient descent algorithm, which is often used in data mining and machine learning. A basic analogy to think of this algorithm would be to think of it like being stuck in the mountains and trying to get down with heavy fog that limits visibility. This means you have to use local information to find the minimum. They can use the gradient descent, which involves looking at the steepness of the hill at their current position, then proceeding in the direction with the steepest descent (downhill). If they were trying to find the top of the mountain (maximium) steepest ascent (uphill). Using this method, they would eventually find their way down the mountain or possibly get stuck in some hole (the local minimum), like a lake. However, assume the steepness of the hill is not immediately obvious. It takes some time to measure with an instrument, thus they should minimize their use of the instrument before it gets dark. The difficult is then choosing the frequency at which they should measure the steepness of the hill so they do not go off track. In this analogy the person represents the algorithm and the path taken down is the sequence of parameters the algorithm will explore. The steepness of the hill represents the slop of the function. The instrument used to measure the steepness is differentiation. The direction they choose to travel is the gradient of the function. The amount of time they travel before taking another measurement is the step size. This in turn was used to determine the two parameters, the cost and mixing Hamaltonian(H_C, H_M), which was then used to calculate a higher overall energy which then led to higher average energy and faster runtimes. This inturn also increases its efficiency on larger sample sizes, which was seen in multiple test that were ran. The percentage increases are as shown: 1.4% increase in highest energy and a 50.5% decrease in average runtime. The road to finding these were not easy as it took a substantial amount of time to tune the parameters that were best. This is to say that there might be parameters that lead to better results as we were time limited. These tuning parameters were the step size(eps) and the learning rate. Overall, we leveraged a diverse set of algorithms and methods to maximize efficiency and results. The backends used in this process were the pytket.backend and the Aerbacked. We employed the Nelder-Mead method, Basin Hopping method, and the Gradient Descent algorithm to achieve this goal and successfully provide better results in areas like runtime, higher max energy, and success rate which are shown below. 

When compared to the baseline our Quantum Basin Hopping Implementation saw:

8% increase in highest energy found

16% Decrease in average  success rate

3% increase in average runtime

When compared to the baseline our Nelder-Mead Implementation saw:

8% Increase in Highest Energy Found with less iterations

4% Increase in the average success rate

180% increase in the average runtime

When compared to the baseline our Gradient Descent Algorithm saw:

1.4% increase in the highest energy 

18.4% decrease in the average success rate

50.5% decrease in the average runtime