Introduzione al Quantum Computing (Lezione 1).

Roberto Campagnola : 3 Ottobre 2021 18:56

Autore: Roberto Campagnola
Data Pubblicazione: 28/09/2021

Siamo nel pieno dell’ Era Digitale, tutta la nostra vita dipende da informazioni, dati digitali, reti informatiche; abbiamo anche una identità digitale. Il prossimo cambiamento epocale, si ritiene, sarà rappresentato dalla computazione quantistica, anche se non è ancora del tutto delineato.

Al momento rappresenta un campo di studi in grande fermento: stati, governi ed enti di ricerca stanno coinvolgendo le migliori menti e indirizzando enormi capitali nella ricerca sulla computazione quantistica, che come le forme di ricerca fondamentale, ha prospettive temporali lunghe ma un ritorno assicurato.

Nel corso del 900 l’introduzione della meccanica quantistica ha segnato uno spartiacque nel mondo scientifico, ha acceso subito grandi dibattiti tra le più grandi personalità dell’epoca ed è tuttora, nei suoi fondamenti, oggetto di ricerca.

In questa rubrica proponiamo un percorso per capire meglio le basi della computazione quantistica, le sue prospettive e possibili applicazioni future; la meccanica quantistica è per sua stessa “costruzione” una materia altamente contro intuitiva,ma siamo sicuri di poter fornire gli strumenti giusti per poter affrontare l’argomento e renderlo comprensibile anche ad un pubblico vasto, non tralasciando gli argomenti più ostici. Inizieremo, in questo capitolo introduttivo, fornendo un breve quadro storico della nascita della “informatica classica”, la base da cui tutto è nato.

Informazioni e algoritmi

Per definizione un algoritmo è una serie di istruzioni che devono essere compiute per svolgere una azione, ne abbiamo esempi nella vita di tutti i giorni e sono il costituente principale di ogni programma o macchina informatica. Le prime testimonianze di algoritmi risalgono all’era babilonese (si hanno prove di uso di operazioni in sequenza per l’utilizzo dell’abaco), ma è solo con il contributo di Alan Turing negli anni 30 del ‘900 che si ha una formulazione teorica organica di cosa sia un algoritmo e del concetto di computabilità, che portò alla nascita della teoria dell’informazione e dell’informatica.

Il lavoro di Turing fu profondamente ispirato e prese la mosse da uno dei problemi a cui gli studiosi, in particolare i matematici, diedero grande importanza, nei primi anni del ‘900.

Nel 1928 il matematico David Hilbert, all’interno del dibattito sui fondamenti della matematica, con il suo Entscheidungsproblem(problema della decisione) si chiese se fosse possibile trovare un algoritmo in grado di risolvere, in linea di principio, ogni problema matematico. Tale problema poi si estese al quesito se fosse possibile trovare un metodo “ meccanico” per dimostrare che, dato un sistema logico matematico e il relativo insieme di regole e assiomi, tutte le sue proposizioni fossero vere o false.

All’epoca i matematici, e in particolare Hilbert, ritenevano che la risposta non potesse che essere affermativa. Nel 1930 Kurt Gödel dimostrò il primo teorema dell’incompletezza, secondo cui dato un sistema logico,esistono proposizioni matematiche che non possono essere confermate o smentite, usando assiomi e regole all’interno dello stesso sistema matematico. Il problema di Hilbert stava per ricevere una risposta negativa, quando indipendentemente nel 1936 AlanTuring e Alonzo Church diedero la “spallata definitiva”.

Macchina di Turing

Nel 1936 Aln Turing invio alla London Mathematical Society il suo articolo “ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM ” in cui propose per la risoluzione del problema di Hilbert un approccio meccanico basato su un dispositivo ideale conosciuto da allora come Macchina di Turing (MdT).

La macchina di Turing, è formata da:

• Un nastro infinito suddiviso in celle, ogni cella contiene una lettera estratta da uno specifico alfabeto oppure è lasciata vuota.
• Una unità di controllo che può assumere solo un set di stati finiti, tra cui H uno stato speciale che porta alla conclusione del calcolo e all’arresto della macchina, condizione che rivestirà una importanza particolare in seguito.
• Una testina che serve a selezionare una cella e può scrivere, leggere, o cancellarne il contenuto. Dopo le operazioni la testine si muove di uno step a destra o a sinistra.

Lo studio di Turing sulla MdT e la contemporanea attività di Alonzo Church sul cosiddetto lambda calcolo, portò alla formulazione della tesi di Church-Turing secondo cui le funzioni calcolabili da una macchina di Turing sono equivalenti a tutte le funzioni calcolabili per mezzo di un algoritmo. Tale assunto è alla base del concetto stesso di algoritmo, per sottolineare l’importanza del lavoro di Turing.

Attraverso i suoi studi, Turing risolse negativamente, come accennato sopra, l’Entscheidungsproblem facendo riferimento al problema della fermata, e dimostrando che, assegnata una qualunque MdT, non è possibile decidere algoritmicamente se essa si fermerà o meno a partire da certe condizioni iniziali.

Esempio di macchina di Turing

Nascita dei primi computer programmabili e il modello circuitale

Gli studi rivoluzionari di Turing e Church precedettero di circa 10 anni la costruzione dei primi calcolatori programmabili, a cui diede un contributo storico John Von Neumann. Nel suo documento First Draft of a Report on the EDVAC del 1945, lo scienziato ungherese diede la prima formulazione di quella che in seguito sarà nota come architettura di Von Neumann, tipologia di progettazione per computer programmabili in cui lo spazio di memoria contiene sia i dati numerici sia le istruzioni del programma della CPU.

Un modello di calcolatore alternativo alla macchina di Turing è il quello circuitale che fa uso di circuiti composti da rami in collegamento tra loro e porte logiche per utilizzare le informazioni codificate in numeri binari. La notazione binaria è, come noto, comoda da usare perché tale numerazione permette la conservazione dei dati nei componenti elettrici che possono avere due stati: un interruttore può essere acceso o spento, un circuito elettrico può avere due tipi di voltaggio (alto o basso oppure alto o nullo). Le porte logiche possono essere descritte da funzioni del tipo:

f: {0,1}j →{0,1}k

che associano a j cifre binarie (bit) in input k cifre binarie di output; tali funzioni sono infinite ma possono essere composte utilizzando un numero finito di porte logiche universali (un risultato simile si ha nel modello circuitale quantistico, che vedremo nei prossimi capitoli della rubrica). Il modello circuitale sembra avere poco in comune con la MdT, ma si può dimostrare la loro equivalenza, sempre a riprova dell’importanza storica di Alan Turing e i suoi lavori.

L’invenzione nel 1947 del primo transistor, ad opera di Bardeen, Brattain e Shockley rappresentò una ulteriore svolta e si poté costruire un dispositivo simile alla macchina di Turing e che seguisse le indicazioni, tra gli altri, proprio di Von Neumann. A partire da quel transistor, la tecnologia si è evoluta in maniera esponenziale, tanto da permettere a Gordon Moore a formulare la “prima legge” nel 1965:

“La complessità di un microcircuito, misurata ad esempio tramite il numero di transistor per chip, raddoppia ogni 18 mesi (e quadruplica quindi ogni 3 anni) “

Il processo di riduzione delle componenti (e quindi il numero di circuiti integrati che possono essere inseriti in un processore) è in costante miglioramento, nel 2021 la IBM ha annunciato1 la costruzione di un chip da 2 nm, per confronto la molecola di DNA ha un lunghezza tra i 2.2 e i 2.6 nm. Le nuove tecnologie e la costruzione di processori sempre più piccoli si basano ovviamente su regole ed effetti quantistici, perché la natura è quantistica, e la descrizione classica ne rappresenta in ultima analisi una approssimazione, ma si sta avvicinando il momento in cui gli effetti quantistici saranno dominanti e si renderà necessario un nuovo paradigma nella costruzione dei computer e relative componenti.

Fonti

https://newsroom.ibm.com/2021-05-06-IBM-Unveils-Worlds-First-2-Nanometer-Chip-Technology,-Opening-a-New-Frontier-for-Semiconductors#assets_all

Photo credit:

https://www.redhotcyber.com/wp-content/uploads/attachments/File-Model_of_a_Turing_machine.jpg

Reference:

Benenti,Casati,Strini – Principles of quantum computation and information

Roberto Campagnola
Laureato in fisica delle particelle, attualmente assegnista di ricerca presso i Laboratori Nazionali di Frascati-INFN e il CERN, si occupa dell’upgrade dell’esperimento CMS – Compact Muon Solenoid per il Large Hadron Collider.