Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 49 min ago
PreprintarXiv licencearXiv

Quantum-classical algorithm interpolation for spatial search

  • Diogo Ramos
  • Duarte Magano
Open at sourcePDFDOICite

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 Õ(HT1−γS + HT1−γ/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.

Related

  1. A quantum algorithm for meshless lattice Boltzmann method with unitary interpolation
    Chi Zhang, Hefeng Wang, Hua Xiang
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingComputational physicsarXiv
  2. Quantum Pointwise Dimension (QUPID): An algorithm for identifying classical chaos in quantum dynamics
    Jonathan Berkheim, David J. Tannor
    arXivPreprintCC BY-NC-SA 4.0Full textQuantum physics & quantum informationarXiv
  3. Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search
    Mansur Ziiatdinov, Fedor Levkovich-Maslyuk, Emmanuel M. Pothos
    Entropy (Basel, Switzerland)Peer-reviewedCC BYFull textGeneral astronomyGeneral physicsEurope PMCDOAJ
  4. Quantum State Search with Classical Interactive Advice
    Mohammed Barhoush
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
    Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1
    arXivPreprintCC BY-SA 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{ramos2026quantumclassical,
  title = {{Quantum-classical algorithm interpolation for spatial search}},
  author = {Diogo Ramos and Duarte Magano},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.19255},
  eprint = {2610.19255},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.19255},
}
RIS
TY  - UNPB
TI  - Quantum-classical algorithm interpolation for spatial search
AU  - Diogo Ramos
AU  - Duarte Magano
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.19255
UR  - https://arxiv.org/abs/2610.19255
AB  - 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.
ER  -