These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.
Abstract
Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erd\H{o}s-R\'enyi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site'potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability $p$, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $\lambda$ is upper bounded by a constant and $\lambda(1 - \beta) \lesssim \Delta^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.
We study the spectrum of the adjacency matrix $A_n$ of directed inhomogeneous random graphs on $n$ vertices. We assume that $A_n$ has independent entries and diverging average degree scale $s_n$. This framework includes, as special cases, the directed Chung--Lu random graph and directed stochastic block models. Assuming boundedness of the variance profile and that $s_n$ diverges faster than a suitable logarithmic function of $n$, we show that the rank-one Chung--Lu model satisfies a non-homogeneous version of the circular law, which in some situations allows for an explicit expression. Moreover, under mild conditions, we identify the asymptotic singular value distribution using tools from free probability. Finally, for finite-rank directed models, we prove the existence of eigenvalues outside the bulk and establish their joint Gaussian fluctuations at the scale $\sqrt{s_n/n}$, with an explicit covariance matrix. These results extend the theory of spectral outliers and their fluctuations to directed inhomogeneous random graphs.
The Rosenzweig--Porter (RP) random matrix ensemble has emerged as a minimal model for the integrability-to-chaos crossover in quantum many-body systems. Its phase diagram features a region with fractal eigenstates, exhibiting intermediate spectral and localization properties between the fully localized and fully delocalized regimes. In this work, we explore several generalizations of the RP model and determine their level statistics at the scale of the Thouless energy $E_T$, which characterizes the crossover. Using tools from free probability theory and the replica method, we compute the full counting statistics in the limit of large system size, and show that it takes a simple, universal scaling form around $E_T$, shared across all variations of the model. We validate our analytical predictions using exact numerical diagonalization of large samples, and large-deviation algorithms that resolve the full counting statistics down to probabilities as low as $10^{-40}$. We also contrast our predictions with measurements on the quantum random energy model, which is the simplest model displaying many-body localization.
Victor Delapalme, L. F. Cugliandolo, Alexander K. Hartmann et al.· 0 citations
Graphons are measurable functions used to describe the asymptotic behavior of convergent graph families. Originally motivated by problems in combinatorics and graph theory, graphons have found numerous applications in the modeling and analysis of dynamical processes on networks. In this work, we use graphons to formulate the Ising model on convergent graph sequences, which include many network topologies common in applications. We derive the mean-field limit for the resulting model and obtain exact results for phase transitions in such systems. Specifically, we show that the critical temperatures of the Ising model on graphons are determined by the eigenvalues of the Hilbert-Schmidt operator associated with the graph limit. For many important network topologies, these eigenvalues can be computed explicitly. We illustrate our results with three representative random network models: Erd\H{o}s-R\'{e}nyi, small-world, and power-law. In the small-world case, we demonstrate phase transitions to both ferromagnetic and antiferromagnetic phases, as well as coexistence of local minima of the free energy. The latter gives rise to multistability, as confirmed by Monte Carlo simulations. The results of this work demonstrate that the Ising model on graphons combines the analytical tractability of exactly solvable mean-field models with the ability to accommodate a broad range of network topologies. We expect that the use of graphons in spin models will lead to new insights into the statistical physics of interacting systems on complex networks.
Random walks with long-range jumps can drive superdiffusive transport, replacing ordinary diffusion with an effective long-range kinetic operator. Such superdiffusive kinetics is also central to critical phenomena, notably the self-avoiding walk with long-range jump statistics, or L\'evy-SAW. This work investigates how the critical behavior is affected when the long-range connectivity itself becomes random. We study self-avoiding walks (SAWs) on a one-dimensional long-range random ring graph, where bonds are independently generated with Bernoulli probability $\sim|i-j|^{-(1+\sigma)}$. We term this walk Sparse-SAW. The same random bonds are responsible for both long-range superdiffusive transport and quenched disorder, with both simultaneously controlled by the single parameter $\sigma$, placing the problem beyond the conventional Harris and Weinrib-Halperin frameworks. Through large-scale Monte Carlo simulations and a Gaussian-truncated field theory, we show that Sparse-SAW belongs to the same universality class as the clean superdiffusive L\'evy-SAW. The random bonds generate short-range uncorrelated and long-range correlated mass disorder while simultaneously producing the long-range kinetic operator. Under coarse-graining, the latter dominates, restoring the clean critical behavior. Our study suggests that the full non-Gaussian Bernoulli statistics may lead to disorder physics beyond the conventional theory of quenched disorder, while establishing random graphs as an efficient platform for extracting the critical exponents of the clean superdiffusive L\'evy-SAW universality class.
The Watts-Strogatz random graph model on $n$ vertices with parameters $K$ (a positive even integer) and $p \in [0, 1]$ is constructed in two steps. First, one starts with a ring lattice on $n$ vertices, where each vertex is connected to its $K/2$ nearest neighbors on each side. Each edge in turn is then independently rewired with probability $p$ by replacing one endpoint with a uniformly chosen vertex not already adjacent to it. We study the empirical eigenvalue distribution of the adjacency matrix for this model, whose entries are highly dependent due to the rewiring construction. In the regime where both $K$ and $pK$ grow to infinity with the vertex size $n$, we show that, after appropriate scaling, the empirical eigenvalue distribution converges to the semicircle law. The proof is based on a novel coupling argument that approximates the adjacency matrix by a sum of two independent random matrices, one a sparse Wigner matrix and the other a random band matrix. In the case where $K$ and $p$ remain fixed, we propose conjectural formulas for the first five moments of the limiting eigenvalue distribution. These conjectures are supported by a convergence result relating the Watts-Strogatz model to another random graph model, together with numerical simulations.