Solving Optimization Problems using Physics: Part 1

The real beauty of engineering lies in recognizing the applicability of one distinct domain of science in another. This has been pivotal in realizing that Quantum physics can help you build computers with so much potential (the Quantum computers and Quantum-inspired computers), that companies and governments around the world are investing billions into it. Through this article and its successors, I will introduce the beautiful intersection of computing and physics to solve optimization problems that find utility in the Finance, Logistics, and Electronics industries.

IBM’s Quantum Computer

Making Physics useful

The Ising model is a physics model used to describe the energy of a magnetic system made up of atoms. A magnet has two poles, north and south. Just like that, an atomic magnet, represented through a quantity called “spin”, has two types, up and down, just like the North Pole and the South Pole.

Now, you may be wondering what a physics model has to do with computation problems. How many states does a bit have in computing? 2. How many states does a magnet have? 2 (north/south or up/down). Rings a bell?

Now, why optimization problems? You see, any physical system has a tendency to minimize its energy. Now, think of minimization problems like cost minimization or maximization problems like profit maximization. Maximizing a number is the same as minimizing its negative. Therefore, the physics of a system’s tendency to minimize its energy can be leveraged to solve optimization problems, Making physics useful for computation.

Bit of Math

We typically represent spins as s , and the up/down configuration numerically as either 0/1 or +1/-1. In the Ising model, we use +1/-1. When we use 0/1 notation i.e. s=0 or s=1 then it is called the QUBO model (Qudratic unconstrained binary optimization).

Now, the Ising model says that energy of a magnetic system of n number of spins is given by:

Here, the summation indices i,j run from 1 to n. The terms J and H are constants that define the contribution of each spin pair and individual spin towards the total energy. Note that only the spins that talk to each other, that is, the spins that are coupled to each other, take part in the first summation. So, the SiSj product represents the energy due to the interaction between spins. The H sum represents the energy of spins on their own when they are not interacting with any other spin.

So, you would observe that E can be minimized in various situations:

1. If J and H are positive, then we want all S to be +1 because then all terms in summation become negative, taking the entire energy to the lowest possible.
2. Similarly, if J is negative, then to make that part negative Si’s and Sj’s will tend to be opposite so that their product is -1. Here, the sign of H makes the problem even more complex.

So, this shows that different signs and magnitudes of J and H would lead to a variety of spin configurations, some being +1 and others -1 to minimize the energy. As it turns out (and I am skipping the proof), you can frame any optimization problem with up to a quadratic term in its variable into the Ising model.

Any optimization with up to a quadratic term?

Let us say I use a certain machine to produce footballs. I need to supply current to it to run it. The production output of the machine increases if I increase the current supply: pump in more power, get more output. Now, I know that the electricity consumed by this machine grows quadratically with my current input. So, while production is growing, so is my cost. Let us say my production grows linearly with increasing current. More production means more money for me but at a higher cost from more electricity consumption. I need to see how much I can increase the production before the electricity costs make the rise in production unfeasible.

If I represent my new current by I and the old current by I0, then my production increases by, say c(I-I0), and my costs increase by bI²-bIo². Then, my change in profit equation would look like:

Change in Profit=c(I-I0)-b(I²-Io²)

This is an example of an optimization problem with up to a quadratic term, the quadratic term being the cost term bI². I want the change in profit to be positive, otherwise increasing electricity consumption is meaningful, in fact, I might have to reduce it from current levels to improve profits.

This was just a small example of how quadratic term shows up in an optimization problem, along with linear terms and constants. There are various problems that have this structure and are of immense importance in Finance, Logistics, Energy Systems, and Circuit Design.

What’s next?

In the next part of this series, I will talk about two ways to solve such problems in Python with code running on a Quantum Computer provided by DWave and using a Quantum-inspired computer provided by Fixstars.

Till the next story,

Namaste, Bye, Sayonara,

Sanyam