Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.19255

Quantum-classical algorithm interpolation for spatial search

Diogo Ramos, Duarte Magano

quant-phSubmitted Oct 13, 2026• Announced Oct 15, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

The paper asks how spatial search on reversible Markov chains trades quantum coherence against total work when each quantum run has bounded depth. It constructs hybrid algorithms that interpolate between classical hitting-time scaling and fully coherent quantum-walk search, accounting separately for stationary-state preparation, walk updates, and marked-vertex checks. Writing $H=\mathrm{HT}(P,M)$, for every $\gamma\in[0,1]$ the general construction finds a marked vertex with constant probability using quantum-walk depth $\widetilde O(H^{\gamma/2})$ and total cost $\widetilde O(H^{1-\gamma}\mathsf S+H^{1-\gamma/2}(\mathsf U+\mathsf C))$. For one marked vertex, with its stationary probability and hitting time known, these bounds hold without logarithmic overhead. For multiple marked vertices, the ordinary-hitting-time guarantee carries polylogarithmic factors. The checking-query dependence matches the worst-case lower bound inherited from unstructured search. The constructions adapt two existing search algorithms using quantum fast-forwarding. One tunes a semi-absorbing walk’s stationary-state overlap and filtering time; its general guarantee depends on extended hitting time. The other randomises walk parameters and uses a new truncated-hitting bound, $\Pr(Z\le t)\ge\frac1{14}\min(1,t/H)$, to obtain ordinary-hitting-time scaling. A separate fixed-point amplitude-amplification interpolation achieves depth $O(\delta^{-\gamma})$ and total queries $O(\delta^{\gamma-2}\log(1/\zeta))$. The stated depth counts walk applications, not complete gate depth. Repeated stationary-state preparation can negate the benefit of shallow runs, so the classical endpoint does not generally reproduce classical setup cost. Setup/update optimality, logarithm-free multiple-marked search, and interpolation from arbitrary initial distributions remain unresolved. Limited prior knowledge is handled with additional overhead.

Little sign of AI-generated textAI use disclosedIncremental
The authors acknowledge the usage of AI to review the writing, help write the code used to generate the figures, assist finding and editing references, and for minor technical assistance when verifying the proofs.

Central claim may not hold: The abstract's circuit-depth guarantee is established only as a bound on quantum-walk operator applications per run, excluding potentially deep initial-state preparation and implementation costs.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
35 pages, 5 figures

Related papers

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•75 citations

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•8 citations

Fixed-point Quantum Walk Search.

Lvzhou Li, Yongzhen Xu, Zhang Delong

n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter $\epsilon$. More specifically, for an $N$-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps $h$ satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}$, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given $\epsilon\in (0,1]$. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.

•Nov 17, 2021•0 citations

Improvement of quantum walks search algorithm in single-marked vertex graph

Xinying Li, Yun Shang

Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.

arXiv:2209.04162•Journal of Physics A Mathematical and Theoretical•Aug 17, 2023•1 citation

Spatial search by continuous-time quantum walks on complex networks

Joonas Malmi

Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.

•Dec 8, 2020•0 citations

Efficient Circuit Implementations of Continuous-Time Quantum Walks for Quantum Search

Renato Portugal, Jalil Khatibi Moqadam

Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.

arXiv:2212.08889•Entropy•Apr 23, 2025•9 citations
Quantum-walk algorithms can quadratically reduce the dependence of spatial search on the classical hitting time HT\mathrm{HT}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]γ\in[0,1]γ∈[0,1], our algorithms use circuits of depth O~(HTγ/2)\widetilde{O}(\mathrm{HT}^{γ/2})O(HTγ/2) and find a marked vertex with constant success probability at total cost O~(HT1−γS+HT1−γ/2(U+C))\widetilde{O}(\mathrm{HT}^{1-γ}\mathsf{S} + \mathrm{HT}^{1-γ/2}(\mathsf{U} + \mathsf{C}))O(HT1−γS+HT1−γ/2(U+C)), where S\mathsf{S}S, U\mathsf{U}U, and C\mathsf{C}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 paper asks how spatial search on reversible Markov chains trades quantum coherence against total work when each quantum run has bounded depth. It constructs hybrid algorithms that interpolate between classical hitting-time scaling and fully coherent quantum-walk search, accounting separately for stationary-state preparation, walk updates, and marked-vertex checks.
Writing H=HT(P,M)H=\mathrm{HT}(P,M)H=HT(P,M), for every γ∈[0,1]\gamma\in[0,1]γ∈[0,1] the general construction finds a marked vertex with constant probability using quantum-walk depth O~(Hγ/2)\widetilde O(H^{\gamma/2})O(Hγ/2) and total cost O~(H1−γS+H1−γ/2(U+C))\widetilde O(H^{1-\gamma}\mathsf S+H^{1-\gamma/2}(\mathsf U+\mathsf C))O(H1−γS+H1−γ/2(U+C)). For one marked vertex, with its stationary probability and hitting time known, these bounds hold without logarithmic overhead. For multiple marked vertices, the ordinary-hitting-time guarantee carries polylogarithmic factors. The checking-query dependence matches the worst-case lower bound inherited from unstructured search.
The constructions adapt two existing search algorithms using quantum fast-forwarding. One tunes a semi-absorbing walk’s stationary-state overlap and filtering time; its general guarantee depends on extended hitting time. The other randomises walk parameters and uses a new truncated-hitting bound, Pr⁡(Z≤t)≥114min⁡(1,t/H)\Pr(Z\le t)\ge\frac1{14}\min(1,t/H)Pr(Z≤t)≥141​min(1,t/H), to obtain ordinary-hitting-time scaling. A separate fixed-point amplitude-amplification interpolation achieves depth O(δ−γ)O(\delta^{-\gamma})O(δ−γ) and total queries O(δγ−2log⁡(1/ζ))O(\delta^{\gamma-2}\log(1/\zeta))O(δγ−2log(1/ζ)).
The stated depth counts walk applications, not complete gate depth. Repeated stationary-state preparation can negate the benefit of shallow runs, so the classical endpoint does not generally reproduce classical setup cost. Setup/update optimality, logarithm-free multiple-marked search, and interpolation from arbitrary initial distributions remain unresolved. Limited prior knowledge is handled with additional overhead.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ\epsilonϵ. More specifically, for an NNN-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps hhh satisfies h≥ln⁡(2ϵ)Nh \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}h≥ln(ϵ​2​)N​, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]\epsilon\in (0,1]ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.
Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.
Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.