Report

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

See allHide authors and affiliations

Science  20 Apr 2001:
Vol. 292, Issue 5516, pp. 472-475
DOI: 10.1126/science.1057726

Abstract

A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.

Although a large quantum computer has yet to be built, the rules for programming such a device, which are derived from the laws of quantum mechanics, are well established. It is already known that quantum computers could solve problems believed to be intractable on classical (i.e., nonquantum) computers. An intractable problem is one that necessarily takes too long to solve when the input gets too big. More precisely, a classically intractable problem is one that cannot be solved using any classical algorithm whose running time grows only polynomially as a function of the length of the input. For example, all known classical factoring algorithms require a time that grows faster than any polynomial as a function of the number of digits in the integer to be factored. Shor's quantum algorithm for the factoring problem (1) can factor an integer in a time that grows (roughly) as the square of the number of digits. This raises the question of whether quantum computers could solve other classically difficult problems faster than classical computers.

Beyond factoring, there is a famous collection of problems called NP-complete [see, for example, (2)]. Hundreds of problems are known to be NP-complete—for example, (a variant of) the Traveling Salesman problem—and they are all related in the following sense: If someone finds a polynomial-time algorithm for one NP-complete problem, then this algorithm could be used as a subroutine in programs that would then solve all other NP-complete problems in polynomial time. That no one has succeeded in finding a classical polynomial-time algorithm for any of these problems is strong evidence for the intractability of all of them. On the other hand, no one has been able to prove that a polynomial-time algorithm cannot be constructed for any NP-complete problem. Settling the question of whether a polynomial-time algorithm does or does not exist for an NP-complete problem is one of the outstanding problems of classical computer science. It is also an open question whether an NP-complete problem could be solved in polynomial time on a quantum computer.

Here, we describe a recently developed approach to quantum computation based on quantum adiabatic evolution [(3); for related ideas, see (4)]. We apply the quantum adiabatic algorithm to a specific NP-complete problem, Exact Cover. A decisive mathematical analysis of this quantum adiabatic evolution algorithm has not been possible. Instead, we resort to numerical simulation of the running of the quantum algorithm (5). Each time we do the simulation, we use as input a randomly generated instance of Exact Cover. The lengths of these inputs are necessarily small because simulating a quantum computer on a classical computer requires memory that grows exponentially in the length of the input. On these small inputs our data look promising. For our randomly generated instances of Exact Cover, we find that the quantum algorithm succeeds in a time that grows only quadratically in the length of the input.

Saying that an algorithm solves a problem in polynomial time means that the algorithm succeeds in polynomial time on every possible input. On the other hand, an algorithm may succeed in polynomial time on a large set of inputs but not on all. This has led to efforts to identify sets of instances that are hard for particular classical algorithms. Researchers working on the NP-complete problem 3-SAT (Three-Satisfiability) have identified a set of instances that are hard for standard classical search algorithms [(6); see also (7) and references therein]. Although the quantum adiabatic evolution algorithm could be applied to 3-SAT, we find it more convenient to study Exact Cover. Our instances of Exact Cover are generated from a set that we believe to be classically intractable for sufficiently large inputs. Using a running time that grows only quadratically in the length of the input, the quantum adiabatic algorithm solves the Exact Cover instances we randomly generated. Again, because of the space requirements inherent in simulating a quantum computer, these instances are necessarily small. However, if classical algorithms indeed require exponential time on this set and the quantum quadratic behavior actually persists for large instances, then quantum computers could outperform classical computers on randomly generated hard instances, although not necessarily in the worst case.

We now define the NP-complete problem Exact Cover [see, for example, (2)]. Consider n bits z 1,z 2, … , zn each of which can take the value 0 or 1. An n-bit instance of Exact Cover is built up from clauses, each of which is a constraint imposed on the values of three of the bits. If a given clause involves the three bits labeled i, j, and k, then the constraint is that one of the three bits must have the value 1 and the other two must have the value 0. An n-bit instance of Exact Cover is a list of triples (i, j,k) indicating which groups of three bits are involved in clauses. The problem is to determine whether there is some assignment of the n-bit values that satisfies all of the clauses. Given an assignment of values for z 1,z 2, … , zn , we can easily check whether the assignment satisfies all of the clauses. But determining whether at least one of the 2nassignments of z 1, z 2, … , zn satisfies all the clauses is in fact an NP-complete problem.

All quantum systems evolve in time according to the Schrödinger equationEmbedded Image(1)where |ψ(t)〉 is the time-dependent state vector and H(t) is the time-dependent Hamiltonian operator. A quantum computer algorithm can be viewed as a specification of a HamiltonianH(t) and an initial state |ψ(0)〉. These are chosen so that the state at time T, |ψ(T)〉, encodes the answer to the problem at hand.

In designing our quantum algorithm we take advantage of the quantum adiabatic theorem, which we now explain. At time t, the Hamiltonian H(t) has an instantaneous ground state |ψg(t)〉, which is the eigenstate of H(t) with the lowest energy. Adiabatic evolution refers to the situation whereH(t) is slowly varying. Suppose the quantum system starts at t = 0 in the ground state ofH(0), that is, |ψg(0)〉. The adiabatic theorem says that if H(t) varies slowly enough, then the evolving state vector |ψ(t)〉 will remain close to the instantaneous ground state |ψg(t)〉. [For a more precise discussion of the adiabatic theorem, see (3).]

To specify our algorithm we must give H(t) for 0 ≤ tT, where T is the running time of the algorithm. We choose H(t) so that the ground state of H(0) is known in advance and is easy to construct. For any instance of the problem under study (Exact Cover in this case), there is a Hamiltonian,HP , whose ground state encodes the solution. Although it is straightforward to constructHP , finding its ground state is computationally difficult. We takeH(T) =HP , which means that |ψg(T)〉 encodes the solution. For intermediate times,H(t) smoothly interpolates betweenH(0) and H(T) =HP , say by takingEmbedded Image(2)We start with the quantum system in the known ground state ofH(0). If the running time T is large enough,H(t) will indeed be slowly varying, and by the adiabatic theorem the final state reached, |ψ(T)〉, will be close to |ψg(T)〉.

The state vector of the quantum computer evolves in a Hilbert space of dimension 2n. We take as a basis the 2n vectorsEmbedded Image(3)where each zi = 0 or 1. Thisn-qubit Hilbert space can be realized as a system ofn spin-½ particles, where |zi = 0〉 corresponds to the ith spin being up in thez-direction and |zi = 1〉 corresponds to spin down in the z-direction. ForH(0) we couple a magnetic field in thex-direction to each quantum spin. [Specifically, the strength of the field at each site is equal to the number of clauses that contain the bit. Thus, H(0) is instance-dependent; see (3).] The ground state of the ith qubit corresponding to spin aligned in the x-direction isEmbedded Image(4)The ground state of H(0) for then-qubit quantum system is thereforeEmbedded Image(5)where the sum is over all 2nbasis vectors. This means that | ψg(0)〉, which we take to be the starting state of our algorithm, is a uniform superposition of states corresponding to all possible assignments of bit values.

To define HP =H(T), we first define a classical energy function h(z 1,z 2, … , zn ) that is a sum of energy functionshC (zi ,zj , zk ) wherei, j, and k are the labels of the bits involved in clause C. It costs energy to violate clauseC:Embedded Image(6)Now letEmbedded Image(7)which for any bit assignment z 1,z 2, … , zn is equal to the number of clauses that the assignment violates. We turn this classical energy function into a quantum operator, diagonal in thez-basis:Embedded Image Embedded Image(8)This means that the ground state ofHP corresponds to the bit assignment that violates the minimal number of clauses. (If more than one assignment minimizes the number of violations, then there will be more than one ground state of HP .) The problem of Exact Cover is to determine whether a given instance (specified by a set of clauses) has an assignment that violates no clauses. If we can produce the ground state of HP , we can solve the computational problem.

At time T, we measure the state |ψ(T)〉 in the basis of (Eq. 3). This will produce a stringz 1, z 2, … ,zn of 0's and 1's. This string can be quickly checked to see whether it satisfies all of the clauses. Note that if we run the quantum algorithm again [with the same instance, starting state |ψ(0)〉 and running time T] we end up in the same quantum state |ψ(T)〉. The probability of obtaining a satisfying assignment depends only on |ψ(T)〉.

The adiabatic theorem ensures that the quantum adiabatic evolution algorithm will produce the desired state that encodes the solution to the instance of Exact Cover if the running time T is long enough. Determining how long is long enough to produce a reasonably large success probability is the key to determining the potential usefulness of the algorithm. For certain specialized examples, we know that the required running time grows only as a polynomial in the number of bits (3). But addressing the general case of all instances of Exact Cover is beyond our analytical abilities. Here we report on a numerical study of the running time needed to solve a randomly generated set of Exact Cover instances.

To simulate the quantum computer, we numerically integrate the Schrödinger equation (Eq. 1). For an n-qubit quantum system, the state vector |ψ(t)〉 has 2n complex components. For n = 20, this means numerically integrating a differential equation with 2,097,152 real variables. This is as large a system as we could handle with our computer resources in a few months of running.

Because the number of bits in our instances of Exact Cover is never more than 20, we can always determine whether the instance has satisfying assignments and what they are. We do this by exhaustively checking all of the bit assignments, which takes virtually no time on a classical computer. The present report concerns randomly generated instances of Exact Cover with a unique satisfying assignment (USA) because we believe that these are the most difficult for the quantum algorithm. We have evidence that the quantum algorithm runs faster on instances with more than one satisfying assignment (8). We also have evidence that the quantum algorithm works well on instances with no satisfying assignment, in which case the algorithm produces an assignment that violates the minimal number of clauses. Thus, the restriction to a USA appears to restrict us to the most difficult cases for the quantum algorithm.

With the number of bits fixed to be n, we generate USA instances of Exact Cover as follows. We pick three distinct bits at random, uniformly over the integers from 1 to n. We then have a formula with one Exact Cover clause. We add clauses one at a time by picking new sets of three bits. After each clause is added we calculate the number of satisfying assignments, which always decreases (or stays the same). If the number of satisfying assignments is reduced to just 1, we stop and accept the instance. If the number of satisfying assignments drops from more than 1 to 0 without hitting 1, we reject the instance and start again. With this procedure, the number of clauses is not a fixed function of the number of bits, but rather varies from instance to instance. These instances, on average, have about as many clauses as bits.

By the adiabatic theorem, the probability of finding the satisfying assignment approaches 1 as the running time approaches infinity. We are, of course, forced to settle for a finite running time and a probability less than 1. We have (somewhat arbitrarily) picked a success probability of 1/8, which, for n ≥ 10, is much larger than 1/2n, the probability that a random bit assignment is the satisfying assignment. For each number of bitsn between 10 and 20, we generated 75 USA instances of Exact Cover. For each value of n, we determined the median time required to achieve a success probability of 1/8. (Because this is a numerical study, we actually hunted for a time that gives a probability between 0.12 and 0.13.)

In Fig. 1, the circles represent the median time to achieve probability 1/8 for 10 ≤n ≤ 20. The error bars give 95% confidence limits on the medians. The solid line is a quadratic fit to the data. In (5) we obtained corresponding data for 7 ≤n ≤ 15, and the dashed line is the quadratic fit to those data. The limited power of classical computers makes it impractical to go even a few bits beyond 20, so further numerical study will not decisively determine how the median running time grows with the number of bits. However, it is possible that the data up to 20 bits already reveal the asymptotic performance of the algorithm.

Figure 1

Each circle is the median time to achieve a success probability of 1/8 for 75 USA instances. The error bars give 95% confidence limits for each median. The solid line is a quadratic fit to the data. The broken line, which lies just below the solid line, is the quadratic fit obtained in (5) for an independent data set up to 15 bits.

To specify the algorithm, we want a running time, set in advance, that depends only on the number of bits and not on the instance being considered. We propose running the quantum algorithm for a timeT = T(n) that is equal to the quadratic fit to the median time required to achieve probability 1/8, the solid curve shown in Fig. 1. To test the algorithm at the proposed running time, we generated 100 new USA instances of Exact Cover, at each value of n between 10 and 20, and ran the simulation on each instance with T = T(n). InFig. 2, the circles show the median probability of success at each n. Not surprisingly, these are close to 1/8. We also show the 10th-worst and worst probability for each n. The good news for the quantum algorithm is that these do not appear to decrease appreciably with n.

Figure 2

(left). Each circle is the median probability of success for 100 USA instances with the algorithm run at the solid-line quadratic fit shown in Fig. 1. Each triangle is the 10th-lowest probability, and each x is the lowest probability. Note that the lowest probabilities do not decrease much as the number of bits nincreases.

We also generated 1000 new USA instances of Exact Cover at both 16 and 17 bits. Figure 3 shows the histograms of the success probability when the instances are run at T(16) and T(17), respectively. The histograms indicate that a USA instance with a success probability below 0.04 is very unlikely to be generated.

Figure 3

(right).Histograms of success probability for 1000 USA instances at 16 bits and another 1000 instances at 17 bits. The running times are given by the solid-line quadratic fit in Fig. 1 at n = 16 andn = 17.

If an algorithm (classical or quantum) succeeds with probability at least p, then running the algorithm k times gives a success probability of at least 1 − (1 −p)k. For example, ifp = 0.04, then 200 repetitions of the algorithm gives a success probability of better than 0.9997. Suppose that as the number of bits increases, it remains true that almost all USA instances (generated as described above) have a success probability of at least 0.04 at the quadratic running time T(n). Then anyn-independent desired probability of success can be achieved with a fixed number of repetitions.

If the behavior we have seen up to 20 bits persists for all values ofn, then we have identified a set of instances on which the adiabatic algorithm performs well. There is also evidence that this set is hard for classical algorithms. Most of the instances we have generated lie near the “phase transition” for Exact Cover. The phase transition region consists of instances with the number of clauses chosen so that half of the instances have one or more satisfying assignments. For 3-SAT, an NP-complete problem closely related to Exact Cover, there is evidence that the hard instances for classical algorithms are located at the phase transition (7).

In previous work (3), quantum adiabatic evolution was studied analytically on certain sequences of instances of Satisfiability where the clauses involve at most two bits. Each of these sequences has enough structure to make it possible to determine the required running time for any number of bits. For each case considered, the quantum adiabatic algorithm succeeds in a time that grows only polynomially in the number of bits. Of course, the structure of those instances makes it possible to determine the satisfying assignment by inspection, so these instances are certainly easy for some classical algorithms.

In (3) and (5) the quantum adiabatic algorithm was also applied to the problem of unstructured search (9). This problem can be cast as a restricted form of Satisfiability where each instance has a single clause that involves all of the bits and determines a USA. In this case the required running time is provably exponential in the number of bits even in the quantum case (10). This exponential behavior is indeed clearly seen in the data out to 14 bits in the numerical simulation of quantum adiabatic evolution presented in (5).

We have also been looking for a structured sequence of instances of Exact Cover that may be difficult for the quantum adiabatic algorithm. We have a candidate sequence where the success probabilities drop sharply as a function of the number of bits when the algorithm is run at the quadratic fit shown in Fig. 1. We have experimented with ad hoc modifications of the quantum algorithm that increase the success probability for this sequence. In any case, sequences of structured instances have little bearing on the performance of the quantum algorithm on randomly generated sets, but are relevant to discussions of whether this algorithm (or a modified version) could solve an NP-complete problem outright.

The quantum adiabatic evolution algorithm operates in continuous time by evolving a quantum state according to the Schrödinger equation (Eq. 1). In the conventional quantum computing paradigm, an algorithm consists of a sequence of discrete unitary transformations. Although the adiabatic time evolution can be well approximated by a sequence of discrete unitary steps (3), we see no advantage in this reformulation. In fact, continuous time evolution may offer an alternative model for the design of a quantum computer.

Quantum computation by adiabatic evolution works by keeping the quantum state close to the instantaneous ground state of the Hamiltonian that governs the evolution. This suggests that a device running the quantum adiabatic algorithm should be kept at a low temperature to reduce unwanted transitions out of the ground state. Conventional quantum computing does not take place in the ground state, and decohering transitions caused by interactions with the environment are a major impediment to current efforts to build a large-scale quantum computer. The quantum adiabatic algorithm running on a cold device may be more fault tolerant than the implementations of discrete-step quantum computation usually envisioned.

Quantum computation by adiabatic evolution applied to a wide variety of combinatorial search problems [see, for example, (11)] will succeed if the running time is long enough. We have seen evidence that for our randomly generated small instances of Exact Cover, the required running time grows slowly as a function of the number of bits. It is possible that the slow growth we have already seen indicates the true asymptotic behavior of the algorithm when applied to randomly generated hard instances of Exact Cover. If this quantum adiabatic algorithm does actually outperform known classical algorithms, we would have reason to eagerly await the construction of a quantum computer capable of running it.

  • * To whom correspondence should be addressed. E-mail: farhi{at}mit.edu

REFERENCES AND NOTES

View Abstract

Navigate This Article