{"id":33613,"date":"2025-09-08T04:51:53","date_gmt":"2025-09-08T02:51:53","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=33613"},"modified":"2025-12-29T18:46:48","modified_gmt":"2025-12-29T17:46:48","slug":"adda-veni-la-fattorizzazione-quantistica","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/09\/08\/adda-veni-la-fattorizzazione-quantistica\/","title":{"rendered":"Adda ven\u00ec la fattorizzazione quantistica!"},"content":{"rendered":"

Non so se avete mai sentito parlare dell’algoritmo di fattorizzazione di Shor<\/a>. Nel 1994 Peter Shor defin\u00ec un algoritmo di fattorizzazione di un numero che, implementato su un computer quantistico, completa il compito in un tempo polinomiale rispetto alla dimensione del numero stesso. Occhei, il risultato \u00e8 quasi certamente corretto: come sappiamo nel mondo quantistico certezze non ce ne possono essere: ma la probabilit\u00e0 di errore pu\u00f2 essere resa piccola a piacere. <\/p>\n

Questo risultato, se avessimo un computer quantistico funzionante, distruggerebbe tutti gli algoritmi di crittografia che si basano sulla difficolt\u00e0 della fattorizzazione, come RSA: infatti gli algoritmi classici di fattorizzazione hanno una complessit\u00e0 che cresce esponenzialmente con la dimensione del numero, e quindi \u00e8 molto pi\u00f9 semplice moltiplicare due numeri primi grandi che partire dal prodotto e arrivare ai due numeri. E in effetti nel 2001 ci fu il primo computer quantistico che riusc\u00ec a fattorizzare 15 con l’algoritmo di Shor. Non molto, ma un punto di partenza.<\/p>\n

\"circuito<\/p>\n

\u00c8 passato quasi un quarto di secolo. I computer quantistici sono diventati sempre pi\u00f9 grandi. Eppure non si \u00e8 ancora riusciti a fattorizzare 21. Craig Gidney spiega il perch\u00e9<\/a>. Qui sopra vedete il circuito logico usato per la fattorizzazione di 15. Ci sono sei porte entangling da due qubit e due porte di Toffoli<\/a> (quelle con due pallini neri in verticale), ciascuna delle quali corrisponde a sei porte entangling. Con i tre rivelatori finali si ha un totale di 21 porte entangling. Non riporto il disegno di un circuito ottimizzato per la fattorizzazione di 21: se volete divertirvi guardatelo nell’articolo. Dico solo che ha 191 porte CNOT e 369 porte di Toffoli, per un totale di 2405 entangling: due ordini di grandezza in pi\u00f9! Insomma, quello che si guadagna in velocit\u00e0 di esecuzione si perde con gli interessi in complessit\u00e0. <\/p>\n

Ma la parte pi\u00f9 divertente, almeno per me, \u00e8 questo articolo<\/a>, sempre di Gidney, che fattorizza i numeri fino a 255 e nota come per numeri cos\u00ec piccoli l’algoritmo \u00e8 cos\u00ec stabile che funziona anche usando un generatore di numeri casuali anzich\u00e9 collassare lo stato quantistico! Insomma, possiamo ancora stare tranquilli per un po’ di tempo…<\/p>\n","protected":false},"excerpt":{"rendered":"

Gi\u00e0 fattorizzare 21 \u00e8 troppo complicato. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[30,1024],"tags":[],"class_list":["post-33613","post","type-post","status-publish","format-standard","hentry","category-ia","category-ia-2025"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-8K9","jetpack-related-posts":[{"id":33311,"url":"https:\/\/xmau.com\/notiziole\/2025\/09\/26\/quanto-sono-migliorati-i-computer\/","url_meta":{"origin":33613,"position":0},"title":"Quanto sono migliorati i computer!","author":".mau.","date":"2025-09-26","format":false,"excerpt":"ma forse anche i programmi di fattorizzazione","rel":"","context":"In "curiosita'"","block_context":{"text":"curiosita'","link":"https:\/\/xmau.com\/notiziole\/category\/curiosita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":29146,"url":"https:\/\/xmau.com\/notiziole\/2024\/06\/19\/quando-la-fattorizzazione-non-e-unica\/","url_meta":{"origin":33613,"position":1},"title":"Quando la fattorizzazione non \u00e8 unica","author":".mau.","date":"2024-06-19","format":false,"excerpt":"quasi sempre, purtroppo","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/06\/163.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":28957,"url":"https:\/\/xmau.com\/notiziole\/2024\/05\/22\/interi-di-gauss-e-fattorizzazione-unica\/","url_meta":{"origin":33613,"position":2},"title":"Interi di Gauss e fattorizzazione unica","author":".mau.","date":"2024-05-22","format":false,"excerpt":"Non vale solo per i numeri naturali","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"i primi gaussiani","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/05\/PrimiGaussiani-1024x994.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/05\/PrimiGaussiani-1024x994.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/05\/PrimiGaussiani-1024x994.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":34160,"url":"https:\/\/xmau.com\/notiziole\/2025\/10\/29\/rsa-non-e-piu-quello-di-una-volta-i\/","url_meta":{"origin":33613,"position":3},"title":"RSA non \u00e8 pi\u00f9 quello di una volta (I)","author":".mau.","date":"2025-10-29","format":false,"excerpt":"da un bel po' di tempo, ma non cambia in realt\u00e0 molto.","rel":"","context":"In "mate-light-2025"","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7153,"url":"https:\/\/xmau.com\/notiziole\/2009\/06\/10\/massimo_comun_d\/","url_meta":{"origin":33613,"position":4},"title":"Massimo comun divisore e minimo comune multiplo","author":".mau.","date":"2009-06-10","format":false,"excerpt":"cosa sono MCD e mcm","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":31864,"url":"https:\/\/xmau.com\/notiziole\/2025\/03\/25\/matematica-lezione-59-teoria-quantistica-basi-matematiche-e-concettuali\/","url_meta":{"origin":33613,"position":5},"title":"MATEMATICA \u2013 Lezione 59: Teoria quantistica: basi matematiche e concettuali","author":".mau.","date":"2025-03-25","format":false,"excerpt":"Cosa sappiamo davvero della teoria quantistica, almeno da un punto di vista matematico?","rel":"","context":"In "rec-2025"","block_context":{"text":"rec-2025","link":"https:\/\/xmau.com\/notiziole\/category\/recensioni\/recensioni-2025\/"},"img":{"alt_text":"copertina","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/03\/mate59-195x300.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33613","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=33613"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33613\/revisions"}],"predecessor-version":[{"id":33617,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33613\/revisions\/33617"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=33613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=33613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=33613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}