11 Searching with quantum computers

In chapter 10, we got to dig into our first application of quantum computing by working with our colleague Marie to help calculate the ground state energy of a hydrogen molecule. To do so, we implemented a Hamiltonian simulation algorithm that used some of the phase-estimation techniques we developed in chapter 9.

In this chapter, we’ll look at another application of quantum computing: searching data. This application area is always a hot topic in high-performance computing areas and shows off another way we can use techniques we learned previously to build up another quantum program, in this case based on phase kickback. We also look at the resources estimator built into the Quantum Development Kit (QDK) to see how it can help us understand the scaling of our quantum programs, even when they get too big to run locally.

11.1 Searching unstructured data

Suppose we want to search through some data to find a contact’s phone number. If the list of contacts is sorted by name, then it’s pretty easy to find the phone number associated with a particular name by using a binary search:

Algorithm 11.1: Pseudocode for binary search

11.2 Reflecting about states

11.2.1 Reflection about the all-ones state

11.2.2 Reflection about an arbitrary state

11.3 Implementing Grover’s search algorithm

11.4 Resource estimation

Summary