8 Solve N queens puzzle using Grover’s algorithm
This chapter covers
- Applying Grover’s algorithm to a non-trivial search problem
- Implementing classical problem constraints on a quantum computer
- Implementing and testing quantum algorithms end-to-end
- Using Q# and Qiskit to write hybrid programs
In the previous chapter, we learned to solve unstructured search problems — problems which, given a black box implementation of a function that returns \(0\) or \(1\), look for a function input \(x\) for which \(f(x) = 1\). There are plenty of problems that can be formulated this way, since pretty much any task can be formulated as a “yes/no” problem: “Is the value \(x\) a solution to the problem I’m looking at? \(f(x) = 1\) if it is, and \(0\) if it’s not”.
The problem we used to test the algorithm implementation was a very simple one: the function identified elements of the given list. This example allowed us to experiment with the algorithm without putting a lot of effort into implementing the oracle that serves as the input to the algorithm, so it was a good starting point. Its downside, however, is that the algorithm looks for one of the values from a pre-defined list that is literally hardcoded into the solution. We need to know the answer upfront before we can start looking for it!