EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Quantum Backtracking in Qrisp Applied to Sudoku Problems

Raphael Seidel, René Zander, Matic Petrič, Niklas Steinmann, David Liu, Nikolay Tcholtchev, Manfred Hauswirth

ACM Transactions on Quantum Computing · 30.09.2026 · 7 (3) · 1-32

DOI: 10.1145/3799888 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Quantum Computing, online erschienen am 11.07.2026. Verfasst von Raphael Seidel und 6 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Federal Ministry for Economic Affairs and Climate Action, European Union.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Federal Ministry for Economic Affairs and Climate Action
  • European Union

Zitieren

APA

Seidel, R., Zander, R., Petrič, M., Steinmann, N., Liu, D., Tcholtchev, N., & Hauswirth, M. (2026). Quantum Backtracking in Qrisp Applied to Sudoku Problems. ACM Transactions on Quantum Computing, 7(3), 1-32. https://doi.org/10.1145/3799888

Vancouver

Seidel R, Zander R, Petrič M, Steinmann N, Liu D, Tcholtchev N, et al. Quantum Backtracking in Qrisp Applied to Sudoku Problems. ACM Transactions on Quantum Computing. 2026;7(3):1-32. doi:10.1145/3799888

BibTeX
@article{Seidel2026,
  author = {Seidel, Raphael and Zander, René and Petrič, Matic and Steinmann, Niklas and Liu, David and Tcholtchev, Nikolay and Hauswirth, Manfred},
  title = {Quantum Backtracking in Qrisp Applied to Sudoku Problems},
  journal = {ACM Transactions on Quantum Computing},
  year = {2026},
  volume = {7},
  number = {3},
  pages = {1--32},
  doi = {10.1145/3799888}
}
Kostenlos starten →