Informatique quantique

Applications dans des domaines tels que la recherche pharmaceutique, la simulation de réactions chimiques, la cryptographie et plus généralement la communication. Les avancées de l'informatique quantique permettront également de grandes améliorations pour l'industrie dans les performances de calculs. Cette technologie permettra de résoudre des problèmes jusque-là non résolubles par des ordinateurs classiques, et cela dans des temps records.

A plus long terme, elle permettra de remplacer les supercalculteurs actuels, ce qui réduira drastiquement les consommations énergétiques liées aux nombreux calculs d'optimisations qui nous accompagnent chaque jour.

L'informatique quantiques est en plein essor et intéresse fortement l'industrie. Elle reste pour le moment assez expérimentale mais ses applications permettront et devront nous permettre de nombreux progrès.

L'informatique quantique pourrait permettre :

• d'améliorer les algorithmes d'optimisation : réseaux de satellites, données, voitures autonomes, transport maritime et gestion des flux, complexe d'autobus dans une mégalopole...
• d'accélérer la découverte de nouveaux médicaments grâce à la simulation de molécules ¹
• de renforcer la sécurité de nos communications

Cryptographie quantique

Vocabulaire :

• Chiffrer : action de transformer un texte dit "en clair" en un autre dit "secret" (ciphertext en anglais) à l'aide d'une clé de chiffrement
• Déchiffrer : action de retrouver le texte dit "en clair" à l'aide d'une clé de déchiffrement
• Décrypter : action de retrouver le texte dit "en clair" sans clé de déchiffrement (peut être fait pour certains messages par analyse statistique ou par force brute)
• Crypter : ce verbe n'existe pas

Pour plus d'informations, voir ce site

Introduction rapide à la cryptographie

L'objectif de la cryptographie est d'échanger des informations entre deux individus de manière confidentielle.

La cryptographie est utilisée partout de nos jours. Elle joue un rôle essentiel dans de nombreuses applications : les transactions bancaires et le World Wide Web sont deux exemples parmi tant d'autres.

Ainsi, il est capital que les systèmes de chiffrement restent sûrs dans le temps et évoluent si besoin.

Une introduction rapide à la cryptographie est disponible sur cette page

Que vient faire la physique quantique là-dedans ?

Les technologies de cryptographie quantique permettent de résoudre les problèmes liés à l'échange de clé du chiffrement symétrique. Elles permettent, grâce aux lois de la physique quantique, de détecter lorsqu'un individu intercepte la clé et permet donc de renforcer la sécurité.

Pour en savoir davantage : Distribution quantique de clé — Wikipédia

Développer de nouveaux systèmes de chiffrement quantique permet également de résoudre un potentiel problème lié aux chiffrements asymétriques. En effet, l'une des principales caractéristiques d'un ordinateur quantique est sa capacité de calcul qui dépasserai celle de tout ordinateur ayant jamais existé. A tel point que la sécurité de tels systèmes de chiffrement serai donc amplement compromise : compte tenue du nombre de ses applications, toutes les sociétés pourraient s'en trouver bouleversées.

A l'heure actuelle, les technologies quantiques ne sont pas assez matures, mais il est de notre recours d'anticiper le futur et de maîtriser l'évolution de ces technologies.

Aparté sur la complexité algorithmique

La complexité algorithmique est une manière de mesurer la performance d'un algorithme en fonction de la taille de son entrée. C'est une mesure de la variation de sa performance.

C'est un outils à la fois utile en mathématiques et en informatique.

Lorsque l'on étudie la complexité algorithmique, on ne prend pas en compte les constantes et facteurs multiplicatifs. Cela s'explique par le fait que ces constantes ne sont en réalité peu significatives, car elles peuvent dépendre de la machine sur laquelle on décide d'exécuter l'algortihme. Enlever les constantes permet aussi de classifier et de comparer les algorithmes entre eux.

Nous prenons aussi en compte uniquement la valeur absolue de la fonction que l'on étudie, car l'objectif est de simplement étudier les variations.

1. Notation Big-O

Définition : soit f et g deux fonctions. On dit que f(x) est en O(g(x)) s'il existe des constantes C > 0 et k >= 0 telles que : pour tout x > k.

On peut dire soit "f est en O(g)" ou alors "g domine f asymptotiquement" Les constantes C et k sont appelées des témoins de la relation.

Exemples :

• 87 est en O(1)
• est en
• est en

2. Notation Big-Omega

Définition : soit f et g deux fonctions. On dit que f(x) est en Ω(g(x)) s'il existe deux constantes C > 0 et k >= 0 telles que : pour tout x > k.

On dit que f(x) est big-Omega de g(x). f(x) est en Ω(g(x)) si et seulement si g(x) est en O(f(x))

Exemples :

• est en
• est en

3. Notation Big-Theta

Définition : soit f et g deux fonctions. On dit que f(x) est en Θ(g(x)) si f(x) est en O(g(x)) et f(x) est en Ω(g(x))

Exemples :

• est en
• est en

Pour en savoir plus, et notamment découvrir les notations little-o et little-omega : The Asymptotic Cheat Sheet

A noter que lorsque l'on étudie la compléxité d'un algorithme, la base du logarithme utilisée n'a pas d'importance. Cela est vrai car les constantes peuvent être éliminées, et les logarithmes de bases différentes sont égaux à une constante près :

Vocabulaire :

• Problème tractable : il existe un algorithme résolvant ce problème en un temps polynomial. Nous disons de ces problèmes qu'ils appartiennent à la classe P.
• Problème intractable : il n'existe aucun algorithme capable de résoudre ce problème en un temps polynomial.
• Problème insolvable : il n'existe aucun algorithme capable de résoudre ce problème. Exemple : le "problème de l'arrêt" (the halting problem en anglais), proposé par Alan Turing en 1936.
• Classe NP ² : l'ensemble des problèmes tels qu'une solution peut être vérifiée en un temps polynomial, mais qu'aucun algorithme n'a été trouvé pour résoudre ce problème en un temps polynomial.
• Classe NP complet : ensemble de problèmes intractables tels que la découverte d'un algorithme capable de résoudre un de ses problèmes en un temps polynomial permettrait de résoudre tous les problèmes de la classe.
• Problème NP-difficile : un problème est dit NP-difficile s'il est intractable et s'il admet cette propriété : trouver un algorithme polynomial à ce problème permettrait de trouver des algoritmes polynomiaux pour tout problème de la classe NP.

Petite liste non exhaustive de problèmes NP-Complet assez populaires : le problème SAT (ainsi que 3-SAT), le problème de coloration des graphes et le problème du sac à dos (Knapsack Problem en anglais).

Algorithmes de Shor et de Grover

Algorithme de Shor

En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique pour factoriser un entier naturel N en temps et en espace , nommé en l'honneur de Peter Shor.

Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implémenté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers. En l'état actuel des connaissances, il n'existe pas d'algorithme classique capable de faire cela en temps pour n'importe quel k, donc, les algorithmes classiques connus deviennent rapidement impraticables quand N augmente, à la différence de l'algorithme de Shor qui peut casser le RSA en temps polynomial. Il a été aussi étendu pour attaquer beaucoup d'autres cryptosystèmes à clé publique.

Comme la plupart des algorithmes pour calculateur quantique, l'algorithme de Shor est probabiliste : il donne la réponse correcte avec une haute probabilité et la probabilité d'échec peut être diminuée en répétant l'algorithme.

L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits.

Algorithme de Grover

En informatique quantique, l’algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi éléments non classés en temps proportionnel à et avec un espace de stockage proportionnel à . Il a été découvert par Lov Grover en 1996.

Dans les mêmes conditions (recherche parmi des éléments non classés), un algorithme classique ne peut faire mieux qu'une recherche dans un temps proportionnel à , en testant successivement le critère sur chaque élément. L'étendue de la gamme de critères pouvant être utilisée par cet algorithme lui donne un caractère universel, ce qui en fait un des algorithmes les plus importants et potentiellement le plus utile de l'informatique quantique.

Les problèmes SAT et de coloration de graphes sont deux problèmes NP-Complet qui pourraient être résolus par cet algorithme.

Transmission de l'information de manière quantique

A l'aide de différentes propriétés de la physique quantique, il est désormais possible d'établir des communications d'un nouveau genre.

Par exemple, la Chine a déjà mis au point une expérience consistant à établir une transmission Terre-Satellite grâce aux propriétés quantiques de la matière.

Protocole BB84 et transmission d'information à des fins cryptographiques

Le protocole BB84 est l'un des protocoles les plus répandus de transmission de messages en utilisant la physique quantique. Il est en grande partie basé sur les principes d'incertitude d'Heisenberg et de superposition quantique).

Explication superposition quantique :

Une superposition quantique est une disposition dans lequel une particule quantique se trouve dans deux états à la fois. Par exemple, les photons possèdent un attribut dit de polarité. Ces états sont les polarités verticales ou horizontales. Dans un état de superposition, un photon peut se trouver dans ces deux états à la fois. Mais le photon ne peut pas garder sa superposition de polarité de manière inconditionnelle. En effet, lorsque l'on mesure la polarité d'un de ces photons, celui-ci va perdre son état superposé pour adopter un état bien défini, et ce de manière probabiliste. Autrement dit, la mesure de sa polarité va forcer le photon à choisir une polarisation, selon une certaines loi de probabilité qui lui est propre. C'est ce hasard fondamental lié à la mesure d'états superposés qui va être à la base du protocole BB84.

Pour généraliser, tout objet quantique perd son état superposé lors de toute mesure d'une de ses propriétés : c'est ce que l'on appelle la réduction d'état quantique ou projection.

Le protocole BB84 va nous permettre le partage de clés de chiffrement utilisées dans les systèmes de chiffrement symétriques. Il permet ainsi de combler une grande faille de ce genre de systèmes.

Le grand intérêt est que la limitation impliquée par ce principe est une limitation physique et non technique.

Mise en oeuvre :

Pour s'échanger la clé de chiffrement, un des deux individus va envoyer à l'autre une série de photons dans des états superposés de polarisation.

Ainsi, si la communication est interceptée lors de l'échange, d'après la réduction d'état quantique, les deux individus pourront se rendre compte de l'interception de leur clé.

Autrement, nous utilisons des photons dans ce protocole car ce sont des objets quantiques plus faciles à manipuler, et l'échange peut notamment se faire grâce à des fibres optiques déjà bien utilisées dans les infrastructures de communications.

Le protocole BB84 se déroule en plusieurs étapes, et permet à deux participants Alice et Bob d'établir une clé cryptographique commune. On suppose un canal de communication établi, sur lequel il est possible d'émettre des photons de polarisation choisie, les référentiels d'Alice et de Bob ayant été étalonnés préalablement.

En première étape, Alice choisit une suite aléatoire de bits ; pour chaque bit , elle choisit aléatoirement une base et émet un photon polarisé selon . De son côté, Bob choisit une base de réception aléatoire pour chaque photon, et aligne son filtre sur . L'illustration suivante donne à voir cette première étape en action :

Bit d'Alice ()	0	1	1	0	1	0	0	1
Base d'Alice ()
Polarisation du photon ()
Base de Bob ()
Photon reçu par Bob

En deuxième étape, Bob transmet à Alice la liste des bases utilisées lors de la réception. Alice répond en indiquant quelles sont les bases que Bob a correctement choisi, et seuls les photons correspondants sont conservés. Dans l'exemple ci-dessus, cela correspond à la séquence , , , , c'est-à-dire aux bits 0, 1, 0, 1. Cette séquence est appelée la clé « réconciliée » ou « trouée ».

Bit d'Alice ()	0	jeté	1	jeté	jeté	0	jeté	1
Base d'Alice ()
Polarisation du photon ()
Base de Bob ()
Photon reçu par Bob		jeté		jeté	jeté		jeté

En troisième étape, Alice et Bob se mettent d'accord sur un sous-ensemble de la clé réconciliée qu'ils vont révéler publiquement. Ils comparent alors s'ils ont obtenu les mêmes bits dans ce sous-ensemble : si oui, ils utilisent le reste de la clé pour dériver une clé cryptographique. S'il y a un désaccord, cela peut signifier un problème de transmission ou une tentative d'écoute le long du canal. En effet, le théorème de non clonage garantit qu'en cas d'écoute, l'espion force le photon sur une base (qui n'est pas forcément celle d'Alice). Ainsi, si l'espion devine correctement la base d'Alice avec une probabilité de 50 %, alors 25 % des bits de la clé de réconciliation seront en désaccord. De manière générale, en sacrifiant bits de la clé de réconciliation, Alice et Bob peuvent détecter un éventuel espion sur le canal avec une probabilité .

Ainsi, en construisant une longue clé de réconciliation, on peut atteindre un niveau de sécurité suffisant en sacrifiant assez de bits.

Explication tirée de Wikipédia