Quantum Backtracking in Qrisp Applied to Sudoku Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929485544161280 |
|---|---|
| author | Seidel, Raphael Zander, René Petrič, Matic Steinmann, Niklas Liu, David Q. Tcholtchev, Nikolay Hauswirth, Manfred |
| author_facet | Seidel, Raphael Zander, René Petrič, Matic Steinmann, Niklas Liu, David Q. Tcholtchev, Nikolay Hauswirth, Manfred |
| contents | 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 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 $6n+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 4x4 Sudoku instances with up to 9 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10060 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Backtracking in Qrisp Applied to Sudoku Problems Seidel, Raphael Zander, René Petrič, Matic Steinmann, Niklas Liu, David Q. Tcholtchev, Nikolay Hauswirth, Manfred Quantum Physics Data Structures and Algorithms Programming Languages 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 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 $6n+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 4x4 Sudoku instances with up to 9 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. |
| title | Quantum Backtracking in Qrisp Applied to Sudoku Problems |
| topic | Quantum Physics Data Structures and Algorithms Programming Languages |
| url | https://arxiv.org/abs/2402.10060 |