shor-algo-ocaml / latex / tipe_dossier_ens.tex

\RequirePackage[l2tabu, orthodox]{nag}
\documentclass[a4paper,11pt]{tipe}


\usepackage{lgrind}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc}
\usetikzlibrary{external}
\tikzexternalize[prefix=tikz/]


\usepackage[top=2.5cm,bottom=2.5cm,left=2.5cm,right=2.5cm]{geometry}
\usepackage{stmaryrd}
\usepackage{mathabx}
\usepackage{xspace}
\input{common_def.tex}


%opening
\title{L'algorithme de \textsc{Shor}}
\subtitle{À la recherche de l'ordre}
\theme{Prévisions}
\scolaryear{2011-2012}
\author{Gabriel Pichot}



%\lstnewenvironment{ocaml}{\lstset{language=(Objective)Caml}}{}

\begin{document}
\maketitle

% INFO : float 1 bit signe, 11 bits exposant, 52 bits nombres.

\begin{abstract}
Le document ci-présent développe les étapes importantes de l'algorithme de
\textsc{Shor} et notamment la recherche de l'ordre. Des aspects
d'implémentation en sont donnés et on propose à ce titre une version simulée
d'un fonctionnement quantique sur une machine classique grâce au langage
OCaml dans ce cadre. Puis suivent quelques tests pour des entiers raisonnables.
\end{abstract}

~\thispagestyle{empty}
\newpage


\tableofcontents

\chapter*{Introduction}
Si on sait aisément factoriser de petits nombres depuis notre plus jeune
âge, il est toutefois plus difficile de trouver des facteurs à des
nombres dont le nombre de chiffre dépasse la dizaine (sauf cas de carré
parfait, multiple de $2$ et utilisation de congruences). Même pour des
ordinateurs de telles opérations se révèlent fastidieuse.

Trouver des algorithmes
pour factoriser des nombres quelconques est en soi une
problématique. On sait que tout nombre est se décompose en produit de facteur(s)
premier(s). Le soucis est bien entendu de trouver ses facteurs. Pour des petits
nombres on y arrive facilement, pour de plus grands par des propriétés
remarquables (carré parfait, multiple de deux, congruences...). Cependant pour
des grands nombre cela vient plus difficile un outil informatique

Tout d'abord nous parlerons de l'informatique quantique et des aspects quelques
peu différents qu'elle revêt par rapport à l'informatique quantique. Par la
suite, on s'intéresse à l'algorithme de \textsc{Shor} et on met en avant les
avantages qu'il y aurait à son implémentation sur un calculateur quantique.
Puis vient un récapitulatif des différents algorithmes à mettre en place pour
une simulation sur un calculateur classique et les soucis principaux.

\chapter{Tirer parti d'un calculateur quantique}
\section{Qubit et registre}
Dans un ordinateur classique, l'information minimale est d'ordinaire stockée
sous la forme d'un \emph{bit} qui peut prendre soit la valeur $0$ soit la
valeur $1$.Le nombre de bits requis pour stocker une information dépendant alors
de la manière choisie de représenter cette information. Par exemple, en OCaml,
les entiers sont codés sur $32$ bits, un premier bit sert généralement pour le
signe (on parle d'\emph{entier signé}), les suivants à coder le nombre en
binaire. On a donc un intervalle d'entiers disponibles allant de $-2^{30}$ à
$2^{30} - 1$ (il ne faut pas oublier de compter $0$). Ces limites supposent
d'ailleurs d'être rigoureux dans le choix des algorithmes par la suite. Ainsi un
bit d'information est-il toujours soit dans l'état $0$ soit dans l'état $1$.

Dans un ordinateur quantique on considère un \emph{qubit} (pour \emph{bit
quantique}). Ceux-ci, a contrario des précédents sont dans une superposition
des deux états possibles, $0$ et $1$. Ainsi l'information codée n'est plus
stockée de façon binaire soit $0$ soit $1$, mais au contraire comme
superposition de ces deux composantes. On peut donc représenter un qubit
$\ket \varphi$ par un vecteur de $\C^2$ :
\[ \ket \varphi = a \cdot \ket 0 + b \cdot \ket 1 \text{ avec } a,b\in\C \text{
et } \abs a ^2 + \abs b ^2 = 1 \]
où, en utilisant la notation de Paul \textsc{Dirac} : le \emph{ket}, $\ket 0$ et
$\ket 1$ forment une base de $\C^2$, et correspondent aux deux états possibles. 

Plus généralement on définit aussi ce qu'est un \emph{$n$-qubit} ou plus
simplement \emph{registre}. Il correspond à un ensemble de $n$ qubits.
Cependant, cela ne se traduit pas par une somme des qubits. C'est-à-dire que
l'état du registre n'est pas traduit par un vecteur de $\C^2$, au contraire,
une fois encore il y a superposition des états des qubits. Le registre est donc
caractérisé par un vecteur de $\C^{2^n} = \C^2 \times \dots \times \C^2$ ce qui
donne un état :
\[ \ket\varphi = a_0 \cdot \ket 0 \ket 0 \dots \ket 0 \ket 0
    + a_1 \cdot \ket 0 \ket 0 \dots \ket 0 \ket 1 
    + \dots + a_{n-1} \cdot \ket 1 \ket 1\dots \ket 1 \ket 1 \]
qu'on peut aussi écrire :
\[ \ket\varphi = a_0 \cdot \ket{00\dots00}
    + a_1 \cdot \ket{00\dots01} + \dots 
    + a_{n-1} \cdot\ket{11\dots11} .\]
Soit utilisant une notation décimale plutôt que binaire pour les vecteurs :
\[\ket\varphi = \sum_{k=0}^{2^n-1} a_k \cdot \ket {k} \text{ avec } \forall k
\in \intEntier{0,n-1} , a_k \in\C \text{ et } \sum_{k=0}^{2^n-1} \abs{a_k} ^2 =
1 \]
La dernière condition étant une \emph{condition de normalisation} qui prendra
son sens par la suite.

Cette superposition des états donne un avantage non négligeable au calculateur
quantique . En effet, pour une fonction $f$ linéaire de ses entrées, un
ordinateur quantique, en une seule opération calculera sa valeur en $2^n$ points
tandis qu'un ordinateur classique le fera en un unique point. En effet, pour un
registre $\ket \varphi$ :
\[f(\ket \varphi) = f\left(\sum_{k=0}^{2^n - 1} a_k\cdot\ket k\right) =
\sum_{k=0}^{2^n-1} a_k \ket{f(k)}.\]
On voit donc tout de suite un intérêt du calcul quantique. Notons que les
opérations que l'on effectue sur un registre sont en fait toutes linéaires, on
les représente par des portes ou, avec une terminologie plus anglophone,
\emph{gates} tandis que les qubits, quant à eux, sont représentés par des
\emph{wire}. Nous ne développerons pas cette aspect par la suite. Mais on
s'accordera à représenter les opérations effectuer sous la forme de matrices
adaptées à notre espace. Les lois de la mécanique quantique imposent que ces
matrices soient unitaires, c'est-à-dire égales au conjugué de sa transposée.
% TODO
\section{Intrication quantique}
Un autre phénomène lié au calcul quantique est l'\emph{intrication} quantique.
En fait, les qubits au sein d'un registre interagissent les uns avec les
autres. Prenons un exemple, si on considère l'opération associée à la matrice
pour un registre de $2$ qubits :
\[\bordermatrix{
  ~ & \ket 0 & \ket 1 & \ket 2 & \ket 3 \cr
  \ket 0 & 1 & 0 & 0 & 0 \cr
  \ket 1 & 0 & 1 & 0 & 0 \cr
  \ket 2 & 0 & 0 & \frac 1 {\sqrt 2} & \frac 1 {\sqrt 2} \cr
  \ket 3 & 0 & 0 & \frac 1 {\sqrt 2} & - \frac 1 {\sqrt 2} \cr
}.\]
Si notre registre est dans l'état :
\[ \ket\varphi = \frac 1 {\sqrt 2} \cdot \ket 2 + \frac 1 {\sqrt 2} \cdot
\ket 3, \]
alors on obtient en sortie un nouvel état du registre :
% TODO c'est vraiment ça la superposition ?
\[ \ket\varphi = \ket 2.\]
\section{Mesure}
On pourrait dire au premier abord que l'informatique quantique présente un
avantage certain. Elle permet avant tout de paralléliser les calculs et la
quantité de mémoire disponible, puisque l'on est dans une superposition
d'états, est exponentiel. Pourtant, il faut nuancer notre propos. En effet, si
notre registre est dans une superposition d'états et permet un calcul en $2^n$
points à la fois ceci ne se déroule que dans un \emph{espace des états}. En
vérité, il faut pouvoir accéder l'information, et c'est la que prend son sens
la condition de normalisation. Lorsqu'on effectue une mesure, on n'obtient pas
toutes les informations sur l'état, au contraire le registre se \og fige \fg{}
dans un des états possibles. C'est-à-dire qu'il se projette aléatoirement sur
un des états avec une probabilité correspondant au module au carré de son
coefficient, c'est-à-dire $\abs{a_i} ^ 2$ pour l'état $\ket i$. Par exemple,
pour un registre dans l'état :
\[ \ket\varphi = \frac 1 {\sqrt 2} \cdot \ket 1
  + \frac 1 2 \cdot \ket 2
  + \frac 1 2 \cdot \ket 3
\]
l'état $\ket 0$ ne sera jamais pris par notre registre car de probabilité $0$,
par contre les états restants (de coefficients non nuls) on tous une certaine
probabilité d'être pris par la registre lors de la mesure : elle correspond à
$0.5$ pour l'état $\ket 1$ et est équiprobable à $0.25$ pour les états $\ket 2$
et $\ket 3$.

C'est donc pour cela que l'on a la relation suivante, dite \emph{condition de
normalisation} :
\[ \sum_{k=0}^{2^n-1} \abs{a_k} ^2 = 1.\]
Les coefficients sont, à une opération près, des probabilités de trouver notre
registre dans un certain état et il faut donc que la somme des modules des
carrés soit égale à $1$, traduisant ainsi le caractère probabiliste du système.

Ce dernier phénomène met donc en avant une limite à l'utilisation de
l'informatique quantique, puisque bien qu'il permette de paralléliser les
calculs au final on se retrouve comme dans le cas de l'informatique classique
avec un seul état lors de la mesure. Cependant il faut bien comprendre que dans
le premier cas il s'agit d'une mesure \emph{déterministe} tandis que dans le
second cas celle-ci est \emph{probabiliste}.









\chapter{L'algorithme de \textsc{Shor}}
Après cette courte introduction à l'informatique quantique, on se propose ici
de présenter l'algorithme de \textsc{Shor} et de présenter ces avantages,
notamment en terme de complexité, par rapport à sa version classique.
\section{Étapes}
On peut scinder, à peu de choses près, cet algorithme en trois parties. D'abord
une partie s'occupant de faire des vérifications sur le nombre en entrée que
l'on notera $n$ par la suite. Ensuite vient la recherche de l'ordre puis
l'exploitation de cet ordre. C'est la seconde partie qui notamment sera plus
efficace sur un ordinateur quantique, à ce titre on l'étudiera spécifiquement
dans une seconde partie. La première et la troisième ne posant pas
de problèmes en termes de complexité.
% FIXME Peut-être mieux délimité seconde et troisième partie ce qui n'apparait
% pas trop pour le moment dans le texte.
%\subsection{Pré-traitement}
Tout d'abord il faut s'assurer que l'entier $n$ est factorisable, a priori oui.
En effet, l'intérêt premier de cet algorithme est d'être exécuté sur des
nombres dont on sait qu'ils sont factorisables mais dont on ne connaît pas la
factorisation. C'est en particulier le cas en ce qui concerne le cryptosystème
RSA qui base justement sa robustesse sur la difficulté à factoriser des
nombres. Brièvement, celui-ci utilise deux nombres premiers et leur produit,
dont seul le produit est connu publiquement. Il suffit de retrouver les
facteurs et on alors \og casser \fg{} le code du message.

D'autre part on peut aussi auparavant utiliser des tests de primalité qui sont
souvent moins coûteux que d'essayer une factorisation.
% TODO compléter quels tests ? En connaître quelques uns et principe de
% fonctionnement, mais aussi en terme de complexité

Puis on élimine certains cas triviaux :
\begin{enumerate}
 \item Si $n$ est pair, on renvoie $2$.
 \item Si $n$ est la puissance d'un entier, on renvoie cet entier
 \item \label{choix_de_p}Ensuite on choisit un entier $p$ compris entre $1$ et
$n-1$.
 \item Si $d = \pgcd(p,n) > 1$, alors on renvoie $d$.  
 \item On récupère l'ordre de 
\end{enumerate} 
% TODO à compléter peut-être !! ?
% Notamment POURQUOI ?!

Enfin on récupère l'ordre de $p$ dans $\ZnZ n$, c'est-à-dire le plus entier $r$
tel que $p ^ r \equiv 1 \mod n$.

%\subsection{Traitement de l'ordre}


\section{La recherche de l'ordre}
La recherche de l'ordre est le point le plus important de l'algorithme de
\textsc{Shor}. Et c'est cette partie qui, notamment, tire partie du calculateur
quantique. En effet, sur un ordinateur classique la transformée de
\textsc{Fourier} s'effectue en $\O(n\log n)$ tandis que sur un calculateur
quantique, on peut l'effectuer en $\O(\log ^ 3 n)$.


\chapter{À la recherche de l'ordre}
L'élément central de l'algorithme de Shor est la recherche de l'ordre. En
effet, sur un ordinateur classique, l'algorithme le plus efficace pour calculer
une transformée de Fourier est de complexité $\O(n log n)$ tandis que, du fait
de l'intrication quantique on peut réaliser cette opération en seulement.
\section{Exponentiation modulaire}
Dans le second registre, on doit calculer $x ^ a \mod n$, pour cela il existe
plusieurs méthodes certaines plus astucieuses que d'autres. Une première
méthode plutôt naïve consisterait à calculer les résidus modulo $n$ successifs
des puissances de $x$ successives (on élimine directement l'idée de calculer
$x^a$ puis son résidu, car on peut facilement dépasser la limite des entiers
définie pour le langage (\code{max\_int} en OCaml)). Ce qui donne un
algorithme d'un ordre de complexité en $\O(a)$. Cependant une solution beaucoup
plus efficace est de considérer un algorithme d’exponentiation rapide.
Si on écrit $a = \sum_{i=0}^{n} a_i 2^i$, c'est à dire $a$ dans son écriture
binaire $a_n a_{n-1} \dots a_1 a_0$. On en déduit donc 
\[ x^a = x ^ {\sum_{i=0}^{n} a_i 2^i} = \prod_{i=0}^{n} x ^ {a_i 2^i}
 =  \prod_{i=0}^{n} \left( x ^ {2^i}\right) ^{a_i} \]
L'opération de congruence possédant des propriétés remarquables par rapport au
produit (et donc au puissance), on remarque qu'il suffit de considérer
uniquement des puissances de $x$ de la forme $x ^ {2^i}$. Encore mieux, lorsque
$a_i = 0$ le résidu est simplement $1$. Par suite il vient l'algorithme suivant
:
\begin{verbatim}
%\begin{ocaml}
let expModulaire x a n =
  let residu  = ref 1
  and a_bin   = ref a
  and x_puis  = ref x in
  while !a_bin > 0 do
    if a_bin land 1 = 1 then begin(* Si le bit de poids faible est 1 *)
      residu := !residu * x_puis % n
    end;
    x_puis := !x_puis * x_puis % n; (* Contient les puissance de 2 de x *)
    a_bin  := a_bin lsr 1; (* On décale vers la droite (supprime le bit de
poids faible *)
  done;
  !residu
\end{ocaml}
\end{verbatim}
Cette algorithme présente l'avantage d'être très rapide ainsi pour des entiers
codés sur $32$ bits, on fait dans le pire des cas $32$ tours de boucle. En
fait, on montre (même principe que pour l'exponentiation rapide) que la
fonction ci-dessus a une complexité en $\O(log_2(a))$. 

\section{Approximation de réels par des fractions continues}
La dernière partie de l'algorithme consiste à trouver, connaissant $c$ et $q$,
deux entiers $d$ et $r$ vérifiant l'inégalité :
\[ \abs{ \frac c q - \frac d r } \leq \frac 1 {2q} \quad .\]
Si ces deux entiers $d$ et $r$ sont premiers entre eux alors l'ordre à une forte
probabilité d'être $r$.
Une bonne méthode afin d'approcher le réel $\frac c q$ est d'utiliser les
fractions continues et notamment les réduites de ce réel.
\begin{definition}[Fraction continue]
On appelle fraction continue une expression de la forme
\[\contFrac{ a_0 // {a_1 // {a_2 // {a_3 + \dots}}}}\] 
\end{definition}



On a utiliser une propriété remarquable du pgcd par la suite qui va nous
permettre de calculer des pgcd sur des nombres arbitrairement grand grâce à
l'exponentiation modulaire.
\begin{propriete}[Pgcd et congruence]
Soient $n$, $p$ et $a$ des entiers naturels et $d$ un entier relatif, en
notant $r$ le reste de la division euclidienne de $p ^ a$ par $n$ alors :
\[ \pgcd( p ^ a + d, n) = \pgcd( r + d, n) \]
\end{propriete}
\begin{demonstration}
Par définition de la division euclidienne, on peut écrire $p ^ a = q n + r$
avec $q \in \Z$ et $ 0 \leq r < n$. Donc en ajoutant $d$ on obtient :
\[ p ^ a + d = q n + r + d \; .\]
Soit $\Delta = \pgcd( p ^ a + d, n)$ alors comme $\Delta$ divise $n$ et $p^a
+d$ alors il divise $r + d$ donc $\Delta \mid \pgcd(r+d,n)$. 
Cette même égalité donne de même la réciproque. D'où le résultat.
\end{demonstration}


\chapter{Exemples}

%\subsection{Exemples}
%\input{../output/shor_7_15.tex}\\
%\input{../output/shor_7_15_fft.tex}\\
%\input{../output/shor_8_15.tex}\\
%\input{../output/shor_7_99.tex} (143,7)
\begin{figure}
  \input{../output/shor_7_15.tex}
%  \input{../output/shor_13_289.tex}
  \caption{État du registre après une transformée de \textsc{Fourier} pour $n =
289$ et $p = 13$}
\end{figure}
\begin{figure}
% \input{../output/shor_67_1001.tex}
 \caption{État du registre après une transformée de \textsc{Fourier} pour le
couple $(67,1001)$}
\end{figure}

%\input{../output/shor_17_1001.tex}

\appendix
\chapter{Implémentation}
\section{Fichier main.ml}
\lgrindfile{main.tex}
\section{Module Arithmetik}
\lgrindfile{arithmetik.tex}
\section{Module Quantum.ml}
\lgrindfile{quantum.tex}
\section{Module MatrixFactory}
\lgrindfile{matrixFactory.tex}

%Le présent document a été rédigé avec l'aide de Kile et du formidable \LaTeX.
%Les programmes proposés ont été codés sous vim.


\nocite*{} % Affiche les références sans que soit nécessaire de les citer.
\bibliographystyle{tipe}
\bibliography{/home/gabriel/Latex/BibTex/TIPE.bib}


\end{document}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.