Solving Sudoku Using Quantum Computing
If you were to name one of the supposed superiorities of quantum computing over classical computing, what might immediately come to mind is the somewhat ambiguous phrase that quantum computers can do things much faster than regular computers.
While this is definitely true, the same phrase could be applied to current classical computers in comparison to classical computers that existed in, say the 1960s. As technology evolves, computers have consistently gotten more powerful, and thus faster. So, simply extending this sentiment to quantum computers does not shed light on the reason for which quantum computers are “faster”.
It’s not just a increase in computing power or improvement in hardware, but because of the fundamental way a quantum computer works that sets it a part from a classical computer.
Let’s say you had a bookshelf filled with books. Each of these books have multiple pages and on one page of one book, you know there is a green checkmark. Your task is to find this green checkmark.
If you were to approach this problem yourself, what you would probably end up doing is just taking each book and flipping through each page until you notice the green checkmark.
If you were to enlist the help of your classical computer, it would take the exact same strategy as you — examining each individual page until it finds the right one. Only, since it is a computer, it could do that much faster than you. And of course, if you get more developed computers (your current laptop rather than a 1970s desktop), the process would keep speeding up incrementally.
On the other hand, if you were to use a quantum computer, it would be able to flip through each book at the same time or perhaps even look at each page at the same time. Which is not only faster but fundamentally different: the classical computers were doing one thing at a time whereas quantum computers can do “multiple” things at a time.
The reason for this is a concept known as superposition. As you may know, classical computers use bits which are either in a 0 or 1 state. Quantum computers on the other hand use qubits which are a combination of 0 and 1 — they can be in 0 and 1 to a certain extent at the same time — and so, they are said to be in “superposition”.
This problem of finding the green checkmark in a library of books is called an unstructured search problem which can be generalized to the idea that you have a list of items and your goal is to find the “winning item” (just, a specific item from the list).
Say your list has N values in it. In the best case scenario, a computer would take one query (one look at the list) to solve the problem. But, in the worst case, it could N tries if it keeps not finding the winning one. This averages out to N/2 tries.
A quantum computer on the other hand could take about sqrt(N) queries.
How? Using something called Grover’s Algorithm which was developed to solve this exact problem.
What is Grover’s Algorithm?
First off, Grover’s algorithm assumes that the number of solutions, N is a power of 2, that is N = 2^n for some nonnegative integer n.
- Initialize 2^n qubits to the state |0>.
- Create an equal superposition of all possible states, |s> by applying Hadamard gates to each qubit.
- Pass it through the quantum oracle — i.e. a function which returns a unique value for the winning state.
- Pass it through the “Grover diffuser” — another functions which flips states over the average (more on this below).
- Keep repeating step 2 and 3.
Before we begin our search, we know nothing about each item in the list. All guesses are equally good and so the “goodness” of all the searches is an equal superposition of all possibilities. Since we have 2^n items in the list, if we were to measure the quantum state, it would collapse to either one of the bases with equal probability and so the probability of guessing the winning state on the first try is 1/(2^n).
What we want to do is increase the probability that we choose the winning state and decrease the probability that we choose anything else. This is done using amplification: the process of stretching the amplitude of the winning state and and shrinking that of the others so that we are more likely to choose the winning one.
This is done in two steps. First off, the oracle. This function is kind of like a filter that is applied to all the values in the list and returns a unique value for the item we are looking for. Specifically, it keeps the phase of all the items we are not looking for positive and changes the phase of the one we are looking for to a negative.
What this does is brings the average of all the amplitudes down to less than amplitudes of all the other non-winning list items.
Then, the Grover diffuser reflects these states over said average. This makes the amplitude of the winning state much higher than the average and the other amplitudes much smaller. So, now the probability of choosing the winning state is much higher than that of the other states.
After several repetitions of the oracle and Grover diffuser, the probability of choosing the winning state will get higher and higher and converge to 100%. However in most cases, it will never quite reach full certainty. This is because it require all the other states to be perfectly reflected over the average to 0 which only happens in some problems.
It turns out that after about sqrt(N) repetitions, the answer gets reasonably close.
Alright, now that we understand the intuition behind the algorithm, let’s apply it to figuring out all the possible “correct” configurations of a sudoku problem.
Sudoku x Grover’s Algorithm
The specific sudoku problem is going to involve a 2 by 2 grid (rather than a 9 x 9 one), which admittedly is a bit less interesting. The reason we are doing this is because then we only have to deal with the digits 0 and 1 which is much easier in binary.
We are going to be using IBM’s qiskit python library. So, first up, we import everything we need.
Let’s say our sudoku grid looked like this.
In order for our solution to be “correct”, we need to have v_0 not equal v_1, v_0 not equal v_2, v_2 not equal v_3 and v_1 not equal v_3.
We create a list of lists called “clause_list” which contains all of these criteria
In order to check if the values in these rows/columns are equal to each other or not, we are going to employ the “XOR” gate. This is a pretty fundamental gate in classical computing which returns one answer if the inputs are the same and another answer if the values are different. In this case, we are going to determine if these values are the same or different individually with another “output” qubit using the CNOT gate which is the quantum equivalent of the XOR gate.
The CNOT gate returns a 1 if the qubits are different and 0 if they are the same. This way, the output qubit’s value will only be flipped to 1 if the input qubits values are different.
If we apply this function to all of the aforementioned pairs of qubits and all of the states are 1, then we know the solution is correct.
But, in order to check if all the states are 1, we are going to combine them all onto another qubit called “out_0” using an extended toffoli gate which is kind of like the classical “AND” gate in that it only returns a 1 if all the inputs are 1.
Now, a principal part of the grover algorithm is that we repeat the fundamental series of steps multiple times. So, after we take these measurements, we need to reverse the states back to how they were. Luckily, the CNOT gate is it’s own inverse so two successions of it will return things to how they used to be.
Now, we define our quantum circuit with a Quantum register (var_qubits) for the grid values, a quantum register (clause_qubits) for comparing them and output_qubit for evaluating all the clause qubits. Then, we have a classical register for measuring. We put this all into a quantum circuit called qc and apply the sudoku oracle to it.
Next, we define the diffuser which initializes the qubits in a superpositioned state, flips everything over the average. We return it as a cumulative gate so that it can be neatly used in the circuit.
Then, we add everything to the quantum circuit: the oracle and the diffuser, twice.
Finally, we can simulate the algorithm 1024 times and get
As you can see, the probabilities of choosing the states 0110 and 1001 are significantly higher. These states correspond to the configurations where v_0 = 1, v_1 = 0, v_2 = 0 and v_3 = 1 and then when v_0 = 0, v_1 = 1, v_2 = 1, and v_3 = 0 which is exactly what we want!
