pipette
ESEspañol

Quantum-classical algorithm interpolation for spatial search

Diogo Ramos, Duarte Magano

Preprint

In the authors' words

Quantum-walk algorithms can quadratically reduce the dependence of spatial search on the classical hitting time . 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 , our algorithms use circuits of depth and find a marked vertex with constant success probability at total cost , where , , and 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.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 35 pages, 5 figures