The Quantum Approach to np-hard Optimization Problems Name: Sam Prager Bio

Google’s Quantum AI Lab promo video: [http://www.youtube.com/watch?v=CMdHDHEuOUE]

For years scientists have hypothesized a new class of computer so impossibly powerful that just one could solve problems that would take all of the world’s computational power the length of the universe to solve. Quantum computers, so called because they rely on the strange properties of quantum physics, have the potential to outclass today’s computers based on classical physics by unimaginable amounts. At the forefront of quantum computer development is a company called D-Wave Systems. Self-described as “The Quantum Computing Company,” D-Wave is the first and only company to make commercially available quantum computers [1]. Although there is an ongoing debate surrounding the extent to which quantum phenomena come into play in the computer, the latest evidence strongly suggests that they are at the very least present and customers seem to be convinced. To date D-Wave has built and sold two computers: The 128 qubit D-Wave One, sold in 2011 to Lockheed Martin and located at USC’s Information Sciences Institute (ISI) in Marina Del Ray, CA and The 512 qubit D-Wave Two, purchased in May 2013 by a collaboration of NASA, Google, and the Universities Space Research Association (Figure 1) [2]. Researchers at these institutions aim to discover ways in which the D-Wave machines can be used to solve a notoriously difficult class of problems with far-reaching applications too challenging for classical computers: discrete combinatorial optimization problems [1]. This hugely important class of problems has applications in a diverse number of fields ranging from network computing, machine learning, and artificial intelligence to neuroscience, zoology, and airline travel. Finding successful solutions to these problems would not only indicate the dawn of a new era in computer science and technology; it would revolutionize a vast range of disciplines and solve a number of today’s grand challenges.

D-Wave Systems Figure 1: (Left) The D-Wave One and D-Wave Two. (Right) The 512 qubit quantum annealing processor at the heart of the D-Wave Two

In order to understand the potential applications of the D-Wave computer, it is important to understand the unique properties inherent in quantum computing (QC). The unit of information in QC is the quantum bit or qubit. While classical bits store information as either 1 in the on state or 0 in the off state, qubits can be both on and off simultaneously due to the superposition of states in a quantum system. The superposition of states persists until the qubits are observed and the wave function collapses at which point they are seen to be in one state or the other. This means that information requiring 2ⁿ classical bits can theoretically be stored in just n qubits and operations on all combinations of n classical bits (2ⁿ operations) can be done in just one operation on n qubits. Because of this property, quantum computers have a significant potential advantage over classical computers when finding an optimal solution from many possible options.

The theory of adiabatic quantum computation (AQC) is a model that focuses on using superposition and other QC properties to arrive at the lowest energy of a complex energy function. In AQC, a quantum system is initialized in its lowest possible energy state called the ground state. Adiabatically, meaning without heat transfer, the energy function known as the Hamiltonian is evolved from the simple Hamiltonian that described the initial system to a more complex Hamiltonian in such a way that the system remains in its lowest possible energy configuration [3]. By ‘fixing’ the complex Hamiltonian in a particular way such that it models a problem of interest, one can interpret the final ground state of the AQC system as the problem’s solution. The quantum processor at the core of the D-Wave, using superconducting flux qubits and spin-spin qubit couplings, attempts to find the lowest energy states of a system by utilizing a process intrinsically related to the AQC model called Quantum Annealing (QA) [4 p. 3]. Because purely adiabatic processes are not practical in real world situations, QA (illustrated in Figure 2 below) allows a degree of non-adiabatic energy (heat) transfer and does not require the system to remain in the ground state for the entire process [3].



Figure 2: (a) Comparison of Classical annealing in which potential energy barriers can only be crossed by thermal excitation to higher energy states and Quantum annealing which allows tunneling through potential barriers. (b) Weight of Disordering Hamiltonian (Γ) and weight of Encoded Hamiltonian (Λ) as a function of time throughout the annealing process [6].

Nature 473

In addition to the encoded Hamiltonian that describes the problem, QA also introduces a disordering Hamiltonian that increases uncertainty in the system (as described by the Heisenberg Uncertainty Principle). This allows the system to pass through high-energy states to low energy states without ever occupying the high-energy state – a process known as quantum tunneling (Figure 2.a) [4 p. 3]. By decreasing the weight of the disordering Hamiltonian (Γ) from 1 to 0 and increasing the weight of the encoded Hamiltonian (Λ) from 0 to 1 (Figure 2.b), the system will settle to a state that is a local minimum of the encoded Hamiltonian and a good solution to the encoded problem, though not necessarily the optimal solution if the annealing time is small [4 p. 3], [6].

Some of the most challenging problems in applied mathematics and computer science are problems that involve finding the optimal object from a set of objects each consisting of a combination of discrete components [7]. Of specific interest is a subset of optimization problems called Non-Deterministic Polynomial-time (NP)-Hard problems. The classic NP-Hard problem is known as the traveling salesman problem (TSP) and is described as such: A salesman needs to visit some number of cities and must visit each city once and only once. What path should he take so that the total distance he travels is minimized [8]? It is clear that using brute-force to find the solution to this problem involves calculating and comparing the distances of every possible route and that as the number of cities increases, the number of possible routes grows exponentially.

Any path optimization between nodes in an interconnected network, from the quickest path to send a network packet over the Internet to DNA sequencing, can be modeled as a variation of the TSP. In general, if we consider a graph G = (V, E) of vertices (V) / nodes (these would be the cities in the original example) connected by edges (E), each with an associated weight corresponding to some arbitrary relationship between the nodes it connects which models the desired problem (this would be distance in the original example), the path that minimizes the sum of its constituent edge weights is the optimal solution [9 p. 12].

Ising Model Formulations and the Quantum Hamiltonian

For even a reasonable number of nodes, the computing power required to solve NP-Hard optimization problems grows so fast it becomes impossible for classical computers to come even remotely close to finding optimal solutions [8]. For AQC based quantum computers, however, these sorts of problems are much simpler. The key is a statistical model originally developed to describe ferromagnetic systems known as the Ising Model. Using this model, theoreticians have been able to formulate many discrete combinatorial optimization problems as the Ising Hamiltonian of a distribution of disordered interacting magnets called spin glasses [9 p. 3]. Spin glasses are perfect classical analogues to qubits making it possible to interpret the Ising Hamiltonian as a Quantum Hamiltonian whose ground state is the optimal solution to the embedded NP-Hard optimization problem [9 p. 3]. By encoding this Hamiltonian into the QA processor, low energy solutions to NP-Hard problems may be arrived at. As the annealing time becomes large, the probability that the result obtained by QA is the ideal solution that would be obtained by AQC approaches 1. In reality however, it is desirable for the annealing time to be as small as possible and thus the system is much more likely to settle at an energy state that is a local minima rather than the ground state located at the absolute minima. Because of this single iterations of QA tend to produce heuristics rather than the optimal solution itself [4 p. 2]. Additionally, the limited number of qubits in the D-Wave’s processor (512 qubtis in the D-Wave Two) makes it impossible to directly embed quantum Hamiltonians for problems with more than 512 nodes. Because of these limitations, the D-Wave must rely heavily on the assistance of classical algorithms able to divide large problems with many nodes into multiple smaller problems that can be directly embedded in a quantum Hamiltonian.

For more than a year after the D-Wave One was released, the big debate was over whether or not the computer was quantum at all. Detractors claimed that the there was no evidence that the annealing was quantum rather than thermal (see Figure 2.a) and that while D-Wave had created an interesting computer made of superconducting magnets, they had not created a quantum computer. The first significant evidence in support of D-Wave’s claim that the computer was quantum came from a USC research group at ISI. The USC research group was able to show that the “experimental signature” created from the aggregate of multiple annealing trials with varying parameters was consistent with the signature produced by simulated quantum annealing, while being markedly different from the signature produced by both simulated and experimental thermal annealing [10]. Despite the evidence that at least some degree of the computer operates on quantum principles, the extent is still unclear. With the D-Wave Two now in the capable hands of NASA, Google, and Universities Space Research Association, it is likely that more information on the true nature of the D-Wave system will emerge. The ease with which some of the world’s hardest problems can be put into forms easily solved by quantum annealing has huge implications and will likely drive an explosion of interest in these systems over the next few years. Problems with nodes small enough to for the Hamiltonian to be embedded directly can already be solved with high probability in just a few iterations of QA. Additionally, some of the world’s brightest researchers and computer scientists are now working on developing algorithms to optimize large problems for D-Wave embedding. This, in conjunction with continued exponential scaling of quantum processors, may very soon allow quantum computers to begin making significant contributions towards finding the solutions of problems that cannot be solved today. The ability to optimize huge amounts of data quickly and effectively would profoundly change what we are technologically capable of -- things like simulation of the brain, the earth’s ecosystem, and even the entire universe would all enter the realm of possibility. Futurists and hopefuls predict that humanity is nearing a technological singularity after which humanity would be so fundamentally changed that, like a black hole, prediction beyond is impossible, and although such sweeping proclamations can seem a bit fanciful, with such a potentially powerful technology just at its very dawn it’s hard not to wonder.

References:

[1] D-Wave Systems Homepage. D-Wave Systems Inc. [Online]. Available: http://www.dwavesys.com