1.1 Energy landscape

Before talking about the crystal structure, let us first consider the energy landscape for exploration. The number of distinct points on the landscape can be estimated as:

  $\displaystyle  C~ =~ \left( \begin{array}{cc} V/\delta ^3\\ N\\ \end{array} \right) \prod _{i}\left( \begin{array}{cc} N\\ n_ i\\ \end{array} \right)  $   (1)

where $N$ is the number of atoms in the unit cell of volume $V$, $\delta $ is a relevant discretization parameter (for instance, 1 ) and $n_ i$ is the number of atoms of $i$-th type in the unit cell. Even for small systems ($N\approx ~ 10-20$), $C$ is astronomically large (roughly 10$^ N$ if one uses $\delta $ = 1   and typical atomic volume of 10 $^3$).

The dimensionality of the energy landscape is:

  \begin{equation}  d = 3N+3 \end{equation}   (2)

where 3$N$ degrees of freedom are from $N$ atoms, and the remaining six dimensions are defined by the lattice. At the first sight, CSP is basically a NP-hard problem, and the difficulty increases exponentially with the dimensionality. Yet, great simplification can be achieved if structures are relaxed, i.e. brought to the nearest local energy minima. Relaxation could introduce some intrinsic chemical constraints (bond length, bond angle). Therefore, the intrinsic dimensionality can be reduced:

  \begin{equation}  d^* = 3N+3-\kappa \end{equation}   (3)

where $\kappa $ is the number of correlated dimensions, which could vary a lot according to the intrinsic chemistry in the system. For example, the dimensionality drops a lot from 99 to 11.6 for Mg$_{16}$O$_{16}$, while only a few from 39 to 32.5 for Mg$_4$N$_4$H$_4$. Thereby, the reduced complexity for the energy landscape of local minima is:

  \begin{equation}  C^* = \text {exp}(\beta d^*) \end{equation}   (4)
Figure 2.1: Simplified illustration of energy landscape. (a) the general landscape, (b) Golf-course like landscape. The landscape (a) could be transformed to a bowl like shape without noise by interpolating local minima point as shown in the solid line; but landscape (b) keeps the same shape

This implies that any efficient search method must include structure relaxation (local optimization). We also note that all the current global optimization methods must assume that the reduced landscape should have a overall shape (Fig. 2.1b) which could be optimized. Otherwise, for the extreme case like Golf-course like landscape (Fig. 2.1b), any global optimization methods would fail if the sampling space is not affordable.