Using Quantum Optimization to find Locations to Place Energy Plants

Have you ever stopped to think about everything that happens behind the scenes to make your daily life work?

Every day, you might get on a train, which hundreds of workers ensure works correctly.

Or, you might get in a car that runs on gasoline that many have worked to extract, refine, and transport to you.

You walk into your office or classroom that is powered by an electrical grid maintained by many others.

Throughout the day, you use an electronic device to access the internet, which thousands of people support to keep servers and websites online.

Energy powers the entirety of our lives. Without it, so many of us would not know what to do. For around 200 years now, energy has opened limitless possibilities to what we can do, from transportation to communication. Society has flourished with constant access to energy and will continue to do so for years to come.

Others are not so fortunate to have what seems to be only a privilege. As someone who spent a lot of my childhood living in a developing country, I remember when the electricity would periodically turn off to prevent the electrical grid from taking too much load. It didn’t take much to realize that others didn’t have access to electricity at all. Their homes and sometimes their entire communities were not connected to the grid, and they lived their lives without such a powerful tool, essentially cut off from any modern technology or communication.

A big factor in the absence of electricity in their lives is that setting up power plants near their relatively remote homes is expensive. The cost of building the plant and implementing some kind of infrastructure like power lines to distribute the power is likely too high for them or the government of developing areas. Therefore, it is imperative that, if one is to build a power plant, they also find the most optimal route to lay down the power lines that would go from community to community.

So, to solve this problem, I decided to use a quantum optimization algorithm. Quantum computing is the next step of the future of how computers function. Regular, or “classical”, computers are slowly reaching their peak in performance in accordance with Moore’s law. Quantum computers have the advantage of being able to harness and interact with the properties of quantum mechanics. This allows quantum computers to tackle certain problems with greater efficiency, speed, and even accuracy than classical computers.

Quantum computers are particularly capable of solving optimization problems. In optimization, there are many solutions to the problem, but there is one best solution. These problems can often be modeled as a cost function, in which the minimum (or maximum) value of the function represents the most optimal solution to the problem. Now, although there is a single individual solution, due to the current limitations in the hardware of quantum computers, an approach is taken instead where the solution is approximated.

Credit: Wikipedia.

For simplicity, I decided to look at a dataset of villages that, according to a government survey, did not have access to electricity at all in the rural areas of Pakistan, which you can find at the bottom of the article in the attached Github repository. The data of interest in this survey was the GPS location of each village (longitude and latitude). Using these coordinates from each village, I now have all the information necessary to solve my optimization problem.

A very convenient way to model the optimization is by framing it as a TSP, or a Travelling Salesman Problem. As a famous problem in computer science, the goal is to find the shortest path given a number of points that the route has to pass through.

These aren’t only locations of people that lack access to electricity, but this is meant to help someone understand the goal of the TSP.

Needless to say, the solution to the TSP would be the route with the shortest distance. This is what I am looking for to solve my optimization problem.

Note: Bohr Technology has developed a similar solution to the TSP using QAOA here, that I modeled my solution off of which you can find at the bottom of this page.

So, the first step is to create a distance matrix given all of our nodes (points). In short, a distance matrix looks something like this:

credit: Wikipedia

Think of it like a table: every element of the matrix is the distance from the point its column it represents to the point that its row represents. The nth row/column refers to the same point, which is why you see a diagonal of zeros across the matrix: the distance from a point to itself is 0.

In a Python script, I took the CSV file from the survey, and restructured and filtered all the irrelevant data out so I could only deal with what I want (using pandas, of course):

Now that we have all of our relevant and filtered locations, we create a distance matrix using a convenient function from the entropica_qaoa library, and turn it into a NumPy array datatype:

Applying the Algorithm

To solve the TSP problem, we can employ the Quantum Approximation Optimization Algorithm (or QAOA for short). This algorithm provides a balance of efficiency in computation and approximation to avoid limitations in today’s QC hardware.

QAOA thinks about the problem in terms of clauses (or constraints) and finds a bitstring z that can satisfy these constraints as much as possible, or something close to it. It’s able to do that by finding the most optimal angles β and γ based on the cost hamiltonian.

Note: In quantum mechanics, hamiltonians are used to describe the total energy of a system and can act as an operator when applied to a quantum state.

The cost hamiltonian is modeled on all the constraints that are laid out in the TSP (all of its rules and what can and cannot be done to solve it), as well as the distances from node to node that we set up in a distance matrix:

The problem is, with all the constraints that make up this cost hamiltonian, it might be very difficult to construct and model this hamiltonian on the quantum computer immediately. The solution lies in a concept very similar to what is known as adiabatic computation. Basically, you would start off with a more basic hamiltonian that is easy to construct, and evolve that state to the hamiltonian you desire, whose lowest eigenstate (ground state represented by a scalar) you can then find.

The angles γ and β exist to act as parameters for the cost hamiltonian and the “driver ” hamiltonian (the “easier” hamiltonian), which we can optimize using the Variational Quantum Eigensolver VQE algorithm using the equation constructed below:

The U symbols are unitary operators, which can be applied to quantum states. They are also known as quantum gates. I won’t go into detail of how the VQE algorithm works, but we use it to find the most optimal set of angles beta and gamma, which can provide us the solution.

This result would be a bitstring as we mentioned before, so we must convert it to a decimal string, which would be the order of points we must go through to travel the least distance (ie the solution to the TSP):

And this ends up being our result:

betas [2.96626006 0.59907979]
gammas [4.43552397 6.18314523]
Solution [0, 2, 1, 3]

One last important thing to mention is that upon choosing p angles to work with, as p grows larger and larger, it will be more and more likely that the solution converged upon will be accurate. In the above output, there are 2 beta and gamma results, meaning in this case, p=2.

Summary

• There are many areas throughout the world where people do not have access to electricity. It prevents them from doing so many things we are accustomed to in our daily lives from communication to finding information.
• To help alleviate this problem, I wanted to find the most optimal route throughout these locations to place power lines to find the most economic configuration of setting up energy infrastructure there.
• I used a quantum computing library called PyQuil to solve this problem by modeling it as a TSP (Travelling Salesman Problem) and using the QAOA (Quantum Approximation Optimization Algorithm) to converge on an answer.
• The QAOA algorithm takes 2 angles as parameters, beta, and gamma which describe a “driving” and “cost” hamiltonian (represented by unitary operators) which the computer can model.
• Using the VQE algorithm, the computer can optimize the angles to find how to get the best result and outputs the bitstring that can satisfy the most constraints. The bitstring is then finally converted into a decimal order of points that represent our answer.

Further Reading

1. Original QAOA Paper
2. Stanford CS 269 QC lecture notes
3. Original TSP Solver by Bohr Technology
4. Repository for my version of the code

Thanks for reading!

Hi! I’m Saad Mufti, an all-around computer enthusiast. If you liked what you just read, don’t be afraid to reach out or follow me here or on LinkedIn!