Wiki du cours

Rédacteur: [Mirlinda Sylejmani]

A traiter [Modifier]

• Calculs quantiques ([1], Section 2): bits quantiques, portes logiques quantiques.
• La transformée de Fourier quantique ([1], Section 4)

1. Introduction au calcul quantique [Modifier]

L’information traitée par un ordinateur « classique » est constituée de bits. Un bit ne peut prendre que deux valeurs : \(0\) ou \(1\) en arithmétique (faux ou vrai en logique). Les outils utilisés pour travailler sur les bits sont appelés portes logiques. Ce sont des circuits qui prennent un ou plusieurs bits en entrée et fournissent un seul bit en sortie. Pour un ordinateur quantique, leurs analogues sont les qubits et les portes quantiques.

1.1 Qubits

Un qubit peut aussi se trouver dans l’état \(0\) ou \(1\) mais il peut également être une superposition de ces deux états. Ceci implique qu’il y a une infinité d’états possibles pour un qubit.

Considérons un système à \(n\) qubits. On représente un état quantique de ce système par un vecteur de dimension \(2^n\) dans un espace de Hilbert. Pour décrire complètement ce système, on additionne plusieurs états, en utilisant la notation ket :

\( \sum_{i=0}^{2^{n}-1} a_i |S_i \rangle \),

où \( \ a_i \in \mathbb{C} \) sont les amplitudes de probabilités telles que \( \sum |a_i|^{2} = 1\) et les \( |S_i \rangle \) forment une base vectorielle de l'espace de Hilbert.

Par exemple, si \(n=3\) :

\( a_1 |000 \rangle + a_2 |001 \rangle + a_3 |010 \rangle + a_4 |100 \rangle + a_5 |011 \rangle + a_6 |101 \rangle + a_7 |110 \rangle + a_8 |111 \rangle \)

Le système quantique est dans un état indéterminé jusqu’au moment de la mesure. En effet, lorsqu’on fait une mesure, on a une probabilité \( |a_i|^2 \) d’observer l’état \( |S_i \rangle \), mais dès lors qu’une mesure est faite, le système se fixe à l’état observé. Ainsi après une mesure, le système est dans un état correspondant à un bit.

1.2 Portes quantiques

Les portes quantiques utilisent le même nombre de qubits en entrée et en sortie. On les représente par des matrices unitaires de taille \( 2^n \times 2^n\) si la porte agit sur \(n\) qubits. Les coefficients sont indexés par les vecteurs d'états de base.

Par exemple, le circuit suivant :

\( |00 \rangle \to |00 \rangle \)

\( |01 \rangle \to |01 \rangle \)

\( |10 \rangle \to \frac{1}{\sqrt{2}} (|10 \rangle + |11 \rangle) \)

\( |11 \rangle \to \frac{1}{\sqrt{2}} (|10 \rangle - |11 \rangle) \)

est décrit par la matrice :

\( \begin{matrix} 1 & 0 & 0 & 0 \end{matrix} \)

\( \begin{matrix} 0 & 1 & 0 & 0 \end{matrix} \)

\( \begin{matrix} 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{matrix} \)

\( \begin{matrix} 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{matrix} \)

Pour connaître l’action de la porte sur un état quantique, on multiplie le vecteur qui représente l’état par la matrice qui représente la porte. Supposons que le système soit dans l’état superposé :

\( \frac{1}{ \sqrt{2} } |10 \rangle - \frac{1}{ \sqrt{2} } |11 \rangle \)

En appliquant la transformation ci-dessus, on obtient :

\( \frac{1}{2} (|10 \rangle - |11 \rangle) - \frac{1}{2} (|10 \rangle - |11 \rangle) = |11 \rangle \)

1.3 Transformée de Fourier quantique

La transformée de Fourier quantique définie par :

\( F_q |a \rangle = \frac{1}{q^{1/2}} \sum_{c=0}^{q-1} |c \rangle \exp( \frac{2 \pi a c}{q} ) \)

est une transformation unitaire qui est utilisée dans l'attaque de Shor.

Voici sa construction dans le cas où \(q\) est une puissance de \(2\) :

Soit \(q=2^l\) tel que le nombre de bits de \(q\) est polynomial et considérons \(a\) tel que \( 0 \leq a \leq q \). Notons \(a\) en binaire : \( |a_{l-1}a_{l-2}...a_0 \rangle \). Soient \(R_j\) les portes qui agissent sur le \(j\)ème bit du système quantique :

\( \begin{matrix} \frac{1}{ \sqrt{2} } & \frac{1}{ \sqrt{2} } \end{matrix} \)

\( \begin{matrix} \frac{1}{ \sqrt{2} } & \frac{-1}{ \sqrt{2} } \end{matrix} \)

Soient \(S_{j,k}\) les portes qui agissent sur les bits en position \(j\),\(k\) avec \(j < k\) :

\( \begin{matrix} 1 & 0 & 0 & 0 \end{matrix} \)

\( \begin{matrix} 0 & 1 & 0 & 0 \end{matrix} \)

\( \begin{matrix} 0 & 0 & 1 & 0 \end{matrix} \)

\( \begin{matrix} 0 & 0 & 0 & \exp(i \theta_{k-j} ) \end{matrix} \),

où \( \theta_{k-j} = \frac{\pi}{2^{k-j}}\).

En appliquant la série de transformations suivante à l'état \(|a \rangle \) :

\(R_{l-1}S_{l-2,l-1}R_{l-2}S_{l-3,l-1}S_{l-3,l-2}R_{l-3}...R_{1}S_{0,l-1}S_{0,l-2}...S_{0,2}S_{0,1}R_0\),

on obtient :

\( \frac{1}{q^{1/2}} \sum_{b} \exp( \frac{2 \pi ac}{q} ) |b \rangle \),

où \(b\) est l'expression binaire inverse de \(c\).

L'amplitude de probabilité pour passer de l'état \(|a \rangle = |a_{l-1}...a_0 \rangle \) à l'état \(|b \rangle = |b_{l-1}...b_0 \rangle \) a une phase égale à :

\( \sum_{0 \leq j < l} \pi a_j b_j\)\(+\)\( \sum_{0 \leq j < k < l} \frac{ \pi }{2^{k-j}} a_j b_k \) \(=\)

\( \sum_{0 \leq j \leq k < l} \frac{ \pi }{2^{k-j}} a_j b_k \) \(=\) (\(c\) est obtenu en lisant \(b\) de droite à gauche)

\( \sum_{0 \leq j \leq k < l} \frac{ \pi }{2^{k-j}} a_j c_{l-1-k} \) \(=\) (on substitue \(l-k-1\) par \(k\))

\( \sum_{0 \leq j+k < l} 2 \pi \frac{2^{j}2^{k}}{2^l} a_j c_k \) \(=\)

\( \sum_{j,k=0}^{l-1} 2 \pi \frac{2^{j}2^{k}}{2^l} a_j c_k \) \(=\) (distributivité de la multiplication par rapport à l'addition)

\( \frac{2 \pi }{2^l} \sum_{j=0}^{l-1} 2^{j} a_j \sum_{k=0}^{l-1} 2^{k} c_k \) \(=\) (on a \(a= \sum_{j=0}^{l-1} 2^j a_j \) et \(c= \sum_{j=0}^{l-1} 2^j c_j \))

\( \frac{2 \pi a c}{q}\)

ce qui donne bien la phase de l'amplitude de \( |a \rangle \to |b \rangle \) dans la transformation \(F_q\).

Références [Modifier]

[1] Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, Sections 2 et 4