I have recently been using Grover's algorithm to solve sudoku by coding. I am unsure how to interpret the graph produced. Could anyone explain? I have included a link where you can view the graph: https://github.com/seop02/sudoku-using-grover/blob/main/sudoku/%08sudoku_4.ipynb
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In your result after two iterations of Grover's search, after measurement, you've got a distribution of probabilities. Each probability in this distribution corresponds to what you call a "condition", which may contain any number of elements between an empty list $[ \emptyset ]$ ("00000000") and $[0,1,2,3,4,5,6,7]$ ("11111111").
That is each probability corresponds to a vector encoding. The highest probability is 0.023 and it corresponds to "01110101". What Grover's search does every iteration it amplifies the amplitude of the answer, i.e. condition to which oracle says "yes". In other words, imagine that the solution you are looking for already exists among all possible solutions. The oracle itself looks at all candidate solutions at the same time (i.e. a linear combination of those candidate solutions) and gives an answer to all of them. The Grover's search is a technique to amplify the probability of the measurement(s) corresponding to the "yes"-answer, while reducing the probabilities of measuring "no"-answers.
Let's take a look how the most probable answer of "01110101" encodes your conditions. The qubit-0 corresponds to the presence or absence of 0 in the "conditions" list. The qubit-1 corresponds to the presence of 1, and so on.
Therefore, you will have to multiply the bitvector in an element-wise manner with all possible conditions $[0,1,2,3,4,5,6,7]$ to decode the answer. That gives us $[0*0,1*1,1*2,1*3,0*4,1*5,0*6,1*7] = [1,2,3,5,7]$.
I would also suggest that you perform more iterations so that the most promising answer becomes yet more prominent. We know that in the worst case this will be $\sqrt N = \sqrt {2^8} = 16$ iterations. However, I suspect that this will be even less than that.
