Note

This page was generated from docs/tutorials/grover_with_sampler.ipynb.

Database search with Grover’s algorithm using the Sampler primitive

In this tutorial, we will solve an unstructured search problem using Grover’s algorithm with the Sampler primitive Qiskit Runtime program.

Set up your local development environment

This tutorial requires a Qiskit Runtime service instance. If you haven’t done so already, follow these steps to set one up.

Background information

Unstructured search problem

In the olden days, you looked up a person’s phone number in a phone book. That is an easy task if you know the person’s name because a phone book is ordered alphabetically by name. However, the opposite task, that is, you are given a phone number and want to find out who it belongs to, is much more difficult. That is because a phone book is not ordered by phone numbers. This is an example of an unstructured search problem. To solve this problem with a classical computer, your best trick is to randomly pick an entry. On average, you will need to look up half of the entires (\(N/2\), if \(N\) is the total number of entries) to find the owner. If you have a quantum computer, however, you can use Grover’s algorithm to find the owner in \(\sqrt N\) tries. That means to identify the owner in a phone book that has 1 million numbers, you only need to do 1000 tries instead of 500,000!

Grover’s algorithm

In a nutshell, Grover’s algorithm uses a nice quantum trick called amplitude amplification to dramatically increase the chances of finding the correct answer - the owner of a phone number - in each try (iteration). That’s all we need to know now. We don’t have to understand the details about how Grover’s algorithm works to apply it, because Qiskit does it for us! However, if you are interested, you can read the chapter about Grover’s algorighm in the Qiskit textbook.

Next, let’s look at a concrete example.

Create Grover’s circuit

Define an unstructured search problem in Qiskit

In this simple example, you are given a small phone book that has 8 entries, person 0 to person 7, and we want to find the owner of a certain phone number. However, we are not allowed to look at the phone book directly. We are only allowed to consult an ‘oracle’: a black-box circuit that immediately tells us if our guess is right or wrong (like the Oracle in “The Matrix”).

import random
from qiskit.quantum_info import Statevector

secret = random.randint(0,7)  # the owner is randomly picked
secret_string = format(secret, '03b')  # format the owner in 3-bit string
oracle = Statevector.from_label(secret_string)  # let the oracle know the owner

Once we have the oracle, we can define the unstructured search problem using the AmplificationProblem class in Qiskit.

from qiskit.algorithms import AmplificationProblem

problem = AmplificationProblem(oracle, is_good_state=secret_string)

Construct Grover’s circuit for the problem

Now we are ready to construct the quantum circuits for Grover’s algorithm for this problem. Grover’s algorithm’s accuracy in finding the correct answer increases with the number of iterations. Let’s create a circuit with one and two iterations to see this effect.

from qiskit.algorithms import Grover

grover_circuits = []
for iteration in range(1,3):
    grover = Grover(iterations=iteration)
    circuit = grover.construct_circuit(problem)
    circuit.measure_all()
    grover_circuits.append(circuit)

Let’s look at the circuits:

# With 1 iteration
grover_circuits[0].draw()

# With 2 iterations
grover_circuits[1].draw()

Submit the circuits to a quantum computer on the cloud

Now that the Grover’s circuits are created, let’s submit them to a quantum computer on the cloud by using the Sampler program.

Connect to the Qiskit Runtime service

First, connect to the Qiskit Runtime service instance that you created in the first step.

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()

Grover’s algorithm determines the correct answer based on the highest probability of measurement outcomes. The Sampler primitive program is perfect for getting probabilities, so we will use that. In the cell below, we create an instance of the Sampler program, and start a Runtime session using the context manager (with ... as ... :), which automatically opens and closes the session for us.

The Sampler program allows a batch submission of circuits in a job. Here we are passing a list of two circuits (Grover with 1 iteration and 2 iterations) to the Sampler but only one call is needed to sample the probability of measurement outcomes of both circuits .

from qiskit_ibm_runtime import Sampler

with Sampler(circuits=grover_circuits) as sampler:
    result = sampler(circuit_indices=[0,1], shots=1000)
    print(result)

SamplerResult(quasi_dists=[{'001': 0.029, '010': 0.026, '101': 0.032, '011': 0.808, '000': 0.029, '111': 0.029, '110': 0.023, '100': 0.024}, {'101': 0.011, '010': 0.012, '000': 0.007, '011': 0.936, '111': 0.005, '110': 0.015, '100': 0.006, '001': 0.008}], metadata=[{'header_metadata': {}, 'shots': 1000}, {'header_metadata': {}, 'shots': 1000}])

Let’s look at the results:

from qiskit.tools.visualization import plot_histogram

# Extract bit string with highest probability from results as the answer
result_dict = result.quasi_dists[1]
answer = max(result_dict, key=result_dict.get)
print(f"As you can see, the quantum computer returned '{answer}' as the answer with highest probability.\n"
       "And the results with 2 iterations have higher probability than the results with 1 iteration."
)

# Plot the results
plot_histogram(result.quasi_dists, legend=['1 iteration', '2 iterations'])

As you can see, the quantum computer returned '011' as the answer with highest probability.
And the results with 2 iterations have higher probability than the results with 1 iteration.

Let’s print out the quantum result, along with the secret string, to check the quantum computer found the correct answer.

# Print the result and the correct answer.
print(f"Quantum answer: {answer}")
print(f"Correct answer: {secret_string}")
print('Success!' if answer == secret_string else 'Failure!')

Quantum answer: 011
Correct answer: 011
Success!

You can re-run the tutorials a few times to generate other random secret strings to see that we are not cheating! The quantum computer finds the correct answer every time.

import qiskit_ibm_runtime
qiskit_ibm_runtime.version.get_version_info()

'0.4.0'

from qiskit.tools.jupyter import *

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
qiskit-terra	0.20.1
qiskit-aer	0.10.4
qiskit-ignis	0.7.0
qiskit-ibmq-provider	0.19.1
qiskit	0.36.1
qiskit-nature	0.3.1
System information
Python version	3.9.7
Python compiler	Clang 10.0.0
Python build	default, Sep 16 2021 08:50:36
OS	Darwin
CPUs	8
Memory (Gb)	16.0
Wed May 11 17:35:00 2022 CEST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.