Matic Petrič
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Matic Petrič has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- David Q. Liu
Rosen Center for Advanced Computing, Purdue University, West Lafayette, IN 47907, USA
1 shared publication - Manfred Hauswirth
Fraunhofer FOKUS, Berlin, Germany
1 shared publication - Niklas Steinmann
SQC, Fraunhofer-Institut für Offene Kommunikationssysteme FOKUS
1 shared publication - Nikolay Tcholtchev
Fraunhofer FOKUS
1 shared publication - Raphael Seidel
SQC, Fraunhofer-Institut für Offene Kommunikationssysteme FOKUS
1 shared publication - René Zander
SQC, Fraunhofer-Institut für Offene Kommunikationssysteme FOKUS
1 shared publication
Latest Publications
- Open Access
- 11 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 7 (3) , 1-32
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, 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.
- 11 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 7 (3) , 1-32
Open AccessQuantum 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, 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.