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:1711.05295 · Physical Review A

Improved quantum backtracking algorithms using effective resistance estimates

Michael Jarret, Kianna Wan

Published Feb 27, 2018• 9 citations
arXivHTMLPDF

Abstract

We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing $k$ marked vertices, where $k$ is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})$ for finding a single marked vertex and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})$ for finding all $k$ marked vertices, where $T$ is an upper bound on the tree size and ${R}_{\mathrm{max}}$ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.

DOI
10.1103/physreva.97.022337

Related papers

Quantum walk search algorithms and effective resistance

Stephen Piddock

We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in $O(\sqrt{RW})$ quantum walk steps, where $R$ is the effective resistance and $W$ is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance $R$.

arXiv:1912.04196•Dec 9, 2019•4 citations

Quantum Search on Computation Trees

Jevgēnijs Vihrovs

We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex \(v\) in the tree of depth \(D\) is computed in \(t_v\) steps from its parent, then we show that detection of a marked vertex requires \(\text O(\sqrt {TD})\) queries to the steps of the computing procedures, where \(T = \sum_v t^2_v\). This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.

arXiv:2505.22405•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•0 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

Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification

Andreas Wichert

In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary $A$, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth $m$ with query complexity $\sqrt{\left(b_{avg}\right)^m}$ where $b_{avg}$ denotes the average branching factor, improving upon the commonly assumed $\sqrt{\left(b_{max}\right)^m}$, where $b_{max}$ is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.

quant-pharXiv:2606.28452•Jun 29, 2026•0 citations

Quantum-Walk Speedup of Backtracking Algorithms

Ashley Montanaro

$ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on $n$ variables, or outputs that none exists, and whose corresponding tree contains $T$ vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using $O(\sqrt{T} n^{3/2} \log n)$ tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.

Theory of Computing•Jan 1, 2018•70 citations

Quantum walk speedup of backtracking algorithms

Ashley Montanaro

We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. We also discuss how, for certain distributions on the inputs, the algorithm can lead to an exponential reduction in expected runtime.

arXiv:1509.02374•Sep 8, 2015•28 citations
We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing kkk marked vertices, where kkk is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of O\ifmmode~\else˜\fi(TRmax)\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})O\ifmmode~\else˜\fi​(TRmax​​) for finding a single marked vertex and O\ifmmode~\else˜\fi(kTRmax)\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})O\ifmmode~\else˜\fi​(kTRmax​​) for finding all kkk marked vertices, where TTT is an upper bound on the tree size and Rmax{R}_{\mathrm{max}}Rmax​ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.
We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in O(RW)O(\sqrt{RW})O(RW​) quantum walk steps, where RRR is the effective resistance and WWW is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance RRR.
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex vvv in the tree of depth DDD is computed in tvt_vtv​ steps from its parent, then we show that detection of a marked vertex requires O(TD)\text O(\sqrt {TD})O(TD​) queries to the steps of the computing procedures, where T=∑vtv2T = \sum_v t^2_vT=∑v​tv2​. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
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.
In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary AAA, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth mmm with query complexity (bavg)m\sqrt{\left(b_{avg}\right)^m}(bavg​)m​ where bavgb_{avg}bavg​ denotes the average branching factor, improving upon the commonly assumed (bmax)m\sqrt{\left(b_{max}\right)^m}(bmax​)m​, where bmaxb_{max}bmax​ is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.
$ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on nnn variables, or outputs that none exists, and whose corresponding tree contains TTT vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(Tn3/2log⁡n)O(\sqrt{T} n^{3/2} \log n)O(T​n3/2logn) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.
We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. We also discuss how, for certain distributions on the inputs, the algorithm can lead to an exponential reduction in expected runtime.