Grover's algorithm is a quantum algorithm that can be used to invert a function more quickly than any classic algorithm. Essentially, that means if there are N possible solutions to a function, only one of which is correct, Grover's algorithm works to efficiently find the one solution out of the pack. Grover's algorithm is sometimes referred to as quantum search or even as quantum database search. This chapter first introduces Grover's algorithm in depth.
It then goes over a specific use case of Grover's algorithm to illustrate its potential: that of solving the Boolean satisfiability problem to figure out which inputs correspond to satisfying a certain Boolean function, with an example of using 3SAT that returns true for exactly one combination of inputs.
To show Grover's algorithm at work for 3SAT, we will have to extend our work with quantum OR gates in the previous chapter to work over three inputs. The chapter will close with a few words about using Grover's algorithm more generally to solve the case of inverting other types of functions and provide some comments on its generality.
The following topics are covered in this section:
- Introduction to Grover's algorithm
- Implementing a 3SAT function to use as a Grover's algorithm checker
- Implementing Grover's algorithm