9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of K

On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants

Daniel A. Lidar

Chemical Physics Theory Group, Chemistry Department, and Ce

nter for Quantum Information and Quantum Control, University of Toronto, 80 St. George St., Toronto, Ontario M5S 3H6, Canada It is shown that the canonical problem of classical statistical thermodynamics, the computation of the partition function, is in the case of ±J Ising spin glasses a particular instance of certain simple sums known as quadratically signed weight enumerators (QWGTs). On the other hand it is known that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating QWGTs. This suggests a connection between the partition function estimation problem for spin glasses and quantum computation. This connection extends to knots and graph theory via the equivalence of the Kau?man polynomial and the partition function for the Potts model. I. INTRODUCTION

arXiv:quant-ph/0309064v2 18 Aug 2004

Feynman famously conjectured that unlike classical computers, quantum computers should be e?cient at simulating quantum mechanics [1, 2]. This was veri?ed by Lloyd [3], and further developed by several other authors, who demonstrated exponential speedup over the best known classical algorithms for a variety of quantum mechanical problems such as solution of the constant potential Schr¨ odinger and Dirac equations using lattice gas automata [4, 5, 6, 7], solution of the Schr¨ odinger equation in the circuit model [8, 9, 10], simulation of fermionic systems [11, 12], computation of the thermal rate constant of chemical reactions [13], computation of correlation functions [14], simulation of topological ?eld theories [15], and simulation of pairing Hamiltonians such as the BCS model [16]. A naturally related question is whether quantum computers can e?ciently solve problems in classical physics. This question was ?rst raised, and partially answered, in the context of Ising spin glasses [17]. It has recently received renewed attention in the context of hydrodynamics [18, 19] (with polynomial speedups), chaos [20, 21, 22] (with exponential speedups, though some of these have been challenged [23]), and knot theory [24] (so far without speedup), which has a deep connection to classical statistical mechanics [25]. Here we revisit classical Ising spin glasses and also address knot theory. The canonical problem of classical statistical thermodynamics is the calculation of the partition function Z . For a system in thermodynamic equilibrium, if the partition function is known, one can obtain exact results for all thermodynamic quantities such as the magnetization, susceptibility and speci?c heat. Models for which analytical calculations of this type can be performed include a variety of one dimensional (1D) models and the 2D Ising model [26, 27]. However, for most systems of interest, including the 3D Ising model and most Ising spin glass models, no analytical calculation of the partition function is available [28]. We consider classical spin systems, in particular the Ising model [29] in which each spin has two states σi = ±1, and spins interact

pairwise with an interaction energy of the form Jij σi σj . From a computational complexity perspective this provides a rich class of problems. In particular, the problem of ?nding the ground state of the short range 3D Ising spin glass (quenched random Jij ), as well as the fully antiferromagnetic (all Jij = ?|J |) 2D Ising model in the presence of a constant magnetic ?eld was shown by Barahona to be NP-hard, by a mapping to problems in graph theory.1 On the other hand, it is known that there exists a fully polynomial randomized approximation scheme for the ferromagnetic Ising model (all Jij = |J |), on arbitrary graphs [30]. The problem of sampling from the Gibbs distribution of the Jij = ±J (with random signs) spin glass on a quantum computer was addressed in [17]. A linear-time algorithm was found for the construction of the Gibbs distribution of con?gurations in the Ising model, including partially frustrated models. A magnetic ?eld can be incorporated as well without increase in the run-time. The algorithm was designed so that each run provides one con?guration with a quantum probability equal to the corresponding thermodynamic weight. I.e., the probabilities of measuring states are ordered by the energies of the corresponding spin con?gurations, with the ground state having the highest probability. Therefore the partition function is approximated e?ciently and statistical averages needed for calculations of thermodynamic quantities obtained from the partition function, are approximated in the fastest converging order in the number of measurements. Unlike Monte Carlo simulations on a classical computer, consecutive measurements on a quantum computer can be totally uncorrelated. Thus the algorithm neither su?ers from critical slowing down (a polynomial slowdown in Monte Carlo moves associated with large correlated spin clusters forming near the

1

NP-hard problems are those whose proposed solution cannot even be veri?ed using a nondeterministic Turing machine in polynomial time; e.g., is the proposed ground state truly the ground state?

2 critical temperature) [31], nor gets stuck in local minima. This uniform performance is an advantage over the best known classical algorithms, which are tailored to speci?c lattices or graphs [31]. However, the main problem of the algorithm is the limited control it o?ers in the construction of a speci?c realization of bonds on the Ising lattice. Indeed, since the run-time of the algorithm is linear, it is reasonable to suspect that it cannot simulate a hard instance of an Ising spin glass. A completely di?erent approach to sampling from the Gibbs distribution for the ferromagnetic Ising model was recently developed by Nayak, Schulman and Vazirani (NSV) [32], which however does not appear to provide a speedup over the best known classical algorithm [33]. The VNS algorithm for the ferromagnetic Ising model uses an interesting representation of the partition function as a discrete Fourier transform, in conjunction with a Markov chain sampling procedure. Two of the main results of the present paper are (i) the generalization of this Fourier transform representation to the ±J spin glass case, (ii) (the central result) a connection of this representation to certain simple sums known as “quadratically signed weight enumerators” (QWGTs). Let us now motivate the importance of result (ii). In virtually all previous work on simulation of physical systems on quantum computers [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], the approach pursued was one of attempting to ?nd a concrete algorithm for a speci?c simulation problem. A fruitful alternative is to consider instead the question of the complexity class that the simulation problem belongs to. We do this here by following a lead due to the Knill and La?amme (KL): KL showed that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating QWGTs [34]. Combined with our results (i),(ii), this suggests that the quantum computational complexity of sampling from the Gibbs distribution for the Ising spin glass problem can be understood in terms of QWGTs. However, we have unfortunately not yet been able to establish the connection at this level. Nevertheless, the possibility of a (spin glass)-(QWGTs)-(quantum computation) connection is su?ciently tantalizing to point it out in detail. We hope that by expressing the partition function as a QWGT we have taken the ?rst step in a direction that will allow future research to explore the important question of the quantum computational complexity of the Ising spin glass problem. In fact, the connections do not end here. There is a rich inter-relation between classical statistical mechanics and topology, in particular the theory of classi?cation of knots. The ?rst such connection was established by Jones [35], who discovered knot invariants (the Jones’ polynomial) during his investigation of topological properties of braids [36]. It is known that classical evaluation of the Jones’ polynomial is #P-hard [37]. The connection between knots and models of classical statistical mechanics was greatly embellished by Kau?man [25]. Here we will exploit this connection to show [our main result (iii)] that the evaluation of another knot invariant, the Kau?man polynomial, can also be cast in some cases as a QWGT evaluation problem. Thus a quantum algorithm for QWGT evaluation should shed light on the quantum computational complexity of knot invariants, a subject which has been explored by Freedman et al. [38] and by Kau?man and Lomonaco [39]. Knot invariants are, in turn, also tightly related to graph theory; e.g., the graph coloring problem can be considered an instance of evaluation of the Kau?man polynomial, via the Tutte polynomial [25]. Mathematically, the reason that these seemingly unrelated subjects are all inter-related is due to the fact that key properties can be expressed, in all cases, in terms of certain polynomials. While these polynomials originate from widely distinct problems, from the point of view of computational complexity their evaluation is one and the same problem, much in the same spirit as the fact that solving one problem in the class of NP-complete problems solves them all [40]. The present work contributes to this uni?cation. The structure of this paper is as follows. In Sec. II we derive our ?rst main result: we rewrite the Ising spin glass partition function for an arbitrary graph as a discrete Fourier transform. This motivates the consideration of the partition function evaluation problem in terms of its computational complexity, which we formalize in Sec. III. We then review QWGTs in Sec. IV. In Section V we derive our second main result: the connection between the evaluation of the Ising spin glass partition function and QWGTs. In Sec. VI we continue the program of connecting disparate objects to the problem of QWGT evaluation, and obtain our third main result: we show that the Kau?man polynomial too can be expressed a QWGT. We do this after ?rst reviewing the connection between knots and classical statistical mechanics. Section VII concludes. Some further observations concerning the representation of the partition function are collected in Appendix A.

II. FOURIER TRANSFORM REPRESENTATION OF THE PARTITION FUNCTION

Let G = (E, V ) be a ?nite, arbitrary undirected graph with |E | edges and |V | vertices. Identify each vertex i ∈ V with a classical spin (σi = ±1) and each edge (i, j ) ∈ E with a bond (Jij = ±J ). Denote a given spin con?guration by σ = (σ1 , σ2 , ..., σ|V | ) and a bond con?guration by (J12 , ..., Jij , ...). We assume that the bond con?guration is chosen at random and then remains ?xed (“quenched randomness”). The Hamiltonian of the system is H (σ ) = ?

(i,j )∈E

Jij σi σj .

(1)

3 (We remark on the case with a magnetic ?eld in Appendix A 1.) The probability of the spin con?guration σ in thermal equilibrium at temperature T is given by the Gibbs distribution: 1 W (σ ), Z

FIG. 1: Illustration of subgraphs.

P (σ ) =

(2)

where the Boltzmann weight is W (σ ) = exp[?βH (σ )], (3)

β = 1/kT is the inverse temperature, and Z is the partition function: Z ({Jij }) =

σ

represents two unconnected bonds (Fig. 1a), whereas if j = k the same term represents two connected bonds sharing one spin (Fig. 1b). Let b ? E denote such a | subgraph, with k = |b| edges. There are ||E ways of b| choosing subgraphs with |b| edges. Thus the total number of subgraphs is:

|E |

exp[?βH (σ )].

(4) |E | |b| = 2 |E | . (12)

Now note the identity

|b|=0

ex = cosh(x)[1 + tanh(x)] and use it to rewrite the Boltzmann weight (3) as W (σ ) =

(i,j )∈E

(5)

cosh(βJij σi σj )[1 + tanh(βJij σi σj )]. (6)

Let Jij = qij J, (7)

where qij = ±1 is a quenched random variable. Since cosh(x) = cosh(?x) and tanh(x) = ? tanh(?x) we ?nd W (σ ) = Θ

(i,j )∈E

(1 + qij σi σj λ),

(8)

where Θ = [cosh(βJ )]|E | , and λ = tanh(βJ ). Next expand out the product to obtain P (σ ) = Θ[1 + λ

(i,j )∈E

(9)

This suggests to label the subgraphs in a binary fashion (to be explained below): Let b = (b1 , b2 , ..., b|E | ) (where bj ∈ {0, 1}) be the binary number of subgraph b. The numbering is such that bj = 1 (0) indicates the presence (absence) of edge number j of G. Further, we will use the convention that ?rst all |E | single-edge subgraphs are counted (i.e., vectors b with a single 1 en| try, all the rest 0), then all |E double-edge subgraphs 2 (vectors b with two 1 entries, all the rest 0), etc. Thus, e.g., b = (0, 0, ..., 0, 1) could corresponds to the subgraph containing only the ?rst edge (or bond): J12 , whereas b = (0, 0, ...0, 1, 0, 1) could correspond to the subgraph containing only J12 and J34 . Note that |b| is the Hamming weight of b. Since the total number of subgraphs is 2|E | , the above numbering scheme is a one-to-one covering of the subgraph space, and moreover, the subgraphs are labeled in increasing order of |b|. Next note that in Eq. (11), a spin σi may appear more than once in sums of order k ≥ 2, in fact as many times as the number of bonds emanating from σi , which we deg (i) denote by degb (i). Then σi b is the contribution of spin i in subgraph b to the product in the sum of order k = |b| in Eq. (11). Collecting all the observations above, it follows that Eq. (11) can be rewritten as: P (σ ) = Θ

b

(10)

λ|b|

i∈V (b)

σi

degb (i) (i,j )∈b

qij .

(13)

σi qij σj (σi qij σj )(σk qkl σl ) + ....](11)

+λ2

(i,j ),(k,l)∈E

Here V (b) denotes the set of vertices in subgraph b. b b Next introduce the parity vector αb = (αb 1 , α2 , ..., α|V | ) of a subgraph, with components αb i = 1 if (i ∈ V (b) and deg (i) degb (i) is odd), αb = 0 otherwise. Then clearly σi b = i σi i . At this point it is more convenient to transform to a binary representation for the spins as well. Let: si = 1 ? σi 2 (14)

αb

Note that λk is the coe?cient in front of a sum containing k bonds qij , which are not necessarily all connected. For example, the term qij σi σj qkl σk σl where all indexes di?er

4 be the components of the binary vector of spin values s = deg (i) (s1 , s2 , ..., s|V | ). We have σi = (?1)si so that σi b = b (?1)αi si . Therefore: σi

i∈V (b) degb (i)

so A is a |V | × |E | matrix of 0’s and 1’s. It is well known that given G and a speci?c subgraph b [41], αb = A · b. (22)

= (?1)α

b

·s

,

(15)

Combining Eqs. (9),(10),(19),(20),(22), we ?nally have: 2 |V | (1 ? λ2 )|E |/2 λ|b| (?1)b·w .

b: A·b=0

where “·” stands for the (mod 2) bit-wise scalar product. The same change can be a?ected for the bonds by introducing: 1 ? qij , 2

Z (w) =

(23)

wij =

(16)

so that the binary vector w = (w12 , w13 , ...) of length |E | speci?es whether edge (i, j ) supports a ferromagnetic (wij = 0) or antiferromagnetic (wij = 1) bond. Again, qij = (?1)wij , so that: qij = (?1)b·w .

(i,j )∈b

In words, the sum over the subgraphs includes only those with zero overall parity, i.e., those having an even number of bonds emanating from all spins. This immediately implies that “dangling-bond” subgraphs are not included in the sum. We note that Z (w) can also be rewritten as a power series in λ, which is useful for a high-temperature expansion; this is discussed in App. A 2. The representation (23) allows us to establish a direct connection with QWGTs, which is the subject of the quantum computational complexity of Z , to which we turn next.

III. FORMULATING THE COMPUTATIONAL COMPLEXITY OF THE ISING SPIN GLASS PARTITION FUNCTION

(17)

Using Eqs. (15),(17) in Eq. (13) it is now possible to rewrite the Boltzmann weight of a particular spin con?guration s as: W (s) = Θ

b

λ|b| (?1)α

b

·s+b·w

.

(18)

Now, the partition function is just the sum over all spin con?gurations. Using Eq. (18) we thus ?nd: Proposition 1 The spin-glass partition function is a double discrete Fourier (or Walsh-Hadamard) transform, over the spin and subgraph variables: Z (w) = Θ

s b

λ|b| (?1)α

b

·s+b·w

.

(19)

The most natural computational complexity class for quantum computation is BQP: the class of decision problems solvable in polynomial time using quantum resources (a quantum Turing machine, or, equivalently, a uniform family of polynomial-size quantum circuits) with bounder probability of error [42, 43]. The class BQPP is the natural generalization of BQP to promise problems [34]. Relative to the polynomial hierarchy of classical computation, it is known that BPP?BQP?PP?PSPACE, but none of these inclusions is known to beproper [44]. In order to address the quantum computational complexity of the spin glass partition function we de?ne: De?nition 1 An instance of the Ising spin glass problem is the data ? ≡ (G, w, λ). Now, let Z ? (s) be the partition function for given data ? and given spin con?guration s ∈ {0, 1}|V | , and let

? Zk (s) : {0, 1}N → {0, 1}

Note that the sum over s extends over 2|V | terms, while the sum over b extends over 2|E | terms. By changing the order of summation, the sum over s can actually be carried out, since: (?1)α

s

b

(24)

·s

= 2|V | δ(αb ,0) ,

(20)

where δ is the Kronecker symbol. A systematic procedure for ?nding the parity vectors from the subgraphs vectors uses the incidence matrix A. For any graph G = (E, V ) this matrix is de?ned as follows (v ∈ V ) [41]: 1 (v = i and (i, j ) ∈ E ) , 0 else

Av,(i,j ) =

(21)

be the k th digit of Z ? (s). Let Γ? (s, k ) be a quantum circuit that takes as input the spin con?guration s and the digit location k , for ?xed data ?. Let WΓ = i Ui be an implementation of Γ? in terms of some unitary operators Ui . Let the circuit be designed so that the answer ? Zk (s) is encoded into the state of the ?rst qubit, and let Π1 = |0 1 0| be the projection onto state |0 of this qubit. Then the probability of measuring the state |0 1 after the circuit was executed, starting from the “blank” initial ? state |0 = |0 · · · 0 , is Pr[Γ? (s, k )] = 0|WΓ Π1 WΓ |0 . We can now de?ne:

5

? De?nition 2 Zk (s) ∈ BQP if there exists a classical polynomial-time algorithm for specifying Γ? such that

V.

THE PARTITION FUNCTION - QWGT CONNECTION

Pr[Γ? (s, k )] ≥

2 ? if Zk (s) = 0 3 1 ? Pr[Γ? (s, k )] ≤ if Zk (s) = 1. 3

and

We are now ready to prove our central result. Theorem 2 The spin-glass partition function is a special case of QWGTs. Speci?cally: (1 ? λ2 )|E |/2 Z (w) = S (A, dg(w), λ, 1). 2 |V | (26)

We can then formulate the following open problem: Problem 1 For which instances ? of the Ising spin glass problem is evaluating the partition function in BQP? A particularly promising way to attack this problem appears to be the connection to QWGTs, which we address next.

IV. QUADRATICALLY SIGNED WEIGHT ENUMERATORS

Here dg(w) is the matrix formed by putting w on the diagonal and zeroes everywhere else, and A is the incidence matrix of G. Proof. In Eq. (25) identify b as the subgraphs of G = (E, V ), n = |V |, m = |E |, and note that when B = dg(w) bBb =

i

bi wi bi = b · w

Quadratically signed weight enumerators (QWGTs) were introduced by Knill and La?amme in Ref. [34] (where “QWGT” is pronounced “queue-widget”). A general QWGT is of the form S (A, B, x, y ) = (?1)bBb x|b| y n?|b|

b:Ab=0

since bi = 0 or 1. Then Eq. (26) follows by inspection of Eqs. (23) and (25). Corollary 1 Evaluating the spin glass partition function is in #P.2 Proof. The problem of evaluating QWGTs at integers is in the class #P [34].3 In our case x = 1, y = λ and the coupling constant J can always be chosen so that λ = tanh(βJ ) is integer. It is tempting to check the relation of Theorem 2 to the KL promise problem (Problem 2). It follows from Eq. (26), from Z > 0, and from 0 ≤ λ = tanh(βJ ) ≤ 1, that sign[S (A, dg(w), λ, 1)] = +. Hence, unfortunately, the KL problem in its present form is of no use to us. Further consideration reveals that, while the constraint that k and l are positive integers is easily satis?ed, and the promise takes a nice symmetric form: Z (w) ≥

λ ) 2|V |?1 (1+ , the remaining constraints – A square, (1?λ2 )|E |/2 diag(A) = I , B = ltr(A) – anyhow result in severely restricted instances of spin glass graphs. We thus leave as open the following problem, inspired by the KL problem:

2 |V |/2

(25)

where A and B are 0, 1-matrices with B of dimension n × n and A of dimension m × n. The variable b in the summand ranges over 0, 1-column vectors of dimension n, and all calculations involving A, B and b are done modulo 2. It should be noted that |S (A, B, x, y )| ≤ (|x| + |y |)n . In Ref. [34] it was shown that quantum computation is polynomially equivalent to classical probabilistic computation with an oracle for estimating the value of certain QWGTs with x and y rational numbers. In other words, if these sums could be evaluated, one could use them to generate the quantum statistics needed to simulate the desired quantum system. More speci?cally, let I be the identity matrix, diag(A) the diagonal matrix whose diagonal is the same as that of A, and ltr(A) a matrix formed from the lower triangular elements of A (the matrix obtained from A by setting to zero all the elements on or above the diagonal). Then for: Problem 2 KL promise problem: Determine the sign of S (A, ltr(A), k, l) with the restrictions of having A square, diag(A) = I , k and l being positive integers, and the promise |S (A, ltr(A), k, l)| ≥ (k 2 + l2 )n/2 /2. KL demonstrated the following: Theorem 1 (Corollary 12 in [34]): The KL promise problem is BQPP-complete. KL’s strategy in showing the connection between QWGT evaluation and quantum computation was to show that in general expectation values of quantum circuits can be written as QWGTs.

Problem 3 Formulate a promise problem in terms of Z (w) [or, equivalently, S (A, dg(w), λ, 1)] which is BQPP-complete. We turn next to showing the connection between our discussion so far and problems in knot theory.

2

3

#P is the class of function problems of the form “compute f (X )”, where f is the number of accepting paths of a nondeterministic polynomial-time Turing machine. The canonical #P-complete problem is #SAT: given a Boolean formula, compute how many satisfying assignments it has [40, 43]. It contains the problem of evaluating the weight enumerators of a binary linear code at rational numbers, which is #P-complete [45].

6 The Potts spin states si are connected to knot properties in an abstract manner; they are related to the Kau?man polynomial variable A, which in turn is a weight for the manner in which 2D-knot diagram is disassembled into a set of microstates (and also related to the Jones’ polynomial variable t: the Jones and Kau?man polynomials coincide when t = A1/4 ). Precise de?nitions can be found in [25]; for our purposes what matters is that the equivalence of the Kau?man polynomial to the Potts spin glass partition function is established once one assigns the Potts variables q and βJij the values q = (A2 + A?2 )2 , βJij = ln(?A?4bij ).

FIG. 2: De?nition of crossing variable for knots.

VI.

THE PARTITION FUNCTION - KNOTS CONNECTION

The canonical problem of knot theory is to determine whether two given knots are topologically equivalent. More precisely, in knot theory one seeks to construct a topological invariant which is independent of the knot shape, i.e., is invariant with respect to the Reidemeister moves [25]. This quest led to the discovery of a number of “knot polynomials” (e.g., the Jones and Kau?man polynomials) [25]. These also play a major role in graph theory as instances or relatives of the dichromatic and Tutte polynomials [46], e.g., in the graph coloring problem. Roughly, two knots are topologically equivalent i? they have the same knot polynomial. It is well known [25, 35] that there is a connection between knot polynomials and the partition function of the Potts spin glass model, a generalization of the Ising spin glass model to q ≥ 2 states per spin: HPotts (q, s) = ?

(i,j )∈E

(29)

Jij δsi ,sj ,

(27)

With these identi?cations Nechaev has shown that the Kau?man polynomial (knot invariant) K (A) = c(A, {bij })ZPotts (q, J ), where the constant c does not depend on the spin states [48]. Solving for A we ?nd A = ±[(q 1/2 ± (q ? 4)1/2 )/2]1/2 . Thus βJij can be real only for q ≥ 4. In the Ising spin glass case (q = 2) we obtain a complex-valued βJij , which in turn implies complex-valued λ = tanh(βJ ), and hence the estimation of the QWGT polynomial with complex-valued x. Finally, we note that a physically somewhat unsatisfactory aspect of the knots-Potts connection is that now the (complex-valued) temperature cannot be tuned independently from the bonds Jij . However, this does not matter from the computational complexity perspective: we have established our third main result: Proposition 2 Computing the Kau?man polynomial at q = 2 is equivalent to the problem of computing the QWGT polynomial with complex-valued x.4 Hence an e?cient quantum algorithm for estimating QWGTs will be decisive for knot and graph theory as well.

VII. CONCLUSIONS

where si ∈ {0, ..., q ? 1} and δsi ,sj = 1 (0) if si = sj (si = sj ). We ?rst brie?y review this connection. Consider a knot embedded in 3D-space (imagine, e.g., a piece of rope). In the standard treatment [25], the knot is projected onto the plane and one obtains a “2D-knot diagram”. The essential topological information about the knot is contained in the pattern of “crossings”, the 2D image of where one rope segment went over or under another rope segment. A crossing takes values bk = ±1 according to Fig. 2 [47]. A connection to spin glasses can be made by assigning quenched random values to the crossing variables bk , so that the links cross above and below at random. It was shown by Nechaev [48] that in this case the Kau?man polynomial is identical, up to an irrelevant multiplicative factor, to the Potts model partition function, ZPotts (q, {Jij }) = s exp[?βHPotts (q, s)]. To explain this connection we need to introduce some terminology. The 2D-knot diagram lives on a lattice M composed of lines oriented at ±45o , intersecting at the crossings bk , that carry the disorder. One can de?ne a dual lattice L, rotated by 45o , so that its horizontal and vertical edges (denoted bij ) are in one-to-one correspondence with the vertices bk of M (Fig. 6 in [48]). Let bij = ?bk if the (ij )-edge is vertical . bk if the (ij )-edge is horizontal (28)

The connection between QWGTs and quantum computational complexity established by KL on the one hand, and the connection between QWGTs and the spin glass and knots problems established here on the other hand, suggests that the quantum computational complexity of spin glass and knots problems may be decided via the connection to QWGTs. Similar remarks apply to a number of combinatorial problems in graph theory, via their well-established connections to knot theory. In particular, it would be desirable to ?nd out the quantum

4

This knots-QWGT connection does not appear to hold in the case q > 2, since in this case we cannot separate δsi ,sj into a product of single-spin variables, a step that is essential in deriving the representation of Z as a QWGT [see text around Eq. (13)].

7 computational complexity of questions framed in terms of properties of S (A, dg(w), λ, 1), with λ real (Ising spin glass) or complex (Kau?man polynomial with q = 2). We leave these as open problems for future research.

Acknowledgments 2. Power Series Representation

The author thanks the Sloan Foundation for a Research Fellowship and Joseph Geraci, Louis Kau?man, Emanuel Knill, Ashwin Nayak, and Umesh Vazirani for useful discussions.

APPENDIX A: ADDITIONAL OBSERVATIONS 1. The case with a Magnetic Field

Another useful representation of Eq. (23) can be obtained by grouping together all subgraphs with the same (k ) number of edges. To this end, let bj denote the j th subgraph with k edges. According to the numbering scheme introduced in Sec. II, the corresponding binary number (k ) of such a subgraph, bj , is the j th permutation of a vector of exactly k 1’s and |E | ? k zeroes. Since |b| is the Hamming weight of b these subgraphs all have |b| = k . | There are |E such subgraphs, all with equal weight λk . k Therefore: 2 |V | Z (w) = × (1 ? λ2 )|E |/2 ? | (|E |E | k ) (k) ? (?1)bj ·b δ λk ?1 +

k=1 j =1

A magnetic ?eld B can be included in the Hamiltonian [Eq. (1)], by adding a term ? i∈V Bi σi . We can repeat the analysis above by introducing a ?ctitious “alwaysup” spin, numbered 0. In this manner we can rewrite the magnetic ?eld term as Bi σi =

i∈V i∈V

(k) b (α j ,0)

?

? ?.

(A3)

Bi0 σi σ0 ,

(A1)

where σ0 ≡ 1. The corresponding graph has a “star” geometry, with spin 0 in the center, connected to all other spins, which in turn are connected only to spin 0 (Fig. 1c). The analysis above can then be repeated step-by-step, with the relevant subgraphs being those of the star graph. However, we then cannot recover the QWGT form, due to the extra summation over the star-graph subgraphs: Denote the latter b′ . Since each spin in V is connected once to the central spin σ0 , the star graph subgraphs all ′ have trivial parity vectors, αb i = 1. Then Eq. (20) is replaced by (?1)

s [αb +(αb )]·s

′

In this form we have a series expansion in powers of λ, corresponding to the number of edges of the subgraphs. A clear simpli?cation results in the fully ferromagnetic Ising model (Z+ ), where w ≡ (0, 0, ..., 0), and in the fully antiferromagnetic case (Z? ), where w ≡ (1, 1, .., 1). In the latter case we have simply b · w = |b|, so that combining the two cases we obtain from Eq. (23):

Z± =

2 |V | (1 ? λ2 )|E |/2

(±λ)|b| δ(αb ,0) .

b

(A4)

Eq. (A3), on the other hand yields:

=2

|V |

δ(αb +αb′ ,0) .

(A2)

Z± =

This causes a violation of the condition b : Ab = 0 needed in the de?nition of the QWGT sum. Thus it appears that QWGTs do not include the case with a magnetic ?eld.

(A5) As already remarked, there exist an e?cient classical algorithm for calculating Z in the case of the fully ferromagnetic Ising model [30].

2 ? (±λ)k ?1 + (1 ? λ2 )|E |/2 k=1

|V |

?

|E |

| (|E k )

δ

j =1

(

(k) b α j ,0)

?

? ?.

R.P. Feynman, Intl. J. Theor. Phys. 21, 467 (1982). R.P. Feynman, Found. Phys. 16, 507 (1986). S. Lloyd, Science 273, 1073 (1996). D.A. Meyer, J. Stat. Phys. 85, 551 (1996). D.A. Meyer, Phys. Rev. E 55, 5261 (1997). B.M. Boghosian and W. Taylor, Intl. J. Mod. Phys. C 8, 705 (1997). [7] B.M. Boghosian and W. Taylor, Phys. Rev. E 57, 54 (1998). [8] S. Wiesner, Simulations of Many-Body Quantum Sys-

[1] [2] [3] [4] [5] [6]

tems by a Quantum Computer, eprint quant-ph/9603028. [9] C. Zalka, E?cient Simulation of Quantum Systems by Quantum Computers, eprint quant-ph/9603026. [10] C. Zalka, Proc. Roy. Soc. London Ser. A 454, 313 (1998). [11] D.S. Abrams and S. Lloyd, Phys. Rev. Lett. 79, 2586 (1997). [12] G. Ortiz, J.E. Gubernatis, E. Knill, and R. La?amme, Phys. Rev. A 64, 022319 (2001). [13] D.A. Lidar and H. Wang, Phys. Rev. E 59, 2429 (1999). [14] B.M. Terhal and D.P. DiVincenzo, Phys. Rev. A 61,

8

022301 (2000). [15] M.H. Freedman, A. Kitaev and Z. Wang, Commun. Math. Phys. 227, 587 (2002). [16] L.-A. Wu, M.S. Byrd, and D.A. Lidar, Phys. Rev. Lett. 89, 057904 (2002). [17] D.A. Lidar and O. Biham, Phys. Rev. E 56, 3661 (1997). [18] J. Yepez, Phys. Rev. E 63, 046702 (2001). [19] D.A. Meyer, Proc. Roy. Soc. London Ser. A 360, 395 (2002). [20] B. Georgeot and D.L. Shepelyansky, Phys. Rev. Lett. 86, 5393 (2001). [21] B. Georgeot and D.L. Shepelyansky, Phys. Rev. Lett. 86, 2890 (2001). [22] M. Terraneo, B. Georgeot, D.L. Shepelyansky, Eur. Phys. J. D 22, 127 (2003). [23] C. Zalka, Comment on “Stable Quantum Computation of Unstable Classical Chaos”, eprint quant-ph/0110019. [24] L.H. Kau?man, Quantum Computing and the Jones Polynomial, eprint math.QA/0105255. [25] L. Kau?man, Knots and Physics, Vol. 1 of Knots and Everything (World Scienti?c, Singapore, 2001). [26] L. Onsager, Phys. Rev. 65, 117 (1944). [27] R.J. Baxter, Exactly Solved Models in Statistical Mechanics (Academic, New York, 1982). [28] H.S. Green and C.A. Hurst, Order-Disorder Phenomena (Interscience Publishers, London, 1964). [29] E. Ising, Z. der Physik 31, 253 (1925). [30] M.R. Jerrum, A. Sinclair, Proc. 17th ICALP, EATCS 462 (1990). [31] R.H Swendsen and J.-S. Wang, Phys. Rev. Lett. 58, 86 (1987). [32] A. Nayak, L. Schulman, and U. Vazirani, manuscript, unpublished. [33] D. Randall and D.B. Wilson, in Sampling spin con?gurations of an Ising system (1999), p. S959, 10th Symposium on Discrete Algorithms (SODA). [34] E. Knill and R. La?amme, Inf. Proc. Lett. 79, 173 (2001). [35] V.F.R. Jones, Paci?c J. Math. 137, 311 (1989). [36] V.F.R. Jones, Bull. Amer. Math. Soc. 12, 103 (1985). [37] F. Jaeger, D. Vertigen, D. Welsh, Math. Proc. Cambridge Philos. Soc. 108, 35 (1990). [38] M.H. Freedman, A. Kitaev, M.J. Larsen, and Z. Wang, Topological Quantum Computation, eprint quant-ph/0101025. [39] L.H. Kau?man and S.J. Lomonaco, New J. Phys. 4, 73.1 (2002). [40] C.H. Papadimitriou, Computational Complexity (Addison Wesley Longman, Reading, Massachusetts, 1995). [41] R.J. Wilson, Introduction to Graph Theory, 4 ed. (Addison-Wesley, Reading, Massachusetts, 1997). [42] D. Aharonov, Annual Reviews of Computational Physics VI (2000). [43] Scott Aaronson’s “complexity zoo” page, http://www.cs.berkeley.edu/~aaronson/zoo.html. [44] L. Adleman, J. DeMarris, and M. Huang, SIAM J. on Computing 26, 1524 (1997). [45] D.L. Vertigan, J. Combin. Theory A 220, 53 (1992). [46] N. Alon, A.M. Frieze, D. Welsh, Electronic Colloquium on Computational Complexity 1(5) (1994). [47] L.H. Kau?man, Topology 26, 395 (1987). [48] S. Nechaev, Statistics of knots and entangled random walks, eprint cond-mat/9812205.

- A New Method to Calculate the Spin-Glass Order Parameter of the Two-Dimensional +-J Ising M
- Numerical Study on Aging Dynamics in the 3D Ising Spin-Glass Model. III. Cumulative Memory
- Geometry of large-scale low-energy excitations in the one-dimensional Ising spin glass with
- Griffiths Singularities in the Disordered Phase of a Quantum Ising Spin Glass
- Theory of Quantum Annealing of an Ising Spin Glass
- Singularities of the Partition Function for the Ising Model Coupled to 2d Quantum Gravity
- Geometrical Aspects of Aging and Rejuvenation in the Ising Spin Glass A Numerical Study
- The ordering temperature and critical exponents of the binomial Ising spin glass in dimensi
- Quantum Critical Behavior of the Infinite-range Transverse Ising Spin Glass An Exact Numer
- Ising-model description of the SU(2)_1 quantum critical point in a dimerized two-leg spin-1
- On the Complexity of the Bethe Lattice Spin Glass
- Complexity in Mean-Field Spin-Glass Models Ising $p$-spin
- A New Method to Calculate the Spin-Glass Order Parameter of the Two-Dimensional +-J Ising M
- Quantum critical point in the spin glass-antiferromagnetism competition for fermionic Ising
- Replica analysis of the p-spin interactions Ising spin-glass model

更多相关文章：
更多相关标签：