Determining the asymptotic relaxation and mixing times of the worm process for the Ising model on critical boxes in $\mathbb{Z}^3$

The 2014 letter of Collevecchio, Garoni, Hyndman and Tokarev proved that the Prokof'ev–Svistunov (PS) worm algorithm for the zero-field ferromagnetic Ising model is rapidly mixing on all finite graphs at all temperatures, and explicitly posed the problem of determining the actual asymptotic behaviour of the relaxation time and mixing time in the specific setting of the critical boxes $\mathbb{Z}_L^3$, where a Li–Sokal-type lower bound of order $L^{d+\alpha/\nu}\approx L^{3.174}$ ($\approx n^{1.06}$, $n=L^3$) contrasts with polynomial upper bounds from the multicommodity-flow proof (improved from $O(n^7)$/$O(n^8)$ in the letter to $O(n^5)$/$O(n^6)$ in the 2016 journal version). No subsequent work determines, or even narrows, the gap for the Ising worm; numerics (Deng–Garoni–Sokal 2007) indicate the Li–Sokal bound is essentially tight in three dimensions, while in two dimensions power-law and $L^2\log^2 L$ scenarios remain undistinguished. The problem is therefore open. The companion direction named in the source's introduction — extending rigorous rapid-mixing results to worm processes for other statistical-mechanical models — has seen both positive partial results (a worm-based FPRAS for the four-vertex model) and negative ones (torpid mixing of worm-like chains for perfect matchings).

Background

The zero-field ferromagnetic Ising model on a finite connected graph $G=(V,E)$ with inverse temperature $\beta>0$ has Gibbs weight proportional to $\exp(\beta\sum_{uv\in E}\sigma_u\sigma_v)$ over spin configurations $\sigma\in\{-1,+1\}^V$. Setting the edge activity $x=\tanh\beta\in(0,1)$, its partition function and correlation functions admit the high-temperature expansion: configurations are represented by spanning subgraphs $A\subseteq E$ in which every vertex has even degree ("even subgraphs", also called Ising high-temperature graphs), each carrying weight $x^{|A|}$; the two-point function $\langle\sigma_u\sigma_v\rangle$ is a ratio of the partition function of such even subgraphs to that of subgraphs in which exactly the two vertices $u$ and $v$ have odd degree.

The worm algorithm, introduced by Prokof'ev and Svistunov (2001), is a Markov chain on the space $W=C_0\cup C_2$ consisting of the even subgraphs $C_0$ together with the subgraphs $C_2$ having exactly two odd-degree vertices (the two odd vertices are called defects or worm heads). One step of the chain chooses a vertex uniformly at random (one of the two defects when the configuration lies in $C_2$, any vertex when it lies in $C_0$), then a uniformly random edge incident to that vertex, and flips that edge — thereby moving a defect across it — with a lazy half-Metropolis acceptance probability. Its stationary distribution is the Prokof'ev–Svistunov measure $\pi(A)\propto x^{|A|}$ multiplied by a sector-dependent factor ($n$ for $A\in C_0$, $2$ for $A\in C_2$), so that within each sector it is proportional to the high-temperature-graph weight $x^{|A|}$. Estimating the stationary probability of being in $C_0$, or in the class $C_{uv}$ of subgraphs whose two odd vertices are $u$ and $v$, yields estimators for the susceptibility $\chi=\sum_{v\in V}\langle\sigma_u\sigma_v\rangle$ (the summed two-point function, the standard measure of overall correlation strength) and for the two-point function $\langle\sigma_u\sigma_v\rangle$ itself. The worm algorithm is one of the most widely used simulation methods in statistical and lattice physics; a large-scale numerical study (Deng, Garoni and Sokal, 2007) found it to be, asymptotically, the most efficient known method for estimating $\chi$ and the correlation length of the three-dimensional Ising model.

For a finite Markov chain with transition matrix $P$ and stationary distribution $\pi$, the mixing time $t_{\rm mix}(\delta)$ is the number of steps needed for the worst-case total-variation distance to $\pi$ to fall below $\delta$, and the relaxation time $t_{\rm rel}$ is the inverse of the (absolute) spectral gap of $P$. A family of chains is rapidly mixing if these quantities are bounded by a polynomial in the state-space descriptor, here the number of vertices $n=|V|$. Before 2014, the one rigorously rapidly mixing chain on Ising high-temperature graphs was that of Jerrum and Sinclair (1993), which however requires a strictly nonzero magnetic field. Collevecchio, Garoni, Hyndman and Tokarev proved in a 2014 letter, with full details in their 2016 journal paper, that the worm process is rapidly mixing at all temperatures on all finite connected graphs — the first such result for any Ising chain, including at the critical point. Their proof uses the method of multicommodity flows, in which one prescribes paths between pairs of states in the transition graph and bounds the mixing time through the maximum congestion accumulated on any edge; the resulting bounds are $t_{\rm rel}\le 4\Delta m n^4$ and $t_{\rm mix}(\delta)=O(\Delta m^2 n^4\log(1/\delta))$, where $\Delta$ is the maximum degree and $m=|E|$. On boxes in a regular lattice this gives $t_{\rm rel}=O(n^5)$ and $t_{\rm mix}=O(n^6)$ (the letter itself stated the weaker $O(n^7)$ and $O(n^8)$).

On the lower-bound side, Li and Sokal (1989) proved for the Swendsen–Wang algorithm (a Markov chain that updates entire connected clusters of aligned spins in a single step) that the autocorrelation time is at least a constant times the specific heat, i.e. the variance of the number of occupied bonds; the same variational argument applies to worm-type chains on graphical representations, as established for the worm by Deng, Garoni and Sokal (2007). Near criticality on $\mathbb{Z}_L^d$ (the $d$-dimensional cubic-lattice box of side $L$, standardly taken with periodic boundary conditions) this forces $t_{\rm rel}\gtrsim L^{d+\alpha/\nu}$, where $\alpha$ and $\nu$ are the specific-heat and correlation-length critical exponents of the Ising universality class. In three dimensions $\alpha/\nu\approx 0.174$, so $t_{\rm rel}\gtrsim L^{3.174}\approx n^{1.06}$ with $n=L^3$. Their simulations found that the slowest mode of the worm (the total number of occupied bonds) has dynamic exponent $z\approx\alpha/\nu$ in three dimensions — the lower bound appears numerically tight — while in two dimensions the competing scenarios $L^2\log^2 L$ and $L^{2+z}$ with $z\approx 0.38$ could not be distinguished, and the worm was observed to decorrelate on three distinct time scales. The result of Collevecchio et al. therefore leaves a gap of about four orders of magnitude in the exponent: between $n^{1.06}$ and $n^5$ for the relaxation time on critical three-dimensional boxes. Determining what the true asymptotic growth is — in particular whether the Li–Sokal-type bound is tight for the worm — is the open problem posed at the close of the 2014 letter. As applications, the rapid-mixing theorem yields fully-polynomial randomized approximation schemes (FPRASes; randomized algorithms achieving relative error $\varepsilon$ with probability $3/4$ in time polynomial in the input and $\varepsilon^{-1}$) for the susceptibility and for the two-point function at bounded graph distance, and the worm's mixing behaviour has recently become relevant to the efficiency of worm-based decoders for quantum low-density parity-check codes (quantum error-correcting codes whose parity checks each act on a bounded number of qubits).

Problem Statement

Determine the actual asymptotic behaviour, as the box side $L\to\infty$, of the relaxation time $t_{\rm rel}$ and the mixing time $t_{\rm mix}$ of the (lazy) Prokof'ev–Svistunov worm process for the zero-field ferromagnetic Ising model, in the specific setting identified by Collevecchio–Garoni–Hyndman–Tokarev — the critical boxes $\mathbb{Z}_L^3$. The current state of knowledge is a gap between the Li–Sokal-type lower bound $t_{\rm rel}\gtrsim L^{d+\alpha/\nu}\approx L^{3.174}\approx n^{1.06}$ ($n=L^3$) at criticality and the multicommodity-flow upper bounds $t_{\rm rel}=O(n^5)$, $t_{\rm mix}=O(n^6)$ valid at all temperatures. A complete answer establishes matching upper and lower bounds, up to constants or explicit logarithmic/subpolynomial factors, for the critical three-dimensional box: for instance, proving or refuting that $t_{\rm rel}$ grows as $\Theta(L^{d+\alpha/\nu})$ — equivalently, in a formulation that avoids the numerically known exponent $\alpha/\nu$, that $t_{\rm rel}$ is proportional up to such factors to the volume times the specific heat, $L^d\,C_H(L)$, since $C_H(L)\sim L^{\alpha/\nu}$ at criticality — or establishing whatever sharper growth law actually holds. The companion direction named in the source's introduction — proving analogous rapid-mixing results for worm processes of other statistical-mechanical models — is not part of the posed problem.

References

1. Andrea Collevecchio, Timothy M. Garoni, Timothy Hyndman, Daniel Tokarev, The worm algorithm for the Ising model is rapidly mixing, arXiv:1409.4484 (2014), DOI: 10.48550/arXiv.1409.4484, https://arxiv.org/abs/1409.4484
2. Andrea Collevecchio, Timothy M. Garoni, Timothy Hyndman, Daniel Tokarev, The Worm Process for the Ising Model is Rapidly Mixing, Journal of Statistical Physics 164, 1082-1102 (2016), DOI: 10.1007/s10955-016-1572-2, https://doi.org/10.1007/s10955-016-1572-2 (preprint: arXiv:1509.03201, https://arxiv.org/abs/1509.03201)
3. N. Prokof'ev, B. Svistunov, Worm Algorithms for Classical Statistical Models, Physical Review Letters 87, 160601 (2001), DOI: 10.1103/PhysRevLett.87.160601, https://doi.org/10.1103/PhysRevLett.87.160601
4. Youjin Deng, Timothy M. Garoni, Alan D. Sokal, Dynamic Critical Behavior of the Worm Algorithm for the Ising Model, Physical Review Letters 99, 110601 (2007), DOI: 10.1103/PhysRevLett.99.110601, https://doi.org/10.1103/PhysRevLett.99.110601 (preprint: arXiv:cond-mat/0703787, https://arxiv.org/abs/cond-mat/0703787)
5. X.-J. Li, A. D. Sokal, Rigorous lower bound on the dynamic critical exponents of the Swendsen-Wang algorithm, Physical Review Letters 63, 827-830 (1989), DOI: 10.1103/PhysRevLett.63.827, https://doi.org/10.1103/PhysRevLett.63.827
6. Mark Jerrum, Alistair Sinclair, Polynomial-Time Approximation Algorithms for the Ising Model, SIAM Journal on Computing 22, 1087-1116 (1993), DOI: 10.1137/0222066, https://doi.org/10.1137/0222066
7. Heng Guo, Mark Jerrum, Random cluster dynamics for the Ising model is rapidly mixing, The Annals of Applied Probability 28(2) (2018), DOI: 10.1214/17-AAP1335, https://doi.org/10.1214/17-AAP1335 (preprint: arXiv:1605.00139, https://arxiv.org/abs/1605.00139)
8. Leslie Ann Goldberg, Mark Jerrum, Approximating Pairwise Correlations in the Ising Model, ACM Transactions on Computation Theory 11(4), 1-20 (2019), DOI: 10.1145/3337785, https://doi.org/10.1145/3337785 (preprint: arXiv:1810.05830, https://arxiv.org/abs/1810.05830)
9. Tianyu Liu, Xiongxin Yang, Beyond windability: Approximability of the four-vertex model, Theoretical Computer Science 995, 114491 (2024), DOI: 10.1016/j.tcs.2024.114491, https://arxiv.org/abs/2302.11336 (arXiv preprint version additionally lists Zhiguo Fu as author)
10. Daniel Štefankovič, Eric Vigoda, John Wilmes, On Counting Perfect Matchings in General Graphs, LATIN 2018: Theoretical Informatics, Lecture Notes in Computer Science (Springer), pp. 873-885, DOI: 10.1007/978-3-319-77404-6_63, https://doi.org/10.1007/978-3-319-77404-6_63 (preprint: arXiv:1712.07504, https://arxiv.org/abs/1712.07504)
11. Zac Tobias, Nikolas P. Breuckmann, Benedikt Placke, Optimal Decoding with the Worm, arXiv:2603.05428 (2026), https://arxiv.org/abs/2603.05428
12. Eren Metin Elçi, Jens Grimm, Lijie Ding, Abrahim Nasrawi, Timothy M. Garoni, Youjin Deng, Lifted worm algorithm for the Ising model, Physical Review E 97, 042126 (2018), DOI: 10.1103/PhysRevE.97.042126, https://arxiv.org/abs/1711.05346