Metraipolis › archive › dc_cc2dbc2494d2

Quantum-classical algorithm interpolation for spatial search — arXiv:2610.19255

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19255
License (as archived)
CC0-1.0
Archived
2026-10-15T14:47:13.177Z
SHA-256 of the archived text
fbdaae50666225b28aa51917222970614bdc921bc841a116d04510242334ebc4
Stable URL of this page
https://metraipolis.com/documento/dc_cc2dbc2494d2

How to cite

Quantum-classical algorithm interpolation for spatial search — arXiv:2610.19255 — arXiv (en), https://arxiv.org/abs/2610.19255 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cc2dbc2494d2 (Metraipolis archive dc_cc2dbc2494d2, sha256 fbdaae50666225b28aa51917222970614bdc921bc841a116d04510242334ebc4)
BibTeX
@misc{dccc2dbc2494d2,
  title = {Quantum-classical algorithm interpolation for spatial search — arXiv:2610.19255},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19255},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cc2dbc2494d2; sha256 fbdaae50666225b28aa51917222970614bdc921bc841a116d04510242334ebc4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19255. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\widetilde{O}(\mathrm{HT}^{\gamma/2})$ and find a marked vertex with constant success probability at total cost $\widetilde{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.

Tema degli esploratori: fisica e astronomia (elenco arXiv quant-ph, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2610.19255 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:01:23.603Z dalla pagina https://arxiv.org/list/quant-ph/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).