Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntroduction to Phase Transitions in Random Optimization Problems
147
0
0.0
(
0
)
Authors
Remi Monasson
Ask ChatGPT about the research
No Arabic abstract
Notes of the lectures delivered in Les Houches during the Summer School on Complex Systems (July 2006).
rate research
Read More
We report a cluster of results regarding the difficulty of finding approximate ground states to typical instances of the quantum satisfiability problem $k$-QSAT on large random graphs. As an approximation strategy, we optimize the solution space over `classical product states, which in turn introduces a novel autonomous classical optimization problem, PSAT, over a space of continuous degrees of freedom rather than discrete bits. Our central results are: (i) The derivation of a set of bounds and approximations in various limits of the problem, several of which we believe may be amenable to a rigorous treatment. (ii) A demonstration that an approximation based on a greedy algorithm borrowed from the study of frustrated magnetism performs well over a wide range in parameter space, and its performance reflects structure of the solution space of random $k$-QSAT. Simulated annealing exhibits metastability in similar `hard regions of parameter space. (iii) A generalization of belief propagation algorithms introduced for classical problems to the case of continuous spins. This yields both approximate solutions, as well as insights into the free energy `landscape of the approximation problem, including a so-called dynamical transition near the satisfiability threshold. Taken together, these results allow us to elucidate the phase diagram of random $k$-QSAT in a two-dimensional energy-density--clause-density space.
This paper presents an introduction to phase transitions and critical phenomena on the one hand, and nonequilibrium patterns on the other, using the Ginzburg-Landau theory as a unified language. In the first part, mean-field theory is presented, for both statics and dynamics, and its validity tested self-consistently. As is well known, the mean-field approximation breaks down below four spatial dimensions, where it can be replaced by a scaling phenomenology. The Ginzburg-Landau formalism can then be used to justify the phenomenological theory using the renormalization group, which elucidates the physical and mathematical mechanism for universality. In the second part of the paper it is shown how near pattern forming linear instabilities of dynamical systems, a formally similar Ginzburg-Landau theory can be derived for nonequilibrium macroscopic phenomena. The real and complex Ginzburg-Landau equations thus obtained yield nontrivial solutions of the original dynamical system, valid near the linear instability. Examples of such solutions are plane waves, defects such as dislocations or spirals, and states of temporal or spatiotemporal (extensive) chaos.
We explore a class of random tensor network models with ``stabilizer local tensors which we name Random Stabilizer Tensor Networks (RSTNs). For RSTNs defined on a two-dimensional square lattice, we perform extensive numerical studies of entanglement phase transitions between volume-law and area-law entangled phases of the one-dimensional boundary states. These transitions occur when either (a) the bond dimension $D$ of the constituent tensors is varied, or (b) the tensor network is subject to random breaking of bulk bonds, implemented by forced measurements. In the absence of broken bonds, we find that the RSTN supports a volume-law entangled boundary state with bond dimension $Dgeq3$ where $D$ is a prime number, and an area-law entangled boundary state for $D=2$. Upon breaking bonds at random in the bulk with probability $p$, there exists a critical measurement rate $p_c$ for each $Dgeq 3$ above which the boundary state becomes area-law entangled. To explore the conformal invariance at these entanglement transitions for different prime $D$, we consider tensor networks on a finite rectangular geometry with a variety of boundary conditions, and extract universal operator scaling dimensions via extensive numerical calculations of the entanglement entropy, mutual information and mutual negativity at their respective critical points. Our results at large $D$ approach known universal data of percolation conformal field theory, while showing clear discrepancies at smaller $D$, suggesting a distinct entanglement transition universality class for each prime $D$. We further study universal entanglement properties in the volume-law phase and demonstrate quantitative agreement with the recently proposed description in terms of a directed polymer in a random environment.
We study network configurations that provide optimal robustness to random breakdowns for networks with a given number of nodes $N$ and a given cost--which we take as the average number of connections per node $kav$. We find that the network design that maximizes $f_c$, the fraction of nodes that are randomly removed before global connectivity is lost, consists of $q=[(kav-1)/sqrtkav]sqrt N$ high degree nodes (``hubs) of degree $sqrt{kav N}$ and $N-q$ nodes of degree 1. Also, we show that $1-f_c$ approaches 0 as $1/sqrt N$--faster than any other network configuration including scale-free networks. We offer a simple heuristic argument to explain our results.
The phase transitions of random-field q-state Potts models in d=3 dimensions are studied by renormalization-group theory by exact solution of a hierarchical lattice and, equivalently, approximate Migdal-Kadanoff solutions of a cubic lattice. The recursion, under rescaling, of coupled random-field and random-bond (induced under rescaling by random fields) coupled probability distributions is followed to obtain phase diagrams. Unlike the Ising model (q=2), several types of random fields can be defined for q >= 3 Potts models, including random-axis favored, random-axis disfavored, random-axis randomly favored or disfavored cases, all of which are studied. Quantitatively very similar phase diagrams are obtained, for a given q for the three types of field randomness, with the low-temperature ordered phase persisting, increasingly as temperature is lowered, up to random-field threshold in d=3, which is calculated for all temperatures below the zero-field critical temperature. Phase diagrams thus obtained are compared as a function of $q$. The ordered phase in the low-q models reaches higher temperatures, while in the high-q models it reaches higher random fields. This renormalization-group calculation result is physically explained.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
