Project 1 - Grover's algorithm (part 1)

Demonstrating quantum advantage using a simple search algorithm

In this lecture, we shall discuss one of the most famous quantum algorithms - Grover's algorithm. Grover’s algorithm is a prototypical quantum algorithm which allows one to search an unstructured database faster than classical algorithms. This lecture is a part of OQN project, which is supposed to be completed by OQN members in teams within a span of approximately a month.

In this project, we will construct a quantum circuit for Grover’s algorithm. We will start with a special case with 4 states (N = 4), and generalize the algorithm to arbitrary N (in future projects).

Consider an unstructured phone book with 4 pages. Each of the pages, 1 through 4, contains a phone number of a different person. Let x = {1,2,3,4} be the page numbers and x = 2 mark the phone number of your mom. (This means your mom’s phone number is located on page 2.) Classically, you create a for loop on python, for example, and go through the phone book pages one by one before finding your mom’s phone number. How many trials do you need on average classically? How many trials do you need in the worst case?

Imagine an unstructured quantum phone book in which the phone numbers are encoded in quantum bits. How easy/hard is it to find your mom’s phone number using a quantum computer?

On a quantum computer, you can search your mom’s phone number much faster. How many trials (or page flips) do you need on a quantum computer? These questions (for N=4) can be answered analytically using pen and paper. For larger N, we shall demonstrate quantum advantage with Grover's algorithm on qiskit using Strangeworks platforms. Thanks to our friends at Strangeworks for the tool!

Please join this weekly meet-up to learn more about the answers to these questions. You can join in via Run the World on 20.05.2021 (next Thursday) at 7 PM (Nepali time) here:

Link to Event

News and Events

Check out a brief history of quantum computing at QC40: Physics of Computation Conference 40th Anniversary:

  1. Germany to support quantum computing with 2 billion euros.

  2. Dutch startup QphoX raises €2M to connect quantum computers with a quantum modem.

  3. First African quantum summit and career fair successfully concludes with around 350 participants. Stay tuned for more events here.