The new Qiskit Textbook beta is now available. Try it out now
Lab 6. Grover's search with an unknown number of solutions

Prerequisite

Other relevant materials

from qiskit import *
from qiskit.tools.visualization import plot_histogram
from qiskit.quantum_info import Operator, Statevector
from qiskit.tools.monitor import job_monitor
from qiskit.ignis.mitigation.measurement import *

import numpy as np
import matplotlib.pyplot as plt


## Part 1: Quantum Counting

Goal

Construct a circuit for quantum counting implementing the IPE (Iterative Phase Estimation) algorithm to find the number of solutions to a search problem.

In Ch.3.10 Grover's Algorithm, we learned how to find search problem solutions through Grover's algorithm and the number of solutions utilizing the quantum counting circuit in Ch.3.11 Quantum Counting. The number of solutions together with the number of total items in the search space determines the number of Grover iterations, and the number of oracle calls that are required. In part 1 of this lab, we build the quantum counting circuit implementing IPE the algorithm rather than the way the circuit was created in Ch.3.11 Quantum Counting using Quantum Phase Estimation (QPE).

### 1. Find the number of solutions of the given oracle for a search problem through quantum counting.

#### Step A. Construct a gate for Grover iteration.

Consider the search space with the total number of item, $N = 8$. Run the following cell to construct an oracle of a search problem.

## Create an Oracle

N = 8 # the number of total items in the search space
m = int(np.log2(N)) # the number of qubits required to construct the search space with N items

myqc = QuantumCircuit(m, name='Oracle')
myqc.x(1)
myqc.z(range(2))
myqc.x(1)

Oracle = myqc.to_gate()


📓 Complete the circuit, qc, to create Grover iteration gate/operator, Grover, by adding the diffuser, explained as the step 3 in the first section 1.Introduction of Ch.3.10 Grover's Algorithm.

qc = QuantumCircuit(m)
qc.append(Oracle, range(m))

####

Grover = qc.to_gate()


#### 📓Step B. Build a quantum circuit, circ, for quantum counting employing the IPE algorithm to find the eigenvalue of the Grover iterator, Grover that we made in Step A.

Read Ch.3.11 Quantum Counting before you start. Suppose the number of iteration of the IPE here is three, which corresponds to three counting qubits in QPE (Quantum Phase Estimate) circuit. (In other words, set the number of classical register to three.)

###### your code goes here

###################
circ.draw()


#### 📓Step C. Execute the circuit that you built in Step B and find the number of solutions, $M$, from the estimated phase.

sim = Aer.get_backend('aer_simulator')
shots = 20000

####### Your code goes here


## Part 2: Implementing Grover's algorithm with an augmented Oracle

Goal

Construct a new augmented oracle to double the search space when the number of solutions, $M$, is more than or equal to the number of total items, $N$, $M \geq N/2$.

When the number of solutions, $M$, is more than or equal to a half of the total items, $N$ ( $M \geq N/2$ ), the angle $\theta (= \arcsin(2\sqrt{M(N-M)}/N) )$, the amount of rotation toward to the solutions through each Grover iteration, gets smaller as $M$ varies from $N/2$ to $N$. Therefore, the number of oracle calls required by the search algorithm rather increases with $M$ even though it should be easier to find a solution to the problem when the majority of the items is solution. In Part 2 of this lab, we build a new augmented oracle that double the search space to resolve the issue.

### 1. Understand the problem.

#### 📓Step A. Verify that the angle $\theta$ gets smaller as $M$ varies from $N/2$ to $N$.

Plot the relationship between $M$ and $\theta$ when $N = 2^{10}$.

## Your code goes here


#### 📓Step B. Obtain the angle $\theta$ and the number of the Grover iterations, $R$, needed to find the solutions of the oracle in Part 1 and interpret the result.

In [QCQI] p253, $R$, is estimated through $R = CI(\frac{\arccos \sqrt{M/N}}{\theta})$ where $\theta$ is determined from $\sin\theta = \frac{2\sqrt{M(N-M)}}{N}$ and $CI(x)$ denotes the integer closest to the real number $x$, where by convention we round halves down, $CI(3.5)=3$, for example.

N = 8


### 2. Find the solutions to the search problem from Part 1.

The solutions can be still found through Grover's algorithm when $M \geq N/2$ by doubling the search space with a single additional qubit $|q\rangle$ in the search index and building a new augmented oracle with the total number of items, $2N$, and $M$ number of solutions.

#### 📓Step A. Build a new augmented oracle gate/operator, Oracle_new, in the doubled search space.

With this new oracle in the doubled search space, the problem now is defined to find $M$ solutions out of 16 ( = 2x$N$ ) total items. Therefore, less than half the items in the new search space are now solutions.

As explained in [QCQI] Ch.6.1.4 (p255), the new augmented oracle marks an item only if it is a solution to the search problem and the extra bit is set to zero. The augmented oracle may be constructed using one application of the original oracle, Oracle in Part 1 and elementary quantum gates, using the extra qubit $|q\rangle$.

## your code goes here


#### 📓Step B. Evaluate the number of Grover iterations, $R$, needed to find $M$ solutions among the total 16 items.

## Your code goes here


#### 📓Step C. Create a quantum circuit qc_final to find solutions to the search problem applying Grover iteration R times.

A diffuser gate, that consist Grover iteration with Oracle_new, should be built accordingly for the new search space. Check the section 3.3.1 Qiskit Implementation in Ch.3.10 Grover's Algorithm to learn how to build a general diffuser.

## Your code goes here

##########################

qc_final.draw()

qc_final_trans = transpile(qc_final, sim)
count = sim.run(qc_final_trans, shots=shots).result().get_counts()
plot_histogram(count)


#### 📓Step D. Check if the solutions are correct using the original oracle, Oracle, in Part 1.

## your code goes here


## Part 3: Grover circuit on Noisy Quantum System

Goal

Execute the Grover circuit, that we built in Part 2 on a real quantum systems.

In Part 3, we run the circuit qc_final that we set up in Part 2 to find the solutions to the search problem on a real quantum system. Since the present day quantum computers are noisy, the answer from it will not be the same as the simulation result that we obtained in Part 2. We examine how noise affects the outcome and discuss the possible sources of the error.

## your code goes here


#### 📓Step B. Generate multiple ( as many as you want ) transpiled circuits of qc_final. Choose one with the minimum circuit depth.

As we learned in Lab3, we can increase the fidelity in the results from noisy quantum systems by minimizing the depth of the circuit that we run.

## your code goes here


#### 📓Step C. Execute the circuit on the backend.

shots = 8192

## Your code goes here