Effect of quantum fluctuations on the coloring of random graphs

We present a study of the coloring problem (antiferromagnetic Potts model) of random regular graphs, submitted to quantum fluctuations induced by a transverse field, using the quantum cavity method and quantum Monte Carlo simulations. We determine the order of the quantum phase transition encountered at low temperature as a function of the transverse field and discuss the structure of the quantum spin-glass phase. In particular, we conclude that the quantum adiabatic algorithm would fail to solve efficiently typical instances of these problems because of avoided level crossings within the quantum spin-glass phase, caused by a competition between energetic and entropic effects.

Figure 1

Classical phase diagram of the coloring problem for $q_{\mathrm{col}}=4$ in the connectivity-temperature plane; see [48, 49] for the actual numerical values. The solid orange line separates the paramagnetic phase (P) from the dynamical paramagnet (dP) while the dashed blue line marks the boundary of the genuine spin-glass (SG) phase. The model is defined only for integer connectivities (indicated by squares and circles); lines serve as a guide to the eye. The connectivities $c_{\mathrm{d}}=9$ and $c_{\mathrm{K}},c_s=10$ are defined in the text. Pink arrows indicate the connectivities that will be studied in the quantum case.

Figure 2

Phase diagram of the coloring problem for $q_{\mathrm{col}}=4$ and $c=13$. The solid black line is the continuous transition line between the 1RSB spin-glass phase and the RS (quantum) paramagnetic phase. For numerical accuracy reasons we were not able to determine the continuation of the dynamical $T_{\mathrm{d}}$ and Kauzmann $T_{\mathrm{K}}$ transitions when $\Gamma >0$.

Figure 3

Results for the coloring problem for $q_{\mathrm{col}}=4$ and $c=13$. Left panel: Scaling form for the complexity upon approaching the third-order transition. The temperature is fixed to $T=0.06$, while $\Gamma$ is varied. Upon approaching the critical field ${\Gamma }_{\mathrm{i}}(T=0.06)=0.595$, the curves collapse. Note that the static value of $m$, $m_{\mathrm{s}}(T,\Gamma )$, at which the complexity $\Sigma (T,\Gamma ,m)$ vanishes is not singular in $\Gamma$ close to the transition. Right panel: Static value of the Parisi parameter divided by $T$, for various values of $T$. The dashed vertical line is the zero-temperature limit for the critical field, ${\Gamma }_{\mathrm{i}}(T=0)=0.598$. In the low-temperature limit, curves collapse. The black (red) dashed lines are fitted to $m_{\mathrm{s}}(T,\Gamma )/T$ for $T=0.06$ ($T=0.09$) near the critical field.

Figure 4

Left: Spinodal lines of the coloring problem for $q_{\mathrm{col}}=4$ and $c=9$. The orange line with squares is the dynamic transition line $T_{\mathrm{d}}\left(\Gamma \right)$, the black line with ticks is the continuous transition line $T_{\mathrm{i}}\left(\Gamma \right)$, and the red line with crosses is the line $T_{☆}\left(\Gamma \right)$. Lines are fits to the data which are shown as guides to the eye. Right: Sketches of the function $\varphi \left(m\right)$ corresponding to the RS and the two 1RSB solutions in the three regions defined by the intersections of the lines in the left panel. For instance, this would correspond to fixing $T=0.1$ and reducing $\Gamma$ from top to bottom.

Figure 5

Phase diagram of the coloring problem for $q_{\mathrm{col}}=4$ and $c=9$. In the left panel only the thermodynamic lines and the thermodynamic phases are reported. The right panel contains all the lines reported in the left panel as well as in Fig. 4; when two solutions of the cavity equations coexist, the stable one is underlined. The orange line with squares is the dynamic transition line $T_{\mathrm{d}}\left(\Gamma \right)$, the black line with ticks is the continuous transition line $T_{\mathrm{i}}\left(\Gamma \right)$, the red line with crosses is the line $T_{☆}\left(\Gamma \right)$, and the blue line with circles is the condensation transition $T_{\mathrm{K}}\left(\Gamma \right)$. Lines are fits to the data which are shown as guides to the eye. In addition, we report a purely conjectural shape of the first-order transition $T_{\mathrm{fo}}\left(\Gamma \right)$ as a purple full line. At large $\Gamma$, $T_{\mathrm{i}}\left(\Gamma \right)$ ends at ${\Gamma }_{\mathrm{i}}^{+}(T=0)\simeq 0.47$.

Figure 6

Transverse magnetization obtained by path-integral Monte Carlo simulations with $N=1000$ spins. All the simulations were started from the same planted state at $T=0$, and then run increasing $\Gamma$ at fixed $T$. The black line is the extrapolation at $T=0$, showing that $m_x^0\left(A\right)={\lim }_{\Gamma \to 0}{\lim }_{T\to 0}{m}_x(A,T,\Gamma )>0$.

Figure 7

Energy (left panel) and transverse magnetization (right panel) as functions of $\Gamma$ at fixed temperature $T=0.06$ for $q_{\mathrm{col}}=4$ and $c=9$. Quantum cavity computations are reported as blue solid lines, path-integral Monte Carlo simulations (for a single system of size $N=10000$) as dashed black lines with triangles, for both increasing and decreasing $\Gamma$. The inset of the left panel shows a zoom on the region of low $\Gamma$ where hysteresis is observed in the Monte Carlo simulation. The red arrow indicates the value of the classical energy (0.0019) that corresponds to a classical annealing starting from $T_{\mathrm{d}}$.

Figure 8

Energy (left panel) and transverse magnetization (right panel) as functions of $\Gamma$ at fixed temperature $T=0.06$ for $q_{\mathrm{col}}=4$ and $c=13$. Quantum 1RSB cavity computations are reported as blue solid lines, path-integral Monte Carlo simulations (for a single system of size $N=10000$) as dashed black lines with triangles, for both increasing and decreasing $\Gamma$; those obtained starting from $\Gamma =0$ were obtained after a slow thermal annealing of the system from $T_{\mathrm{d}}(\Gamma =0)$ [in this case, because $T_{\mathrm{K}}(\Gamma =0)$ is finite, it is not possible to use quiet planting at low temperature]; hence the small discrepancy in the energy for $\Gamma =0$ between the cavity computation and the Monte Carlo results. The (erroneous) replica-symmetric results (for the magnetization only) are shown in red with dash-dotted lines and circles; the absence of hysteresis around the transition ($\Gamma \simeq 0.56$) confirms that the first-order transition predicted by the RS computation is spurious.

Figure 9

Phase diagram of the spherical $p$-spin model for $p=3$ (all values of $p\ge 3$ are qualitatively similar). The dashed orange line corresponds to the dynamic transition, the solid blue one to the Kauzmann (condensation) transition line, and the dotted black one to the continuous transition line. SG refers to the 1RSB spin-glass phase, dP to the dynamical paramagnet (1RSB phase with $m=1$), and $P$ to the paramagnetic (RS) phase. The three lines meet at the point $(h_{\mathrm{c}},T_{\mathrm{c}})$. The orange dash-dotted line is the limit of coexistence of the two RS solutions, whose free energies cross at a spurious first-order phase transition not shown on this figure.

Figure 10

Scaling form of the complexity $\Sigma (\beta ,h,m)/\delta h^3$ of the spherical three-spin model for $\beta =1/0.3$ and $h=h_{\mathrm{i}}^{+}\left(\beta \right)-\delta h$. The solid black line was obtained from the analytical expansion given in Eq. (A14).

Figure 11

Study of the coexistence of two RSB solutions, for $T=0.55$ and a field $h=0.166$ in the narrow range $[h_{\mathrm{i}}^{-}\left(T\right)\simeq 0.1649,h_{☆}\left(T\right)\simeq 0.167]$ where the two RSB solutions have a common domain of existence $m\in [m_{\mathrm{hq}}^{\mathrm{sp}},m_{\mathrm{lq}}^{\mathrm{sp}}]$. For $T=0.55$ and $h=0.166$ the continuous solution exists for $m\in [0,m_{\mathrm{lq}}^{\mathrm{sp}}]$, with $m_{\mathrm{lq}}^{\mathrm{sp}}\simeq 0.48$, while the discontinuous one is defined for $m\in [m_{\mathrm{hq}}^{\mathrm{sp}},1]$, with $m_{\mathrm{hq}}^{\mathrm{sp}}\simeq 0.34$. Left: Complexity $\Sigma (\beta ,h,m)$ as a function of $m$. The discontinuous solution has the largest complexity in the domain of coexistence $[m_{\mathrm{hq}}^{\mathrm{sp}},m_{\mathrm{lq}}^{\mathrm{sp}}]$. Note that the complexity of the continuous solution is very small, but nonzero. The relevant value of the parameter $m$ for the thermodynamics, $m_{\mathrm{s}}(T,h)\simeq 0.77$ where the complexity vanishes, is outside the domain of existence of the continuous solution. Right: The potential $V(m,q_1)$ defined in Eq. (A15) as a function of $q_1$ for several values of $m$. The inset is a zoom near $q_1=q_0$, and the ticks indicate the replica-symmetric solution.

Figure 12

Scaling form (C1) for $\overline{q_1}=q_1-1/q_{\mathrm{col}}$, for $c=9$, $T=0.09$, and the small-field instability [${\Gamma }_{\mathrm{i}}^{-}(T=0.09)=0.08$] in the left panel, and the large-field instability [${\Gamma }_{\mathrm{i}}^{+}(T=0.09)=0.44$] in the right. The dotted lines are the linear asymptotics for the scaling functions $\mathcal{F}$; ${\Gamma }_{\mathrm{i}}^{\pm }$ have been adjusted to obtain the best data collapse.

Figure 13

Domains of existence of the solutions of the 1RSB equation for $c=9$, $T=0.09$, in the $(\Gamma ,m)$ plane. The $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution exists for $m\ge m_{\mathrm{hq}}^{\mathrm{sp}}\left(\Gamma \right)$, while the $1{\mathrm{RSB}}_{\mathrm{lq}}$ solution exists for $\Gamma \ge {\Gamma }_{\mathrm{i}}^{-}$ and $m\le m_{\mathrm{lq}}^{\mathrm{sp}}\left(\Gamma \right)$. The (extrapolated) intersection of $m_{\mathrm{hq}}^{\mathrm{sp}}\left(\Gamma \right)$ and $m_{\mathrm{lq}}^{\mathrm{sp}}\left(\Gamma \right)$ defines the point ${\Gamma }_{☆}$ at which the two 1RSB solutions merge into a single one. The region of coexistence is therefore delimited by ${\Gamma }_{\mathrm{i}}^{-}<\Gamma <{\Gamma }_{☆}$ and $m_{\mathrm{hq}}^{\mathrm{sp}}\left(\Gamma \right)<m<m_{\mathrm{lq}}^{\mathrm{sp}}\left(\Gamma \right)$. However, only the $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution is thermodynamically relevant: The value of $m_{\mathrm{s}}\left(\Gamma \right)$ is equal to 1 for $\Gamma <{\Gamma }_{\mathrm{K}}$, and it is smaller than 1 for $\Gamma >{\Gamma }_{\mathrm{K}}$, but it always correspond to the $1{\mathrm{RSB}}_{\mathrm{hq}}$ branch.

Figure 14

Complexity $\Sigma \left(m\right)$ for $c=9$, $T=0.09$, and $\Gamma =0.07$ (left), $\Gamma =0.1$ (middle), and $\Gamma =0.2$ (right). Results obtained with ${\mathcal{N}}_{\mathrm{pop}}=1200$ and ${\mathcal{N}}_{\mathrm{traj}}=3500$. The red points are obtained by decreasing $m$ from 1 down to 0, thus selecting the $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution, while the black points are obtained by increasing $m$ from 0, thus selecting the $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution (if any). Note the resemblance with Fig. 11. For this temperature, ${\Gamma }_{\mathrm{K}}\simeq 0.064$, ${\Gamma }_{\mathrm{i}}^{-}\simeq 0.08$, and ${\Gamma }_{☆}\simeq 0.25$. The left plot is for ${\Gamma }_{\mathrm{K}}<\Gamma <{\Gamma }_{\mathrm{i}}^{-}$; in this region there exists only the $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution with $\Sigma (m=1)<0$. For ${\Gamma }_{\mathrm{i}}^{-}<\Gamma <{\Gamma }_{☆}$ (middle and right panels) there exist two branches $1{\mathrm{RSB}}_{\mathrm{hq}}$ and $1{\mathrm{RSB}}_{\mathrm{lq}}$, which can be seen to merge when $\Gamma$ approaches ${\Gamma }_{☆}$. To find the thermodynamic solution, one has to maximize the free energy of the system, which amounts to enforce the condition $\Sigma \left(m\right)=0$ [or $\Sigma (m=1)>0$]: this condition always selects the $1{\mathrm{RSB}}_{\mathrm{hq}}$ solution.

Figure 15

Complexity of the 1RSB solution at $m=1$, for the coloring problem with $c=9$. Left panel: As a function of $\Gamma$ for $T=0.09$. Right panel: As a function of $T$ for $\Gamma =0.13$. No clear finite-size effect could be found so we report the data obtained with three large sizes. The black line is a quadratic fit on the ranges $\Gamma \in [0.02,0.12]$ (left panel), $T\in [0.14,0.17]$ (right panel), giving ${\Gamma }_{\mathrm{K}}(T=0.09)=0.063$ and $T_{\mathrm{K}}(\Gamma =0.13)=0.155$. The value of $T_{\mathrm{d}}$ is marked by an arrow.

Figure 16

Difference between the intra- and extracluster overlaps on the Kauzmann transition line for the spherical three-spin model (left panel) and the coloring problem with $q_{\mathrm{col}}=4$ and $c=9$ (right panel). The triple points $h_{\mathrm{c}}$ and ${\Gamma }_0$ are defined in the text and do not have the same interpretation in the two cases. Note that the $y$ axis does not start from zero in the right panel.

Figure 17

Coloring problem at $q_{\mathrm{col}}=4$, $c=13$, and $T=0.06$. Left panel: Internal overlap $\overline{q_1}(T,\Gamma ,m)$ for several $m$ as a function of $\Gamma$. The value of the continuous instability ${\Gamma }_i\left(T\right)$ is indicated by an arrow. For $m\ge 0.6$ (including the RS case $m=1$), hysteresis can be seen between the curves coming from high $\Gamma$ and those coming from small $\Gamma$; but this hysteresis disapppears for $m\le 0.5$, in particular for the static value $m_{\mathrm{s}}(T,{\Gamma }_{\mathrm{i}}\left(T\right))\simeq 0.13$. Right panel: Phase diagram in the $(\Gamma ,m)$ plane. The replica symmetry is broken on the left of the dashed black line, which represents the continuous instability of the RS solution. The high-overlap solution exists above the red line with squares, and the low-overlap one below the blue line with circles. These two lines meet at the value of $m$ below which no hysteresis remains. The relevant solution is always the low-overlap one; it becomes RSB for $\Gamma$ below the continuous instability shown as a vertical dashed black line. Finally, we also report in this region the static value of the Parisi parameter $m_{\mathrm{s}}(T,\Gamma )$.