Quantum Backtracking in Qrisp Applied to Sudoku Problems
<|reference_start|>Quantum Backtracking in Qrisp Applied to Sudoku Problems: 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.<|reference_end|>
@article{seidel2024quantum,
    title={Quantum Backtracking in Qrisp Applied to Sudoku Problems},
    author={Raphael Seidel, Ren'e Zander, Matic Petriv{c}, Niklas Steinmann,
  David Q. Liu, Nikolay Tcholtchev, Manfred Hauswirth},
    journal={arXiv preprint arXiv:2402.10060},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10060},
    primaryClass={quant-ph cs.DS cs.PL}
}