Learning Home Catalog Composer
Learning
Home Catalog Composer Return to tutorial
Learning
Grover's algorithm
BackgroundRequirementsSetupStep 1: Map classical inputs to a quantum problemSpecific Grover's instanceGroverOperatorFull Grover circuitStep 2: Optimize problem for quantum executionStep 3: Execute using Qiskit PrimitivesStep 4: Post-process, return result in classical format

Grover's algorithm

Category

Workflow example

Topics

Scheduling
Download notebook Download notebook

Background

Usage estimate: 4 seconds on ibm_nairobi. (NOTE: This is an estimate only. Your runtime may vary.)

Amplitude amplification is a general purpose quantum algorithm, or subroutine, that can be used to obtain a quadratic speedup over a handful of classical algorithms. Grover’s algorithm was the first to demonstrate this speedup on unstructured search problems. Formulating a Grover's search problem requires an oracle function that marks one or more computational basis states as the states we are interested in finding, and an amplification circuit that increases the amplitude of marked states, consequently suppressing the remaining states.

Here, we demonstrate how to construct Grover oracles and use the GroverOperator from the Qiskit circuit library to easily set up a Grover's search instance. The runtime Sampler primitive allows seamless execution of Grover circuits.

Requirements

Before starting this tutorial, ensure that you have the following installed:

  • Qiskit SDK 1.0 or later, with visualization support (pip install 'qiskit[visualization]')
  • Qiskit Runtime (pip install qiskit-ibm-runtime) 0.22 or later

Setup

Here we import the small number of tools we need for this tutorial.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'ibm_algiers'

Step 1: Map classical inputs to a quantum problem

Grover's algorithm requires an oracle that specifies one or more marked computational basis states, where "marked" means a state with a phase of -1. A controlled-Z gate, or its multi-controlled generalization over NN qubits, marks the 2N12^{N}-1 state ('1'*NN bit-string). Marking basis states with one or more '0' in the binary representation requires applying X-gates on the corresponding qubits before and after the controlled-Z gate; equivalent to having an open-control on that qubit. In the following code, we define an oracle that does just that, marking one or more input basis states defined through their bit-string representation. The MCMT gate is used to implement the multi-controlled Z-gate.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Specific Grover's instance

Now that we have the oracle function, we can define a specific instance of Grover search. In this example we will mark two computational states out of the eight available in a three-qubit computational space:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

GroverOperator

The built-in Qiskit GroverOperator takes an oracle circuit and returns a circuit that is composed of the oracle circuit itself and a circuit that amplifies the states marked by the oracle. Here, we decompose the circuit to see the gates within the operator:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Repeated applications of this grover_op circuit amplify the marked states, making them the most probable bit-strings in the output distribution from the circuit. There is an optimal number of such applications that is determined by the ratio of marked states to total number of possible computational states:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Full Grover circuit

A complete Grover experiment starts with a Hadamard gate on each qubit; creating an even superposition of all computational basis states, followed the Grover operator (grover_op) repeated the optimal number of times. Here we make use of the QuantumCircuit.power(INT) method to repeatedly apply the Grover operator.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Step 2: Optimize problem for quantum execution

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Step 3: Execute using Qiskit Primitives

Amplitude amplification is a sampling problem that is suitable for execution with the Sampler runtime primitive.

Note that the run() method of Qiskit Runtime SamplerV2 takes an iterable of primitive unified blocs (PUBs). For sampler, each PUB is an iterable in the format (circuit, parameter_values). However, at a minimum, it takes a list of quantum circuit(s).

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Step 4: Post-process, return result in classical format

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'0.23.0'
Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'1.0.2'