Tilen Cadez

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 graph (ER) graphs. This produces a doubly random system where ER graph connectivity masks which interactions exist, while RP disorder controls their strength. The edge probability $p$ tunes the sparsity of the graph, and the parameter $\gamma_{RP}$ independently controls disorder strength, providing a two-parameter framework to study quantum dynamics on disordered networks. We first establish that the RP phase structure survives under graph constraints. We further derive an analytical estimate for the localization boundary, explicitly capturing localization boundary shifting systematically with $p$ in a manner consistent with an analytical hybridization argument. 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 phases on graphs and quantum algorithmic performance, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.