Data encoding and processing for quantum-based Monte Carlo simulations in finance

Quantum computers have the potential to outperform classical computers in many problems. However, their exploitation in practical applications, requires strong developments. Current devices have limited scale and significant noise, and do not enable the exploitation of full error correction protocols. Nevertheless, while hardware and algorithmic improvements proceed at an unprecedented rate, applicative users pursue the quest for practical use cases, that can run despite error, accepting more limited speedups. In computational finance, quantum computers are considered promising for diverse workloads: from portfolio optimization to transaction settlement, from option pricing to risk analysis, just to mention a few. Most of the works in the scientific literature either focus on solutions implementable on current hardware, often leading to unrealistic hypotheses or oversimplified models, or they design long-term, bold use cases, assuming perfect hardware and neglecting the troubled path of current practical experiments. This thesis contributes to bridging such gap, starting from algorithms providing proven theoretical speedup on real-world problems, moving such applications from the abstract modeling level to the circuit implementation, and addressing the main challenges that arise at such level. Indeed, the state of the art in quantum computing cannot tolerate any inefficiency accumulating along abstraction levels: on the contrary, it demands circuit optimization across the full stack. A major challenge that we tackle, is efficient data loading. It is known that in absence of specific data structures, the exact loading of a classical dataset requires a linear time in the dataset size, thus undermining the speedup of some quantum algorithms, and becoming the bottleneck in others. This fact justifies approximate data loading techniques, that typically accept a one-time costly pre-processing, in favor of an efficient loading circuit, under the hypothesis that the same input is reused multiple times. Among many proposed approaches, we focus our investigation on quantum artificial intelligence, and specifically on quantum Generative Adversarial Networks. We tune the hyperparameters of the network obtaining a 43-64% improvement compared to the state of the art. We pay close attention to multivariate distributions, of practical relevance in advanced financial use cases, and show that gradient free optimization (SPSA) methods cannot achieve results comparable to that of gradient-based methods (Adam AMSGRAD), in terms of accuracy, thus calling for new advancements to support the scaling capability of qGANs. The second challenge is efficient arithmetic manipulation. We propose a novel data format that achieves a sharper representation of floating-point random variables under a limited number of qubits, and reduces the circuit depth needed for addition and multiplication. We achieve a circuit depth reduction up to 89% against prior formats. The third contribution is about circuit compilation. Before execution, a logically synthesized circuit needs to be adapted to the constraints given by the target hardware, such as the available gates, the topology, etc. Recent announcements of commercial companies introduced the future possibility to resort to multiple quantum chips connected by quantum communication channels, allowing for distributed quantum computing. Such opportunity, that opens disruptive scenarios in quantum processing capabilities, requires for ad-hoc compiling techniques, keeping into account the specific nature of distributed hardware and the fact that the most critical resource becomes the creation of a remote entanglements. In this context, we formalize the compilation as a dynamic network flow problem, and exploit special gate parallelization capabilities to further enhance results. The work concurs in drawing the applicability of quantum computing to real-world problems closer. The results have implications for instance on the financial problem of Bermudan option pricing, consisting of finding the fair price of a contract which allows the owner to buy or sell an underlying asset, such as a stock, at fixed price, in any time in the future before expiration. The possibility to exercise the option at any time represents a computational challenge, requiring intensive Monte Carlo simulations on classical computers. It is known that the execution time of Monte Carlo techniques can be quadratically improved on quantum devices by recurring to the so-called Quantum Amplitude Estimation and its variants. Our results are applicable also beyond the boundaries of finance: we show that the same techniques can be exploited for other tasks that classically resort to Monte Carlo models, such as in particle physics.

I computer quantistici hanno la capacità di superare le performance dei computer classici in molti problemi, in prospettiva futura. Tuttavia il loro impiego in applicazioni pratiche richiede ulteriori avanzamenti tecnologici. Infatti, i dispositivi attuali hanno una scala limitata, soffrono significativamente del rumore, e non consentono di sfruttare protocolli completi di correzione degli errori. Mentre i miglioramenti nell’hardware e negli algoritmi procedono a ritmo serrato, gli utenti applicativi perseguono la ricerca di casi d'uso pratici che possano essere eseguiti già oggi nonostante gli errori, eventualmente dedicandosi ad algoritmi con speedup più limitati. Nella finanza computazionale, i computer quantistici sono promettenti per diversi utilizzi: dall'ottimizzazione dei portafogli al regolamento delle transazioni, dal pricing delle opzioni all'analisi del rischio, per citarne alcuni. La maggior parte dei lavori nella letteratura scientifica si polarizzano su soluzioni implementabili sull'hardware attuale, spesso portando a ipotesi irrealistiche e modelli ipersemplificati, oppure all’estremo opposto indirizzano casi d'uso di rilevanza primaria, destinati però a dare risultati sul lungo termine, assumendo hardware perfetto e trascurando le complessità pratiche dell’esecuzione sull’hardware attuale. Questa tesi contribuisce ad avvicinare i due estremi, partendo da algoritmi che forniscono un comprovato speedup teorico su problemi industriali, calando tali applicazioni dal livello della modellazione astratta all'implementazione del circuito, e affrontando le principali sfide che si presentano a tale livello. Lo stato dell'arte nell'informatica quantistica non può tollerare l’accumularsi di inefficienze lungo i livelli di astrazione: al contrario, richiede l'ottimizzazione dei circuiti attraverso l’intero stack. Una fondamentale sfida che affrontiamo è il caricamento efficiente dei dati. È noto che in assenza di strutture dati specifiche, il caricamento esatto di un data set classico richiede un tempo lineare nella dimensione del data set, minando così il vantaggio di alcuni algoritmi quantistici e diventando il collo di bottiglia in altri. Questo fatto giustifica tecniche di caricamento approssimato dei dati, che tipicamente richiedono una costosa pre-elaborazione una tantum, a favore di un circuito di caricamento efficiente, nell'ipotesi che lo stesso input venga riutilizzato più volte. Tra i molti approcci proposti, concentriamo la nostra indagine sull'intelligenza artificiale, e in particolare sulle Quantum Generative Adversarial Networks (qGAN). Gli iperparametri della rete neurale sono affinati in modo da ottenere un miglioramento del 43-64% rispetto allo stato dell'arte. Particolare attenzione viene riposta nel caricamento di distribuzioni multivariate, che hanno rilevanza pratica per problemi avanzati della finanza. Mostriamo che i metodi di ottimizzazione senza gradiente (SPSA) non riescono ad ottenere risultati paragonabili a quelli dei metodi basati sul gradiente (Adam AMSGRAD) in termini di accuratezza, e quindi nuovi avanzamenti sono richiesti per garantire la scalabilità delle qGAN. La seconda sfida è il calcolo aritmetico efficiente su computer quantistici. Proponiamo una nuova rappresentazione dei dati in virgola mobile che fornisce maggiore precisione con un numero limitato di qubit e riduce la profondità dei circuiti necessari per l'addizione e la moltiplicazione. Otteniamo una riduzione fino all'89% rispetto alle rappresentazioni precedenti. Il terzo contributo riguarda la compilazione di circuiti. Per poter essere eseguito sull’hardware, un circuito deve essere adattato ai vincoli dell’hardware di destinazione, fra cui i gate fisicamente disponibili, la topologia del dispositivo, etc. Recenti annunci di aziende commerciali hanno introdotto la possibilità di ricorrere in futuro a più chip quantistici collegati da canali di comunicazione quantistica, aprendo la strada del calcolo quantistico distribuito. Tale possibilità, che offre opportunità molto significative nelle capacità di elaborazione quantistica, richiede tecniche ad hoc di compilazione, che tengano conto della specificità dell'hardware distribuito e del fatto che la risorsa critica è la creazione di un entanglement remoto. In questo contesto, formalizziamo il problema di compilazione come un dynamic network flow problem, e sfruttiamo opportunità di parallelizzazione dei gate per migliorare ulteriormente i risultati. Il presente lavoro contribuisce ad avvicinare l'applicabilità del calcolo quantistico ai problemi del mondo reale. I risultati hanno implicazioni, ad esempio, al problema finanziario di pricing delle opzioni bermudiane, consistente nel determinare il prezzo equo di un contratto che consente al detentore di acquistare o vendere un asset sottostante, come un'azione, a un prezzo fissato, in qualsiasi momento futuro prima della scadenza. La possibilità di esercitare l'opzione in qualsiasi momento rappresenta una sfida computazionale, che richiede simulazioni intensive di Monte Carlo su computer classici. È noto che il tempo di esecuzione delle tecniche Monte Carlo può essere migliorato quadraticamente su dispositivi quantistici ricorrendo alla cosiddetta Quantum Amplitude Estimation e alle sue varianti. Inoltre, i nostri risultati hanno impatti anche oltre i confini della finanza: le stesso impianto si applica ad altri problemi classicamente risolti con i modelli Monte Carlo, come mostriamo tramite un esempio tratto dalla fisica delle particelle.