Note

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

# 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 `GroverOperator`

from the Qiskit circuit library to easily setup a Grover’s search instance. The runtime `Sampler`

primitive allows for seamless execution of Grover circuits, including automatic compilation, error suppression, and readout error mitigation techniques.

## Setup¶

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

```
[24]:
```

```
# Built-in modules
import math
# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import GroverOperator, MCMT, ZGate
from qiskit.visualization import plot_distribution
# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService, Sampler
```

## Initialize Runtime service and select backends¶

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.

```
[3]:
```

```
service = QiskitRuntimeService()
```

```
[32]:
```

```
sim = service.get_backend("ibmq_qasm_simulator")
backend = service.get_backend("ibm_brisbane")
```

## 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 (`'1'`

*\(N\) 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.

```
[5]:
```

```
def grover_oracle(marked_states):
"""Build a Grover oracle for multiple marked states
Here we assume all input marked states have the same number of bits
Parameters:
marked_states (str or list): Marked states of oracle
Returns:
QuantumCircuit: Quantum circuit representing Grover oracle
"""
if not isinstance(marked_states, list):
marked_states = [marked_states]
# Compute the number of qubits in circuit
num_qubits = len(marked_states[0])
qc = QuantumCircuit(num_qubits)
# Mark each target state in the input list
for target in marked_states:
# Flip target bit-string to match Qiskit bit-ordering
rev_target = target[::-1]
# Find the indices of all the '0' elements in bit-string
zero_inds = [ind for ind in range(num_qubits) if rev_target.startswith("0", ind)]
# Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
# where the target bit-string has a '0' entry
qc.x(zero_inds)
qc.compose(MCMT(ZGate(), num_qubits - 1, 1), inplace=True)
qc.x(zero_inds)
return qc
```

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

```
[6]:
```

```
marked_states = ["011", "100"]
oracle = grover_oracle(marked_states)
oracle.draw("mpl")
```

```
[6]:
```

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

```
[7]:
```

```
grover_op = GroverOperator(oracle)
grover_op.decompose().draw("mpl")
```

```
[7]:
```

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:

```
[8]:
```

```
optimal_num_iterations = math.floor(
math.pi / 4 * math.sqrt(2**grover_op.num_qubits / len(marked_states))
)
```

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

```
[9]:
```

```
qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw("mpl")
```

```
[9]:
```

## Execution with the Sampler primitive¶

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

runtime primitive. Because we have a single circuit, we instantiate a `Sampler`

using the target backend. To begin, this is the simulator:

```
[33]:
```

```
sim_sampler = Sampler(session=sim)
```

Now we execute the circuit by using `sim_sampler.run`

. The result is obtained in the returned quasi-probability distribution:

```
[34]:
```

```
sim_dist = sim_sampler.run(qc, shots=int(1e4)).result().quasi_dists[0]
```

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 `marked_states`

.

```
[35]:
```

```
plot_distribution(sim_dist.binary_probabilities())
```

```
[35]:
```

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

instance targeting that system:

```
[36]:
```

```
real_sampler = Sampler(session=backend)
```

```
[37]:
```

```
real_dist = real_sampler.run(qc, shots=int(1e4)).result().quasi_dists[0]
```

```
[38]:
```

```
plot_distribution(real_dist.binary_probabilities())
```

```
[38]:
```

```
[1]:
```

```
import qiskit_ibm_runtime
qiskit_ibm_runtime.version.get_version_info()
```

```
[1]:
```

```
'0.11.1'
```

```
[1]:
```

```
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
```

### Version Information

Qiskit Software | Version |
---|---|

`qiskit-terra` | 0.24.1 |

`qiskit-aer` | 0.12.0 |

`qiskit-ibmq-provider` | 0.20.2 |

`qiskit` | 0.43.0 |

System information | |

Python version | 3.11.3 |

Python compiler | Clang 14.0.6 |

Python build | main, Apr 6 2023 08:58:31 |

OS | Darwin |

CPUs | 8 |

Memory (Gb) | 16.0 |

Mon Jun 12 17:59:08 2023 EDT |

### This code is a part of Qiskit

© Copyright IBM 2017, 2023.

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.

```
[ ]:
```

```
```