8 Solving N queens puzzle using Grover’s algorithm
This chapter covers
- Applying Grover’s algorithm to a nontrivial search problem
- Implementing search problem constraints on a quantum computer
- Implementing and testing quantum algorithms end to end
- Using Q# and Qiskit to write hybrid programs
In chapter 7, we learned to use Grover’s algorithm for solving search problems—problems that, given a black box implementation of a function that returns \(0\) or \(1\), aim to find a function input \(x\) for which \(f(x) = 1\). There are plenty of problems that can be formulated as a search problem, since pretty much any task can be phrased 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 our implementation of Grover’s algorithm was a very simple one: looking for 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 describes the problem, so it was a good starting point. Its downside, however, is that the algorithm looks for one of the values from a predefined list that is literally hardcoded into the solution. We know the answer up front before we can start looking for it!