arXiv:2610.19255
Quantum-classical algorithm interpolation for spatial search
Diogo Ramos, Duarte Magano
Abstract
Quantum-walk algorithms can quadratically reduce the dependence of spatial search on the classical hitting time $\mathrm{HT}$. Realising this speedup using standard quantum-walk algorithms, however, requires deep coherent circuits, limiting their applicability on near-term and early fault-tolerant quantum devices. We derive a parameterised family of hybrid quantum-classical spatial search algorithms that continuously interpolates between the classical and fully coherent quantum regimes, trading off circuit depth for total query complexity. For any $γ\in[0,1]$, our algorithms use circuits of depth $\widetilde{O}(\mathrm{HT}^{γ/2})$ and find a marked vertex with constant success probability at total cost $\widetilde{O}(\mathrm{HT}^{1-γ}\mathsf{S} + \mathrm{HT}^{1-γ/2}(\mathsf{U} + \mathsf{C}))$, where $\mathsf{S}$, $\mathsf{U}$, and $\mathsf{C}$ denote the setup, update, and checking costs, respectively. We also derive an optimal continuous depth-query trade-off for fixed-point amplitude amplification, providing a potential building block for other hybrid designs.
AI Summary
The paper asks how spatial search on reversible Markov chains trades quantum coherence against total work when each quantum run has bounded depth. It constructs hybrid algorithms that interpolate between classical hitting-time scaling and fully coherent quantum-walk search, accounting separately for stationary-state preparation, walk updates, and marked-vertex checks. Writing $H=\mathrm{HT}(P,M)$, for every $\gamma\in[0,1]$ the general construction finds a marked vertex with constant probability using quantum-walk depth $\widetilde O(H^{\gamma/2})$ and total cost $\widetilde O(H^{1-\gamma}\mathsf S+H^{1-\gamma/2}(\mathsf U+\mathsf C))$. For one marked vertex, with its stationary probability and hitting time known, these bounds hold without logarithmic overhead. For multiple marked vertices, the ordinary-hitting-time guarantee carries polylogarithmic factors. The checking-query dependence matches the worst-case lower bound inherited from unstructured search. The constructions adapt two existing search algorithms using quantum fast-forwarding. One tunes a semi-absorbing walk’s stationary-state overlap and filtering time; its general guarantee depends on extended hitting time. The other randomises walk parameters and uses a new truncated-hitting bound, $\Pr(Z\le t)\ge\frac1{14}\min(1,t/H)$, to obtain ordinary-hitting-time scaling. A separate fixed-point amplitude-amplification interpolation achieves depth $O(\delta^{-\gamma})$ and total queries $O(\delta^{\gamma-2}\log(1/\zeta))$. The stated depth counts walk applications, not complete gate depth. Repeated stationary-state preparation can negate the benefit of shallow runs, so the classical endpoint does not generally reproduce classical setup cost. Setup/update optimality, logarithm-free multiple-marked search, and interpolation from arbitrary initial distributions remain unresolved. Limited prior knowledge is handled with additional overhead.
The authors acknowledge the usage of AI to review the writing, help write the code used to generate the figures, assist finding and editing references, and for minor technical assistance when verifying the proofs.
Central claim may not hold: The abstract's circuit-depth guarantee is established only as a bound on quantum-walk operator applications per run, excluding potentially deep initial-state preparation and implementation costs.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, 5 figures