Quantum computing: un’esplorazione top-down con l’ausilio di Q#

Quantum computers can, potentially, solve real mathematical and physical pro- blems intractable with classical computers. In real-world, current quantum hard- ware does not allow us to benefit from the full potential offered by quantum com- puting. As matter of fact the technology available today is in the order of about four hundred qubits. Despite the fact that quantum hardware is still being development and diffi- cult to achieve, quantum computing is an area of strong interest in the academic, professional and commercial worlds – there are several cloud services that allow the execution of quantum applications and many programming languages are also available. Programming languages are tools needed to translate ideas into instruc- tions executable by a quantum processor. Their development is not only crucial for the programming of large-scale quantum computers, but they can also facilitate the discovery and conception of new quantum algorithms even before there is hardware able to execute them. This work uses the Q# language and the related Quantum Development Kit from Microsoft, as an exploratory tool of quantum computing, using a top-dow pattern of learning. The first part of this thesis is dedicated to presenting the concepts required to consider the quantum nature of the physical world: such as superposition of states and entanglement. This is followed by a semantic and syntactic analysis of the Q# language and then, an interesting application is proposed: a very popular quantum search algorithm in the quantum computing literature: the Grover algorithm. This algorithm makes it possible to identify one or more elements of an unordered set of size N , in the order of O(√N ) steps.

I computer quantistici possono, potenzialmente, risolvere problemi matematici e fisici reali intrattabili con le macchine classiche. In termini di applicazioni reali, l’attuale hardware quantistico, non ci consente di beneficiare di tutte le potenzialità offerte dal quantum computing, poiché la tecnologia oggigiorno disponibile, rientra nell’ordine di circa quattrocento qubit. Nonostante le difficoltà realizzative, lo sviluppo di hardware quantistico si carat- terizza per una decisa fecondità ed effervescenza. Insomma, il quantum computing è un settore che suscita forte interesse nel mondo accademico, professionale e com- merciale – sono diversi i servizi cloud che consentono di eseguire calcolo quantistico e sono inoltre disponibili molti linguaggi di programmazione: strumenti necessari per tradurre le idee in istruzioni eseguibili da un processore quantistico. Il loro sviluppo non è solo cruciale per la programmazione di computer quantistici su lar- ga scala, ma possono anche facilitare la scoperta e l’ideazione di nuovi algoritmi quantistici ancor prima che esista un hardware in grado di eseguirli. Il lavoro presentato utilizza il linguaggio Q# e il relativo Quantum Development Kit di Microsoft, come strumento esplorativo del quantum computing, adottando un modello top-dow di apprendimento. La prima parte di questa tesi è dedicata alla presentazione dei concetti necessari per tenere conto della natura quantistica del mondo fisico: come la sovrapposizione di stati e l’entanglement. A seguire viene proposta un’analisi semantica e sintattica del linguaggio Q# per poi proporre un’applicazione interessante: un algoritmo di ricerca quantistico molto popolare nella letteratura del quantum computing: l’algo- ritmo di Grover. Tale algoritmo permette di individuare uno o più elementi, di un insieme non ordinato di grandezza N , nell’ordine di O(√N ) passi.