text:
# Theory of Quantum Annealing of an Ising Spin Glass

## Abstract

Probing the lowest energy configuration of a complex system by quantum annealing was recently found to be more effective than its classical, thermal counterpart. Comparing classical and quantum Monte Carlo annealing protocols on the random two-dimensional Ising model we confirm the superiority of quantum annealing relative to classical annealing. We also propose a theory of quantum annealing, based on a cascade of Landau-Zener tunneling events. For both classical and quantum annealing, the residual energy after annealing is inversely proportional to a power of the logarithm of the annealing time, but the quantum case has a larger power which makes it faster

The annealing of disordered and complex systems towards their optimal (or lowest energy) state is a central problem in statistical physics, with impact in a large variety of areas. The unknown ground state of a system can be approximated by slow-rate cooling of a real or fictitious temperature: the slower the cooling, the closer the approximation. Although this kind of standard classical annealing (CA) has been extensively investigated over the last two decades, and is routinely used in a variety of technological applications, such as chip circuitry design, the premium on any alternative better optimization algorithms would certainly be enormous.

Recent results of Brooke et al. , on the spin 1/2 disordered Ising ferromagnet LiHo0.44Y0.56F4 suggested however that a different, quantum annealing (QA) procedure works surprisingly better than classical annealing. In QA, temperature is replaced by a quantum mechanical kinetic Hamiltonian term – in the specific case a transverse magnetic field $`\mathrm{\Gamma }`$ mixing the up and down spin states at each site. Initially the quantum perturbation starts out so large in magnitude as to completely disorder the system even at zero temperature. When the transverse field is subsequently reduced to zero at some slow rate $`1/\tau `$, the system is “annealed” towards its ground state, much in the same way as when its temperature is reduced to zero in CA. The question is which of the two, CA or QA, works better, and how and why. Experimental comparison of the properties displayed by the same system transported from the same initial state A – a classical high-T state – to the same nominal final state B – a low-T glassy state – through two different routes in the \[T,$`\mathrm{\Gamma }`$\] plane, presents evidence that QA, the “quantum route” from A to B, yields with the same “cooling” rate, a state B apparently closer to the ground state than CA, the classical one. The data however do not clarify how, and even less why, that should be so.

Theoretical suggestions and exemplifications of QA made by various groups over the past decade  have stimulated considerable interest in understanding the mechanism of QA better. A theoretical discussion of the relative merits of CA and QA is therefore desirable. For this, it is necessary to carry out a direct comparative test on a sufficiently representative benchmark system, such as a spin glass, and to lay the bases of a theory of the processes underlying QA. The issues are pressing, both because the physical underpinnings of QA call to be explored, and because of the practical potential of QA in the fields of optimization in complex systems, should QA turn out to be (as recently shown in a protein folding model) actually superior. Our work is meant as a step aimed at filling these gaps.

En route, open issues are found even in the context of plain CA, where the very rate of decay of the residual energy above the actual ground state energy as a function of the annealing rate $`1/\tau `$ is controversial. Whereas general theoretical arguments by Huse and Fisher  predict a slow logarithmic convergence $`ϵ_{res}(\tau )=E_{final}(\tau )E_{GS}\mathrm{log}^\zeta (\tau )`$, with $`\zeta 2`$, early simulations, but also more recent studies , favor a different form, such as power-law, $`ϵ_{res}(\tau )\tau ^\alpha `$, or stretched exponential. The question remains whether the discrepancy between simulations and theory is real, or only apparent.

Our work proceeded in three steps. First, we chose a benchmark system, the Ising spin glass, where we carried out CA and QA, and compared the results to find that QA is indeed faster. Second, we focused on the residual energy in CA, to find deviations from power law decay versus rate $`1/\tau `$ that are quite compatible at very slow rates with the Huse-Fisher asymptotically logarithmic decay. Third, we built a theory of QA of a spin glass based on the idea of a cascade of level crossings, each with its associated Landau-Zener probability to miss the ground state. That theory suggests an asymptotic decay of residual energy with QA rate that is again logarithmic as in CA, but governed by somewhat different exponents that makes it faster.

Step 1. Benchmarking quantum versus classical annealing. At the outset, inspired by Brooke et al.’s experimental system, we selected the two-dimensional (2D) random Ising model as an appropriate realistic test case. This choice is dictated by the fact the 2D random Ising model is technically a polynomial problem  – where $`E_{GS}`$ can be calculated up to sufficiently large lattice sizes  (thus avoiding an extra fitting parameter in $`ϵ_{res}(\tau )`$) – which is nonetheless of prohibitively large complexity for any physical dynamics as a true glass .

The Edwards-Anderson Hamiltonian of an Ising spin glass in transverse field

$$H=\underset{ij}{}J_{ij}\sigma _i^z\sigma _j^z\mathrm{\Gamma }\underset{i}{}\sigma _i^x,$$
(1)
where nearest-neighbor spins $`ij`$ of a $`d`$-dimensional cubic lattice interact with a random exchange coupling $`J_{ij}`$, $`\mathrm{\Gamma }`$ is the transverse field inducing transitions between the two states, $``$ and $``$, of each spin, and $`\sigma _i^x,\sigma _i^z`$ are Pauli matrices of the spin 1/2 on site $`i`$. The problem is to anneal this system as close as possible to its classical, $`\mathrm{\Gamma }=0`$, ground state. In CA , there is no tranverse field and no quantum mechanics ($`\mathrm{\Gamma }=0`$): one starts with a sufficiently high temperature $`T_0`$, which is then reduced linearly to zero in a time $`\tau `$. In QA, $`T`$ is instead fixed to zero or some small value, and one starts with a transverse field $`\mathrm{\Gamma }_0`$ sufficiently large to throw the system in a “disordered” quantum paramagnetic state, decreasing $`\mathrm{\Gamma }`$ linearly to zero, again in a time $`\tau `$. Because real time annealing is computationally out of the question for the large systems addressed here, we carried out annealing as a function, as customary, of the fictitious “time’ represented by the number of Monte Carlo steps. Our implementation of CA was a standard Metropolis Monte Carlo (MC). That for QA was a path-integral Monte Carlo (PIMC)  scheme for a quantum system at a small finite temperature $`T`$. The 2D quantum Ising model is first mapped on a (2+1)D classical model consisting of $`P`$ copies (Trotter replicas) of the original lattice, with a nearest-neighbors uniform ferromagnetic coupling in the third (Trotter) direction $`J^{}=(PT/2)\mathrm{log}\mathrm{tanh}(\mathrm{\Gamma }/PT)`$, at temperature $`PT`$ . At the beginning of the annealing, when $`\mathrm{\Gamma }`$ is large, the replicas are only weakly coupled; as $`\mathrm{\Gamma }`$ decreases to zero the ferromagnetic coupling $`J^{}`$ increases, eventually forcing all replicas into the same configuration. At the end of either annealing cycle the system, unable to negotiate all barriers in the finite time $`\tau `$, remains generally trapped at energy $`E_{final}=E_{GS}+ϵ_{res}`$, higher than the ground state value $`E_{GS}`$. The efficiency of each protocol is measured by the decrease of the average residual energy $`ϵ_{res}(\tau )`$ as a function of $`\tau `$.

For a given 2D lattice size $`L\times L`$, ($`L`$ up to 80) we took a realization of the random couplings $`J_{ij}`$, drawn from a flat distribution in the interval $`(2,2)`$, and for that we got at the outset the exact classical ground state energy $`E_{GS}`$ by the Branch and Cut algorithm. Keeping the couplings fixed, we then carried out a sufficient number of repeated annealings, (45 for the $`80\times 80`$ lattice), both CA and QA. The annealing parameters $`T`$ (CA) or $`\mathrm{\Gamma }`$ (QA) were decreased stepwise from the initial value of $`T_0=3`$ or $`\mathrm{\Gamma }_0=2.5`$ down to zero, with a total of $`\tau `$ MC steps per spin. In QA we used fixed values of $`PT=1,1.5,2`$ at several $`P`$ values, and prepared the initial state (same for all replicas) by classical annealing from a temperature of 3.0 down to the corresponding value of $`PT`$. In all cases the residual energy $`ϵ_{res}(\tau )`$ was calculated by subtracting $`E_{GS}`$ from the averaged final annealed energies.

Fig. 1 shows the residual energy, for both CA and QA for the $`80\times 80`$ lattice, plotted against the inverse annealing rate $`\tau `$, actually the actual Monte Carlo computer time. QA appears definitely superior to CA, with a lower residual energy for large $`\tau `$. This theoretical finding goes very much in the same direction as the experimental evidence of a significantly faster frequency-dependent relaxations observed after QA of the disordered magnet. The $`\tau `$ dependence of our QA data does depend on the chosen values of $`P`$ and $`T`$, particularly upon the value of $`PT`$, whose optimal value appears to be around $`PT=1`$. An increase of $`P`$ for a fixed value of $`PT`$, see inset in Fig. 1, ceases to be effective beyond a certain characteristic length (which depends on $`PT`$) in the imaginary time direction, . The computational cost increases linearly with $`P`$, and the choice $`P=20`$ (corresponding to $`T=0.05`$), was found to be optimal up to the largest values of $`\tau `$ used. Another property (not shown in Fig. 1) of the CA results is that residual energies obtained for different sizes $`32<L<80`$, or even for different realizations of the couplings $`J_{ij}`$ are remarkably size independent and self-averaging, and all fall essentially on top of the CA curve in Fig. 1.

Step 2. Asymptotic behavior of classical annealing. A feature evident in our $`ϵ_{res}(\tau )`$ CA data, is its gentle but consistent deviation from a pure power law, suggesting serious reconsideration of all the earlier power law claims . Since the slope (or apparent power) systematically declines for increasing $`\tau `$, it is natural to ask whether it will asymptotically extrapolate to zero in accordance with the Huse-Fisher logarithmic law . Writing that in the form $`ϵ_{res}^{1/\zeta }=A\mathrm{log}(\gamma \tau )`$ and replacing time with number of Monte Carlo steps, we can plot the CA data as in Fig. 2. The extrapolated behavior is indeed compatible with a Huse-Fisher straight line. However, as Fig. 2 shows, it proves impossible to extract a value for the exponent $`\zeta `$, in particular to establish if $`\zeta 2`$  is any better, as one could have expected.

Step 3. Landau-Zener theory of quantum annealing. In order to shed some light on the actual asymptotic form of residual energy in QA, and eventually rationalize why that might be superior, we start off with a cartoon of the instantaneous energy spectrum of (1) versus $`\mathrm{\Gamma }`$ in Fig. 3, suggested by small-systems exact diagonalizations. For sufficiently large initial $`\mathrm{\Gamma }>>|J_{ij}|`$ the ground state, generally nondegenerate, must have a finite excitation gap. Imagine following the Schrödinger evolution of an initial ground state wavefunction $`|\mathrm{\Psi }_{\mathrm{\Gamma }_0}(t=0)`$ while reducing $`\mathrm{\Gamma }`$ gradually to zero as a function of time . The instantaneous gap of our disordered magnet will close as $`\mathrm{\Gamma }`$ decreases through the quantum phase transition at $`\mathrm{\Gamma }_c`$ . After that, ground state level crossings begin. The arrows in the cartoon point to two crossings \[really avoided crossings , the problem possessing no symmetry\]. Each instantaneous ground state crossing is associated with tunneling of the whole system between two valleys – say from a broader but shallower valley to a narrower but deeper one, taking place when kinetic energy diminishes – and represents a major crisis in the otherwise quasi-adiabatic evolution caused by the time-dependent decrease of $`\mathrm{\Gamma }(t)`$.

For sufficiently slow annealing, each tunneling event can be treated as a Landau-Zener (LZ) problem, see inset in Fig. 3. The probability $`P(\tau )`$ that the system, starting in the lower state $`|b`$ at high $`\mathrm{\Gamma }`$ will continue nonadiabatically onto the higher branch as $`\mathrm{\Gamma }`$ is reduced with time is given by $`P(\tau )=\mathrm{exp}(\tau /\tau _c)`$ where $`\tau _c`$, the characteristic tunneling time, is $`\tau _c=(\mathrm{}\alpha \mathrm{\Gamma }_0)/(2\pi \mathrm{\Delta }^2)`$. Here $`\mathrm{\Delta }`$ is the tunneling amplitude between the two states $`|a`$ and $`|b`$ (whose splitting at crossing is 2$`|\mathrm{\Delta }|`$), and $`\alpha `$ is the relative slope of the two crossing branches as a function of $`\mathrm{\Gamma }`$ . One can estimate $`\mathrm{\Delta }e^{d_{ab}/\xi (\mathrm{\Gamma })}`$, where $`d_{ab}`$ is a suitable distance between states $`a`$ and $`b`$ (in the Ising case, the number of spins that are flipped in the tunneling process, $`N_{flip}`$), and $`\xi (\mathrm{\Gamma })`$ is a typical wavefunction localization length, which must vanish as $`\mathrm{\Gamma }0`$, $`\xi (\mathrm{\Gamma })\mathrm{\Gamma }^\varphi `$, with some exponent $`\varphi >0`$. The tunneling time becomes exponentially large for small $`\mathrm{\Gamma }`$, $`\tau _\mathrm{\Gamma }e^{2d_{ab}/\mathrm{\Gamma }^\varphi }`$, and an exceedingly small width $`\mathrm{\Delta }`$ of each tunneling event justifies treating the multiple crossings as a cascade of independent LZ events. Once the system fails, with a probability $`P_\mathrm{\Gamma }(\tau )=e^{\tau /\tau _\mathrm{\Gamma }}`$, to follow the ground state at the LZ crossing occurring at $`\mathrm{\Gamma }`$, it will eventually attain an average excitation energy $`E_{ex}(\mathrm{\Gamma })>0`$. Letting $`Z(\mathrm{\Gamma })d\mathrm{\Gamma }`$ be the number of LZ crossings which take place between $`\mathrm{\Gamma }`$ and $`\mathrm{\Gamma }+d\mathrm{\Gamma }`$, the average residual energy can be estimated as

$$ϵ_{res}(\tau )=_0^{\mathrm{\Gamma }_c}𝑑\mathrm{\Gamma }Z(\mathrm{\Gamma })E_{ex}(\mathrm{\Gamma })e^{\tau /\tau _\mathrm{\Gamma }},$$
(2)
where $`\mathrm{\Gamma }_c`$ marks the first level crossing. The large $`\tau `$ behavior of this expression is dominated by the $`\mathrm{\Gamma }0`$ behavior of $`Z(\mathrm{\Gamma })E_{ex}(\mathrm{\Gamma })`$, and $`\tau _\mathrm{\Gamma }`$. If we assume that, for small $`\mathrm{\Gamma }`$, $`Z(\mathrm{\Gamma })E_{ex}(\mathrm{\Gamma })\mathrm{\Gamma }^\omega `$, and $`\tau _\mathrm{\Gamma }e^{A/\mathrm{\Gamma }^\varphi }`$ we get finally a residual energy which vanishes as the inverse power of the rate logarithm $`ϵ_{res}(\tau )\mathrm{log}^{\zeta _{QA}}(\tau )`$, with an exponent $`\zeta _{QA}=(1+\omega )/\varphi `$. The exponents $`\omega `$ and $`\varphi `$ are not obvious. A semiclassical (WKB) expression for the decay of a wavefunction inside a barrier suggests $`\varphi =1/2`$. The average excitation energy attained by missing the ground state “track” at $`\mathrm{\Gamma }`$ should scale as $`\mathrm{\Gamma }^2`$ for small $`\mathrm{\Gamma }`$, because all eigenvalues start out as $`\mathrm{\Gamma }^2`$ for $`\mathrm{\Gamma }0`$. The total number of LZ crossings occurring from $`0`$ to $`\mathrm{\Gamma }`$ should not be larger than the total number of classical states in the energy window $`(E_{GS},E_{GS}+\mathrm{\Gamma })`$, which is approximately equal to $`\rho (0)\mathrm{\Gamma }`$ \[where $`\rho (0)`$ s the density of classical states at the ground state energy \], so that the density of crossings $`Z(\mathrm{\Gamma }0)\rho (0)`$, at most. This yields $`\omega =2`$ as our most reasonable estimate.

We conclude that $`\zeta _{QA}=(1+\omega )/\varphi `$ can be as large as $`6`$ for a spin glass, and in any case above the classical Huse-Fisher bound $`\zeta 2`$ . Hence, quantum annealing of the Ising spin glass is predicted to be again logarithmically accurate, not fundamentally different in that from classical annealing. We therefore expect that a quantum computation based on QA will not transform a hard nonpolynomial (NP-complete) computational problem into a polynomial one. On the contrary, the above reasoning suggests a logarithmically slow annealing to apply also to the present 2D Ising case, which is not NP-complete . The slowing down effect of the LZ cascade illustrated above is particularly severe in problems, like the Ising spin glass we have considered, where the classical spectrum has a gapless continuum of excitations above the ground state. Satisfiability problems, for which much more encouraging results were recently presented  differ from the Ising spin glass in that they possess a discrete classical spectrum and a finite excitation gap. We observe that in general a gap will cut off the LZ cascade precisely in the dangerous low-$`\mathrm{\Gamma }`$ region, and that may eliminate the logarithmic slowing down of QA. Nonetheless, even in the gapless case, the advantage of QA over CA is far from negligible, due to the generally larger exponent $`\zeta _{QA}`$ of the logarithm. To get an idea of the order of magnitudes involved, consider the relative increase of annealing time $`(\tau ^{}/\tau )`$ needed to improve the accuracy of a certain annealing, say with $`\tau 10^6`$ (in appropriate units) by a factor 10. In CA ($`\zeta =2`$), this would require $`(\tau ^{}/\tau )\tau ^{10^{1/\zeta }1}10^{13}`$. In QA ($`\zeta =6`$), the same result would be accomplished with $`(\tau ^{}/\tau )10^{2.8}`$, an enormous saving of computer effort. Moreover, the PIMC version of QA is easy to implement on a parallel computer, and that provides an extra advantage.

In summary, our test of QA in the disordered Ising magnet indicates a faster convergence than CA, and a time-dependent cascade of Landau-Zener tunneling events across barriers is pinpointed as the crucial ingredient of QA. Optimization by QA of a vast variety of problems beyond statistical mechanics, of course after a suitable fictitious kinetic energy operator is identified case by case, is an open avenue, and stands as a worthy challenge for the future.

This project was sponsored by MIUR under project COFIN, by INFM/F, INFM/G, and by INFM’s “Iniziativa Trasversale Calcolo Parallelo”. R.M acknowledges European Union support through CINECA under project MINOS3, which also provided much of the computer resources. We are grateful to G. Aeppli, L. Arrachea, J. Berg, C. Micheletti, M. Parrinello, F. Ricci Tersenghi, R. Zecchina, for helpful discussions and suggestions.


format: text

text:
# Minimum energy paths for dislocation nucleation in strained epitaxial layers

\[

## Abstract

We study numerically the minimum energy path and energy barriers for dislocation nucleation in a two-dimensional atomistic model of strained epitaxial layers on a substrate with lattice misfit. Stress relaxation processes from coherent to incoherent states for different transition paths are determined using saddle point search based on a combination of repulsive potential minimization and the Nudged Elastic Band method. The minimum energy barrier leading to a final state with a single misfit dislocation nucleation is determined. A strong tensile-compressive asymmetry is observed. This asymmetry can be understood in terms of the qualitatively different transition paths for the tensile and compressive strains.

\]

May 20, 2002

The growth and stability of heteroepitaxial overlayers is one of the central problems in current materials science. Energy-balance arguments for the competition between strain energy build-up and strain relief due to dislocation nucleation in mismatched epitaxial films lead to the concept of an equilibrium critical thickness. This is defined as the thickness at which the energy of the epitaxial state is equal to that of a state containing a single misfit dislocation . The predicted critical value from this equilibrium consideration however, both from continuous elastic models  and from models incorporating layer discreteness , is much smaller than the observed experimental value for the breakdown of the epitaxial state. This suggests that the defect-free (coherent) state above the equilibrium critical thickness is metastable  and the rate of dislocation generation is actually controlled by kinetic considerations. The idea of strain relaxation as an activated process is supported by experimental results for the temperature dependence of the critical thickness . It is also the fundamental assumption in kinetic semi-empirical models .

Physically, it is expected that the lowest energy barrier for the nucleation of dislocations would correspond to a path that initiates from the free surface (with or without defects). Such processes have been considered in a number of studies within continuum models . It has been pointed out that surface steps and surface roughness that are not included in the continuum model could play an important role for dislocation nucleation . Thus, atomistic study is important for a detailed understanding and direct determination of the mechanisms for defect nucleation in epitaxial films. However, determination of the correct transition path and the nucleation barrier from the initial coherent state to the final state with misfit dislocations is an extremely challenging problem in an atomistic model. There are many saddle points and transition paths in the neighborhood of the initial coherent state. A brute force molecular dynamics (MD) study is impractical because of the rare event nature of the activated processes. In recent years, great progress has been made in the general field of search for transition paths for complicated energy landscapes . In addition, various accelerated hyperdynamics schemes  have been developed to overcome the computational problems for rare events. However, these schemes still involve considerable computational efforts for complicated, large energy barriers and often require a qualitative picture of the energy landscape as a starting point. Recently we have developed a repulsive potential minimization method  which allows automatic generation of many paths leading away from the initial minimum energy coherent state. When combined with the Nudged Elastic Band method (NEB) , this method can be used to efficiently locate saddle point configurations and barriers for each transition path without having to make any specific assumptions about the nature of the transition path.

For the present study, we consider a two-dimensional model of the epitaxial film and substrate where the atomic layers are confined to a plane as illustrated in Fig. 1 (a). Interactions between atoms in the system are modelled by a generalized Lennard-Jones pair potential , that is modified to insure that the potential and its first derivative vanish  at a cut-off distance $`r_c`$ as

$`U(r)=V(r),rr_0;`$ (1)
$`U(r)=V(r)\left[3\left({\displaystyle \frac{r_cr}{r_cr_0}}\right)^22\left({\displaystyle \frac{r_cr}{r_cr_0}}\right)^3\right],r>r_0,`$ (2)
where

$$V(r)=\epsilon \left[\frac{m}{nm}\left(\frac{r_0}{r}\right)^n\frac{n}{nm}\left(\frac{r_0}{r}\right)^m\right],$$
(3)
and $`r`$ is the interatomic distance, $`\epsilon `$ the dissociation energy and $`r_0`$ the equilibrium distance between the atoms. This potential has been used previously , with $`n=12`$ and $`m=6`$, in a Monte Carlo simulation of epitaxial growth. We have chosen the value $`n=8`$ and $`m=5`$ for the present study. In contrast to the standard $`612`$ potential, this $`58`$ potential has a slower fall-off. Thus, when combined with the variation of the cutoff radius $`r_c`$, this choice allows us to systematically study the effect of the range of the potential on misfit dislocation. Also, the $`58`$ potential gives a more realistic description of metallic systems than the $`612`$ case. The equilibrium interatomic distance $`r_0`$ was set to different values for the substrate, epitaxial film, and the substrate-film interfaces. The substrate $`r_0=r_{\mathrm{ss}}`$ and the epitaxial film $`r_0=r_{\mathrm{ff}}`$ parameters were varied to give a misfit $`f`$ between lattice parameters as $`f=(r_{\mathrm{ff}}r_{\mathrm{ss}})/r_{\mathrm{ss}}`$. For the film-substrate interaction we set the equilibrium distance as the average of the film and substrate lattice constants, $`r_0=r_{\mathrm{fs}}=(r_{\mathrm{ff}}+r_{\mathrm{ss}})/2`$. Positive misfit $`f`$ corresponds to compressive strain and negative $`f`$ to tensile strain when the film is coherent with the substrate. Calculations were performed with periodic boundary conditions in the direction parallel to the film-substrate interface. Typically, one-dimensional layers containing 50 atoms or more were used in the calculations. In the calculations the bottom five layers represented the substrate, with the last two layers held fixed to simulate a semi-infinite substrate while all other layers were free to move.

Our new scheme of identifying the saddle points and the transition paths consists of several stages. First, the initial epitaxial state is prepared by minimizing the total energy of the system using MD cooling. This leads to an initial coherent epitaxial state in which the interlayer spacing is relaxed, but the atoms within the layers are under compressive or tensile strain according to the misfit. Next, we introduce a short-ranged repulsive potential centered at the starting epitaxial configuration of the form

$$U_{tot}(r)=U(r)+A\mathrm{exp}\{\alpha (rr_0)^2\},$$
(4)
where $`r_0`$’s are the coordinates of the initial state at the minimum . The basic idea here is to modify the local energy surface to make the initial epitaxial state unstable. When the system is slightly displaced from the initial state (randomly or in a selective way), it will then be forced to move to nearby minimum energy states. By making this repulsive potential sufficiently localized around the initial potential minima, the surrounding minima would be unaffected and the final state energy would then depend only on the true potential of the system. This method can generate many different final states depending on both the initial displacements and the parameters of the repulsive potential. In this work, we only consider final configurations corresponding to a single misfit dislocation. Rather than trying random initial displacements, some knowledge of the dislocation generation mechanism is useful for expediting the process. Given the knowledge of the final state, we then use the NEB method to locate the saddle point and find the minimum energy path (MEP) between the initial and final states. We note that the path generated in the first part of moving away from the repulsive potential can be used as an initial guess for the MEP determination in the NEB method.

We have performed calculations for various misfits but in this paper we concentrate on the case of a relatively large 8% misfit. We work with dimensionless quantities with $`\epsilon `$ as the energy scale and $`r_{\mathrm{ss}}`$ as the length scale. Two different choices of cutoff, namely $`r_c`$=1.5 $`r_{\mathrm{ss}}`$ and $`r_c`$=4.7 $`r_{\mathrm{ss}}`$ were made. The results for the barriers are qualitatively similar, so we present here only the results for the short range potential with $`r_c`$=1.5 $`r_{\mathrm{ss}}`$. However, the equilibrium critical thickness and its asymmetry with respect to tensile or compressive strain are very sensitive to the range of the potential .

The results for the MEP from coherent to incoherent states are shown in Fig. 1 for a film under tensile strain and Fig. 2 for compressive strain. They show clearly the existence of an energy barrier for the nucleation of a misfit dislocation. Thus, the non-equilibrium critical thickness can be much larger than the equilibrium value and it is controlled in practice by the kinetics of defect nucleation.

For compressive strain, the final state is characterized by the presence of an adatom island on the surface of the film for each misfit dislocation. The number of adatoms in the island exactly corresponds to the number of layers in the film. Such form of the final state is determined by the geometry of the misfit dislocation. For every misfit dislocation, an extra atom is removed from each layer to relieve the compressive stress. For tensile strain, the final state is characterized by the presence of pits on the surface. Again, the size of the pit is determined by geometrical considerations. For every misfit dislocation, an extra atom has to be added to each layer to relieve the tensile stress. For both cases, the dislocation core is localized in the substrate-film interface region.

Figures 1 and 2 also show the particle configurations at the different points along the MEP which reveal details of defect nucleation and strain relaxation process. The transition path for the compressive strain has a more local nature, with relatively fewer bonds involved initially, whereas for the tensile strained film, the nucleation proceeds via a more collective path, involving concerted motion along glide planes. The energy barrier for nucleation of a dislocation is much higher for the compressive strain relative to the case of tensile strain. This asymmetry is very robust and it persists when we change the range of the potential by varying the cutoff.

To understand the origin of this asymmetry, we plot in Fig. 3 the distribution of the nearest-neighbor bond lengths for the film from the initial epitaxial film to the saddle point configuration for both the compressive and tensile cases. It can be seen that the behavior of the compressively strained film and the tensile-strained film is very different. In the tensile case, the redistribution of the bond lengths going from the initial coherent state to the saddle point configuration involves a significant contraction of the intralayer bonds leading to partial relaxation of the tensile strain in the film. On the other hand, for the compressively strained film, the initial delta function peak for the intralayer bond lengths broadens almost symmetrically and there are no significant relaxation of the compressive strain in the film. This explains the relatively higher energy costs and a corresponding larger nucleation barrier for the compressive strained film. Microscopically, the origin of the different behavior could arise from the strong anharmonicity of the interaction potential. For the compressive strain, intralayer rearrangements involve some further compression of the bonds which is energetically costly. Thus, a more localized initial configuration with a higher barrier results as opposed to the collective behavior of the tensile strained layer. We have also checked that the boundary conditions and system sizes do not affect the results qualitatively by comparing results from systems with periodic and free boundary conditions, and for layers twice as long.

In summary, we have developed a new scheme of identifying minimal energy path for spontaneous generation of misfit dislocation in an epitaxial film. This new approach requires no a priori assumptions about the nature of the transition path or the final states. A nonzero activation barrier for dislocation nucleation is found in the minimum energy path from coherent to incoherent state above the equilibrium critical thickness, confirming the meta-stability of the epitaxial coherent film. The nucleation mechanism from a flat surface depends crucially on whether we start from a tensile or compressive initial state of the film. This asymmetry originates from the anharmonicity of the interaction potentials which leads to qualitatively different transition paths for the two types of strains. A tensile-compressive asymmetry has also been found previously  in other contexts. The present method can be extended to three-dimensional models with more realistic interaction potentials. Preliminary calculations for the Pd/Cu and Cu/Pd systems  with the Embedded Atom Model potentials  confirms the effectiveness of the method in three dimensions. These results will be published elsewhere.

This work was supported by a NSF-CNPq grant (E.G. and S.C.Y.), by the Russian Ministry of Science and Technology (O.T.), FAPESP (E.G.), and by the Academy of Finland through its Center of Excellence program (O.T., P.S., and T.A-N.).


text:
# 1 Introduction

## 1 Introduction

Recent empirical evidence of an accelerating universe  is most easily explained in terms of a positive vacuum energy density or cosmological constant. This observation has triggered substantial interest in de Sitter (dS) space, which happens to be the maximally symmetric solution of Einstein gravity when this constant takes on a positive, non-vanishing value.

In particular, one hopes that a quantum theory of dS gravity can eventually be realized. Work along this line has been inspired by significant achievements in the realm of anti-dS space (i.e., maximally symmetric Einstein gravity with a negative cosmological constant). For instance, higher-dimensional spacetimes in string theory (our best candidate for a fundamental theory of quantum gravity) can often be decomposed into anti-dS space times a simple compact manifold. (For a review on string theory, see .) Furthermore, there is a well-known correspondence between any anti-dS spacetime and a conformal field theory (CFT) that “lives” at spatial infinity . Significantly, this duality is a direct manifestation of the holographic principle , which is expected to be a fundamental constituent in the ultimate theory of quantum gravity.

Unfortunately, the remarkable achievements of anti-dS space have not translated well into a dS setting. For example, attempts at compactifying string theory into a stable vacuum with a positive cosmological constant have been plagued by pathologies; including singularities, wrong-sign kinetic terms and non-compact “compactification” manifolds. (See  and references therein for further discussion.) Meanwhile, from a holographic perspective, there has, actually, been significant progress in establishing a dS analogue111A dS/CFT holographic duality was first rigorously formulated in . For both earlier and later studies on this topic, one can consult the bibliographies of . More recent studies of interest include . to the anti-dS/CFT correspondence. However, the status of this conjectured dS/CFT duality still remains a very open question .

Progress along the desired lines has been stymied by various “detrimental” features of dS space; including the lack of an asymptotic spatial infinity, the absence of an objective observer, the existence of an observer-dependent event horizon, the lack of a global timelike killing vector, the eternally thermal background, etcetera. (For further discussion on the properties of dS space, see .) However, it is the finite entropy of dS space  that appears to be the main impediment towards a quantum gravity realization . Significantly, this finite bound on the entropy implies that any dS theory of quantum gravity should be described by a finite-dimensional Hilbert space. Alas, this deduction is in conflict with the infinite-dimensional Hilbert space associated with string theory, any of its related conceptualizations (such as matrix theory ) and, from a holographic perspective, any CFT. That is to say, the finite entropy of dS space appears to sabotage any prospective quantum-gravity framework at a very fundamental level.

With regard to the above conundrum, it is of further interest that the finite entropy of dS space serves as an upper bound on the observable entropy of a large class of spacetimes with a positive cosmological constant; including any spacetime with an asymptotically dS future .

It should be quite clear that any assimilation of quantum physics and dS gravity will have to overcome some very formidable obstacles. Although speculative, one possible road to salvation may yet arise out of the realm of brane-world scenarios . For sake of definiteness, let us now outline a particular form of brane-world model, as inspired by Randall and Sundrum , which will be adhered to throughout the paper. In the scenario of interest, our physical universe is regarded as a 3+1-dimensional hypersurface, or 3-brane, immersed in a 4+1-dimensional anti-dS bulk spacetime (with any additional dimensions having been compactified to string-length scale). We also follow the usual convention of confining all standard-model particles to the brane except for the graviton. In compliance with the observed cosmological constant , we further stipulate a non-critical brane with positive curvature.222Although the graviton propagates freely into the bulk, it has been shown that gravity will typically remain localized even when the brane is curved . Furthermore, following Kraus , we take the viewpoint of a brane that flows through an otherwise static, black hole bulk.

Given the above framework, there are a couple of points of interest that should be kept in mind. Firstly, the brane dynamics will effectively describe the cosmological evolution of the universe. That is to say, from the perspective of an observer, the motion of the brane will appear as either a cosmological contraction or expansion. Secondly, the (effective) cosmological constant on the brane can be expressed in terms of a pair of bulk parameters; namely, the anti-dS curvature radius and the brane tension. In this sense, the cosmological constant can be regarded as an input parameter , rather than a variable quantity of the lower-dimensional gravity theory.

One might well query as to how this brane-world interpretation could possibly address the difficulties associated with a quantum formulation of dS gravity. The answer lies in the notion of a physical universe that can now be holographically viewed in an anti-dS framework . As discussed earlier, the quantum-gravitational aspects of anti-dS spacetimes are much better understood than their dS counterparts. Hypothetically speaking, one could obtain a string-theoretical description of the $`5`$-dimensional bulk spacetime and then apply the anti-dS/CFT duality to translate this theory onto the brane . Although, admittedly, such a prospect remains somewhat speculative at the present time.

In the current treatment, we investigate the above brane-world scenario for the intriguing case of a charged (anti-dS) black hole in the bulk. Before discussing the content of this paper, let us take note of some recent works of relevance. First of all, Petkou and Siopsis  considered the cosmological and holographic implications of a brane world evolving in the background of an anti-dS Schwarzschild black hole. This study was subsequently generalized by the present author  to include “topological” anti-dS black holes . That is, Schwarzschild-like black holes (static with a constant-curvature horizon), but having an arbitrary horizon topology (flat, hyperbolic or spherical).

More recently, Mukherji and Peloso  have considered topological anti-dS black holes with a finite electrostatic charge (i.e., Reissner-Nordstrom-like).333For some earlier studies and discussion on brane cosmology with a bulk charge, see . These authors focused their analysis on a critical brane (i.e., the effective cosmological constant is fine tuned to vanish); although they briefly touched upon the qualitative features of a non-critical brane scenario as well. In the program to follow, we elaborate on this last case of a non-critical (positively curved) brane evolving in a charged black hole background. Along with the switch in emphasis (from critical to non-critical), the current study substantially deviates from  in the following manner: we come here not to praise charged black hole bulks but, rather, to bury them.

The remainder of the paper is organized as follows. In Section 2, we introduce the relevant formalism; including the bulk solutions of interest (topological anti-dS black holes with charge) and the equation of motion for the brane. Notably, this equation mimics the Friedmann equation for radiative matter, along with an additional exotic form of matter. This latter contribution, which only arises when the bulk solution has a finite charge, can be identified as stiff matter with a negative-energy density .

In Section 3, we consider the cosmological implications for a certain class of solutions of the priorly mentioned Friedmann equation. Although explicit analytical expressions are out of our reach, it is still possible to describe the cosmologies of interest. Here, we appeal to asymptotic regimes for which the relevant solutions have already been formulated . In this process, we observe that a non-vanishing charge in the bulk (even an arbitrarily small one) generally induces a FRW “bounce” universe; that is, asymptotically dS and devoid of singularities.444For general discussion on Friedmann-Robertson-Walker (FRW) bounce cosmologies, see . For a recent, topical study, from both a brane-world and string-theoretical perspective, see . Conversely, for the class of solutions under investigation, a vanishing charge implies a singular spacetime; either a “big bang” or a “big crunch”.

In Section 4, we consider the holographic implications of the charged-induced bounce cosmologies. More precisely, we calculate their generalized $`c`$-functions  (as prescribed for renormalization group flow in an asymptotically dS spacetime ) and then determine how these functions evolve in time. On the basis of this analysis, we deduce that any such bounce cosmology, although free of singularities, is of an unphysical nature. We attribute this failure to the exotic, negative-energy matter that is induced by the bulk charge. Here, we note that similar failures have been observed when negative-energy matter is introduced into an otherwise purely dS spacetime .

Finally, Section 5 contains a summary and considers future prospects.

## 2 Brane-World Scenario

The formal interest of this paper is a Randall-Sundrum  type of brane-world scenario; more specifically, a 3+1-dimensional brane (of positive tension) moving in a 4+1-dimensional bulk spacetime that is otherwise static. Furthermore, we will assume that the bulk geometry is described by an anti-dS black hole with an electrostatic charge and a constant-curvature horizon. The relevant black hole solutions can be regarded as “Reissner-Nordstrom-like”, but with an arbitrary horizon topology.

The solutions in the anti-dS bulk can thus be expressed as follows :

$$ds_5^2=f(r)dt^2+\frac{1}{f(r)}dr^2+r^2d\mathrm{\Omega }_{k,3}^2,$$
(1)
where:

$$f(r)=\frac{r^2}{L^2}+k\frac{\omega M}{r^2}+\frac{3\omega ^2Q^2}{16r^4},$$
(2)
$$\omega =\frac{16\pi G_5}{3𝒱}.$$
(3)
Here, $`d\mathrm{\Omega }_{k,3}^2`$ denotes the line element of a 3-dimensional constant-curvature (Euclidean) hypersurface, $`𝒱`$ is the dimensionless volume of this hypersurface, $`L`$ is the curvature radius of the anti-dS bulk (i.e., $`\mathrm{\Lambda }_5=3/L^2`$ is the bulk cosmological constant) and $`G_5`$ is the 5-dimensional Newtonian constant. There are also three constants of integration in this solution: $`k`$, $`M`$ and $`Q^2`$. Without loss of generality, $`k`$ can be set equal to +1, 0 or -1; describing a horizon geometry that is respectively spherical (i.e., the anti-dS Reissner-Nordstrom case), flat or hyperbolic. Meanwhile, $`M`$ and $`Q^2`$ respectively measure the conserved mass and the electrostatic charge (squared) of the black hole; with these being regarded as strictly non-negative quantities.555It should be noted that the $`k=1`$ hyperbolic solution supports a negative value for the mass . However, this controversial scenario will be disregarded, on the grounds that a negative-mass black hole probably induces a non-unitary boundary theory .

Note that the existence of a pair of positive, real horizons or non-extremal black hole solution (as we assume to be the case in this analysis) depends on, in general, a sufficiently large value of $`L^2`$ and, for $`k=+1`$, a sufficiently small value of $`Q^2`$ (in fact, $`Q^2<4M^2/3`$).666One can verify these claims by solving for the roots of Eq.(2). These roots, of course, locate the positions of the horizons. To be definite, we will assume that $`M`$ is “large” (with $`L^2`$ always taking on a large enough value to compensate) and $`Q^2`$ is “small”. More precisely, we henceforth limit the following dimensionless parameters: $`\stackrel{~}{M}>1`$ (where $`\stackrel{~}{M}M`$ is defined below) and $`ϵ^23Q^2/4M^2<1`$ (and, typically, $`ϵ^2<<1`$). That is, the black hole of interest is appropriate for a semi-classical regime and has a small (but non-vanishing) electrostatic charge.

As demonstrated elsewhere (for instance, ), if one considers an evolving brane in an otherwise static bulk, the dynamics of the brane will mimic that of a FRW universe . Here, we will skip the gory details (see  for a recent presentation) and simply quote the results.

As it so happens, the induced metric on the brane can be expressed in the following FRW form:

$$ds_4^2=d\tau ^2+r^2(\tau )d\mathrm{\Omega }_{k,3}^2,$$
(4)
where $`\tau `$ measures the physical time from the point of view of a brane observer and $`r`$ is the time-dependent cosmological scale factor. Moreover, the corresponding Friedmann equation is found to be as follows:

$$H^2=\frac{\mathrm{\Lambda }_4}{3}\frac{k}{r^2}+\frac{\omega M}{r^4}\frac{\omega ^2M^2ϵ^2}{4r^6},$$
(5)
where $`H\dot{r}/r`$ is the usual Hubble “constant” (with a dot denoting differentiation with respect to $`\tau `$) and $`\mathrm{\Lambda }_4`$ is the effective cosmological constant on the brane. In achieving this form, we have invoked the following defining relation:

$$\mathrm{\Lambda }_43\left[\left(\frac{\sigma }{3}\right)^2\frac{1}{L^2}\right],$$
(6)
where $`\sigma `$ represents the tension of the brane (see  for a precise definition).

To touch base with the status of our own universe , we will assume that $`\mathrm{\Lambda }_4`$ takes on a relatively small, positive value. From a brane-world standpoint, this translates into a non-critical, positively curved brane universe.777Traditionally, the Randall-Sundrum brane-world scenario  assumes a fine tuning of the brane tension so that $`\mathrm{\Lambda }_4`$ vanishes; that is, a critical brane. However, there is no a priori rationale for this choice of brane tension, and we note some prior studies  that have considered the dynamics of a non-critical brane. Note that the horizon geometry of the black hole (i.e., the choice of $`k`$) directly determines the topology of the spatial slicing in the brane universe.

The above form (5) can, in fact, be identified with the 4-dimensional Friedmann equation for radiative matter (since $`\rho _{rad}r^4`$, where $`\rho `$ denotes energy density) along with an exotic matter contribution by virtue of the $`r^6`$ term. This latter contribution can be identified with stiff matter (which is defined by $`p_{sti}=\rho _{sti}`$, where $`p`$ denotes pressure) . What makes this holographic stiff matter all the more intriguing is its negative prefactor in Eq.(5); thus implying that $`\rho _{sti}<0`$. Although negative-energy matter is typically frowned upon, as it directly violates any number of positive-energy conditions , we note that such conditions have their foundation in technical convenience rather than fundamental arguments . That is to say, it is still too early in the game to base the physical status of a theory on this criteria alone. Hence, we will keep an open mind (for the time being) and go on to consider the implications of including this exotic matter.

Although we have clearly established a brane-world pedigree for the relevant cosmological equation (5), one can bypass the brane description altogether and view this picture from a strictly 4-dimensional sense. That is to say, one may regard Eq.(5) as the Friedmann equation for a toy cosmological model; namely, a model universe that contains radiative matter, exotic stiff matter and a positive cosmological constant. From this perspective, one can view the current work as another chapter in “How not to construct an asymptotically de Sitter universe” .

## 3 FRW Cosmology on the Brane

Ideally, we would like to obtain an analytical solution to Eq.(5) for reasonably generic circumstances. Although this does not seem to be possible, it is still instructive to consider the asymptotic limits (i.e., very large or very small $`r`$) for which (approximate) analytic expressions are indeed obtainable. As it turns out, the asymptotic behavior of the scale factor is, by itself, sufficient for our current purposes.

First, let us consider the solutions for the special circumstance of vanishing charge (i.e., $`Q^2`$ or $`ϵ^2=0`$). For this special case, we turn to a recent work  (also see ) and quote the relevant expressions for all three choices of $`k`$:
(i) $`k=+1`$:

$$r^2=\frac{1}{2^2}\left(1+\sqrt{\stackrel{~}{M}1}\mathrm{sinh}\left[\pm 2(\tau \tau _o)\right]\right).$$
(7)
(ii) $`k=0`$:

$$r^2=\frac{\sqrt{\stackrel{~}{M}}}{2^2}\mathrm{sinh}\left[\pm 2\tau \right].$$
(8)
(iii) $`k=1`$:

$$r^2=\frac{1}{2^2}\left(\sqrt{\stackrel{~}{M}1}\mathrm{sinh}\left[\pm 2(\tau \tau _o)\right]1\right).$$
(9)
Here, we have incorporated the following definitions: $`^2\mathrm{\Lambda }_4/3`$, $`\stackrel{~}{M}4\omega M^2`$, and $`\tau _o`$ is a constant of integration that can always be chosen so that $`r^2`$ vanishes at $`\tau =0`$ (for sake of convenience). Keep in mind that we have assumed $`^2`$ to be positive and $`\stackrel{~}{M}>1`$. (Solutions for other choices of $`\stackrel{~}{M}`$ are given in .)

Some discussion on the above solutions is in order. Each solution describes a FRW universe that either begins at a “big bang” or ends at a “big crunch”, depending on the choice of sign in the hyperbolic argument (positive or negative, respectively). These two scenarios are effectively equivalent, by way of time-reversal symmetry, so it is sufficient to illustrate just the big bang universe. In this case, the brane world “comes into existence” at $`\tau =0`$, where $`r=0`$ and the curvature can be shown to diverge. As time proceeds, the scale factor monotonically increases and ultimately describes an asymptotically dS universe ($`re^\tau `$) in the far future ($`\tau \mathrm{}`$). It is interesting to note that the asymptotic solution is essentially ignorant of the details of the bulk geometry.

What makes the above solutions particularly significant is their general validity for very large values of $`r`$ (or, equivalently, large values of $`|\tau |`$). In this regime, we can neglect the effects of charge, given that the charge term in Eq.(5) falls off rapidly ($`r^6`$) as the scale factor increases. Hence, as long as there is no singularity in the spacetime (which is always, as shown below, to be true for non-vanishing charge), the scale factor must asymptotically approach the above forms in either the distant past or far future.888Note that the sign in the hyperbolic functions should always be suitably chosen to ensure $`r^2>0`$.

Next, let us consider the solutions for another special case; namely, $`\mathrm{\Lambda }_4=0`$ or a critical brane. For these solutions, we turn to a recent analysis by Mukherji and Peloso . These authors obtained the following results:
(i) $`k=+1`$:

$$r^2=\frac{\omega M}{2}\left(1\sqrt{1ϵ^2}\mathrm{cos}\left[2\eta \right]\right).$$
(10)
(ii) $`k=0`$:

$$r^2=\frac{\omega M}{4}\left(ϵ^2+4\eta ^2\right).$$
(11)
(iii) $`k=1`$:

$$r^2=\frac{\omega M}{2}\left(\sqrt{1+ϵ^2}\mathrm{cosh}\left[2\eta \right]1\right).$$
(12)
Note that the above have been expressed in terms of conformal time, $`\eta `$, which is defined according to $`d\tau =rd\eta `$. Also note that $`ϵ^2>0`$ has been assumed.

A very interesting feature of these critical solutions is that they all have a non-vanishing minimum value for the scale factor (which occurs in the above forms, by way of arbitrary convention, precisely at $`\eta =0`$). That is to say, as long as the charge is non-vanishing, a singularity will certainly be avoided. To put it another way, these critical solutions all “bounce” (at least) at the surface of vanishing time. In fact, the $`k=+1`$ solution bounces, by virtue of its periodicity, an infinite number of times.

As for the prior case of vanishing charge, the special nature of a critical brane belies the generality of the above solutions. On inspecting the Friedmann equation (5), we see that, for small enough values of the scale factor, the $`\mathrm{\Lambda }_4`$ term will make a negligible contribution. More to the point, $`\mathrm{\Lambda }_4`$ is a finite-valued constant, whereas all the other terms in Eq.(5) increase rapidly as the scale factor decreases. Hence, any relevant solution must asymptotically approach the above forms (10-12) as $`\eta `$ goes to zero. Therefore, given a bulk black hole with a non-vanishing charge, there will always be a non-vanishing minimum for the scale factor on the brane. In fact, this singularity-free status holds up for arbitrarily small values of $`ϵ^2Q^2`$.

In spite of the conspicuous absence of a generic analytical solution, we are now in a position to say something about the brane cosmologies of interest (i.e., those with $`\mathrm{\Lambda }_4>0`$, $`1>ϵ^2>0`$, and $`\stackrel{~}{M}>1`$). It is clear that, for at least the cases of a flat ($`k=0`$) and open ($`k=1`$) brane universe, the scale factor will have an asymptotically dS form in the distant past, contract to a non-vanishing minimum at $`\tau =0`$, and then expand towards an asymptotically dS future. Such a cosmological scenario is often said to describe a FRW bounce universe. The closed-universe ($`k=+1`$) case is, however, not so clear. It is not evident whether the scale factor, after its initial bounce, will oscillate between a maximal and minimal value (as suggested by Eq.(10)), or manage to “escape” towards an asymptotically dS future (as implied by Eq.(7)). The ultimate outcome depends, in all likelihood, on the relative values of the model-dependent parameters; in particular, $`M`$ and $`\mathrm{\Lambda }_4`$. One can imagine that, for a sufficiently small value of $`M`$, the vacuum energy will dominate and an exponential expansion will ensue. Conversely, if $`M`$ is above some threshold value, one might expect that the radiative matter wins out and the brane universe eternally oscillates. It would be interesting to verify the existence (or lack thereof) of such a threshold value; however, a numerical analysis is almost certainly required.

It is quite interesting that even an arbitrarily small amount of negative-energy matter can have such a dramatic effect on the underlying cosmology. When the bulk charge is precisely vanishing (i.e., no exotic matter on the brane), a bounce cosmology will never be possible; assuming that $`\stackrel{~}{M}>1`$ has also been enforced.999In fact, for vanishing charge, a closed brane universe can only bounce if $`\stackrel{~}{M}<1`$  and an open/flat universe will only bounce if $`\stackrel{~}{M}=0`$ . That is, under these conditions, a singular surface (either a big bang or big crunch) is an inevitable feature of the spacetime manifold. Conversely, after introducing arbitrarily small amounts of negative energy onto the brane, we find that the universe is regular throughout and (in most cases) has both an asymptotically dS past and future.

On some intuitive level, the above outcome is not particularly surprising. Regardless of how small (a non-vanishing) $`ϵ^2`$ is chosen to be, it is clear from the Friedmann equation (5) that the negative-energy term will dominate at sufficiently small values of the scale factor (thanks to the $`r^6`$ factor in this stiff-matter term). Hence, as the brane universe contracts towards $`r=0`$, the negative-energy matter must, at some point, take over and create a significant repulsive force; thus preventing the otherwise inevitable collapse of the spacetime.

In spite of the ambiguous status  of the various positive-energy conditions , one might be troubled by a universe that is dominated by negative-energy matter at some time in its evolution. Moreover, the resilient nature of these bounce cosmologies is most puzzling, insofar as any asymptotically dS spacetime should have an upper bound on its observable entropy ( and see Section 1). That is to say, there is clearly no upper limit on the size of $`M`$ and, hence, presumably no bound on the amount of entropy that can be “pumped” onto the brane. Therefore, at least naively, one would expect that the dS entropy bound can easily be violated.

Fortunately, these unsettling matters can still be resolved without bringing the positive-energy conditions or entropic upper bound directly into play. For this purpose, we next call on our old friend, holography.

## 4 Holographic Interpretation

Essential to the following analysis is the concept of holographically induced renormalization group (RG) flows. Let us, therefore, give a brief account of this phenomenon.

Firstly, we consider RG flows as they apply to the well-known anti-dS/CFT correspondence . In this anti-dS context, it has been established that the monotonic evolution of a relevant bulk parameter induces a “flow” in the renormalization scale of the dual boundary theory, and vice versa. (Keep in mind that this renormalization scale determines the ultraviolet cutoff or, equivalently, the lattice spacing of the boundary theory.) This framework follows, in large part, from the so-called ultraviolet/infrared correspondence . That is, high (low) energies in the boundary theory translate into large (small) distances in the anti-dS bulk.

Significant to any RG flow is the existence of a generalized $`c`$-function. Such a function follows, by way of analogy, with the $`c`$-function of a 2-dimensional CFT . For anti-dS holography in particular, any such $`c`$-function is expected to exhibit various monotonicity properties that are reflective of the ultraviolet/infrared duality. For further pertinent discussion, see (for instance) .

Next, we will extend the above discussion to a dS holographic framework. It is first worth recalling that, in analogy to anti-dS holography, a dS spacetime has been conjectured to have a dually related boundary theory .101010For the pathway to other literature on this subject matter, see Section 1. Such a boundary theory, if it does exist, would presumably be a Euclidean CFT that lives at one or both of past and future infinity. On the other hand, the dS/CFT correspondence is not without its detractors (most notably, 111111And for the inevitable counter-argument, see .). However, in spite of the unclear status of this duality, there is little doubt that many aspects of anti-dS holography do indeed translate over to a dS setting; including RG flows.

Let us now (finally!) focus on RG flows in a dS context. As observed by Strominger  (also see ), time evolution in a purely dS spacetime will generate conformal-symmetry transformations on its asymptotic spacelike boundaries. However, this conformal symmetry will be broken if the spacetime is “demoted” to being only asymptotically dS. On the basis of these observations, the author went on to argue that time evolution (in an asymptotically dS universe) will naturally induce a RG flow between a pair of conformal fixed points. These fixed points occur in the asymptotic past and future when the symmetries of pure dS space ultimately re-emerge. Moreover, in analogy to anti-dS holography, Strominger proposed an associated $`c`$-function of the form:

$$c\left|\left(\frac{\dot{r}(\tau )}{r(\tau )}\right)^{(n1)}\right|,$$
(13)
where $`r`$ is the FRW scale factor, a dot denotes differentiation with respect to cosmological time ($`\tau `$), and $`n+1`$ is the spacetime dimensionality.

Significantly to its status as a legitimate $`c`$-function, the above form does indeed exhibit appropriate monotonicity properties . In particular, $`c`$ flows to the ultraviolet (infrared) - that is, increases (decreases) - for an expanding (contracting) universe.

One issue of concern is that Eq.(13) can only be applied to a FRW spacetime with flat spatial slices (i.e., $`k=0`$). Nonetheless, the above form of $`c`$ has since been generalized so that all choices of spatial slicing can indeed be utilized .121212In particular, Leblond et al  proposed the generalized form and verified the appropriate monotonic behavior, while Kristjansson and Thorlacious  provided a geometrical interpretation by identifying $`c`$ with the area of an apparent horizon. This generalization can be expressed as follows:

$$c\left(\frac{r^2(\tau )}{k+\dot{r}^2(\tau )}\right)^{(n1/2)},$$
(14)
where $`k`$ is the usual FRW topological parameter. It is easy to see that this form reduces to the prior one when $`k=0`$.

To reclarify, $`c`$ is expected to increase if the universe is expanding and decrease if the universe is contracting. An interesting technical issue is the application of this “$`c`$-theorem” to a bounce universe, as such a cosmology obviously has both an expanding and a contracting phase. In this sense, one is forced to abandon the conventional wisdom that a $`c`$-function should evolve in a strictly monotonic fashion. (For further discussion on this caveat, see .)

By this time, the reader may be wondering as to the point of this minor dissertation on holographic RG flows and the like. Well, as it so happens, RG flows have recently been utilized (specifically by McInnes ; also see ) to expose certain types of bounce cosmologies as being physically unacceptable. Interestingly, these charlatan cosmologies also contain negative-energy matter. However, unlike the current study, no other form of matter was included (besides a cosmological constant). In spite of this fundamental difference, we will proceed to show that the same debilitating argument applies here as well.

For sake of calculational simplicity, let us consider the case of an open brane universe or flat-horizon black hole (i.e., $`k=0`$). We will restrict considerations to the expanding phase ($`\tau `$ or $`\eta >0`$), as time-reversal symmetry enables one to choose either expansion or contraction without loss of generality. First of all, let us focus on the large $`r`$ (or late time) solution, as presented in Eq.(8). Substituting this result into the above form of the $`c`$-function (14), we find that:

$$c\frac{\mathrm{sinh}^2\left[2(\tau \tau _o)\right]}{\mathrm{cosh}^2\left[2(\tau \tau _o)\right]},$$
(15)
where we have set $`n=3`$ and neglected any irrelevant constant factors.

Our primary objective is to ascertain how $`c`$ responds to temporal variations. Given the generic positivity of the $`c`$-function, it is sufficient (and considerably simpler) to consider variations in $`\mathrm{ln}[c]`$. Again neglecting constant (positive) factors, we have:

$$\frac{\mathrm{ln}[c]}{\tau }=\frac{1}{\mathrm{sinh}\left[4(\tau \tau _o)\right]}>0.$$
(16)
Evidently, this expression satisfies the expectations of the $`c`$-theorem; namely, $`c`$ should monotonically increase with time during an expanding phase of the universe.

Next, let us consider the small $`r`$ (or small $`|\tau |`$) solution, as documented in Eq.(11). Before proceeding, we should first re-express the $`c`$-function (14) in a form that is directly compatible with the conformal-time variable, $`\eta `$. That is:

$$c\left(\frac{r^4(\eta )}{kr^2(\eta )+\left[r^{}(\eta )\right]^2}\right)^{(n1/2)},$$
(17)
where a prime indicates differentiation with respect to conformal time.

Substituting Eq.(11) into the above, we obtain:

$$c\frac{1}{\eta ^2}\left(ϵ^2+4\eta ^2\right)^3.$$
(18)
Again varying the logarithm (and recalling that $`\eta >0`$ has, without loss of generality, been assumed), we find that:

$$\frac{\mathrm{ln}[c]}{\eta }=\frac{12\eta }{ϵ^2+4\eta ^2}\frac{1}{\eta }.$$
(19)
It is difficult to make sense of this result, until we remember that this asymptotic solution (11) is only strictly valid for vanishingly small values of $`\eta `$. Hence, it is most appropriate to consider the limit of $`\eta 0_+`$, in which case:

$$\frac{\mathrm{ln}[c]}{\eta }\frac{1}{0_+}<0.$$
(20)
This time around, we observe a direct violation of the relevant $`c`$-theorem. That is, for small values of $`r`$, $`c`$ monotonically decreases with time during an expanding phase of the universe. This outcome implies that time flows in the “wrong” direction when the brane universe is small; assuming that Strominger’s interpretation \- time evolution is dual with a RG flow to the ultraviolet  \- should be taken literally.

Before elaborating on this curious behavior, we point out that the above qualitative features will naturally persist for both the closed ($`k=+1`$) and open ($`k=1`$) brane-universe scenarios. This realization follows from an inspection of Eq.(5), from which it is clear that the topological ($`k`$) term will not play a significant role in either asymptotic regime.

Generally speaking, a violation in the $`c`$-theorem, although definitely a “red-flag”, should not necessarily be regarded as an unphysical outcome. In support of this claim, we point out that dS holography is not particularly well understood (not in comparison to its anti-dS analogue), and it remains uncertain as to how literally its predictions should be interpreted. Moreover, the validity of the $`c`$-theorem depends on the assumption of the “weak energy condition” , which will certainly be violated whenever negative-energy matter is dominant. (For our brane model, this domination occurs when the universe is small.) With this caveat in mind, one could well have anticipated the observed failure of the $`c`$-theorem at small values of $`r`$. To put it another way, the preferred direction of time flow is not particularly clear until the second law of thermodynamics can somehow be invoked.

In spite of this attempt at spin-doctoring, there remains a pressing concern that cannot, quite so easily, be argued away: not only does time apparently flow in the wrong direction, but it actually reverses direction at some point in the evolution of the universe. That is, the $`c`$-function flows to the infrared when the universe is small but ends up flowing to the ultraviolet at some later time. Such a “phase transition” in the $`c`$-function131313This behavior seems oddly reminiscent of the Hawking-Page anti-dS phase transition . It may be of interest to investigate this possible analogy; however, such a line is impeded by our lack of a solution for the non-asymptotic universe. does not appear to be compatible with any interpretation of holographic RG flows; taken literally or otherwise. That is to say, we can perhaps tolerate a RG flow that reverses direction at a bounce, but not one that reverses direction while the universe is in the process of expanding (or contracting).

In view of the preceding discussion, we are forced to conclude that these bounce cosmologies with exotic stiff matter are physically unacceptable on holographic grounds. Moreover, from a brane-world perspective, this failure implies that a bulk black hole should be prohibited from acquiring an electrostatic charge.

## 5 Conclusion

In summary, we have been studying the cosmological and holographic implications of a certain class of brane-world scenarios. To elaborate, we have focused on a non-critical (positively curved) 3-brane moving in an anti-dS background that is described by a Reissner-Nordstrom-like black hole. It should be noted that our analysis incorporated the topological variants of the “standard” (anti-dS) Reissner-Nordstrom solution; thus allowing for spherical, flat and hyperbolic horizon geometries.

We began the analysis by introducing the relevant bulk solutions and the equation of motion for the brane. It is significant that the form of the latter essentially mimics the Friedmann equation for radiative matter. Along with the radiative contribution (which is proportional to the mass of the bulk black hole) and an effective cosmological constant, this induced Friedmann equation contains an additional exotic form of matter. This exotic contribution, which is holographically induced by the bulk electrostatic charge, can be identified as stiff matter with a negative energy density. Also of interest, the horizon geometry of the black hole fixes the spatial topology of the brane universe.

In the next section of the analysis, we specifically considered bulk black holes with a relatively large mass and a relatively small (but non-vanishing) charge. The interest in this regime follows from prior studies on uncharged black holes in the bulk . These earlier treatments have indicated that a cosmological singularity is inevitable when the black hole mass exceeds a certain (topology-dependent) value. That is, under these conditions, the brane universe must either begin with a big bang or end in a big crunch.

Although the induced Friedmann equation is not generally solvable, we were still able to proceed by focusing on a pair of asymptotic regimes. In fact, the solutions for very large and very small values of the scale factor are known ( and , respectively), and these could be used to deduce the gross features of the relevant cosmologies (up to some ambiguity in the case of a closed brane universe). In precisely this manner, we have demonstrated that even an arbitrarily small charge (in the bulk) is sufficient to avoid a singularity in the brane universe. Rather than collapsing to a singularity (as is inevitable in the uncharged scenario), the brane universe either bounces towards an asymptotically dS future (as is always the case for a flat or open universe) or eternally oscillates between a maximal and minimal size.

In the final phase of our study, we investigated the charge-induced bounce cosmologies from a holographic perspective. More to the point, we calculated the generalized $`c`$-functions (as prescribed for dS-holographic RG flows ) in the asymptotic regimes and then tested these functions against the recommended $`c`$-theorem. Notably, this methodology was inspired by prior treatments  that revealed a violation of the $`c`$-theorem for a special class of bounce cosmologies. Significantly, these cosmologies also contain negative-energy matter.

Ultimately, in applying this litmus test, we have demonstrated that the charge-induced bounce cosmologies are of an unphysical nature. More precisely, when the universe is very small (and the negative-energy matter dominates), the associated $`c`$-function decreases as the universe expands; an outcome which is in direct violation of the $`c`$-theorem. Although one could still argue on how literally the $`c`$-theorem should be interpreted (given that the direction of time is perhaps ambiguous in a universe with built-in time-reversal symmetry), we pointed out an even more disturbing consequence of this calculation. Namely, the RG flow must reverse its direction, at some point, while the universe is expanding. (This follows from the behavior of the $`c`$-function in the other asymptotic regime, where it clearly increases as the universe expands.) Such a reversal is decidedly in conflict with the philosophical premise of holographic RG flows.

In view of the above arguments, we conclude that the charge-induced bounce universes are, indeed, unphysical cosmologies. Moreover, assuming the feasibility of brane-world scenarios in general, we suggest the necessity for censoring against charge in a bulk black hole.

Of course, the last declaration may be somewhat premature, inasmuch as we still have no direct knowledge of the non-asymptotic evolution. It would be interesting to identify the “reversal point” and better understand whatever mechanism is deviously at work. However, it would appear that such an investigation would require a numerical analysis. As an alternative to this unsettling proposition, one might consider the scenario of a 2-brane moving in a 4-dimensional charged black hole bulk. Although unphysical, this simpler model may have an analytical solution with similar features to that of the priorly studied case.

One might also extend the prior treatment by considering other FRW cosmologies that contain negative-energy matter (as well as a positive cosmological constant). Clearly, a pattern is arising: the presence of such exotic matter consistently leads to violations in the holographic $`c`$-theorem. On the other hand, the models so-far studied have a common feature; namely, the negative-energy matter dominates when the universe is very small. It may be of interest to construct an analytically solvable model in which this is not the case. Given the ambiguous status of the various positive-energy conditions , it would certainly be useful to ascertain their feasibility via such independent means. Naturally, we defer the above prospects to a future (cosmological or conformal) time.

## 6 Acknowledgments

The author would like to thank V.P. Frolov for helpful conversations.


text:
# A Statistical Measure of Complexity

Abstract

A measure of complexity based on a probabilistic description of physical systems is proposed. This measure incorporates the main features of the intuitive notion of such a magnitude. It can be applied to many physical situations and to different descriptions of a given system. Moreover, the calculation of its value does not require a considerable computational effort in many cases of physical interest.

PACS number(s): 05.20.-y, 02.50.+s, 02.70.+d

On the most basic grounds, an object, a procedure, or system is said to be ”complex” when it does not match patterns regarded as simple. This sounds rather like an oxymoron but common knowledge tells us what is simple and complex: simplified systems or idealizations are always a starting point to solve scientific problems. The notion of ”complexity” in physics  starts by considering the perfect crystal and the isolated ideal gas as examples of simple models and therefore as systems with zero ”complexity”. Let us briefly recall their main characteristics with ”order”, ”information” and ”equilibrium”.

A perfect crystal is completely ordered and the atoms are arranged following stringent rules of symmetry. The probability distribution for the states accessible to the perfect crystal is centered around a prevailing state of perfect symmetry. A small piece of ”information” is enough to describe the perfect crystal: the distances and the symmetries that define the elementary cell. The ”information” stored in this system can be considered minimal. On the other hand, the isolated ideal gas is completely disordered. The system can be found in any of its accessible states with the same probability. All of them contribute in equal measure to the ”information” stored in the ideal gas. It has therefore a maximum ”information”. These two simple systems are extrema in the scale of ”order” and ”information”. It follows that the definition of ”complexity” must not be made in terms of just ”order” or ”information”.

It might seem reasonable to propose a measure of ”complexity” by adopting some kind of distance from the equiprobable distribution of the accessible states of the system. Defined in this way, ”disequilibrium” would give an idea of the probabilistic hierarchy of the system. ”Disequilibrium” would be different from zero if there are privileged, or more probable, states among those accessible. But this would not work. Going back to the two examples we began with, it is readily seen that a perfect crystal is far from an equidistribution among the accessible states because one of them is totally prevailing, and so ”disequilibrium” would be maximum. For the ideal gas, ”disequilibrium” would be zero by construction. Therefore such a distance or ”disequilibrium” (a measure of a probabilistic hierarchy) cannot be directly associated with ”complexity”.

In figure 1. we sketch an intuitive qualitative behaviour for ”information” $`H`$ and ”disequilibrium” $`D`$ for systems ranging from the perfect crystal to the ideal gas. This graph suggests that the product of these two quantities could be used as a measure of ”complexity”: $`C=HD`$ (Fig. 1.). The function $`C`$ has indeed the features and asyntotical properties that one would expect intuitively: it vanishes for the perfect crystal and for the isolated ideal gas, and it is different from zero for the rest of the systems of particles. We will follow these guidelines to establish a quantitative measure of ”complexity”.

Before attempting any further progress, however, we must recall that ”complexity” cannot be measured univocally, because it depends on the nature of the description (which always involves a reductionist process) and on the scale of observation. Let us take an example to illustrate this point. A computer chip can look very different at different scales. It is an entangled array of electronic elements at microscopic scale but only an ordered set of pins attached to a black box at a macroscopic scale.

We shall now discuss a measure of ”complexity” based on the statistical description of systems. Let us assume that the system has N accessible states $`\{x_1,x_2,\mathrm{},x_N\}`$ when observed at a given scale. We will call this an N-system. Our understanding of the behaviour of this system determines the corresponding probabilities $`\{p_1,p_2,\mathrm{},p_N\}`$ (with the condition $`_{i=1}^Np_i=1`$) of each state ($`p_i0`$ for all $`i`$). Then the knowledge of the underlying physical laws at this scale is incorporated into a probability distribution for the accessible states. It is possible to find a quantity measuring the amount of ”information”. Under to the most elementary conditions of consistency, Shannon  determined the unique function $`H(p_1,p_2,\mathrm{},p_N)`$ that accounts for the ”information” stored in a system:

$$H=K\underset{i=1}{\overset{N}{}}p_i\mathrm{log}p_i$$
(1)
where $`K`$ is a positive constant. The quantity $`H`$ is called information. In the case of a crystal, a state $`x_c`$ would be the most probable $`p_c1`$, and all others $`x_i`$ would be very improbable, $`p_i0`$ $`ic`$. Then $`H_c0`$. On the other side, equiprobability characterizes an isolated ideal gas, $`p_i1/N`$ so $`H_gK\mathrm{log}N`$, i.e., the maximum of information for a N-system. (Notice that if one assumes equiprobability and $`K=\kappa Boltzmann`$ $`constant`$, $`H`$ is identified with the thermodinamic entropy ($`S=\kappa \mathrm{log}N`$)). Any other N-system will have an amount of information between those two extrema.

Let us propose a definition of disequilibrium $`D`$  in a N-system. The intuitive notion suggests that some kind of distance from an equiprobable distribution should be adopted. Two requirements are imposed on the magnitude of $`D`$: $`D>0`$ in order to have a positive measure of ”complexity” and $`D=0`$ on the limit of equiprobability. The straightforward solution is to add the quadratic distances of each state to the equiprobability as follows:

$$D=\underset{i=1}{\overset{N}{}}(p_i\frac{1}{N})^2$$
(2)
According to this definition, a crystal has maximum disequilibrium (for the dominant state, $`p_c1`$, and $`D_c1`$ for $`N\mathrm{}`$) while the disequilibrium for an ideal gas vanishes ($`D_g0`$) by construction. For any other system $`D`$ will have a value between these two extrema.

We now introduce the definition of complexity $`C`$ of a $`N`$-system. This is simply the interplay between the information stored in the system and its disequilibrium:

$$C=HD=\left(K\underset{i=1}{\overset{N}{}}p_i\mathrm{log}p_i\right)\left(\underset{i=1}{\overset{N}{}}(p_i\frac{1}{N})^2\right)$$
(3)
This definition fits the intuitive arguments. For a crystal, disequilibrium is large but the information stored is vanishingly small, so $`C0`$. On the other hand, $`H`$ is large for an ideal gas, but $`D`$ is small, so $`C0`$ as well. Any other system will have an intermediate behavior and therefore $`C>0`$.

As was intuitively suggested, the definition of complexity (3) also depends on the scale. At each scale of observation a new set of accessible states appears with its corresponding probability distribution so that complexity changes. Physical laws at each level of observation allow us to infer the probability distribution of the new set of accessible states, and therefore different values for $`H`$, $`D`$ and $`C`$ will be obtained. (In the most complicated situations, where there exist extremely many different states, there are methods to calculate functions of the probability distribution ). The passage to the case of a continuum number of states, $`x`$, is straighforward. Thus we must treat with probability distributions with a continuum support, $`p(x)`$, and normalization condition $`_{\mathrm{}}^+\mathrm{}p(x)𝑑x=1`$. Disequilibrium has the limit $`D=_{\mathrm{}}^+\mathrm{}p^2(x)𝑑x`$ and the complexity is defined by:

$$C=HD=\left(K_{\mathrm{}}^+\mathrm{}p(x)\mathrm{log}p(x)𝑑x\right)\left(_{\mathrm{}}^+\mathrm{}p^2(x)𝑑x\right)$$
(4)
Direct simulations of the definition give the values of $`C`$ for general N-systems. The set of all the possible distributions $`\{p_1,p_2,\mathrm{},p_N\}`$ where an N-system could be found is sampled. For the sake of simplicity $`H`$ is normalized to the interval $`[0,1]`$. This magnitude is called $`\overline{H}`$. Thus $`\overline{H}=_{i=1}^Np_i\mathrm{log}p_i/\mathrm{log}N`$. For each distribution $`\{p_i\}`$ the normalized information $`\overline{H}(\{p_i\})`$, and the disequilibrium $`D(\{p_i\})`$ (eq. 2) are calculated. In each case the normalized complexity $`\overline{C}=\overline{H}D`$ is obtained and the pair $`(\overline{H},\overline{C})`$ stored. These two magnitudes are plotted on a diagram $`(\overline{H},\overline{C}(\overline{H}))`$ in order to verify the qualitative behavior predicted in figure 1. For N=2 an analytical expression for the curve $`\overline{C}(\overline{H})`$ is obtained. If the probability of one state is $`p_1=x`$, that of the second one is simply $`p_2=1x`$. The complexity of the system will be:

$$\overline{C}(x)=\overline{H}(x)D(x)=\frac{1}{\mathrm{log}2}[x\mathrm{log}\left(\frac{x}{1x}\right)+\mathrm{log}(1x)]2(x\frac{1}{2})^2$$
(5)
Complexity as a function of $`\overline{H}`$ is shown in figure 2a. It vanishes for the two simplest 2-systems: the crystal ($`\overline{H}=0`$; $`p_1=1`$, $`p_2=0`$) and the ideal gas ($`\overline{H}=1`$; $`p_1=1/2`$, $`p_2=1/2`$). Let us notice that this curve is the simplest one that fulfills all the conditions discussed in the introduction. The largest complexity is reached for $`\overline{H}1/2`$ and its value is: $`C(x0.11)\overline{C}\mathrm{log}20.105`$. For N$`>`$2 the relationship between $`\overline{H}`$ and $`\overline{C}`$ is not univocal anymore. Many different distributions $`\{p_i\}`$ store the same information $`\overline{H}`$ but have different complexity $`\overline{C}`$. Figure 2b. displays such a behavior for $`N=3`$. If we take the maximum complexity $`\overline{C}_{max}(\overline{H})`$ associated with each $`\overline{H}`$ a curve similar to the one shown in a 2-system is recovered. Every 3-system will have a complexity below this line. In figure 2a. curves $`\overline{C}_{max}(\overline{H})`$ for the cases $`N=3,5,7`$ are also shown. Let us observe the shift of the complexity-curve peak to smaller values of entropy for rising $`N`$. This fact agrees with the intuition telling us that the biggest complexity (number of possibilities of ’complexification’) be reached for lesser entropies for the systems with bigger number of states.
Also it is possible to compute these quantities in other relevant physical situations and in continuum systems.

We can now go one a step further. The most important point is that the new definition should work in systems out of equilibrium. We use two examples of such systems where it is known that very complex dynamics could show up. They are the logistic map and the ’Lorenz’ map.
Logistic Map: The mapping $`x_{n+1}=\alpha x_n(1x_n)`$, $`\alpha [0,4]`$, is a well known chaotic system. There are two points in this system where the behaviour is extremely ”complex”. The first is the accumulation point of the subharmonic cascade. The second is the transition point from chaos to a period three orbit via intermittency . We are going to discuss and study the complexity in the second case only, which corresponds to parameter values around $`\alpha _t3.8284`$. Complexity must increase as $`(\alpha \alpha _t)0`$ when $`\alpha <\alpha _t`$ because the closer we get to the critical point $`\alpha _t`$ the more improbable and unpredictable is the firing and development of the intermittent bursts. On the contrary, when $`\alpha >\alpha _t`$ the system becomes periodic and does not have any complexity. Complexity  undergoes a rapid increase in the intermittency region and a sharp transition to zero at the transition point (Fig. 3a). (This resembles the curve of the specific heat as a function of temperature in a second order phase transition).
Lorenz Map: Let us consider a mapping that mimics the behavior and development of the Lorenz attractor. This is the simplest mapping that includes the main features of the first return map of this attractor: {$`x_{n+1}=\alpha x_n`$ if $`x_n<0.5`$ and $`x_{n+1}=\alpha (x_n1)+1`$ if $`x_n>0.5`$} where $`\alpha (0,2)`$. Its dynamic evolution displays three different behaviors: 1) $`R_1`$: $`\alpha (0,1)`$. The system goes to a fixed point ($`0`$ or $`1`$) and the output is a constant signal; 2) $`R_2`$: $`\alpha (1,2)`$. A variable chaotic attractor is present in all this region and a chaotic signal is obtained; 3) $`R_3`$ : $`\alpha 2`$. The Bernouilli-shift is reached and the output signal is random. Results for complexity are given in figure 3b. In region $`R_1`$, $`C`$ vanishes because there is nothing to explain a constant signal. In region $`R_2`$, $`C0`$ and shows a complicated dependence on $`\alpha `$. Variations in $`C`$ are due to changes in the structure of the underlying chaotic attractor. When $`\alpha 2`$ (region $`R_3`$) a random system is reached, and again $`C=0`$.

Let us return to the point at which we started the intitial discussion. Any notion of complexity in physics  should only be made on the basis of a well defined or operational magnitude. But two additional requirements are needed in order to obtain a good definition of complexity in physics: ($`c1`$) the new magnitude must be measurable in many different physical systems and ($`c2`$) a comparative relationship and a physical interpretation between any two measurements should be possible.

Many different definitions of complexity have been proposed to date, mainly in the realm of computational sciences. Among these, several can be cited: algorithmic complexity (Kolmogorov-Chaitin) , the Lempel-Ziv complexity , the logical depth of Bennett , the effective measure complexity of Grassberger , the complexity of a system based in its diversity , the thermodynamical depth , complexities of formal grammars, etc. The definition of complexity proposed in this work offers a new point of view, based on a statistical description of systems at a given scale. In this scheme the knowledge of the physical laws governing the dynamic evolution in that scale is used to find its accessible states and its probability distribution. This process would inmediately indicate the value of complexity. In essence this is nothing but an interplay between the information stored by the system and the distance from equipartition (measure of a probabilistic hierarchy between the observed parts) of the probability distribution of its accessible states . Besides giving the main features of a ”intuitive” notion of complexity, we showed that it sucessfully enables us to discern situations regarded as complex, both for a local transition (Fig. 3a.) and for a global behavior (Fig. 3b.) in systems out of equilibrium.

Acknowledgements: We thank Prof. C. Pérez-García from Universidad Privada de Navarra for useful comments and references. This research was funded by the DGICYT (Spanish Government) under grant PB-93-0708. One of us (R.L-R) thanks the French Government for a research grant.

Figure Captions

Fig 1. Sketch of the intuitive notion of the magnitudes of ”information” (H) and ”disequilibrium” (D) for the physical systems and the behavior intuitively required for the magnitude ”complexity”. The quantity $`C=HD`$ is proposed to measure such a magnitude.

Fig 2a. Complexity ($`\overline{C}=\overline{H}D`$) as a function of the information ($`\overline{H}`$) for a system with two accessible states ($`N=2`$). Also curves of maximum complexity ($`\overline{C}_{max}`$) are shown for the cases: $`N=3,5,7`$.

Fig 2b. In general, dependence of complexity ($`\overline{C}`$) on information ($`\overline{H}`$) is not univocal: many distributions $`\{p_i\}`$ can present the same value of $`\overline{H}`$ but different $`\overline{C}`$. This is shown in the case $`N=3`$.

Fig 3a. Behavior of complexity $`C`$ in the transition point ($`\alpha _t3.8284`$) where the system (logistic map) goes from a chaotic dynamics ($`\alpha <\alpha _t`$) to a period three orbit ($`\alpha >\alpha _t`$) by intermittency.

Fig 3b. Complexity displayed by the ’Lorenz’ map for a region of the parameter space $`\alpha [0,2]`$. (See explanation in the text). (Calculations have been done for a scale $`n=12`$, $`n`$ length of the binary strings analyzed).