This chapter covers:
- Implement a quantum algorithm for searching unstructured data.
- Recognize how the resource estimator for the QDK can help understand the costs for running particular algorithms.
- Implement reflections of quantum registers about states.
Suppose you want to search through some data, such as to find a contact’s phone number. If that 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 10.1: Pseudocode for binary search
- Pick a name/phone number pair in the middle of your list, call this pair your pivot.
- If the pivot’s name is the name you’re looking for, return the pivot’s phone number.
- If the name you’re looking for comes before the pivot’s name, repeat the search on the first half of the list.
- Else, if the name you’re looking for comes after the pivot’s name, repeat the search on the second half of the list.
Not just a character on Star Trek.
In this Chapter, we talk a lot about searching through data. That data can come in a lot of different forms.
Kinds of data
- Phone numbers
- Names of dogs
- Weather measurements
- Types of doorbells
What all of these have in common is that we can represent them on classical computers as strings of bits, using a variety of different conventions about how that representation should work.