Master's Thesis

Solving sudoku by quantum computation

Final Thesis 1.51 MB

Author of thesis: Ing. Deepthy Saji

Acad. year: 2024/2025

Supervisor: doc. Mgr. Jaroslav Hrdina, Ph.D.

Reviewer: Dietmar Hildenbrand

Abstract:

In this thesis, Sudoku is solved by the well-known quantum algorithms. The algorithms used are Grover’s algorithm and quantum counting that uses quantum phase estimation. The grid size of the Sudoku is varied to study the impact on the quantum hardware such as Qiskit while performing quantum computation to solve the Sudoku using these algorithms. Furthermore, this thesis explores an alternative implementation pathway for these Sudoku-solving quantum algorithms using Clifford algebra, offering insights into the improvement of resources for quantum computation.

Keywords:

Quantum computation, Grover’s algorithm, Quantum phase estimation, Quantum Register Algebra.

Date of defence

17.06.2025

Result of the defence

Defended (thesis was successfully defended)

znamkaBznamka

Grading

B

Process of defence

The student presented their master’s thesis, and the supervisor read their evaluation report in person. The opponent joined the examination online, read their report aloud, and posed several questions. The student responded to the questions effectively, and the opponent expressed satisfaction with the answers provided.

Language of thesis

English

Faculty

Department

Study programme

Applied and Interdisciplinary Mathematics (N-AIM-A)

Composition of Committee

doc. Ing. Luděk Nechvátal, Ph.D. (předseda)
prof. RNDr. Josef Šlapal, CSc. (místopředseda)
doc. Ing. Petr Tomášek, Ph.D. (člen)
doc. Ing. Jiří Šremr, Ph.D. (člen)
prof. RNDr. Miloslav Druckmüller, CSc. (člen)
Prof. Bruno Rubino, Ph.D. (člen)
Prof. Corrado Lattanzio, Ph.D. (člen)
Gennaro Ciampa, Ph.D. (člen)

Supervisor’s report
doc. Mgr. Jaroslav Hrdina, Ph.D.

The original task of the thesis was completed relatively quickly, and the topic was gradually expanded with further perspectives on mathematical description. At the same time, unexpected problems arose during the implementation of higher-dimensional algebras (based on memory and hexadecimal representation of numbers). The topic thus developed in an interesting and unexpected direction. How is it possible to work in geometric algebra with a larger number of generators using appropriate mathematical apparatus.  For this purpose, the available computational resources were analyzed, and the most suitable method was selected. The student worked independently, and the thesis includes the theory, proposed solution, and implementation.
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita A
Schopnost interpretovat dosažené výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii B
Logické uspořádání práce a formální náležitosti A
Grafická, stylistická úprava a pravopis B
Práce s literaturou včetně citací B
Samostatnost studenta při zpracování tématu A

Grade proposed by supervisor: A

Reviewer’s report
Dietmar Hildenbrand

This work is based on the example of the Quiskit tutorial [26] for a quantum computing solution of a 2x2 Sudoku. This is reasonable extended with an approach in order to compute important parameters such as the number of solutions. This 2x2 solution is then extended in a straightforward way to a 2x3 Sudoku. A drawback of the thesis is, that the state-of-the-art of other quantum computing based approaches is missing and not discussed.
Since the simulation of the 2x3 Sudoku failed with Quiskit, an advantage of this work is, that also other promising mathematical tools to solve this problem are investigated and discussed.
The structure of the thesis in principle is good, but, as already mentioned, the state of the art is missing. Also some important explanations are missing. The rules of Sudoku, for instance, are not explained. They can only be derived by the algorithm. The thesis also lacks of descriptions where it would be important to have some more detailed information as for instance in order to better understand Example 5.2.1. Also the listings and figures of the  results of the quantum computing algorithms and how to interpret them could be explained in more detail.

Some additional remarks:
•    Introduction:
      o    „solve most of the problems“: better would be something like „solve many problems“
      o    Not completed sentence „support solving problems that classical computers ...“
      o    „From the 1980s, prominent results emerged in quantum mechanics“ seems to mean quantum computing
•    Figure 2.1: X is not explained
•    Section 5.4.9 „it takes inputs quantum bits“?
•    In the introduction of Chapt. 7 is the use of „Geometric Algebra“ and „Clifford Algebra“ confusing
•    Page 46: „from the from“
•    In Chapt. 7.5 is the last sentence a bit confusing. It should be better used in Chapt. 7.6.
•    In the introduction of Chapt. 8, the last sentence seems to be not complete.
•    From the language point of view, there are some typos and the article „the“ is sometimes missing.
•    The reference [3] is wrong. GAALOP is not from Christian Perwass but from Christian Steinmetz and Dietmar Hildenbrand.
Evaluation criteria Grade
Splnění požadavků a cílů zadání C
Postup a rozsah řešení, adekvátnost použitých metod C
Vlastní přínos a originalita B
Schopnost interpretovat dosaž. výsledky a vyvozovat z nich závěry B
Využitelnost výsledků v praxi nebo teorii B
Logické uspořádání práce a formální náležitosti D
Grafická, stylistická úprava a pravopis D
Práce s literaturou včetně citací D
Topics for thesis defence:
  1. - Do you know other quantum computing approaches in order to solve Sudoku?
  2. - How do you distinguish between Geometric Algebra and Clifford Algebra?
  3. - How good is the scalability of your approach in order to study the complexity in quantum computing?

Grade proposed by reviewer: C

Responsibility: Mgr. et Mgr. Hana Odstrčilová