Quantum Backtracking in Qrisp Applied to Sudoku Problems
summary
Implements Montanaro-style quantum backtracking in Qrisp and reports a concrete gate budget for the controlled diffuser: 6n + 14 CX gates for a binary backtracking tree of depth n. Builds accept/reject oracles for Sudoku, compiles to current simulators and backends, and runs simulator experiments that solve 4x4 Sudoku with up to 9 empty fields. Claims this is the first compilable, general implementation and demonstrates practical resource counts and end-to-end execution.
AI-written summary · about
chapters (5)
- 0:00Introduction to quantum backtracking
- 13:00Quantum backtracking in Qrisp
- 16:39Applying to Sudoku problems
- 18:30Overhead and qubit requirements
- 19:50Performance and limitations
related talks
26mQrisp: A Framework for Compilable High-Level Programming of Gate-Based Quantu...
33mAn accessible approach to quantum algorithms with QFrame and Qrisp
19mAn Industry Perspective on the Path Forward in Quantum Optimization
14mDependency-Aware Compilation for Surface Code Quantum Architectures
20mJKQ: JKU Tools for Quantum Computing
18mAn Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits
55mScalable Quantum Compilation With Jasp
19mExtracting maximum value from today's quantum computers while prep