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:1908.11291 · Lecture notes in computer science

Practical Implementation of a Quantum Backtracking Algorithm

Simon Martiel, Maxime Remaud

Published Jan 1, 2020• 8 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-38919-2_49

Related papers

Tracing Quantum State Distinguishers via Backtracking

Mark Zhandry

Lecture notes in computer science•Jan 1, 2023•4 citations

On quantum algorithms

CleveRichard, EkertArtur, HendersonLea +2 more

Complexity•Sep 1, 1998•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.

arXiv:1509.02374•Theory of Computing•Jan 1, 2018•131 citations

Quantum Backtracking in Qrisp Applied to Sudoku Problems

Raphael Seidel, René Zander, Matic Petrič +4 more

The quantum backtracking algorithm proposed by Ashley Montanaro raised considerable interest, as it provides a quantum speed-up for a large class of classical optimization algorithms. It does not suffer from Barren-Plateaus, that affect variational quantum algorithms, and transfers well into the fault-tolerant era, as it requires only a limited number of arbitrary angle gates. Despite its potential, the algorithm has seen limited implementation efforts, presumably due to its abstract formulation. In this work, we provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances. For a single controlled diffuser of a binary backtracking tree with depth n , our implementation requires only 6 n +14 CX gates. We detail the process of constructing accept and reject oracles for Sudoku problems using our interface to quantum backtracking. The presented code is written using Qrisp, a high-level quantum programming language, making it executable on most current physical backends and simulators. Subsequently, we perform several simulator based experiments and demonstrate solving 4× 4 Sudoku instances with up to nine empty fields. This is, to the best of our knowledge, the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.

arXiv:2402.10060•ACM Transactions on Quantum Computing•Apr 20, 2026•4 citations

On quantum algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Complexity•Sep 1, 1998•28 citations

Progress in Quantum Algorithms

Peter W. Shor

Springer eBooks•Apr 2, 2007•3 citations
$ $ 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.
The quantum backtracking algorithm proposed by Ashley Montanaro raised considerable interest, as it provides a quantum speed-up for a large class of classical optimization algorithms. It does not suffer from Barren-Plateaus, that affect variational quantum algorithms, and transfers well into the fault-tolerant era, as it requires only a limited number of arbitrary angle gates. Despite its potential, the algorithm has seen limited implementation efforts, presumably due to its abstract formulation. In this work, we provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances. For a single controlled diffuser of a binary backtracking tree with depth n , our implementation requires only 6 n +14 CX gates. We detail the process of constructing accept and reject oracles for Sudoku problems using our interface to quantum backtracking. The presented code is written using Qrisp, a high-level quantum programming language, making it executable on most current physical backends and simulators. Subsequently, we perform several simulator based experiments and demonstrate solving 4× 4 Sudoku instances with up to nine empty fields. This is, to the best of our knowledge, the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.