Quantum-classical algorithm interpolation for spatial search

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 $\gamma \in [0,1]$, our algorithms use circuits of depth $\tilde{O}({\mathrm{HT}}^{\gamma /2})$ and find a marked vertex with constant success probability at total cost $\tilde{O}({\mathrm{HT}}^{1-\gamma }\mathsf{S}+{\mathrm{HT}}^{1-\gamma /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.

arXiv comment35 pages, 5 figures