Décomposition en facteurs premiers et ordinateur quantique (l'algorithme de Shor)
ฝัง
- เผยแพร่เมื่อ 27 พ.ค. 2024
- Factoriser les entiers en produits de nombres premiers est un problème central pour de nombreuses applications cryptographiques, et il est réputé difficile (exponentiel en le nombre de chiffres de l'entier à factoriser). Cependant, un ordinateur quantique pourrait effectuer cette tâche en complexité polynomiale, en utilisant l'algorithme de Shor. Dans cette vidéo, je décortique cet algorithme et explique comment il exploite de façon fondamentale la superposition quantique. Avant cela, il sera nécessaire de faire quelques rappels d'arithmétique : entiers modulo N, corps finis, groupe des inversibles, ordre d'un élément, etc. On verra ensuite comment la transformée de Fourier quantique permet de détecter à l'aide d'astucieuses interférences l'ordre d'un entier modulo N, et comment cela permet, quand on la combine avec des algorithmes utilisant des fractions continues, de factoriser efficacement les entiers.
LIEN VERS LES NOTES DE LA VIDÉO : www.antoinebourget.org/attachm...
-------------------------------------------------------------------
Je m'appelle Antoine Bourget, je suis physicien théoricien, et j'essaie de transmettre en vidéo ce que je trouve élégant en mathématiques et en physique. Pour suivre les actualités de la chaîne, et me contacter, vous pouvez rejoindre le serveur Discord ou me suivre sur les réseaux sociaux. Si vous voulez faire un don, j'ai également un compte Tipeee
Discord : / discord
Twitter : / antoinebrgt
Mon site personnel : www.antoinebourget.org
Tipeee : fr.tipeee.com/scientia-egregia/
-------------------------------------------------------------------
Référence : Je me suis énormément appuyé sur le livre de Nielsen et Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2010.
-------------------------------------------------------------------
Plan :
Introduction
00:00 Début
8:20 Le problème difficile de la factorisation
I) Transformée de Fourier Quantique
21:40 Qu'est-ce que la QFT ?
30:15 Exemples en petite dimension
44:00 Circuits quantiques
II) Arithmétique
1:01:00 Rappels sur l'arithmétique modulaire
1:12:17 Ordre d'un élément modulo N
1:17:34 Problème du logarithme discret
1:26:44 Illustration sur Mathematica
III) Logarithme discret quantique
1:30:50 Circuit quantique pour l'ordre d'un élément
1:48:48 Mesure de phase et fractions continues
IV) Décomposition en facteurs premiers
2:01:50 Lemmes préliminaires
2:18:00 Algorithme de Shor
2:34:55 Résumé et conclusion - วิทยาศาสตร์และเทคโนโลยี
Quelle déception de savoir que lors de mon stage au Synchrotron Soleil j'avais l'occasion de te remercier en personne. Je ne savais pas que t'étais à l'institut de Physique Théorique.
Je me contenterai donc de te remercier ici même si moins convivial
Merci pour votre générosité
Génial, comme d'habitude 😀
Merci!
Bonjour
Encore une vidéo très intéressante! J'ai hâte de voir celle sur la théorie des cordes.
(entre parenthèse je rentre en MPSI l'année prochaine, j'ai été accepté à Henri IV. J'essaie de préparer la rentrée, pour l'instant je lis surtout les livres)
Félicitations, et bonne lecture !
@@antoinebrgt merci!
… passionnant
Merci pour cette belle pédagogie.
Merci Antoine pour cette nouvelle excellente vidéo ! Et tes vidéos ne sont maintenant plus salies par des pubs incessantes comme elles l'étaient il y a encore quelques mois ! Ni avant, ni pendant ! Un vrai plaisir enfin retrouvé ! As-tu trouvé la solution pour éviter toutes ces pubs ? Il semble que oui ! Bravo !
Ah c'est super si les pubs sont parties, ce que j'ai fait c'est que j'ai activé la monétisation sur la chaîne, ce qui me donne pour chaque vidéo la possibilité de monétiser ou non, et je coche non ! Si ça marche c'est cool!
Analyse spectrale, interférométrie, coalescence, polynôme, théorie du signal. Excellente vulgarisation. On ne peut factoriser les entiers car ils ne sont pas entier mais doublés. Si ils étaient réellement entier, ils seraient premier. Autoreverse.
Merci pour cette super vidéo, cela me laisse à présent avec la remarque suivante : des portes logiques, c'est beaux, mais concrètement, on fait ça comment ? Une porte de Hadamard par exemple, concrètement ça ressemble à quoi et c'est fait comment...
Du coup merci de me laisser avec pleins de nouvelles questions qui attisent ma curiosité...
A très vite pour la théorie des cordes ;-)
En effet c'est une bonne question, je ne suis pas du tout spécialiste des aspects expérimentaux, et là la réponse dépend fortement de la façon que tu choisis pour réaliser physiquement les qubits !
@@antoinebrgt merci, je vais poursuivre ma curiosité 😉
Merci beaucoup pour cette vidéo très intéressante.
J'ai une petite question : existe-t-il un analogue de l'algorithme de Shor pour les courbes elliptiques ? Si oui, est-il implémentable quantiquement ?
Je ne sais pas, désolé!
Génial ! À quand la vidéo sur la correction d'erreur quantique ?
Pas pour tout de suite, peut-être à plus long terme que je reviendrai sur ce genre de sujet!
Masterclass
Merci !
Magnifique ! Merci.