Quantum-classical algorithm interpolation for spatial search

Abstract

Quantum-walk algorithms can quadratically reduce the dependence of spatial search on the classical hitting time 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 γ∈[0,1], our algorithms use circuits of depth Õ(HT^γ/2) and find a marked vertex with constant success probability at total cost Õ(HT^1−γS + HT^1−γ/2(U + C)), where S, U, and 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: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.