Quantum Annealing
Operations Research (OR) is a rare gem in the analytics world. It has significant impact in almost all industries (e.g. finance, oil and gas, logistics). Though, it has a “curse of dimensionality” of its own. Computational complexity, especially for combinatorial optimization problems, tends to grow exponentially; so is your pain (computation time) to solve them. Quantum Annealing (QA) offers a solution.
An example
Suppose you are solving an instance of Travelling Salesman Problem. Suppose you are going to visit N (say, 5) cities and come back to your starting point. You would want to find the shortest route (e.g. 1–4–3–5–2–1). Total number of alternatives are 24. If we had 10 cities, there would be 362,880 alternatives (factorial of N-1). In 20 cities, it is 1.21*10^17.
Then, you have to resort to “heuristic” methods. Simulated Annealing is one of such heuristics. Basically you explore the solution space (i.e. whole set of alternative solutions) in M iterations and converge to a good (even optimal) solution by reducing your exploration step size.
Heuristic methods, unlike, solvers (specialized algorithms to find global optimal) do not usually guarantee a global optimal. A good heuristic converges to a global or near-global solution faster than other algorithms.
What about quantum annealing?
Quantum Annealing is an algorithm with similarities to Simulated Annealing but much more complex methodology called “quantum tunneling”. Now that we have an algorithm to solve quite large optimization problems, all we need is quantum computers.
Enter D-Wave Systems
In 2011, D-Wave Systems, a company which builds quantum computers and systems, announced their first commercial Quantum Annealing service on their 128 qubit computer D-Wave One. Price tag for the quantum computer was 10M USD. Its customers were companies like Google, Lockheed Martin etc.
In 2015, Google Research announced in a blog post that QA can be 10^8 (100,000,000) times faster than Simulated Annealing according to their experiments with single core DWave2X.
DWave2X was 1152 qubits, their latest Advantage machine released in 2020 is 5640 qubits.
Can I use it?
“You don’t need to be a quantum physicist to get started with Leap. All you need to know is Python.” — Extract from Leap landing page.
Yes, you can! It even has a Python SDK. There is also a recently (March 2022) released cloud service for hybrid computing, called Leap. It is even possible to try it out using examples on GitHub. You can also use it through AWS service Amazon Braket. They even might have a “free tier”.
Perhaps there will be a research project in the future so that I might try it out as well :)
