Optimizing Quantum Annealing to Advance Graph Coloring Algorithms

Overview

Quantum computing is a rapidly growing field that applies quantum mechanics to computer science and its algorithms, and it has many applications, including optimization problems, where the goal is to obtain an optimal solution to a multivariable problem. Quadratic unconstrained binary optimization problems can represent combinatorial optimization problems, which have a wide range of applications from artificial intelligence to finance. Thus, Sudoku problems, which can be classified as graph-coloring problems, can be represented as optimization problems so that they can be solved with quantum annealing, the process of using quantum fluctuations to solve optimization problems. This project aimed to use Sudoku as a method of evaluating the performance of the latest quantum annealer and to develop a novel method to reduce the number of variables in a QUBO formulation representing Sudoku problems. Creating a more efficient formulation has applications in artificial intelligence and data mining. First, the Sudoku problem was formulated as an objective function so that it could be converted into a QUBO formulation and the variables could be reduced. Then, test cases of various difficulties were created and each was solved with both quantum annealing and simulated annealing. The experiment showed that both quantum annealing and simulated annealing can be used to effectively solve Sudoku problems, although they do have limitations when the number of missing digits from the puzzle exceeds a certain amount. The variable reduction technique was also proven to be effective as it reduced 85 to 99% of variables in all test cases.

Awards (1)

• Third Award of $1,000 $1,000

Competition history

• ISEF 2023 Mathematics · Entry MATH026 · Dallas, Texas, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.