We present general mappings between classical spin systems and quantum physics. More precisely, we show how to express partition functions and correlation functions of arbitrary classical spin models as inner products...
详细信息
We present general mappings between classical spin systems and quantum physics. More precisely, we show how to express partition functions and correlation functions of arbitrary classical spin models as inner products between quantum stabilizer states and product states, thereby generalizing mappings for some specific models established in our previous work [M. Van den Nest et al., Phys. Rev. Lett. 98, 117207 (2007)]. For Ising- and Potts-type models with and without external magnetic field, we show how the entanglement features of the corresponding stabilizer states are related to the interaction pattern of the classical model, while the choice of product states encodes the details of the interaction. These mappings establish a link between the fields of classical statistical mechanics and quantum information theory, which we utilize to transfer techniques and methods developed in one field to gain insight into the other. For example, we use quantum information techniques to recover well known duality relations and local symmetries of classical models in a simple way and provide new classical simulation methods to simulate certain types of classical spin models. We show that in this way all inhomogeneous models of q-dimensional spins with pairwise interaction pattern specified by a graph of bounded tree width can be simulated efficiently. Finally, we show relations between classical spin models and measurement-based quantum computation. (C) 2009 American Institute of Physics. [DOI: 10.1063/1.3190486]
Let [a,b] be a line segment with end points a, b and ν a point at which a viewer is located, all in R 3. The aperture angle of [a,b] from point ν, denoted by θ(ν), is the interior angle at ν of the triangle Δ(a...
详细信息
作者：
Lenka ZdeborováFlorent KrząkałaLPTMS
UMR 8626 CNRS et Université Paris-Sud 91405 Orsay CEDEX France PCT
UMR Gulliver 7083 CNRS-ESPCI 10 rue Vauquelin 75231 Paris France
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and system...
详细信息
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdős-Rényi and regular random graphs and determine their asymptotic values for a large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to...
详细信息
Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.
We investigate the phase transition in vertex coloring on random graphs, using the extremal optimization heuristic. Three-coloring is among the hardest combinatorial optimization problems and is equivalent to a 3-stat...
详细信息
We investigate the phase transition in vertex coloring on random graphs, using the extremal optimization heuristic. Three-coloring is among the hardest combinatorial optimization problems and is equivalent to a 3-state anti-ferromagnetic Potts model. Like many other such optimization problems, it has been shown to exhibit a phase transition in its ground state behavior under variation of a system parameter: the graph’s mean vertex degree. This phase transition is often associated with the instances of highest complexity. We use extremal optimization to measure the ground state cost and the “backbone,” an order parameter related to ground state overlap, averaged over a large number of instances near the transition for random graphs of size n up to 512. For these graphs, benchmarks show that extremal optimization reaches ground states and explores a sufficient number of them to give the correct backbone value after about O(n3.5) update steps. Finite size scaling yields a critical mean degree value αc=4.703(28). Furthermore, the exploration of the degenerate ground states indicates that the backbone order parameter, measuring the constrainedness of the problem, exhibits a first-order phase transition.
These years, WLAN- based positioning technology developed rapidly due to the limitation of GPS in "city canyon". Some people try to apply the indoor fingerprint positioning technology in the outdoor environm...
详细信息
These years, WLAN- based positioning technology developed rapidly due to the limitation of GPS in "city canyon". Some people try to apply the indoor fingerprint positioning technology in the outdoor environment. Unfortunately, they ig- nore the difference between the indoor and outdoor environment and can’t achieve preferable results. Considering more complex factors in outdoor environment, we propose a new approach called Common-APs（Access points）-Likelihood Algorithm, which uses the overlapping APs to measure the similarity among users and training points instead of the traditional Signal Strength （SS） information. Our experiment shows that our algorithm could improve the accuracy by 48.75% and reduce the time cost significantly. In addition, the proposed algorithm has strong robustness and could work much better in the busy downtown surrounding dense APs.
暂无评论