An interpreter for a concurrent quantum language

Abstract

Despite all progress being made over the years in the Quantum Computing field, quantum noise remains a challenge for the realization of quantum computers. A possible way of minimizing the effect of noise in quantum computing is to reorder the instructions that are set for execution in a quantum computer. By introducing concurrency to quantum programs, together with an appropriate scheduler that decides the order of execution of these instructions, it is possible to realize this reordering. In this dissertation project, we implement in Haskell a concurrent quantum language. This task involved the implementation of a parser using Parsec and the implementation of the operational semantics of the language. The goal of this implementation is to study to what extent concurrency (and, specifically, reordering) can reduce noise in quantum computing. Specifically, this implementation allows to simulate the execution of programs of the language. For a given program and an initial state, it is possible to obtain all the possible final results of the execution, as well as an histogram that represents the results of several executions. Therefore this implementation is useful for evaluating if the introduction of concurrency in a program does not change its input-output behaviour.

Apesar de todo o progresso a ser feito ao longo dos anos na área da Computação Quântica, o ruído quântico permanece um desafio para a concretização de computadores quânticos. Uma maneira possível de minimizar o efeito do ruído na computação quântica é reordernar as instruções que são dadas a um computador quântico para serem executadas. Através da introdução de concorrência nos programas quânticos, juntamente com um scheduler apropriado que decide a ordem de execução destas instruções, é possível realizar esta reordenação. Neste projeto de dissertação, implementamos em Haskell uma linguagem quântica concorrente. Esta tarefa involveu a implementação de um parser usando o Parsec a implementação a semântica operacional da linguagem. O objetivo desta implementação é estudar até que ponto a concorrência (e, especificamente, a reordenação) conseguem reduzir o ruído na computação quântica. Especificamente, esta implementação permite simular a execução de programas da linguagem. Dados um programa e um estado inicial, é possível obter todos os estados finais da execução possíveis, bem como um histograma que representa os resultados de várias execuções. Consequentemente, esta implementação é útil para avaliar se a introdução de concorrência num programa não modifica o seu output para um dado input.