# Quantum-classical algorithm interpolation for spatial search

Preprint · Diogo Ramos, Duarte Magano

- Archive id: arxiv:2610.19255
- Published: 2026-10-13
- arXiv: <https://arxiv.org/abs/2610.19255>
- Source URL: <https://arxiv.org/abs/2610.19255>
- PDF: <https://arxiv.org/pdf/2610.19255>
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._


---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.