quantum computing,

Wisdom of Quantum Annealing

Rahul Gopan Rahul Gopan Follow Jan 13, 2020 · 5 mins read
Wisdom of Quantum Annealing
Share this

Bob has got an ice-cream van. Bob wants to give free ice-creams around his neighbourhood and wants to get to the next town at the earliest. Bob would like to know the shortest distance for doing so.

Considering Bob’s case, it isn’t too hard for a classical algorithm to solve but a scenario where the neighborhood is spread across miles of area, classical algorithms aren’t the best to go with. These are the NP complex problems that are hard to solve efficiently.

Now taking things to a quantum level, these problems can be solved with much greater efficiency from what a classical computer could ever accomplish thanks to the annealing based quantum computation.

Understanding Hamiltonian & Eigenspectrum

Physical systems have a tendency to remain at the lowest energy state, known as ground state. It’s similar to having ease at walking down a mountain than climbing one. With that in mind, we could encode our problem into a physical system and finding the lowest energy state of that system would get us the most efficient solution to the problem.

img

A Hamiltonian is basically a mathematical representation of the energy state of a system. A Hamiltonian has to be fed with the position of the system inorder to get the energy state. For solving a problem using Hamiltonian, we have to input the ground state Hamiltonian of the system and evolve it to the problem Hamiltonian which would obtain us the energy states of the system.

img

We give the input of the ground state Hamiltonian H0 and s would be zero initially, so we get H = H0. The value of s would be gradually increased until s becomes 1 and so we get H = H1 which is our problem Hamiltonian that could be at the lowest energy state which is our answer to the problem.

An eigenspectrum is just a graphical representation of the energy states of the system. Hamiltonians of the system is plotted on an eigenspectrum and is then used to find out the lowest energy state. Different energy states are plotted on different levels on the eigenspectrum. There exists a gap between the lowest state and the other states that keeps them separated from each other. This gap would be extremely small for a hard question and the gap keeps on getting smaller as the problem gets its complexity.

img

Unlike classical way of things, quantum particles have a special property of being able to pass through barriers and obstacles, such as a ball passing right through a mountain rather than climbing it to get to the other side. This property is known as Quantum Tunnelling. But on doing so, we could also end up at the local minima of the ball and not the global minimum which is our actual solution. This leads us to problems on how we’d know if the state obtained by the above method has fetched us the lowest possible energy state (Global minima) and how do we know when we get to one ?

Adiabatic Quantum Computing

Rolling a ball around a valley could get the ball to its local minima state but as our problems require the most efficient solution to such complex problems, obtaining the local minima state of the system does no good. To tackle this, we are introduced with Adiabatic Quantum computing. The subatomic particle that is trying to find it’s Global minima is evolved very slowly so as to maintain the particle’s energy at minimum. This process of slowly evolving the particle maintaining its energy at minimum is know as an Adiabatic process.

The slightest interference in the propagation of the particle could get the particle to a higher energy state which would result in a wrong solution. At the end of the adiabatic annealing process, we are obtained with the most probable least energy state of the particle and this whole process happens in a very short span of time. These particles are manipulated with microwave frequencies and are extremely fragile to external noise which makes the adiabatic process of annealing a challenge.

Annealing based QPUs over Gate based QPUs ?

img

Annealing based Quantum processing units (QPUs) aren’t bound to complexities that we face during designing a gate based QPU and for that matter, annealing based QPUs can have many Qubits. D-Wave, a Canadian Quantum computing startup has made a annealing based QPU that has over 2000 Qubits whereas the most powerful gate based QPU at the time is a 79 Qubit QPU by Google codenamed Bristlecone.

The increase of Qubits in annealing based QPUs helps to obtain Hamiltonian of many states which would eventually increase the efficiency of the solution. Though the number of Qubits are very different in both, gate based QPUs are capable of doing a wide variety of tasks including optimisation problems, AI/ML research and run algorithms such as shor’s algorithm and Grover’s algorithm (though current gate based QPUs are not powerful enough to perform these algorithms). For that reason, gate based QPUs are widely known as Universal QPUs supposedly capable of performing any task unlike annealing based QPUs which are specifically designed for optimisation based problems and AI/ML research.

To conclude, even though annealing based QPUs are bound to perform optimisation based problems, they have proved their stand against gate based QPUs by being more efficient in that matter. This is no surprise when you find tech titans such as Google, NASA and Volkswagen buy these annealing based Quantum computers which costs over 15M$ taking the dream of harnessing the true potentials of Quantum computing a step further.

Join Newsletter
Get the latest news right in your inbox. We never spam!
Rahul Gopan
Written by Rahul Gopan Follow
I'm a undergrad CS student aspiring to research on Deep Learning and its implementation on Quantum Computers. My area of interests would be Machine Learning, Quantum Computing, Geometric Deep Learning and Bayesian Deep Learning. I like to write content related to the field I’m working on with an intension of making the general public aware of what’s going on in the field.