Solving the Sudoku Puzzle using Quantum Annealing - (:unkn) unknown (My University, 2023)
Η παρούσα διατριβή επικεντρώνεται στη μελέτη του γρίφου Sudoku μέσω της χρήσης κβαντικών συστημάτων της D-Wave. Αναπτύξαμε μια νέα μορφοποίηση πινάκων για το πρόβλημα Sudoku, η οποία επιτρέπει την εύκολη ενσωμάτωση των περιπτώσεων αναφοράς σε κβαντικές πλατφόρμες. Η μαθηματική ανάλυση προσδιορίζει τον ακριβή αριθμό των περιορισμών που απαιτούνται για την έκφραση του Sudoku ως μοντέλα Ising και QUBO. Επιπλέον, δημιουργήσαμε μια τεχνική για τη δημιουργία μοντέλων QUBO για παζλ Sudoku διαφορετικών μεγεθών. Εκτεταμένα πειράματα δείχνουν ότι το σύστημα D-Wave Advantage_system6.2 μπορεί να χειριστεί επιτυχώς μικρότερα Sudoku, αλλά τα μεγαλύτερα εξακολουθούν να μην είναι δυνατά. Επιπλέον, τα πειράματά μας επιβεβαιώνουν ότι οι υβριδικοί λύτες της D-Wave παράγουν πάντα έγκυρες λύσεις με χωρίς να παραβιάζουν τους δεδομένους περιορισμούς.

This thesis focuses on studying the Sudoku puzzle on D-Wave quantum systems. We have developed a new matrix formulation for the Sudoku problem, which allows for easy integration of benchmark instances in quantum platforms. Our mathemat- ical analysis determines the exact number of constraints needed to express Sudoku puzzles as Ising and QUBO formulations. Additionally, we have created a technique for generating QUBO models for Sudoku puzzles of different sizes. Our extensive experiments show that the D-Wave Advantage_system6.2 can handle smaller Su- doku instances, but larger ones are still not possible. Furthermore, our experi- ments confirm that the D-Wave hybrid solvers always produce valid solutions with- out violating the given constraints.
Keywords: Κβαντική Υπολογιστική, Αλγόριθμοι, Κβαντική Ανώπτηση, Βελτιστοποιήση, Σουντόκου; Quantum Computing, Algorithms, Quantum Annealing, Optimization, Sudoku