Adda venì la fattorizzazione quantistica!

Non so se avete mai sentito parlare dell’algoritmo di fattorizzazione di Shor. Nel 1994 Peter Shor definì 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 è quasi certamente corretto: come sappiamo nel mondo quantistico certezze non ce ne possono essere: ma la probabilità di errore può essere resa piccola a piacere.

Questo risultato, se avessimo un computer quantistico funzionante, distruggerebbe tutti gli algoritmi di crittografia che si basano sulla difficoltà della fattorizzazione, come RSA: infatti gli algoritmi classici di fattorizzazione hanno una complessità che cresce esponenzialmente con la dimensione del numero, e quindi è molto più 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ì a fattorizzare 15 con l’algoritmo di Shor. Non molto, ma un punto di partenza.

circuito logico quantistico per fattorizzare 15

È passato quasi un quarto di secolo. I computer quantistici sono diventati sempre più grandi. Eppure non si è ancora riusciti a fattorizzare 21. Craig Gidney spiega il perché. 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 (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ù! Insomma, quello che si guadagna in velocità di esecuzione si perde con gli interessi in complessità.

Ma la parte più divertente, almeno per me, è questo articolo, sempre di Gidney, che fattorizza i numeri fino a 255 e nota come per numeri così piccoli l’algoritmo è così stabile che funziona anche usando un generatore di numeri casuali anziché collassare lo stato quantistico! Insomma, possiamo ancora stare tranquilli per un po’ di tempo…

Quizzino della domenica: grafo numerato

764 – configurazioni

Posizionate i numeri da 0 a 9 nel grafo qui sotto, in modo che la somma dei numeri sui nodi collegati con un arco a ciascun numero sia quella indicata a destra. Se per esempio si assegna ad A il valore 1, la somma dei valori assegnati alle caselle a cui è collegato A (cioè B e D) deve essere 4. Quindi una di esse è 0 e l’altra 4, perché 1 è già stato assegnato e non si può avere 2 e 2.

il grafo
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p764.html; la risposta verrà postata lì il prossimo mercoledì. Problema dalla Grange Newsletter di Chris Smith.)

The Art of Uncertainty (ebook)

copertina David Spiegelhalter è probabilmente il più grande statistico britannico vivente, e in questo libro parla effettivamente della statistica. Ma lo fa da un punto di vista inaspettato, e diverso dal suo precedente “L’arte della statistica”. L'”arte dell’incertezza” è vista appunto come un’arte. Non ci sono formule matematiche, e Spiegelhalter cerca di spiegare cosa c’è davvero oltre le formule, e come l’incertezza possa essere di vari tipi (ci sono cose che in teoria sarebbero conoscibili ma non sono note, e cose future per cui non possiamo fare altro che fare supposizioni); ma soprattutto che nella statistica, e nel calcolo della probabilità che è alla sua base, il fattore personale è fondamentale. Il tutto è inframezzato da pensieri personali, dal suo coinvolgimento quando ci fu la necessità di dare delle stime per contagi e morti per Covid a come si sta comportando (dal punto di vista di uno statistico…) con il cancro alla prostata che gli è stato diagnosticato. Un testo che dovrebbe essere letto da tanti leoni da tastiera, anche se non credo lo faranno mai.

David Spiegelhalter, The Art of Uncertainty : How to Navigate Chance, Ignorance, Risk and Luck Pelican 2024, pag. 482, € 14,99 (cartaceo 22,68), ISBN 9780241658642 – come Affiliato Amazon, se acquistate il libro dal link qualche centesimo va a me
Voto: 5/5

Chiacchiere e distintivi

E quindi è stato riformato per l’ennesima volta l’esame alla fine delle superiori. Meno commissari, così si risparmia. Niente percorsi multidisciplinari, ma quattro materie per l’orale (e mi stupisco non ne vengano poi scelte due, come ai miei tempi). Ma soprattutto… (rullo di tamburi) la Vera Novità: chi farà volontariamente scena muta agli orali sarà bocciato.

Non è che gli esempi riportati dalla stampa quest’estate mi abbiano detto chissà che cosa. Banalmente, mostrano che c’è stata una persona che si è resa conto che uscire con 65/100 oppure 80/100 non avrebbe fatto alcuna differenza, e a questo punto ha deciso di togliersi uno sfizio e arrivare almeno sui giornali, dopo aver contattato un giornalista. Poi c’è stato qualcun altro che ha copiato. Evidentemente nell’esame così congegnato c’era qualcosa che non funzionava, ma il ministro non ha cercato di capire cosa e si è limitato a mostrare il suo distintivo e sanzionare quello specifico comportamento. Mi aspetto ora che qualcuno si preparerà la performance 2026 rispondendo alla prima domanda e poi salutando la commissione (non facendo così scena muta), oppure dando risposte situazioniste a tutte le domande (idem). Il tutto sempre con copertura mediatica, dimostrando che l’unica utilità “soluzione” valditaresca consiste nel fare la conferenza stampa e fregiarsi dei risultati: a pensarci bene, nulla di tanto diverso da quanto hanno fatto quegli studenti.

Ah, sì: ancora due cose. Valditara ha annunciato con Gran pompa che ci saranno 240 milioni per gli stipendi degli insegnanti: peccato che siano una tantum. E l’esame non si chiamerà più esame di Stato, ma… esame di maturità. Il vecchio che avanza.

Prese per i fondelli

Il mio conto corrente è su una banca dove la mia azienda ha una convenzione per cui non pago spese di conto. Ma nonostante tutti gli utili che in questi anni le banche stanno facendo (per dire, l’utile nel primo trimestre della mia banca è stato di due miliardi, il miglior risultato da 14 anni) si vede che la cosa non basta. Però non possono appunto introdurre un canone… e così si sono inventati le “Spese annue per conteggio interessi e competenze”, cioè una formula da applicare (formula teorica nel caso degli interessi, che sono zero). Semplice, no?

Davvero italianità?

L’altro giorno mi è capitato su Twitter un post dell’europarlamentare leghista Anna Cisint, che scrive

«Ho ritenuto doveroso scrivere al Presidente Mattarella per esprimere il profondo disorientamento dell’Unione degli Istriani di fronte all’ipotesi di cessione, nel corso della sua prossima missione in Slovenia, dell’opera d’arte “Madonna con il Bambino”, oggi custodita a Padova. Si tratta di un simbolo identitario per il popolo istriano, che ne rivendica l’appartenenza morale.»

Non sapendo nulla della storia, ho fatto qualche ricerca. La pala del Carpaccio è stata dipinta nel 1518 per la chiesa di San Francesco a Pirano, della Provincia religiosa del Santo, che al tempo corrispondeva ai territori della Repubblica Veneta corrispondenti alle Tre Venezie. Nelle tante divisioni e riunioni dei francescani la chiesa è rimasta ai Frati Minori Conventuali. Arriviamo alla seconda guerra mondiale: come spiega Finestre sull’Arte, la pala viene spostata a Villa Manin a Passariano di Codroipo assieme a molte altre opere. Nel 1943, dopo l’armistizio, le opere vennero restituite ai legittimi proprietari, ma per la pala ciò non fu possibile perché l’Istria era diventata zona di operazione speciale tedesca e le SS avevano imprigionato i frati: a questo punto essa venne lasciata in custodia ai frati minori conventuali a Padova (dal Santo); quando finalmente in Jugoslavia il complesso di Pirano tornò ai frati, la provincia religiosa patavina cominciò a chiedere ai governi italiano e sloveno di poterla far tornare al suo luogo originario, cosa che è avvenuta ora, come raccontano anche i frati dell’attuale provincia del Nord Italia.

Rileggiamo la storia: non ci fossero stati i nazisti in Istria, la pala nel 1945 sarebbe stata a Pirano e lì ci sarebbe restata, a meno che qualcuno degli esuli l’avesse trafugata. Il “valore simbolico” per gli istriani non c’era, tanto che per decenni l’opera era rimasta nei magazzini del Santo. Tutto questo l’onorevole Cisint lo sa? (probabilmente sì, ma la cosa è irrilevante)

È settembre

Lunedì sono rientrato in ufficio, dopo tre settimane di ferie. Mi sono avviato alla macchinetta del caffè, ho aperto l’app, cercato di connettermi… niente da fare. Provo ad andare alla macchinetta dell’altro piano: idem. Mi stufo, tiro fuori il badge da esterno e vado al bar Fibercop nell’altra parte del complesso. Anche i miei colleghi confermano: la macchinetta (che a quanto pare è stata cambiata) non funziona né con la chiavetta né con l’app, ma solo con le monete. Poi nel pomeriggio il collega mi offre un caffè, e a lui l’app funzionava. Bene, mi dico, è settembre anche per le macchinette.
Stamattina sono arrivato in ufficio, mi connetto: di nuovo nulla. Non ci sto a pensare troppo e me ne vado al bar “interno ma non per noi”. Dopo pranzo ritorno e funziona. Ma a questo punto mi viene in mente che però non avevo usato il codice salvato “per la macchinetta preferita” ma avevo scansionato il QRCode: e in effetti essendo la macchina diversa il codice era diverso.

(Ora devo solo ricordarmi che il default di zucchero in questa macchinetta è zero, e non “medio” come in quella precedente. Ce la posso fare)

tf–idf

Non avevo mai sentito parlare di questa funzione, il cui nome completo è “term frequency–inverse document frequency”. Eppure è una funzione del tutto naturale nel caso si voglia trovare documenti “simili” a quello di partenza in una collezione di testi.

L’idea sottostante è a posteriori ovvia. Se ho un documento in cui una parola appare molto spesso, altri documenti in cui questa parola compare spesso dovrebbero essere simili. Ma ci accorgiamo subito che questa euristica non funziona: connettivi come “che”, “perciò” oppure articoli e forme dei verbi ausiliari appariranno spesso in praticamente ogni documento. La funzione tf-idf relativa a una parola P tiene conto di tutto questo: è direttamente proporzionale alla probabilità che P appaia nel testo, ma inversamente proporzionale alla probabilità che P appaia nella collezione completa di testi. In altri termini, la funzione assume un valore tanto maggiore quanto la parola è in genere meno usata rispetto a quanto lo sia nel testo iniziale; una parola usata sempre più o meno allo stesso modo ha i due fattori che si elidono a vicenda.

In formule, abbiamo che tf-idf è il prodotto di due funzioni: tf, la frequenza del termine nel nostro documento, e idf, l’inverso della frequenza in tutti i documenti. Più precisamente,

$$\mathrm{tf_{i,j}} = \frac{n_{i,j}}{|d_j|},$$

dove $n_{i,j}$ è il numero di occorrenze del termine $i$ nel documento $j$ e il denominatore (il numero di parole nel documento) serve per perequare i valori per i documenti di lunghezza variabile, e

$$\mathrm{idf_{i}} = \log_{10} \frac{|D|}{|\{d: i \in d\}|},$$

dove $|D|$ è il numero di documenti nella collezione e al denominatore c’è il numero di documenti che contengono il termine $i$. (Per definizione ce n’è almeno uno, altrimenti non calcoleremmo idf, e quindi il denominatore non può mai essere nullo).

Il tutto funziona? Diciamo che funzionicchia. Già il concetto di idf è più euristico che altro, perché applica la legge di Zipf che come sappiamo non è scolpita nel granito; e visto che a quanto pare le raccomandazioni di libri simili nelle librerie online pare basarsi anche su tf-idf direi che ci sono ampi margini di miglioramento. Secondo Wikipedia in inglese la formula è stata anche applicata in altri campi, con risultati deludenti. Però è sempre meglio una cattiva formula che nessuna formula, e spesso si può usare il sistema “al rovescio”, per esempio cercando di scoprire se alcune delle lettere paoline siano o no state effettivamente scritte dall’apostolo. L’idea è che in questo modo brutale non si può riconoscere lo stile ma almeno si verifica che la terminologia non sia cambiata troppo, e si ha un punteggio numerico e non una sensazione come si faceva un tempo. Insomma, è comunque una freccia all’arco dei filologi.