Quantum computing promises to solve certain complex problems by exploiting the principles of quantum mechanics, such as superposition, which allows qubits to leverage parallelism in a way that differs from what is available in classical computing. Despite this potential, today’s quantum devices have significant limitations, such as high error rates, short coherence times, and a limited number of qubits. Accurately estimating the resources required by quantum algorithms — in particular, the number of qubits and operations — is essential to determine their feasibility on current and near-future hardware. This thesis addresses these challenges with QuRA, a tool for analysing the resource consumption of quantum programs. The approach is demonstrated through a detailed analysis of Shor’s algorithm, a key quantum algorithm with important implications for cryptography thanks to its ability to efficiently factor large integers, threatening to break protocols such as RSA. By providing mathematically supported guarantees on resource bounds, this work clarifies the practical requirements for implementing Shor’s algorithm. These contributions have significant implications both for the theoretical study and the practical realization of quantum computing.
Stima delle Risorse di Programmi Quantistici attraverso Inferenza di Tipo: QuRA e l'Algoritmo di Shor
Il calcolo quantistico promette di risolvere alcuni problemi complessi sfruttando i principi della meccanica quantistica, come la sovrapposizione, che consente ai qubit di sfruttare il parallelismo in un modo diverso da quello disponibile nel calcolo classico. Nonostante questo potenziale, i dispositivi quantistici odierni presentano limitazioni significative, come alti tassi di errore, tempi di coerenza brevi e numero limitato di qubit. Stimare con precisione le risorse necessarie agli algoritmi quantistici, in particolare il numero di qubit e di operazioni, è fondamentale per determinarne la fattibilità sull'hardware esistente e su quello del prossimo futuro. Questa tesi affronta tali sfide con QuRA, un tool per l'analisi del consumo di risorse di programmi quantistici. L'approccio è dimostrato attraverso un'analisi dettagliata dell'algoritmo di Shor, un algoritmo quantistico chiave con importanti implicazioni per la crittografia grazie alla sua capacità di scomporre efficacemente grandi numeri interi, minacciando di rompere protocolli come RSA. Fornendo garanzie matematicamente supportate sui limiti delle risorse, questo lavoro chiarisce le esigenze pratiche dell'implementazione dell'algoritmo di Shor. Questi contributi hanno implicazioni significative sia per lo studio teorico che per la realizzazione pratica del calcolo quantistico.