7 Grover’s search algorithm
This chapter covers
- Using Grover’s algorithm to solve simple search problems
- Implementing simple classical functions on a quantum computer
- Implementing and testing end-to-end quantum algorithms
- Using Q# and Qiskit to implement Grover’s algorithm
As we saw in chapter 6, solving a classical problem on a quantum computer takes several steps (see figure 7.1). It starts with converting the classical problem to its “quantum” formulation that allows us to come up with a quantum algorithm for it. Then, this algorithm has to be implemented as a quantum program. Finally, we need to compare the performance of the quantum solution to that of the best classical solution for the same problem to decide whether using the quantum algorithm for this problem is a good idea.
In chapter 6, we learned the general approach to the first step, converting a classical computation that describes the problem into an equivalent quantum computation. In this chapter, we’ll consider the second step and learn an example of a quantum algorithm for solving a classical problem. In the last two chapters, we’ll see how to implement this algorithm as an end-to-end solution for a specific problem and to evaluate its performance.