# Grover's algorithm using the Sampler primitive

## Background

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 make use of the

## Setup

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

Output:

## Initialize Runtime service

Here we instantiate the Runtime service that gives access to the quantum devices and the simulator that we use in this tutorial. We will first use a simulator to validate our circuit, then execute it on a real quantum system.

Output:

## Define a Grover experiment

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 $N$ qubits, marks the $2^{N}-1$ state (

Output:

### 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:

Output:

### The GroverOperator

The built-in Qiskit

Output:

Repeated applications of this

Output:

### 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 (

Output:

## Execution with the Sampler primitive

Amplitude amplification is a sampling problem that is suitable for execution with the

Output:

```
'ibmq_qasm_simulator'
```

Output:

Now we execute the circuit by using

Output:

To see that the marked states are visible in the returned distribution, we convert the returned quasi-probability distribution from integer to bit-string representation to compare to the list of

Output:

Output:

Having verified that our code does indeed produce the desired outcome, we now execute it on a real device, creating an

Output:

```
'ibmq_lima'
```

Output:

Output:

Output:

Output:

Output:

```
'0.11.3'
```

Output:

```
'0.25.0'
```