REVIEW 3 major objections 5 minor 59 references
On disordered random graphs, quantum-walk search finds a marked vertex more reliably in the localized phase than in the ergodic phase, at the price of longer search times.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
2026-08-04 00:58 UTC pith:SP5XZRKX
load-bearing objection Solid spectral study of a new disordered graph model; the search trade-off is plausible but rests on the authors' own CNR algorithm and lacks a uniform-initial-state baseline. the 3 major comments →
Marked vertex search on disordered graphs with Rosenzweig-Porter phases
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
On a doubly random ensemble—Erdős–Rényi graph connectivity masked with Rosenzweig–Porter scaling of hoppings and on-site potentials—the paper finds that marked-vertex search performance mirrors the underlying phase: the ergodic phase yields low peak success probability because the marked state has small maximum overlap with any eigenstate, whereas the localized phase drives that overlap toward unity and raises the success fraction to near 1, while the median search time grows strongly with the disorder parameter. The study derives the finite-size localization boundary γ_c = 2 + 2 log p / log N and shows that the spectral crossover from Wigner–Dyson to Poisson statistics persists under graph
What carries the argument
The central object is the maximum marked-state overlap ϵ_wi = max_i |<w|λ_i>|², the largest weight of the marked vertex in the eigenbasis of the normalized hopping Hamiltonian; it transitions from small to near unity across the localization crossover and is the mechanism that makes localized phases better at concentrating search amplitude. The quantitative predictions are carried by the overlap-weighted spectral sums S_k = Σ_{i≠N} |<w|λ_i>|² (1−λ_i)^{−k}, which set the hopping rate α=S1 and predict P_peak ~ S1²/S2 and search time τ ~ (π/2)√S2/(S1√ε).
Load-bearing premise
The reported phase-dependence rests on the spectral search recipe of Sec. IV B — initializing in the principal eigenstate of the normalized hopping Hamiltonian and fixing the hopping rate at S1 — being a correct and near-optimal way to run the search; if that recipe is suboptimal in the ergodic phase, the low success probability observed there may be an artifact of the algorithm rather than an intrinsic property of the phase.
What would settle it
Run the same marked-vertex search on the RP–ER graphs using the standard uniform initial state and scan the hopping rate α over a broad range; if the ergodic phase then yields an order-one peak success probability for some α, the claimed phase trade-off is an artifact of the spectral recipe. Alternatively, test the quantitative link by checking, realization-by-realization, whether the numerically measured P_peak matches S1²/S2 within the stated precision; a systematic mismatch would disprove the direct link.
If this is right
- In the localized phase, the fraction of disorder realizations with peak success ≥ 0.8 approaches unity across a wide range of graph densities, so disorder can be deliberately tuned to make marked-vertex detection reliable.
- The search slowdown is quantitatively tied to the same spectral sums: the peak time grows like √S2/S1 as the marked-state weight migrates away from the spectral edge.
- The analytic boundary γ_c = 2 + 2 log p / log N predicts, for a given graph size and edge probability, the disorder strength at which search performance should transition from fast-and-unreliable to slow-and-reliable.
- Sparsity and disorder act in the same direction: both shift the effective transition to smaller γ_RP, so even sparse graphs can be brought into the reliable-search regime with modest disorder.
Where Pith is reading between the lines
- The non-ergodic extended regime, which the paper does not directly search over, may combine partial amplitude concentration with faster transport than full localization; checking P_peak and τ there would test whether there is an optimal intermediate disorder strength.
- A practical diagnostic follows: measuring ϵ_wi on a given disordered graph could predict search reliability without running the full dynamics, which may be useful for calibrating quantum-walk hardware.
- The resonant-hybridization derivation likely generalizes to other random graph ensembles; if so, the trade-off could be a generic feature of quantum search on disordered networks, not specific to ER–RP graphs.
- Because the trade-off is continuous in γ_RP, one could in principle optimize the disorder level to meet a target error budget within a time constraint—effectively using disorder as a dial for the algorithm's speed-accuracy operating point.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a graph-constrained Rosenzweig–Porter (RP) ensemble on Erdős–Rényi random graphs, in which the ER edge probability p controls graph sparsity and the RP parameter γ_RP controls the strength of random hoppings. The authors first show that the RP spectral crossover from Wigner–Dyson to Poisson statistics survives under the ER constraint, and they derive a finite-size localization boundary γ_{⟨r⟩}(p,N)=2+2 log p / log N from a resonant-hybridization argument. They then study continuous-time quantum walk (CTQW) marked-vertex search using the Chakraborty–Novo–Roland (CNR) spectral framework, tuning the hopping rate to α=S1 and initializing in the principal eigenstate of the normalized hopping Hamiltonian. The main reported finding is a phase-dependent trade-off: in the ergodic phase the search is fast but the peak success probability is low, while in the localized phase the peak success probability is high but the search time is significantly longer. The paper also includes a disordered line-graph example and an appendix robustness check with doubly random graph and disorder realizations.
Significance. If the central trade-off is robust, the paper makes an interesting and counterintuitive contribution: it suggests that disorder can be used as a tunable resource in quantum search, improving detection reliability at the cost of runtime. The construction of the graph-constrained RP ensemble is novel, and the spectral crossover analysis is extensive, with system sizes up to N=4000 and up to 1500 realizations. The paper also provides a falsifiable analytical prediction for the p-dependent localization boundary and validates the CNR spectral predictions against direct dynamics in Fig. 6. The appendix checks that the qualitative trade-off is not an artifact of fixing the graph realization. However, the search results are obtained entirely within the CNR prescription, and the lack of a comparison with the standard uniform-initialization search algorithm leaves the central claim underdetermined.
major comments (3)
- [Sec. IV D, Eqs. (22)-(27)] The central trade-off claim is established only under the CNR prescription: the initial state is the principal eigenstate of the normalized hopping Hamiltonian and α is fixed to S1 (Eq. (25)). The standard uniform-initialization algorithm defined in Sec. IV A is never run, and α is not scanned. On a disordered graph the principal eigenstate differs qualitatively from |s⟩; in the ergodic phase the uniform state has an O(1/√N) amplitude at the marked vertex, so the reported low P_peak may be an artifact of the initialization rather than an intrinsic property of the ergodic phase. I request a control experiment: run the standard |s⟩ initialization with optimized α for representative (γ_RP, p) points and report P_peak and τ. If the conclusions are intended to apply only to the CNR algorithm, the abstract and conclusion must be qualified accordingly.
- [Figs. 7 and 9] The success fraction f and the median search time ln(τ) are the central quantitative results supporting the phase-dependent trade-off, yet no error bars or confidence intervals are reported despite ensemble sizes of 500–1500 realizations. Bootstrap errors are straightforward to compute and would establish whether the ergodic-phase success fraction is statistically distinguishable from the localized-phase value. Without them, the claim that the ergodic phase 'yields lower success probability' is not statistically quantified.
- [Sec. III B/C, Fig. 3] The numerical crossover γ_c is estimated by minimizing the mutual separation of ⟨r⟩ curves at three system sizes, and the analytical estimate Eq. (16) is compared to an anchored iso-⟨r⟩ criterion. Neither estimator is standard, and the text says γ_c is 'consistent with the transition at γ=2' while Fig. 3 shows γ_c decreasing with decreasing p. This should be clarified as a finite-size crossover, and a scaling collapse or at least bootstrap errors on γ_c would strengthen the validity of Eq. (16).
minor comments (5)
- [Sec. IV D] The notation H0 is used for the diagonal disorder matrix in Eq. (2) and later for the 'normalized hopping Hamiltonian' in Sec. IV D. This is confusing; use a different symbol (e.g., H_norm) for the normalized search Hamiltonian.
- [Sec. IV B, Eq. (17)] Eq. (17) defines H as γ_walk L, but the CNR framework in Eq. (22) uses a normalized Hamiltonian with eigenvalues in [0,1]. The relation between these two Hamiltonians is not stated explicitly; clarify that the CNR method normalizes H before computing S1 and S2.
- [Sec. IV C, Fig. 5] The caption mentions both P_peak and Δ_bulk, but the axis label in the described figure shows only P_peak. Please label both curves or explain the axis in the caption.
- [Abstract and Conclusion] The abstract and conclusion state the trade-off without qualification. If the uniform-state control reveals a different behavior, these statements must be revised; even if not, a sentence limiting the claims to the CNR algorithm would improve precision.
- [References] Reference [59] (Chakraborty et al., Phys. Rev. A 113, 032430 (2026)) appears to be a self-citation with a future date; verify bibliographic details.
Circularity Check
No circular reduction found; CNR-spectral predictions are tested against direct dynamics, but the search protocol rests on the authors' prior framework.
full rationale
The derivation chain is not circular in the sense of the stated patterns. The spectral analysis of the graph-constrained RP ensemble is self-contained: the adjacent-gap ratio is computed directly from the eigenvalues via Eq. (4), and the finite-size localization boundary, Eq. (16), follows from the resonance-counting condition k_res ~ p N^{1-gamma_RP/2} ~ 1, independent of the later search observables. The numerical crossover line is obtained from an anchored iso-<r> criterion and is not constructed from Eq. (16), so the comparison in Fig. 4 is an independent consistency check. In the search section, the CNR framework of Ref. [6] is indeed the authors' own prior work, and Eqs. (25)-(27) are used to set alpha = S1 and to predict P_peak ~ S1^2/S2 and t* ~ (pi/2) sqrt(S2)/(S1 sqrt(epsilon)). However, the paper does not define P_peak or the search time as these spectral formulas; it explicitly evolves the state with the Schrödinger equation (Eq. (19)) and records the first maximum of P_w(t). Fig. 6 then compares the CNR spectral predictions against this independently computed dynamics, so the 'predictions' are tested rather than imposed by construction. The central trade-off is thus a numerical finding under a specific, cited protocol. The absence of a control with the standard uniform initial state |s> and the lack of an alpha scan are robustness and external-validity limitations: they mean the claim that the ergodic phase yields lower success probability may be protocol-dependent, but they do not make the derivation circular. No uniqueness theorem, ansatz smuggled via citation, or renaming of a known result is exhibited.
Axiom & Free-Parameter Ledger
free parameters (2)
- Resonance condition constant =
1
- Success threshold =
0.8
axioms (5)
- domain assumption CNR spectral search framework (α=S1; P_peak ~ S1^2/S2; t ~ sqrt(S2)/S1 sqrt(ε))
- domain assumption Localization criterion: system localizes when the number of resonant neighbors k_res does not grow with N
- standard math ER degree concentration k ≈ pN
- domain assumption Standard RP phase boundaries at γ_RP=1 and γ_RP=2
- domain assumption Principal eigenstate of normalized hopping Hamiltonian is the valid search initial state
Cite this review
Pith. "Pith review of Marked vertex search on disordered graphs with Rosenzweig-Porter phases." pith.science (2026). https://pith.science/paper/SP5XZRKX
@misc{pith2026260800224,
author = {Pith},
title = {Pith review of: Marked vertex search on disordered graphs with Rosenzweig-Porter phases},
year = {2026},
howpublished = {\url{https://pith.science/paper/SP5XZRKX}},
note = {Machine review of arXiv:2608.00224}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Farhi and S
E. Farhi and S. Gutmann, Physical Review A58, 915 (1998)
1998
-
[2]
Kempe, Contemporary Physics44, 307 (2003), https://doi.org/10.1080/00107151031000110776
J. Kempe, Contemporary Physics44, 307 (2003), https://doi.org/10.1080/00107151031000110776
-
[3]
Portugal,Quantum Walks and Search Algorithms, 1st ed., Quantum Science and Technology (Springer, New York, NY, 2013) pp
R. Portugal,Quantum Walks and Search Algorithms, 1st ed., Quantum Science and Technology (Springer, New York, NY, 2013) pp. XI, 222, 37 b/w illustrations
2013
-
[4]
A. M. Childs and J. Goldstone, Phys. Rev. A70, 022314 (2004)
2004
-
[5]
Chakraborty, L
S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Phys. Rev. Lett.116, 100501 (2016)
2016
-
[6]
Chakraborty, L
S. Chakraborty, L. Novo, and J. Roland, Phys. Rev. A 102, 032214 (2020)
2020
-
[7]
Apers, S
S. Apers, S. Chakraborty, L. Novo, and J. Roland, Phys. Rev. Lett.129, 160502 (2022)
2022
-
[8]
M¨ ulken, V
O. M¨ ulken, V. Pernice, and A. Blumen, Phys. Rev. E76, 051125 (2007)
2007
-
[9]
M¨ ulken and A
O. M¨ ulken and A. Blumen, Physics Reports502, 37 (2011)
2011
-
[10]
P. W. Anderson, Phys. Rev.109, 1492 (1958)
1958
-
[11]
P. A. Lee and T. V. Ramakrishnan, Rev. Mod. Phys.57, 287 (1985)
1985
-
[12]
L. Razzoli, M. G. A. Paris, and P. Bordone, Entropy23, 10.3390/e23010085 (2021)
-
[13]
Roth and A
N. Roth and A. L. Goodwin, Nature Communications14, 4328 (2023)
2023
-
[14]
A. Kurt, M. A. Rossi, and J. Piilo, Journal of Physics A: Mathematical and Theoretical56, 145301 (2023)
2023
-
[15]
Longhi, Optics Letters48, 2445 (2023)
S. Longhi, Optics Letters48, 2445 (2023)
2023
-
[16]
Z. Khodadad, J. Tarabishi, and G. Hanna, The Journal of Chemical Physics162, 10.1063/5.0247924 (2025)
-
[17]
D. J. Thouless, Journal of Physics C: Solid State Physics 3, 1559 (1970)
1970
-
[18]
Abrahams, P
E. Abrahams, P. W. Anderson, D. C. Licciardello, and T. V. Ramakrishnan, Physical Review Letters42, 673 (1979)
1979
-
[19]
W. Chen, I. Garc ´ ıa-Mata, J. Martin, J. Gong, B. Georgeot, and G. Lemari´ e, Phys. Rev. Lett.136, 177101 (2026)
2026
-
[20]
Saha and S
B. Saha and S. Roy, Phys. Rev. B113, 144204 (2026)
2026
-
[21]
B¨ ottcher and M
L. B¨ ottcher and M. A. Porter, Phys. Rev. E112, L062301 (2025)
2025
-
[22]
Sierant, M
P. Sierant, M. Lewenstein, and A. Scardicchio, SciPost Phys.15, 045 (2023)
2023
-
[23]
K. S. Tikhonov, A. D. Mirlin, and M. A. Skvortsov, Phys. Rev. B94, 220203(R) (2016)
2016
-
[24]
De Luca, B
A. De Luca, B. L. Altshuler, V. E. Kravtsov, and A. Scardicchio, Phys. Rev. Lett.113, 046806 (2014)
2014
-
[25]
Pino, Phys
M. Pino, Phys. Rev. Res.2, 042031(R) (2020)
2020
-
[26]
ˇCadeˇ z, B
T. ˇCadeˇ z, B. Dietz, D. Rosa, A. Andreanov, K. Slevin, and T. Ohtsuki, Phys. Rev. B108, 184202 (2023)
2023
-
[27]
L. F. Cugliandolo, G. Schehr, M. Tarzia, and D. Venturelli, Phys. Rev. B110, 174202 (2024)
2024
-
[28]
Y. Yin, D. E. Katsanos, and S. N. Evangelou, Phys. Rev. A77, 022302 (2008)
2008
-
[29]
Benedetti, F
C. Benedetti, F. Buscemi, P. Bordone, and M. G. A. Paris, Phys. Rev. A93, 042313 (2016)
2016
-
[30]
Chawla, C
P. Chawla, C. Ambarish, and C. M. Chandrashekar, Jour- nal of Physics Communications3, 125004 (2019). 13
2019
-
[31]
Cattaneo, M
M. Cattaneo, M. A. C. Rossi, M. G. A. Paris, and S. Man- iscalco, Phys. Rev. A98, 052347 (2018)
2018
-
[32]
Malmi, M
J. Malmi, M. A. C. Rossi, G. Garc ´ ıa-P´ erez, and S. Manis- calco, Phys. Rev. Res.4, 043185 (2022)
2022
-
[33]
Rosenzweig and C
N. Rosenzweig and C. E. Porter, Physical Review120, 1698 (1960)
1960
-
[34]
V. E. Kravtsov, I. M. Khaymovich, E. Cuevas, and M. Amini, New Journal of Physics17, 122002 (2015)
2015
-
[35]
Facoetti, P
D. Facoetti, P. Vivo, and G. Biroli, EPL (Europhysics Letters)115, 47003 (2016)
2016
-
[36]
Truong and A
K. Truong and A. Ossipov, EPL (Europhysics Letters) 116, 37002 (2016)
2016
-
[37]
Monthus, Journal of Physics A: Mathematical and Theoretical50, 295101 (2017)
C. Monthus, Journal of Physics A: Mathematical and Theoretical50, 295101 (2017)
2017
-
[38]
von Soosten and S
P. von Soosten and S. Warzel, Letters in Mathematical Physics109, 905 (2019)
2019
-
[39]
M. Pino, J. Tabanera, and P. Serna, Journal of Physics A: Mathematical and Theoretical52, 475101 (2019)
2019
-
[40]
De Tomasi, M
G. De Tomasi, M. Amini, S. Bera, I. M. Khaymovich, and V. E. Kravtsov, SciPost Physics6, 014 (2019)
2019
-
[41]
Berkovits, Physical Review B102, 165140 (2020)
R. Berkovits, Physical Review B102, 165140 (2020)
2020
-
[42]
I. M. Khaymovich and V. Kravtsov, SciPost Physics11, 045 (2021)
2021
-
[43]
Zhang, W
X. Zhang, W. Zhang, J. Che, and B. Dietz, Physical Review E108, 044211 (2023)
2023
-
[44]
Buijsman, Phys
W. Buijsman, Phys. Rev. B109, 024205 (2024)
2024
-
[45]
ˇCadeˇ z, D
T. ˇCadeˇ z, D. Kumar Nandy, D. Rosa, A. Andreanov, and B. Dietz, New Journal of Physics26, 083018 (2024)
2024
-
[46]
Zhang, J
X. Zhang, J. Che, and B. Dietz, Physical Review E113, 024211 (2026)
2026
-
[47]
Erd˝ os and A
P. Erd˝ os and A. R´ enyi, Publicationes Mathematicae6, 290 (1959)
1959
-
[48]
Erd˝ os and A
P. Erd˝ os and A. R´ enyi, Publ. Math. Inst. Hungar. Acad. Sci5, 17 (1960)
1960
-
[49]
Altland, M
A. Altland, M. Janssen, and B. Shapiro, Phys. Rev. E56, 1471 (1997)
1997
-
[50]
Serbyn and J
M. Serbyn and J. E. Moore, Phys. Rev. B93, 041424(R) (2016)
2016
-
[51]
S. H. Tekur, U. T. Bhosale, and M. S. Santhanam, Phys. Rev. B98, 104305 (2018)
2018
-
[52]
Buijsman, V
W. Buijsman, V. Cheianov, and V. Gritsev, Phys. Rev. Lett.122, 180601 (2019)
2019
-
[53]
P. Tian, R. Riser, and E. Kanzieper, Phys. Rev. Lett. 132, 220401 (2024)
2024
-
[54]
Bogomolny and M
E. Bogomolny and M. Sieber, Phys. Rev. E98, 032139 (2018)
2018
-
[55]
Oganesyan and D
V. Oganesyan and D. A. Huse, Physical Review B75, 155111 (2007)
2007
-
[56]
Y. Y. Atas, E. Bogomolny, O. Giraud, and G. Roux, Physical review letters110, 084101 (2013)
2013
-
[57]
R. K. Ray, R. Srikanth, and S. Majumder, Phys. Rev. E 112, 044120 (2025)
2025
-
[58]
Biroli and M
G. Biroli and M. Tarzia, Phys. Rev. B103, 104205 (2021)
2021
-
[59]
Chakraborty, R
S. Chakraborty, R. S. Sarkar, S. Majumder, and R. K. Ray, Phys. Rev. A113, 032430 (2026)
2026
This paper was first reviewed by deepseek-v4-flash on August 4, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.