User:MARKALOIDE/sandbox

Notation

• $\otimes$ denotes the tensor product. The notation is used to concatenate two qubits.
• $|x\rangle$ for $x\in \mathbb {N}$ denotes qubits. The notation is used for both a column vector and a tensor. For example, $|0\rangle$ is a 1-qubit in the zero-state, and $|x\rangle =|0\rangle \otimes |1\rangle$ is a 2-qubits.

routine ===

Quantum subroutine in Shor's algorithm.

The quantum circuits used for this algorithm are custom designed for each choice of $N$ and each choice of the random $a$ used in $f(x)=a^{x}{\bmod {N}}$. Given $N$, find $Q=2^{q}$ such that $N^{2}\leq Q<2N^{2}$, which implies that ${\dfrac {Q}{r}}>N$. The input and output qubit registers need to hold superpositions of values from $0$ to $Q-1$, and so have $q$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least $N$ different values of $x$ that produce the same $f(x)$, even as the period $r$ approaches ${\dfrac {N}{2}}$.

Proceed as follows:

1. Initialize the registers of $q$ qubits to the zero-position where $2^{q}=Q$.
2. Apply the hadamard gate in parallel to each of the $q$ qubits to get

${\frac {1}{\sqrt {Q}}}\sum _{x=0}^{Q-1}|x\rangle =\left({\frac {1}{\sqrt {2}}}\sum _{x_{1}=0}^{1}|x_{1}\rangle \right)\otimes \cdots \otimes \left({\frac {1}{\sqrt {2}}}\sum _{x_{q}=0}^{1}|x_{q}\rangle \right).$ where $\otimes$ denotes the tensor product. This state is a superposition of $Q$ states where every qubit is a superposition of 0 and 1.

1. Construct $f(x)$ as a quantum function and apply it to the above state, to obtain

$U_{f}|x,0^{q}\rangle =|x,f(x)\rangle$

$U_{f}{\frac {1}{\sqrt {Q}}}\sum _{x=0}^{Q-1}|x,0^{q}\rangle ={\frac {1}{\sqrt {Q}}}\sum _{x=0}^{Q-1}|x,f(x)\rangle$

1. This is still a superposition of $Q$ states. However, the $q+n$ qubits, i.e, the $q$ input qubits and $n$ ($>{\log _{2}}(N)$) output qubits, are now entangled or not separable, as the state cannot be written as a tensor product of states of individual qubits.
2. Apply the inverse quantum Fourier transform to the input register. This transform (operating on a superposition of $Q=2^{q}$ states) uses a $Q$-th root of unity such as $\omega =e^{\frac {2\pi i}{Q}}$ to distribute the amplitude of any given $|x\rangle$ state equally among all $Q$ of the $|y\rangle$ states, and to do so in a different way for each different $x$. We thus obtain

${U_{\operatorname {QFT} }}(|x\rangle )={\frac {1}{\sqrt {Q}}}\sum _{y=0}^{Q-1}\omega ^{xy}|y\rangle .$ This leads to the final state

${\frac {1}{Q}}\sum _{x=0}^{Q-1}\sum _{y=0}^{Q-1}\omega ^{xy}|y,f(x)\rangle .$

Now, we reorder this sum as

${\frac {1}{Q}}\sum _{z=0}^{N-1}\sum _{y=0}^{Q-1}\left[\sum _{x\in \{0,\ldots ,Q-1\};~f(x)=z}\omega ^{xy}\right]|y,z\rangle .$

This is a superposition of many more than $Q$ states, but many fewer than $Q^{2}$ states, as there are fewer than $Q$ distinct values of $z=f(x)$. Let

• $\omega =e^{\frac {2\pi i}{Q}}$ be a $Q$-th root of unity,
• $r$ be the period of $f$,
• $x_{0}$ be the smallest of the $x\in \{0,\ldots ,Q-1\}$ for which $f(x)=z$ (we actually have $x_{0}<r$), and
• write $m-1=\left\lfloor {\frac {Q-x_{0}-1}{r}}\right\rfloor$
• $b$ indexes these $x$, running from $0$ to $m-1$, so that $x_{0}+rb<Q$.

Then $\omega ^{ry}$ is a unit vector in the complex plane ($\omega$ is a root of unity, and $r$ and $y$ are integers), and the coefficient of ${\dfrac {1}{Q}}\left|y,z\right\rangle$ in the final state is

$\sum _{x\in \{0,\ldots ,Q-1\};~f(x)=z}\omega ^{xy}=\sum _{b=0}^{m-1}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b=0}^{m-1}\omega ^{rby}.$

Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors $\omega ^{ryb}$ point in nearly the same direction in the complex plane, which requires that $\omega ^{ry}$ point along the positive real axis.

1. Perform a measurement. We obtain some outcome $y$ in the input register and some outcome $z$ in the output register. As $f$ is periodic, the probability of measuring some state $|y,z\rangle$ is given by

$Pr(|y,z\rangle )=\left|{\frac {1}{Q}}\sum _{x\in \{0,\ldots ,Q-1\};~f(x)=z}\omega ^{xy}\right|^{2}={\frac {1}{Q^{2}}}\left|\sum _{b=0}^{m-1}\omega ^{(x_{0}+rb)y}\right|^{2}={\frac {1}{Q^{2}}}|\omega ^{x_{0}y}|^{2}\left|\sum _{b=0}^{m-1}\omega ^{bry}\right|^{2}$ $={\frac {1}{Q^{2}}}\left|\sum _{b=0}^{m-1}\omega ^{bry}\right|^{2}={\frac {1}{Q^{2}}}{\frac {\omega ^{mry}-1}{\omega ^{ry}-1}}={\frac {1}{Q^{2}}}{\frac {\sin ^{2}({\frac {\pi mry}{Q}})}{\sin ^{2}({\frac {\pi ry}{Q}})}}$ Analysis now shows that this probability is higher the closer the unit vector $\omega ^{ry}$ is to the positive real axis, or the closer ${\dfrac {yr}{Q}}$ is to an integer. Unless $r$ is a power of $2$, it will not be a factor of $Q$.

1. Since ${\frac {yr}{Q}}$ is close to some integer $c$, the known value ${\dfrac {y}{Q}}$ is close to the unknown value ${\dfrac {c}{r}}$. Performing [classical] continued fraction expansion on ${\dfrac {y}{Q}}$ allows us to find approximations ${\dfrac {d}{s}}$ of it that satisfy two conditions: