arXiv preprint ·
Quantum-classical algorithm interpolation for spatial search
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $γ\in[0,1]$, our algorithms use circuits of depth $\widetilde{O}(\mathrm{HT}^{γ/2})$ and find a marked vertex with constant success probability at total cost $\widetilde{O}(\mathrm{HT}^{1-γ}\mathsf{S} + \mathrm{HT}^{1-γ/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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Chromatic Block-Gibbs p-Bit Decoding of QLDPC Codes
A note on the A.C. spectrum of limit-periodic Jacobi matrices
Coherent optical control of a thousand qubits in a three-dimensional trapped-ion crystal
Quantum LDPC Codes from Polynomial Minors
Universal entanglement detection with geometrically optimal witnesses
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.