Quantum Annealing: The First Wave of Quantum Computing 

Quantum computing is poised to become the next breakthrough technological advancement in how organizations leverage IT resources for a competitive advantage. With the recent surge in academic and industry analyst research dedicated to this computational paradigm, many believe it will mirror the impact of artificial intelligence as a ubiquitous means of solving computational problems that far exceeds the capability to do so with conventional approaches.

Quantum annealing is a form of quantum computing that provides a superior approach to optimizing the allocation of resources, costs or time. It is particularly useful for solving massive optimization problems with robust performance not possible with other computing methods that take far too long for practical implementations.

Quantum Logic Gate vs Quantum Annealing

Quantum annealing is a type of quantum computing that’s different from quantum logic gate—which is what most people refer to when the quantum computing term is used. Quantum gate computers utilize mechanisms like logic gates to implement quantum logic gates at the speed of quantum computing. However, quantum annealing functions more like a traditional anneal, which is a process for repeatedly heating and cooling metal slowly enough to minimize its internal stress so it becomes stronger. With quantum annealing, the computer seeks to find its minimum energy state, and a programmer uses it to work on a specific business problem. By designing the problem so that when the computer reaches what appears to be its minimum energy state, it can solve certain problems of enormous complexity.

For example, in the classic traveling salesman problem (often called TSP), classic computer science algorithmic problem, a salesperson might need to fly to several cities in many countries to sell goods in 100 locations. The objective is to determine a route to complete the job as quickly as possible. With regular computing, it takes an exponential amount of time compared to the number of cities to find the best route. By designing this problem so the energy of the quantum annealing system is at its minimum when the time of travel also is, the answer is quickly produced. This quantum annealing approach works for several problems; simply describing the problem to the computer reaches its minimum energy state produces an answer.

The Importance of QUBO Modeling

The way to model business problems so that a quantum annealing system reaches its minimum energy state is to use Quadratic Unconstrained Binary Optimization (QUBO). By transforming a problem like the traveling salesman—which has a host of real world implications for logistics or the airline industry—into QUBO’s mathematical model, users can insert it into the quantum annealing system via Python. The system’s hardware will then reduce its energy based on QUBO’s representation of the problem. This approach is critical for resolving many quantum computing problems like the Non-Fungible Token (NFT) barter problem, a variation of the traditional subset sum problem.

For example, an NFT holder may want to obtain an NFT valued at $50 by exchanging a number of NFTs of varying denominations (perhaps $3, $9, $4). The objective is to do so and come as close as possible to the desired $50 token. This problem would take an exponential amount of time using conventional methods, but is rapidly solved by employing QUBO with quantum annealing. QUBO enables users to convert exponential problems into polynomial ones that require much less time to solve. No matter how many variables are involved, this approach reaches answers in milliseconds. QUBO provides the values of the energy for the quantum annealing system so that when this energy reaches its minimum state, the polynomial’s does as well to answer the question.

Quantum Annealing Is Not Exact

However, quantum annealing is not the solution for every problem. It is questionable as to whether quantum annealing actually solves a QUBO by reaching the exact minimum energy state or if it only reaches a near minimum energy state. The quantum annealing system attempts to reach a minimum energy state and comes close—but how close depends on how long it cools. If we let the system take an exorbitant amount of time, say 100 years to solve each problem, it would always attain complete minimum energy state. But in practice most problems need to be solved in seconds or milliseconds, so the system often only reaches a near minimum energy state.

However, there are many problems for which a near minimum energy state is sufficient. In the traveling salesman example, it’s not critical if the time is off by 10-15 seconds or in the NFT example the $50 NFT marker is a few cents over/under. However, there are certain types of ‘constraint problems’ that require an exact answer. For example, there are many constraints involved in solving the problem in which several pilots are needed to fly planes to numerous destinations for weekly service. The constraints include: each plane needs two pilots; one pilot must be a captain; both pilots need eight hours of sleep; they can’t fly more than 12 hours a day; and their journeys need to begin where they previously ended. To solve this problem, an inexact answer could result in no pilots located when/where a plane is taking off or tired pilots flying too long and potential disasters for the airlines and passengers on these flights.

If there are few variables and uncomplicated scenarios, quantum annealing may actually work for constrained problems that need exact answers. However, the caveat is there is no guarantee it will. Therefore this method is not appropriate for solving problems in high-risk scenarios. Additionally, there are physical limitations to some problems that can’t be modeled in QUBO exactly as they are in the real world. Problems with immense variables and complexity can’t all fit in an available quantum annealer.

In addition, since every run of the annealer potentially reaches a different state based on certain probability distribution (the lower the energy of the final state, the higher is the probability), better and better solutions can be obtained by running the program multiple times. For example, if we are trying to find the optimal solution to the traveling salesman problem, we can run the program many times on a quantum annealer and take the best solution out of all of the solutions. We can check which one is the best by using a classical computer.

Broad Business Use Case Potential

Quantum annealing offers a high-performance solution for effectively solving a myriad of business problems that require finding the absolute min/max amount, cost, distance, time or size within a very large, but finite set of possible solutions. For solving these business use cases, it is one of the most promising quantum computing technologies available today.

About the Author

Debasish Ray Chawdhuri is a Senior Principal Engineer at Talentica Software, a global product development company that helps startups build their own products. Debasish is an IIT Delhi alumnus and a researcher who has worked closely with founders of high-growth startups and enabled the adoption of emerging technologies like Blockchain. He has published several research papers on Privacy, Cryptocurrency, Smart Contracts, and Cryptography on prominent platforms like IEEE, Springer and authored a renowned book on Data Structure and Algorithms.