## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Anderson localization makes adiabatic quantum optimization fail

Edited by Bertrand I. Halperin, Harvard University, Cambridge, MA, and approved April 30, 2010 (received for review March 2, 2010)

## Abstract

Understanding NP-complete problems is a central topic in computer science (NP stands for nondeterministic polynomial time). This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer’s Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. This implies that unfortunately, adiabatic quantum optimization fails: The system gets trapped in one of the numerous local minima.

One of the central concepts in computational complexity theory is that of NP (nondeterministic polynomial time) completeness (1). A computational problem belongs to the class NP if its solution can be verified in a time at most polynomial in the input size *N*; i.e., the verification requires not more than *cN*^{k} computational steps, where *c* and *k* are independent of *N*. An NP-complete problem satisfies a second criterion: Any other problem in the class NP can be reduced to it in polynomial time. Remarkably, such problems exist, many of them being of a great practical importance. The question of whether NP-complete problems are “easy to solve,” or in other words whether they may be solved in polynomial time, is one of the most fundamental open problems in computer science: This is the famous “” question (2). It is commonly believed, however, that it is not the case, i.e., that solving such a problem requires a computational time that is exponential in *N*.

## Adiabatic Quantum Optimization

The discovery of an efficient (polynomial time) quantum algorithm for the factorization of large numbers—a problem in NP but not believed to be NP complete—is a milestone in quantum computing (3), as no algorithm is known to solve this problem efficiently on a classical (nonquantum) computer. However, this success was not extended to NP-complete problems. That was why the proposal of Farhi et al. (4) to use adiabatic quantum optimization (AQO) to solve NP-complete problems has attracted much attention since initial numerical simulations suggested such a possibility (5).

The basic idea of AQO is as follows: Suppose that the solution of a computational problem *P* can be encoded in the ground state (GS) of a Hamiltonian . To implement AQO one needs to construct a physical quantum system that is governed by a Hamiltonian , where *s* is a tunable parameter, and is a Hamiltonian with a known and easy-to-prepare ground state. The idea is to start with *s* = 0, initialize the system in the ground state of , and increase *s* with time as *s* = *t*/*T*. According to the adiabatic theorem (6), slow enough variation of the parameter *s* = *s*(*t*) keeps the system in the ground state of the Hamiltonian at any time *t*. Therefore, if *T* is large enough, at *t* = *T* the system would find itself in the ground state of , and the problem would be solved. This model has since been shown to be equivalent to the standard (circuit) model of quantum computing (7). Of course, as long as the computational time *T* remains finite, there is a nonzero probability that the system would undergo a Landau–Zener transition (6) and end up in an excited state. In order to maintain the excitation probability less than *ϵ*, the adiabatic condition requires that , where Δ(*s*) = *E*_{ES} - *E*_{GS} is the energy gap between the ground state and first excited state (ES) of the Hamiltonian . Therefore AQO is not efficient when Δ is small. More precisely, the adiabatic quantum approach to NP-complete problems would beat known classical algorithms (which require exponential time) if the minimal value of the gap scales as an inverse power of the problem size *N*.

Previously, it was shown that the gap can become exponentially small under specific conditions, such as a bad choice of initial Hamiltonian (8, 9), or for specifically designed hard instances (10, 11). More recently, it was argued that the presence of a first-order phase transition could induce an exponentially small gap, and this effect was demonstrated for a particular instance of an NP-hard problem (12). While these examples show that small gaps can occur for *specific* instances of NP-complete problems, one could hope that this is not the typical behavior; i.e., for randomly generated instances the gap could be small only with very low probability. This hope followed from numerical simulations (5, 13, 14) where the minimum gap seemed to decrease only polynomially for small instances, up to *N* = 124 for the latest simulations (15). In this paper we show that this scaling does not persist for larger *N*. It turns out that as *N* → ∞, the typical value of the minimal gap for random instances decays even faster than exponentially. As a result, the probability for AQO to yield a wrong solution in this limit tends to unity. Note that in refs. 16 and 17, the quantum cavity method and replica symmetry breaking were used to show that a first-order phase transition between a quantum paramagnet phase and a spin glass phase may occur for some problems during the adiabatic evolution, leading to an exponentially small gap. While this also implies the failure of adiabatic quantum optimization for these problems, the small gap predicted by these methods, which are quite different from ours, is also due to a very different phenomenon. Here, we show that exponentially small gaps appear due to avoided crossings between levels corresponding to local and global minima, similar to ref. 12. We show here that this effect is not just an accident occurring for specific instances, but that it is generic for random instances of NP-complete problems. This effect was also studied for randomly generated *planted* instances of 3-satisfiability (3-SAT), by use of quantum Monte Carlo simulations (18). One important difference of our approach is to show the relevance of Anderson localization to the study of adiabatic quantum optimization.

## Anderson Localization

The appearance of exponentially small spectral gaps can be naturally attributed to the Anderson localization (AL) of the eigenfunctions of in the space of the solutions. Originally, AL implied that the wave function of a quantum particle in *d*-dimensional space (*d* = 1,2,3,…) subject to a strong enough disorder potential turns out to be spatially localized in a small region and decays exponentially as a function of the distance from this region. Accordingly the probability for the particle to penetrate through a large disordered region is suppressed exponentially.

Recall that the gap Δ cannot vanish at any *s* without a special symmetry reason. This is the famous Wigner-von Neumann noncrossing rule (19): The curves that describe the *s* dependence of two eigenenergies do not cross on the (*E*,*s*) plane. This so-called level repulsion follows from the consideration of a reduced 2 × 2 Hamiltonian that describes two anomalously close energy states and neglects the rest of the spectrum. Let *E*_{1} and *E*_{2} be the diagonal matrix elements of the Hamiltonian, and be its off-diagonal matrix elements. We then find the energy gap to be [1]Now suppose that *E*_{1}(*s*) and *E*_{2}(*s*) become equal at *s* = *s*_{c}, as depicted in Fig. 1. One can see that Δ > 0 even for *s* = *s*_{c}. This behavior is known as a level anticrossing. The minimal value of the energy gap is determined by the off-diagonal matrix element, i.e., Δ_{min} = |*V*_{12}|, which is exponentially small under AL conditions. Accordingly the energy level repulsion between the localized states should be exponentially small in the spatial distance. Fig. 1 illustrates this situation schematically. At a certain interval of *s* close to *s*_{c} the difference *E*_{1}(*s*) - *E*_{2}(*s*) is smaller or of the order of the tunneling matrix element *V*_{12}. It is the interval where the anticrossing takes place. Since *V*_{12} depends exponentially on the distance between the wells, both the width of the anticrossing interval and the minimum gap turn out to be exponentially small.

The concept of AL was introduced more than 50 years ago in order to describe spin and charge transport in disordered solids (20). Since then AL was found to be relevant for a variety of physical situations. It also turned out to exist and make physical sense in a much broader class of spaces than . Below we demonstrate that a phenomenon analogous to AL on the vertices of the *N*-dimensional cube naturally appears in connection with AQO.

## Exact Cover 3

In order to explain the connection between the AQO approach to NP-complete problems and Anderson localization, we pick a particular NP-complete problem known as Exact Cover 3 (EC3), the same problem that was used for the early numerical simulations of AQO (5). However, we believe that this analysis can be extended to any NP-complete problem. EC3 can be formalized in the following way. Consider *N* bits *x*_{1},*x*_{2},…,*x*_{N}, which take values 0 or 1. An instance of EC3 consists of *M* triplets of bit indices (*i*_{c},*j*_{c},*k*_{c}) (the clauses), where each clause is said to be satisfied if and only if one of the corresponding bits is 1 and the other two are 0. A solution of a particular instance of EC3 is an assignment of the bits **x** = (*x*_{1},*x*_{2},…,*x*_{N}), which satisfies all of the clauses. This problem can be assigned a cost function given by [2]such that each solution has zero cost and all other assignments have a positive cost.

We consider a standard distribution of random instances, where an instance is built by picking the *M* clauses independently, each clause being obtained by picking 3 bit indices uniformly at random. The hardness of such random instances is characterized by the clauses-to-variables ratio *α* = *M*/*N*. There are two characteristic values of *α*: the clustering threshold *α*_{cl} and the satisfiability threshold *α*_{s} (21). For *α* < *α*_{cl}, the density of the solutions is high and essentially uniform, while for *α* > *α*_{cl} the solutions become clustered in the solution space with different clusters remote from each other (the distance between two assignments is the so-called Hamming distance, which is defined as the number of bits in which they differ). As *α* increases from *α*_{cl} to *α*_{s}, the clusters become smaller and the distance between them increases. For *α* > *α*_{s}, the probability that the problem is satisfiable vanishes in the limit *N*,*M* → ∞. It has been shown (22) that *α*_{s} ≈ 0.6263. We will be interested in instances with *α* close to *α*_{s}, which accept only a few isolated solutions and are therefore hard to solve. More precisely, known classical algorithms cannot solve such hard instances for a number of bits *N* more than a few thousands, so that this is the regime where an efficient quantum algorithm would be particularly desirable.

## Methods and Results

### Adiabatic Quantum Algorithm.

In order to define an adiabatic quantum algorithm for EC3, we need to choose and . The problem Hamiltonian for an EC3 instance can be obtained from the above cost function by first replacing *x*_{i} by the Ising variables and then substituting by the Pauli *Z* operators , thus replacing the bits by qubits. The problem Hamiltonian becomes [3]where *B*_{i} is the number of clauses that involve the bit *i*, *J*_{ij} is the number of clauses where the bits *i* and *j* participate together, and is the identity operator. For , we make the conventional choice , which corresponds to spins in the magnetic field directed along the *x* axis (Pauli *X* operators). For us it will also be convenient to modify the Hamiltonian as . The parameter changes adiabatically from *λ* = +∞ at the beginning *t* = 0 to *λ* = 0 at *t* = *T*.

### Connection to Anderson Localization.

We can now see the relevance of AL to the quantum system described by . Note that this Hamiltonian also describes a single quantum particle that is moving between the vertices of an *N*-dimensional hypercube. Indeed, each vector , where , determines a vertex of the hypercube, which is body-centered at the origin of the *N*-dimensional space. Let |** σ**〉 denote the quantum state of a particle localized at a site

**. The full set of these states forms a basis, in which the first term of the Hamiltonian is diagonal. Since the operator transforms the state |**

*σ***〉 into its nearest neighbor in the**

*σ**i*th direction, the second term of describes a hopping of this fictitious particle between the nearest neighbors (n.n.) [4]Each on-site energy

*E*

_{P}(

**) is nothing but the cost function**

*σ**f*(

**x**) of the corresponding assignment

**. For random instances, the on-site energies are obviously also random, introducing disorder in the Hamiltonian. Hence, Eq.**

*σ***4**describes the well-known Anderson model, which was used to demonstrate the phenomenon of localization (20). The only difference from more familiar situations is that lattices in

*d*-dimensional space, which have

*L*

^{d}sites where

*L*≫1 is the system size, are substituted by the

*N*-dimensional hypercube with 2

^{N}sites, where

*N*≫1.

### Anticrossings in AQO.

Now we are ready to discuss the fundamental difficulties that AQO faces. We will show that (*i*) the anticrossings of the ground state with the first excited state happen with high probability and (*ii*) that the anticrossing gaps in the limit *N* → ∞ are even less than exponentially small.

Let us start with the first statement. An EC3 instance with *α* < *α*_{s} typically has several solutions ** σ** with

*E*

_{P}(

**) = 0. If**

*σ**α*is close to

*α*

_{s}, there are few solutions at a distance of order

*N*of each other. The presence of multiple solutions implies that the ground state of is degenerate. Note that this degeneracy does not contradict the noncrossing rule: The symmetry is manifested by the commutation of with each of the operators . The second term in Eq.

**4**violates this symmetry, so that the degeneracy is raised at

*λ*> 0.

Consider now a particular instance with *M* - 1 clauses accepting two solutions *σ*_{1} and *σ*_{2} that are separated by *n* ∼ *N* spin flips. When *λ* adiabatically changes from zero to a small but finite value, the solutions evolve into eigenstates of the Hamiltonian, |Ψ_{1},*λ*〉 and |Ψ_{2},*λ*〉 with the energies *E*_{1}(*λ*) and *E*_{2}(*λ*). According to the noncrossing rule, a degeneracy of these two states at a finite *λ* is improbable; i.e., the term in splits the ground state degeneracy. This situation is sketched in Fig. 2*A*. Suppose that *E*_{2}(*λ*) < *E*_{1}(*λ*); i.e. |Ψ_{2},*λ*〉 is the unique ground state of the Hamiltonian . If we now add one more clause to the existing *M* - 1 ones, i.e., we add a term (*x*_{iM} + *x*_{jM} + *x*_{kM} - 1)^{2} to the cost function leading to Hamiltonian , both |*σ*_{1}〉 and |*σ*_{2}〉 remain eigenstates, but their eigenenergy can increase by either 1 or 4. With a nonzero probability the last clause is satisfied by *σ*_{1} but not by *σ*_{2}, i.e., while , where is the cost function of the new instance. Accordingly |*σ*_{1}〉 rather than |*σ*_{2}〉 is the new ground state at *λ* = 0. At the same time |Ψ_{2},*λ*〉 can still remain the ground state at large enough *λ* if , as shown on Fig. 2*B*. Such a situation corresponds to the anticrossing of |Ψ_{1},*λ*〉 and |Ψ_{2},*λ*〉 at certain *λ*, as previously described in Fig. 1. Note that the addition of a clause to the cost function increases any eigenenergy of by less than 4. To satisfy the condition , it is thus sufficient to achieve a large enough splitting between the eigenvalues of the instance with *M* - 1 clauses: *E*_{1}(*λ*) - *E*_{2}(*λ*) > 4. It turns out that if *N*≫1, this happens when *λ* is small and one can use perturbation theory in *λ*.

### Perturbation Theory.

Let us consider the eigenstate that in the limit *λ* → 0 evolves to |** σ**〉. At small

*λ*its energy can be expanded in a series [5]We can show that each term in this sum scales linearly in

*N*. For the energy

*E*

_{P}(

**) of an arbitrary assignment, we immediately have that 0 ≤**

*σ**E*

_{P}<

*M*=

*αN*. As for the coefficients

*F*

^{(m)}(

**), the cluster expansion (23) of the Hamiltonian implies that they may be expressed as a sum of ∼**

*σ**N*statistically independent terms, each being of order 1. The key element to prove this is that since

*M*/

*N*=

*α*is constant, with overwhelming probability each bit participates in a finite number of clauses as

*N*→ ∞. As a result, all the coefficients

*B*

_{i}and

*J*

_{ij}in Eq.

**3**are also finite*: . In particular, when

**is a solution we obtain , which is therefore of order**

*σ**N*. This statement is valid for

*F*

^{(m)}(

**) with arbitrary finite**

*σ**m*> 1: All of these coefficients can be presented as a sum of

*O*(

*N*) random terms, each one being of order unity. Let us now consider the perturbative expansion for the energy splitting between two solutions. Similarly to Eq.

**5**, we obtain [6]where is a sum of

*O*(

*N*) terms of order 1. Each of the terms is random with a zero mean, and hence the sums average to zero as

*N*→ ∞. Therefore, it is rather than that is proportional to

*N*. We thus arrive at the conclusion that [7]where the coefficients

*f*

^{(m)}=

*O*(1) can be evaluated by the cluster expansion (23). We have seen that for any solution

**, so that . However, terms with**

*σ**m*> 1 do not vanish, making the splitting finite. In Fig. 3, we show the results of the statistical analysis of the numerical calculations of the coefficients and , with linear fits confirming their scaling

*O*(

*N*). For small

*λ*, we can restrict ourselves to the leading term (

*m*= 2) in Eq.

**7**. Accordingly in the

*N*→ ∞ limit, the splitting |

*E*

_{1}(

*λ*) -

*E*

_{2}(

*λ*)| exceeds 4 as long as

*λ*>

*λ*

_{*}, with [8]and

*λ*

_{*}≪ 1 so that we can neglect higher orders,

*λ*

_{∗}≪ 1 (the validity of this approximation is discussed in the next paragraph). From Eq.

**8**, it follows that the anticrossing probability for the instance with

*M*clauses is finite provided that

*λ*≥

*λ*

_{*}∼

*N*

^{-1/8}.

How big is the gap Δ of such an anticrossing? As explained above, we can evaluate the gap by considering the matrix element *V*_{12} between the states |Ψ_{1},*λ*〉 and |Ψ_{2},*λ*〉 corresponding to the two assignments, at the value *λ* where the anticrossing occurs. Note that if the two assignments *σ*_{1} and *σ*_{2} satisfying the (*M* - 1) clauses are separated by a distance (number of flips) *n*, this matrix element appears only at the *n*th order of the perturbation theory; i.e., it is proportional to *λ*^{n}: [9]where the sum is over all “trajectories” tr—all possible orders of the *n* spin flips needed to transform *σ*_{1} into *σ*_{2}, is the assignment along a particular trajectory that appears after *k* flips, and is the cost function of this assignment. Therefore, we can estimate the matrix element and thus the anticrossing gap as *V*_{12} < *w*(*n*)*λ*^{n}. The prefactor *w*(*n*) reflects the fact that many (∼*n* !) trajectories contribute to the sum in Eq. **9**. For a typical trajectory for *k* < *n*/2 and for *k* > *n*/2. As a result the product of in Eq. **9** is also ∼*n* !. The factorials thus cancel each other, and *w*(*n*) cannot increase faster than *A*^{n} with some constant *A* ∼ 1. Therefore, *V*_{12} < (*Aλ*)^{n}. Combining this with Eq. **8**, we see that an anticrossing at *λ* close to *λ*_{∗} yields the minimum gap as small as Δ_{min} ∼ exp[-(*n*/8) ln(*N*/*N*_{0})], where *N*_{0} = 16*A*^{8}(*f*^{(2)})^{-2} = *O*(1). Within the clustering phase (*α*_{cl} < *α* < *α*_{s}), the expected distance *n* between solutions scales as *v*(*α*)*N*, where *v*(*α*) is a constant that depends only on the clauses-to-variable ratio *α*. Therefore, we obtain the final form of the minimal gap estimation [10]One can see that as *N* → ∞, the gap indeed decreases even faster than an exponential—statement (*ii*). This implies that the adiabatic computation time exceeds exp(*N*). In Fig. 4, we have plotted an anticrossing for a particular instance with *N* = 200 generated during our numerical simulations. The figure shows two energy levels (estimated by fourth-order perturbation theory) corresponding to assignments separated by 60 bit flips, and crossing at *λ* ≈ 0.51.

## Discussion

### Applicability of the Perturbation Theory.

Our main result, the estimation of the minimal gap (**10**), is based on the perturbative expansion for the energies (Eq. **5**) and the matrix element *V*_{12} (Eq. **9**). Is the perturbation theory in *λ* always applicable? At first sight Eq. **9** becomes meaningless if *E*_{P} = 0 for any of the intermediate assignments . In this case there is an avoided crossing between the states corresponding to the assignments *σ*_{1} and (such as in Eq. **1**), and formally perturbation theory fails in the vicinity of this anticrossing point. This apparent difficulty can be overcome by considering only a finite time *T* for the evolution. This is equivalent to adding imaginary parts *iη* ≈ *i*/*T* to the energies. For the AQO algorithm, it is the computation time *T* that determines *η*. In the limit *N* → ∞, we have that *T* → ∞ and thus *η* → 0. This is the limit that was shown to be relevant for the localization problem (20, 24). The celebrated discovery of Anderson was that if the limit *η* → 0 is taken after the volume (here *N*) tends to infinity, and *λ* is small enough i.e., *λ* < *λ*_{cr}, the spectrum of the Hamiltonian described in Eq. **4** remains discrete (all states are localized) and thus the second term in Eq. **4** (the kinetic energy term) can be treated perturbatively. As soon as *λ* > *λ*_{cr}, there appears a strip of extended states in the middle of the energy band that widens as *λ* increases further. States within this strip are not perturbative because the number of the trajectories connecting two points in a *d*-dimensional space (for finite *d*) increases exponentially with distance. The large number of terms in the expansions such as Eq. **9** overwhelms the smallness of *λ*^{n}, and the perturbation series thus diverges for *λ* > *λ*_{cr}. For a *d*-dimensional space, the critical value *λ*_{cr} is believed to be (in our units) of the order of *λ*_{cr} ∼ 1/ log *d* (25, 26). We have seen that the AQO algorithm for problems such as EC3 can be mapped to the Anderson model on an *N*-dimensional hypercube. Then, the number of trajectories increases with the length *n* as *n* ! ∼ *n*^{n}*e*^{-n}, i.e., even faster than an exponential. However, as we already mentioned, the *n*^{n} factor cancels with the same factor in the products of the energy in the denominators of Eq. **9**. Accordingly, *λ*_{cr} can still be estimated as *λ*_{cr} ∼ 1/ log *N*, which, together with Eq. **8**, implies that anticrossings appear for *λ*_{∗} ≪ *λ*_{cr} when *N*≫1. Moreover, at *λ* < *λ*_{cr} all of the states are supposed to be localized. The AQO algorithm involves only low-energy states, which remain localized much longer than the middle-band states with the energies ∼*N*. Therefore, it is quite likely that the exponentially small gaps appear even at *λ* ∼ 1.

## Conclusions

We finish our discussion with the following observation. We monitored two assignments that satisfied *M* - 1 clauses and added an extra clause to create a small gap at finite *λ*. Of course, for randomly selected clauses this happens only with a finite probability, and the situation sketched in the inset in Fig. 2*A* is also possible. One could thus hope (18) that the AQO algorithm can find the solution with a sizable probability. Unfortunately, the situation is not so optimistic when we take into account all low-energy states. Indeed, let us adopt the most conservative limitation on the perturbative approach *λ*_{cr} ∼ 1/ log *N* and consider the spectrum at *λ*_{∗} ≪ *λ*_{cr} ∼ 1/ log *N*. According to Eq. **7**, all states in the energy interval [0,*ϵ*] with have similar chances to evolve into the ground state at *λ* = 0. This means that typically the ground state undergoes *ν*(*ϵ*) anticrossings [participates in *ν*(*ϵ*) anticrossing gaps] as the parameter evolves from 0 to *λ* (see the inset of Fig. 2*B*). Here *ν*(*ϵ*) is the number of states, whose energies at the given *λ* differ from the ground state energy by less than *ϵ*. Taking into account that *ν*(*ϵ*) increases with *ϵ* exponentially and that the probability to completely avoid anticrossings (the probability to have a gap of size *ϵ* separating the ground state from the rest of the spectrum) is exponentially small in *ν*(*ϵ*), we conclude that this probability is indeed negligible. Therefore, these findings suggest that there is no chance of obtaining the solution of the problem in polynomial time using the AQO algorithm for random instances of the Exact Cover 3 problem. We also believe that the methods described in this paper can be applied to other similar NP-complete problems, such as 3-SAT.

## Acknowledgments

We thank A. Childs, E. Farhi, J. Goldstone, S. Gutmann, M. Rötteler, and A. P. Young for interesting discussions. We thank the *High Availability Grid Storage* department of NEC Laboratories America for giving us access to their cloud to run our numerical simulations. This research was supported in part by US Department of Energy contract AC0206CH11357.

## Footnotes

^{1}To whom correspondence should be addressed. E-mail: bla{at}phys.columbia.edu.Author contributions: B.A., H.K., and J.R. designed research; B.A., H.K., and J.R. performed research; B.A., H.K., and J.R. analyzed data; and B.A., H.K., and J.R. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

↵

^{*}Throughout this article, we use the notation*O*(*f*(*N*)) to denote a function that scales as*f*(*N*) when*N*→ ∞, as is common in the physics literature. Note that this corresponds to the notation Θ(*f*(*N*)) in the mathematics and computer science literature.

## References

- ↵
- Garey MR,
- Johnson DS

- ↵
- Arora S,
- Barak B

- ↵
- ↵
- Farhi E,
- Goldstone J,
- Gutmann S,
- Sipser M

- ↵
- Farhi E,
- et al.

- ↵
- Messiah A

- ↵
- ↵
- ↵
- ↵
- Reichardt B

- ↵
- van Dam W,
- Mosca M,
- Vazirani U

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Jörg T,
- Krzakala F,
- Semerjian G,
- Zamponi F

- ↵
- Farhi E,
- et al.

- ↵
- von Neumann J,
- Wigner E

- ↵
- ↵
- ↵
- ↵
- Mayer GE,
- Goeppert-Mayer M

- ↵
- Anderson PW

- ↵
- Efetov K

- ↵

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Physics