<jupyter_start><jupyter_text>$\newcommand{\ket}[1]{\lvert {1}\rangle}\newcommand{\ds}{\displaystyle}$  Shor's Algorithm IntroductionProblem> Integer factorizationUse Case> $n = p \cdot q$, where $p,q$ are large prime numbers, often used in cryptographic functionsClassical Solution> **General Number Field Sieve** has best asymptotic behaviour> Superpolynomial scaling:> $\displaystyle O(e^{(\ln n)^\frac{1}{3}(\ln\ln n)^{\frac{2}{3}}})$Shor's Algorthim> Factorization algorithm with poylnomial complexity > Partially on Quantum processor, pre & post processing is classical> Quantum complexity: $O\big( (\log n)^2 (\log \log n) (\log \log \log n) \big)$> Polynomial time achieved with Quantum Forier Transform ---- Algorithm  1. Preconditions of $n$Exit if $n$ is any of the following- even- prime - prime power  2. Attempt brute-force solutionPick a random integer $x \lt n$, and calculate $\gcd(x, n)$.If this is not 1, then we have a factor of $n$.  3. Quantum Algorithm1. Pick q as the smallest power of 2 where $n^2 \leq q \leq 2n^2$2. Find the period $r$ of $x^a \mod n$3. Measure $c$ which has property $\displaystyle \frac{c}{q} \approx \frac{d}{r}$, where $d \in \mathbb{N}$  4. Determine ratio$r, d$ can be determined if $gcd(d, r) = 1$ using fraction expansion algorithm  5. Try to obtain factorsReturn to step 2> if $r$ is odd > if $x^{\frac{r}{2}} \equiv -1 \mod n$Factors are >$\displaystyle p, q = \gcd(x^{\frac{r}{2}} \pm 1, n)$ ---- Quantum Fourier Transform (QFT)Define QFT with respect to an ONB $\left\{\ket{x}\right\} = {\ket{0}, \dots, \ket{q-1}}$> $\ds QFT: \ket{x} \mapsto \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \exp \left\{ \frac{2\pi i}{q}x \cdot y \right\} \ket{y} = \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \omega^{x \cdot y} \ket{y}$Apply QFT to a general state $\ds\ket{\psi} = \sum_x \alpha_x\ket{x}$ :> $\ds QFT(\ket{\psi}) = \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \beta_y\ket{y}$ > where the $\beta_y$'s are the discrete Fourier tansform of the amplitudes $\alpha_x$The QFT is unitary> $QFT^\dagger QFT\ket{x} = \ket{x}$ ---- References- [Lecture Notes - Shor's Algorithm][1]- [Continued Fraction Expansion][2] [1]: https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf [2]: https://www.math.u-bordeaux.fr/~pjaming/M1/exposes/MA2.pdf ---- Addendum I - Euclidean Algorithm$\gcd(a,b) = \Bigg\{\begin{split}&b  & \text{ if } a \bmod b = 0 \\&\gcd(b, a \bmod b) & \text{ else } \\\end{split}$ References- [Euclidean Algorithm][1] [1]: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm<jupyter_code># Euclidian Algorithm
def gcd(a, b):
    h,l = (max(a,b),min(a,b))
    q = h % l
    if q == 0:
        return l
    return gcd(l,q)

def is_coprime(a, b):
    return (gcd(a, b) == 1)<jupyter_output><empty_output><jupyter_text>----$\newcommand{\ds}{\displaystyle}$ Addendum II - Continued FractionsTools to approximate a Real number to a Rational number. Example 1 - 1 and 2'1' can be written as a fraction> $\ds1 = \frac{2}{3-1}$and as a continued/infinite fraction> $\ds1 = \frac{2}{3-\frac{2}{3-\frac{2}{3-\dots}}}$interestingly, using 2 instead would suggest the contradiction $1=2$> $\ds2 = \frac{2}{3-\frac{2}{3-\frac{2}{3-\dots}}}$ Example 2 - $\sqrt{2}$> $\begin{split}\sqrt{2} &= 1.414213  \\&= 1 + 0.41421  \\&= 1 + \frac{1}{\frac{1}{0.41421 }} \\&= 1 + \frac{1}{2+ 0.41421 } \\&= 1 + \frac{1}{2+ \frac{1}{2 + \frac{1}{2 + \dots}}} \\\end{split}$ > Sequence `11111111...` Example 3 - $\phi$ (Golden Ratio)> $\begin{split}\phi &= \frac{1 + \sqrt{5}}{2} \\&= 1 + \frac{1}{1+ \frac{1}{1 + \frac{1}{1 + \dots}}}\end{split}$ > Sequence `11111111...` Example 4 - $e$ (2.718)> $\begin{split}e &= \frac{1 + \sqrt{5}}{2} \\&= 2 + \frac{1}{1+ \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \dots}}}}}\end{split}$ > Sequence - `2114116118...` Example 5 - Rational $\frac{1473}{50}$*Rational numbers tend to be finite*> $29 + \frac{1}{2 + \frac{1}{5 + \frac{1}{1 + \frac{1}{3}}}}$ Example 5 -$\pi$> $\begin{split}\pi &= 3.14159265358979 \\&= 3 + \frac{1}{7+ \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \dots}}}} \\3 &= 3.0 \\3 + \frac{1}{7} = \frac{22}{7} &= 3.14 \\3 + \frac{1}{7+\frac{1}{15}} = \frac{333}{106} &= 3.1415 \\3 + \frac{1}{7+\frac{1}{15 + 1}} = \frac{355}{113} &= 3.141592 \\3 + \frac{1}{7+\frac{1}{15 + \frac{1}{1 + \frac{1}{292}}}} = \frac{103993}{33102} &= 3.14159265 \\\end{split}$ ---- Addendum III - Example, Factoring n=21 1. Choose a random integer $x$, where $1 < x < n$> if x *is **not** coprime* with n (i.e. x=6) > $\gcd(x,n) = \gcd(6, 21) = 3$ > $\therefore \frac{21}{3} = 7$ > The factors are 7 and 3 > if x *is coprime* with n (i.e. x=11) > $\gcd(11,21) = 1$ > then continue... 2. Determine q> Where q is the smallest power of 2 between $n^2$ and $2n^2$ > $441 \leq q > $l=9, q=512$> Initial state for 2 registers with length of 'l' > $\ket{\Phi_i} = \ket{0}_{r_1} \ket{0}_{r_2} = \ket{0}^{\otimes 2^l}$ 3. Initialize first register ($r_1$)> Initialize first register with superposition of all stats $a \pmod{q}$ > $\ds\ket{\Phi_0} = \frac{1}{\sqrt{512}} \sum\limits_{a=0}^{511} \ket{a}\ket{0} $ > therefore all bits are $\frac{1}{\sqrt{2}}\Big(\ket{0} + \ket{1}\Big)$ 4. Initialize second register ($r_2$)> Initialize Register with superposition of all states $x^a \pmod{n}$> $\ds\begin{split}\ket{\Phi_1} &= \frac{1}{\sqrt{512}} \sum\limits_{a=0}^{511} \ket{a}\ket{11^a(\bmod{21})} \\&= \frac{1}{\sqrt{512}} \Big( \ket{0}\ket{1} + \ket{1}\ket{11} + \ket{2}\ket{16} + \ket{3}\ket{8} \dots \Big)\end{split}$ > The sequence looks like this>$ \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\1 & 11 & 16 & 8 & 4 & 2 & 1 & 11 & 16 & 8 & 4 & \dots \\\end{matrix}$ > *The period is 6, but not yet observable* 5. Quantum Fourier Transform> $\ds \overset{\sim}{\ket{\Phi}} = \frac{1}{512} \sum\limits_{a=0}^{511} \sum\limits_{c=0}^{511} e^{\big(\frac{1}{512} 2\pi i a c\big)} \ket{c}\ket{11^a(\bmod{21})}$ 6. Measurement> Probability for state $\ket{c, x^k\pmod{n}}$ e.g. $k=2 \rightarrow \ket{c,16}$ > $\ds\begin{split}p(c) &= \Bigg| {\frac{1}{512}}_{a:11^a} \sum\limits_{\bmod{21}=16}^{511} e^{\big(\frac{1}{512} 2\pi iac\big)} \Bigg|^2 \\&= \Bigg| {\frac{1}{512}}_{a:11^a} \sum\limits_{b} e^{\big(\frac{1}{512} 2\pi i(6b+2)c\big)} \Bigg|^2\\\end{split}$ >> Simulation of the probability amplitude of a period of 6<jupyter_code>PERIOD=6

import sympy as sm
import numpy as np
import matplotlib.pyplot as plt

fig = plt.gcf()
fig.set_size_inches(8,5)

sm.var('x')
# This function is a simulation, it does not 
# reflect a multi-modal normal distribution 
f = lambda x: ((sm.cos((x*PERIOD*2*sm.pi)/512)+1)/2)**80/PERIOD

x = np.linspace(0,512,1000)
y = np.array([f(v) for v in x],dtype='float')

plt.title(r"Probaility Amplitudes with a period of 6 peaks fro $c =\frac{512}{6} \cdot d, d \in \mathbb{Z}$")
plt.plot(x,y,color='gray')
plt.fill_between(x,y,0,color='#c0f0c0')

plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.23398448721631715, 'fraction_numerical': 0.07239299051996553, 'mean_word_length': 3.9104372355430184, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 61, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '343871', 'license': 'MIT', 'n_tokens_mistral': 3026, 'n_tokens_neox': 2709, 'n_words': 740, 'path': 'notebooks/quantum-computing/shors_algorithm.ipynb', 'repo_name': 'sparkboom/my_jupyter_notes', 'size': '6962'}