Saavan Patel, CTO InfinityQ Technology Inc.
Here at InfinityQ, we are engaged in what we call “Quantum Inspired Optimization” or QIO for short.
Our particular approach to QIO is around probabilistic computing.
We have received a lot of questions about what that is, and rightfully so.
There is no Wikipedia page for quantum inspired optimization, and the dictionary does not have an entry for it.
Hopefully this post can help our users, customers, and the community understand what that means in our eyes, and help demonstrate the opportunities that quantum inspired optimization and probabilistic computing can bring for the future.
Physics Solves Problems for Free
When you think of physics, you might get flashbacks to your high school physics course while learning Newton's Laws of Motion.
What they didn’t teach you in those physics courses is that while learning physics can be tedious and difficult, physical systems themselves are “lazy”.
Most physical systems will take the path of least resistance to relax to the lowest energy state. For example, if I drop a ball onto a tilted floor, it will roll to the lowest point on that floor and stay there.
By preparing the system correctly, I was able to use gravity to help me find the lowest point on the floor without doing any additional work myself.
This idea extends further to things like the “Principle of Least Action”, very nicely written and described by the biographer of Richard Feynman.
When a lifeguard is trying to save a swimmer in the water, they have a few options, the path of least distance, the path of least time, and the path of least water.
Of course, the lifeguard will try to choose the path of least time, as it helps save the swimmer’s life the quickest. In physics, the principle of least action tells us that light does the exact same thing.
When you shine a light between water and air, you’ll notice that the light seems to “bend”. This bending is actually the Principle of Least Action at work.
Light has a different speed in air vs. water, and so when it wants to travel between two points, it will always choose the point that minimizes its travel time, just like the lifeguard!
This is another example of physics finding the optimal solution without us engaging in any additional work.
The last example of “Physics Solves Problems for Free” is related to how quantum computation is able to find the minimum energy state of a system, in a natural way.
The example we will explore here is the example of “Quantum Adiabatic Computation” that has been an inspiration for the design of the D-Wave computer.
Quantum and Classical Annealing
The good
If physics gives some power for free, how do we harness the properties of physics to enable the next generation of computation? The first answer is quantum computing.
In the original paper where Richard Feynman introduced the idea of quantum computing, it was first introduced as a method for simulating physics and physical systems.
However, since then we have found new uses for these quantum computers for optimization, for cryptography, for machine learning, and for many other applications.
One of the important examples of quantum computing is in the field of optimization, where physical systems are used to find low energy (i.e. really high quality) states (i.e. solutions) to systems that could support many configurations (i.e. optimization problems).
Let’s examine the method of action for adiabatic quantum computing (AQC), a method used to find solutions to these complex optimization problems.
In the figure and equation above, we can see what AQC looks like.
The computation starts with an initial state which is a simple state where it is in the lowest energy configuration, and then the system slowly progresses from the initial state to a final state which represents the problem that we are trying to solve.
The adiabatic theorem of quantum mechanics dictates that the system progresses slowly enough, then it will remain in the optimal (lowest energy) state at all times during the computation.
The system is using a physical process to solve the optimization problem at hand, without any external computation involved. We just prepare the system and let it run, pretty cool!
The bad
The problem, as it continues to be, is that an evolution such as the one required by AQC is really fragile, and as a result quantum computers are really hard to build and really really expensive.
To date, quantum computers have only been able to get up to ~hundreds of qubits (for gate based computers), and ~thousands of qubits (for analog computers such as the D-Wave machine, which does not run AQC but a similar "dirtier method" at finite temperature called quantum annealing) with many studies indicating that millions of qubits are necessary to be useful for many applications.
To give some sense of the cost for procurement of a quantum computer, up to now there have been about 40 procurements around the world, with prices ranging from a minimum of $3M to more than $100M (the median price is about $15M).
For the same money you could buy 1000 Nvidia A100 GPUs.
An Ising Machine: part classical, part quantum, all fun
The quantum system shown above for optimization problems is usually used to solve problems that look like the below equation, called the “Ising Model” (Some say its “eye-zing” à-la-American some say its “ee-zing” because of the inventor who was German both are fine).
The Ising model represents a system of "spins", variables that can be in one of two states, similar to a magnetic dipole pointing up or down.
In an Ising machine, these spins are analogous to bits in a computer, but with interactions that mimic the magnetic forces between atoms.
The goal is to find the lowest energy configuration of these spins, which corresponds to the optimal solution of the problem that is inputted to the system.
In addition to work on quantum annealing, there have been a lot of work around solving Ising Model problems with other physical systems, ranging from Optical Systems, Magnetic Systems, Bose Einstein Condensates, Oscillator Systems, and so much more.
Probabilistic Computing
In 1981, Richard Feynman first proposed the idea of a quantum computer in his work “Simulating Physics with Computers”, kicking off the excitement around a new idea of computation.
One of the ideas that is usually forgotten in that paper is that he proposes a probabilistic computer along with a quantum computer.
In his original view, the probabilistic computer was a stop-gap between the digital (0 and 1) world and the quantum world (superposition and complex phenomena).
The only difference is that a probabilistic computer misses the idea of negative probabilities!
Instead of generating probability from the laws of quantum mechanics, we generate probabilities by the laws of thermodynamics either physically implemented or digitally simulated.
We like to think of this using the diagram below, probabilistic computing (like InfinityQ’s) sit between the quantum effects of superposition and the singular effects of digital computing.
But what do we do with a probabilistic computer?
Probabilistic systems are intensively used to study and simulate quantum and statistical systems.
When we look at algorithms like simulated quantum annealing, simulated annealing and others, the algorithms to simulate physical systems have a probabilistic nature to them.
So what if we base our computing systems around probabilistic methods instead of quantum methods?
Instead of using quantum tunneling or entanglement to find good ground state solutions to our problem (which are fragile and it is unclear if they make the problem more complicated), what if we used probabilistic (and thermally assisted) methods for finding good solutions?
This is the idea behind many of the algorithms that InfinityQ works on, replacing quantum effects with probabilistic effects to achieve the same effect as a quantum computer might do.
You can see this in the figure below, showing the difference between probabilistic/thermally assisted movement vs. quantum tunneling to find good solutions to an optimization problem.
While everything depends case by case, but as of today we can outperform quantum computing both in quality, scale and cost, by many orders of magnitude.
And with respect to traditional, deterministic digital algorithms, we are seeing 100x speedup or more in many use cases.
We are really excited about what that can do for our customers, today.
Parting Thoughts
This is a lot of information to take in, and we hope that we can provide more learning, more blog posts and more information to show you the amazing effects of our probabilistic computing based systems.
Many of the reasons we chose to do quantum-inspired approaches come from the realization that physics can give us a lot of free power and quantum computing is not offering a solution to most problems industry care about.
Just like how the brain gave inspiration to modern artificial intelligence and deep learning, but modern AI systems look nothing like the brain, we hope that quantum inspired methods can build upon what works from quantum computing (the methods, simulation systems, the phenomenological principles of the algorithms) and leave the stuff that doesn’t work (the which is still unclear) behind.
We are excited by our approach and hope that you will be too!
Acknowledgements & further reading
I can’t say that I’m the first person to talk about probabilistic computers, quantum simulation methods, and thermally assisted methods. I have had many colleagues and mentors who have shaped my views on this concept. I’ve listed a few of their works on the subject below for further reading and understanding: