This is the third installment of my commentary on Quantum Integer Programming (QuIP) that brings together – an union (सम्हित, Samhita) – Quantum Mechanics and Integer Programming.
The two earlier posts are:
Imaginary Numbers and Electron Spin
Integer Solutions
In ancient India, several problems seeking integer solutions were posed “simply for pleasure”. The first general solutions of first degree indeterminate equations are by Brahmagupta (625 AD).
For centuries, this type of recreational mathematics, like approximations for pi, occupied the priestly class enjoying their leisurely life.
I suppose, in the 21st Century, we would call them University Professors. 😏
Bhaskara II (as there was a Bhaskara I in 650 AD who is credited with having pioneered the decimal system, the use of circle to represent zero, provided a remarkable rational approximation for pi and so on) provided some wonderful results in his Līlāvatī, which is Book 1 of Siddhānta Śiromani (सिद्धांत शिरोमणी),”Crown of treatises”, around 1150 AD, especially for quadratic equations.
Siddhānta means an established way, a settled issue, a canonical text-book, a tenet. Treatise.
The earliest one of these that have been found is the Surya Siddhanta (300-400 AD).
Among other things, it introduced trigonometric functions of angles, such as jyā-ardha.
This was transliterated by Arabic mathematicians and astronomers as jiba, which was mistranslated by the Europeans (into Latin) as sinus. 🤷🏽♂️
This is why today we use the phrase sine to represent (the acute angle in the context of a right triangle) the ratio of the length of opposite side to the hypotenuse!
As is now properly understood (Dirk Struik, A Concise History of Mathematics, 1948):
It is therefore, strictly speaking, incorrect to call linear indeterminate equations Diophantine equations. Where Diophantus still accepted fractional solutions, the Hindus were satisfied only with integer solutions. They also advanced beyond Diophantus in admitting negative roots…..
Indeed, the Arabic translations of these Siddhantas were the basis of learning for future generations of scholars, including Omar Khayyam (see my post In Praise of Poetry…and James Bond).
As I mentioned in my earlier post, the Italians took the solution of higher order equations to a whole new level and conceived imaginary numbers. This study of roots of algebraic equations was further vastly elevated by Evariste Galois (1811-1832).
Let us take a different route.
An entirely different way to find feasible integer solutions for linear indeterminate equations is as follows:
Convert integers to binary representation.
Write the equations in the form ax-b=0.
Minimize the sum of squares of the equations.
Because x(i) squared is x(i), we will have an expression that is the sum of terms, each of the form A(i)x(i) and B(i,j)x(i)x(j) where A(i) and B(i,j) are integers if a and b are.
If we minimize the expression and obtain a zero objective function value, we have a feasible solution.
This is called Quadratic Unconstrained Binary Optimization (QUBO).
This approach is not limited to first order equations, and can be applied to any set of polynomials. This takes us into algebraic geometry.
However, we will not solve such a QUBO algebraically, nor by geometric construction, like our mathematical ancestors from Egypt, Greece, India, Iran, Iraq, Italy, England, Germany and France might have attempted to do so.
Instead, we will manipulate spins on a quantum computer. 😳
Ising Model
Consider a graph G = (V,E) whose vertices V have electrons that have spin (sigma(i) on vertex i), which when measured can take on a value of either -1 or +1.
This graph of electrons is in a transverse field that has strength H(i) on vertex i, and the edges between the vertices have coupling strengths (between vertex i and j, it is J(i,j)); the values of H and J can be positive, zero or negative.
The Ising model (in Physics) is a mathematical abstraction to study interacting spins among adjacent electrons (arranged on a lattice, or a graph) at the microscopic (sub-atomic) level.
Under certain conditions, when all the electron spins point in the same direction, as that is the lowest energy level (which is Nature’s equilibrium), magnetism emerges as a macroscopic phenomenon that we can observe in our physical world at human scale.
The energy of the Ising model is of the form:
It is not hard to see that there is a one-one mapping between solutions that give a zero objective function value to a QUBO and the minimum energy levels of a corresponding Ising model.
Indeed, if x(i) is a 0-1 variable in an integer constraint, and sigma (i) is a spin (that can take on a value of -1 or +1), then sigma(i) = 2x(i)-1.
A simple illustration of this is at the top of this post where H(i)=0 for i=1,2,3 and J(1,2)=1 and J(1,3)=-1. (Set mu to 1).
How to solve the Ising model?
We use a physical device that has spins on a graph. This is a physical quantum computer.
We first prepare the spins on each of the electrons to be in a superposition state (“Hadamard transformation”) such that they have 50-50 chance of being -1 or +1.
For the toy problem of 3 variables above, if we measure the spins right now, then we will get any one of the eight solutions with equal probability, and so with probability 6/8, any such measured solution will be wrong for our problem.
However: Every one of the measured solutions is correct for a problem where all H(i) and J(i,j) are zero. (Trivially.)
Thus, this “equal superposition” state needs to be manipulated before measuring, for the result to be correct for our values of H(i) and J(i,j).
Unlike a Gate (Circuit) model where a quantum algorithm specifies how to manipulate the spin state using a quantum gate, we follow a different approach (that has been shown to be computationally equivalent).
We slowly change the field that this device is immersed in.
That is, we slowly start changing H(i) and J(i,j) from zero values to their true values.
In our toy example, H(i) are zero throughout, so there is no change. But J(1,2) and J(1,3) need to slowly become +1 and -1 respectively from 0.
There is a fundamental result in quantum mechanics (from 1928, von Neumann and Wigner) called the adiabatic theorem. It says that:
if you slowly change the Hamiltonian (field), then the ground state (previous optimal solution) will remain in the ground state for the newer field. That is, the spins will change their (pre-measured complex values of amplitudes) accordingly.
So, if we gently change the field, making sure that that spins remain in their ground state throughout, then, when we are done reaching our problem values of H(i) and J(i,j), we can measure the spins.
They will have 50-50 chance of being in one or the other of the two correct solutions (with very high probability)!
This is called Adiabatic Quantum Computing.
Repeatedly doing the above will give us a sampling of all the feasible solutions.
Note that if we convert the sigma(i) values to x(i) values and find that QUBO objective value is not zero, it means we have infeasibility.
QuIP: Finding integer feasible solutions by physically manipulating spins in line with the adiabatic theorem of quantum mechanics.
