10 Grover’s search algorithm

 

This chapter covers

  • Understanding Grover’s search algorithm
  • Grover’s search algorithm relative to existing data storage systems
  • Using Grover’s search from classical Java code

In this chapter, we answer two important questions posed by developers:

  • When is it a good idea to use Grover’s search algorithm?
  • How does the algorithm work?

Grover’s search algorithm is one of the most popular and well-known quantum algorithms. Despite its name, this algorithm is not really a replacement for the search algorithms used today in classical software projects. In this chapter, we explain what kind of problems can benefit from Grover’s search algorithm. After reading this chapter, you will be able to determine whether a particular application you are dealing with can use Grover’s search algorithm. If so, you can immediately use the classical API in Strange to use Grover’s algorithm.

10.1 Do we need yet another search architecture?

Many excellent libraries, protocols, and techniques are available for searching structured and unstructured data systems. Grover’s search algorithm doesn’t compete with those technologies.

10.1.1 Traditional search architecture

Searching a database is one of the most popular tasks delegated to computers. Many IT applications are architected in a three-tier approach, as shown in figure 10.1.

Figure 10.1 Typical three-layered architecture for classical applications

The three layers that are involved in this approach are as follows:

10.1.2 What is Grover’s search algorithm?

10.2 Classical search problems

10.2.1 General preparations

10.2.2 Searching the list

10.2.3 Searching using a function

10.3 Quantum search: Using Grover’s search algorithm

10.4 Probabilities and amplitudes

10.4.1 Probabilities

10.4.2 Amplitudes

10.5 The algorithm behind Grover’s search

10.5.1 Running the example code

Summary