\n", "

\n",
"

\n",
"\n",
"\n",
"In [Ch.3.10 Grover's Algorithm](https://qiskit.org/textbook/ch-algorithms/grover.html), 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](https://qiskit.org/textbook/ch-algorithms/quantum-counting.html). 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](https://qiskit.org/textbook/ch-algorithms/quantum-counting.html) using Quantum Phase Estimation (QPE)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Goal**

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

\n", "`circ`

, for quantum counting employing the IPE algorithm to find the eigenvalue of the Grover iterator, `Grover`

that we made in Step A. \n", "

\n",
"

\n",
"\n",
"When the number of solutions, $M$, is more than or equal to a half of the total items, $N$ ( $M \\geq N/2$ ), \n",
"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. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**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$.

\n", "`Oracle_new`

, in the doubled search space.`qc_final`

to find solutions to the search problem applying Grover iteration `R`

times.`Oracle`

, in Part 1.\n", "

\n",
"

\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Goal**

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

\n", "`qc_final`

. Choose one with the minimum circuit depth.`ibmq_athens`

together with the simulation result to compare and discuss how noise affects the result.