\n", "

\n",
"

\n",
" \n",
"Shor's algorithm consists of the following steps; choose a co-prime $a$, where $a \\in [2, N-1]$ and the greatest common divisor of $a$ and $N$ is 1, find the order of $a$ modulo $N$, the smallest integer $r$ such that $a^{r}modN = 1$, and then obtain the factor of $N$ by computing the greatst common divisor of $a^{r/2} \\pm 1$ and $N$. In this procedure, the second step, finding the order of $a$ modulo $N$, is the only quantum part, *quantum order-finding*. \n",
"\n",
"In [Ch.3.9 Shor's Algorithm](https://qiskit.org/textbook/ch-algorithms/shor.html), we built a quantum circuit to find the order for $a=7$ and $N=15$. However, as we are very well aware by now, such a large depth circuit is not practical to run on near-term quantum systems due to the presence of noise. Here in part 1 of this lab, we construct a practical quantum circuit for the same example, which could generate a meaningful solution when executed on today's quantum computers. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In general, the quantum order-finding circuit to factorize the number $N$ requires $m = [log_{2}(N)]$ qubits in the computational (auxiliary) register and $2m (=t)$qubit in the period ( counting ) registers .i.e. total $3m$ qubits, at minimum. Therefore, 12 qubits were used in the quantum circuit to factorize the number 15 in [Ch.3.9 Shor's Algorithm](https://qiskit.org/textbook/ch-algorithms/shor.html). In addition, the cotrolled unitary operator for the modular function, $f(x) = a^xmodN$ was applied in a cascading manner as shown in the figure below to produce the highly entangled state $\\Sigma^{2^m-1}_{x=0}|x\\rangle|a^xmodN>$, which increseas the circuit depth substantially. However the size of the circuit can be reduced based on several observations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](image/L5_Circ_gen.svg)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Goal**

Construct a compiled version of quantum circuit for Shor's algorithm.

\n", "`U`

for the function `7mod15`

.`unitary_simulator`

to obtain the matrix resprentation of the gates in the circuit. Verify $U^{2^{2}} = I $ `shor_QPE`

, and execute it on the `qasm_simulator`

to check if it reproduce the estimated phases in the Qiskit textbook Ch.3.9.