Integration of time in a quantum process algebra

Abstract

Process algebras are mathematical structures used in Computer Science to study, model, and verify concurrent systems. Essentially, a process algebra consists of a language (used to specify a system that one wishes to study), a semantic domain to interpret the language (which allows the interpretation and the study of the system) and a set of axioms related to the language operators (which facilitates the derivation of properties of the system be ing studied). These basic ingredients make process algebras powerful tools, with many applications in the development of concurrent systems and many successful stories in in dustry, Bunte et al. (2019); Groote and Mousavi (2014). The three classical examples of a process algebra are: CCS introduced by Robin Milner, ACP introduced by Jan Bergstra and Jan Willem Klop, and CSP introduced by Tony Hoare. Of the three, the first stands out because of its main goal to isolate and study the elementary principles of communication and concurrency. The development of Quantum Mechanics supports the design of computational systems ruled by quantum laws, which, in the context of certain problems, perform significantly better than any classical computational system. This is exemplified with Shor and Grover algorithms, respectively used in the factorization of integers and in unstructured searching. Moreover, Quantum computing has applications in the communications area, having as main examples the quantum teleportation protocol and the BB84 communication protocol. However, due to their high sensitivity to noise, quantum computers have a very limited memory space, and therefore they usually integrate a QRAM architecture: essentially, a net work of classical computers that process and manage a general task list, invoking quantum computers only when high-cost computational tasks arise. This highlights the importance of extending the theory of process algebras to the quantum domain. In fact, some quantum process algebras were already proposed in last years: examples include qCCS, developed by Mingsheng Ying et al based on CCS, and the CQP algebra, introduced by Simon Gay and Rajagopal Nagarajan. Related to qCCS, a typing system was developed, where the typable processes are exactly the valid qCCS processes. Current quantum process algebras assume the existence of an ideal quantum system, i.e. a quantum system immune to noise. In contrast, the aim of this dissertation is to study and develop a quantum process algebra in which this assumption is discarded. More specifically, we do not assume that a quantum state can be stored indefinitely, it may become corrupted over time, or in other words, have a limited time of coherence. For that goal, 1) we developed a new quantum process algebra that merges the strengths of qCCS and CQP, in particular, recursion, memory allocation, and a typing system, so that we can study complex quantum systems that integrate the QRAM architecture; 2) we extended the new process algebra with a notion of time so that we could study its effects on quantum states; and 3) we developed a number of case studies, via the mentioned extension, in which the coherence time of quantum systems has a central role. This includes, for example, a simplified version of the IBM Cloud, which provides access to a quantum computer via web.

Álgebras de processos são estruturas matemáticas usadas em Ciências da Computação para o estudo, modelação, e verificação de sistemas concorrentes. Essencialmente, uma álgebra de processos é composta por uma linguagem (usada para especificar o sistema que se deseja estudar), um domínio semântico para interpretação dessa linguagem (o que permite interpretar e estudar o sistema) e um conjunto de axiomas relativos aos operadores da linguagem (o que facilita a derivação de propriedades do sistema em estudo). Estes ingredientes básicos tornam as álgebras de processos ferramentas poderosas, com várias aplicações no desenvolvimento de sistemas concorrentes e várias histórias de sucesso na indústria, Bunte et al. (2019); Groote and Mousavi (2014). Os três exemplos clássicos de álgebras de processos são: CCS introduzida por Robin Milner, ACP introduzida por Jan Bergstra e Jan Willem Klop, e CSP introduzida por Tony Hoare. Das três, destaca-se a primeira como sendo aquela cujo objectivo principal é isolar e estudar os princípios elementares da comunicação e da concurrência. O desenvolvimento da Mecânica Quântica, permitiu conceber sistemas de computação regidos pelas leis quânticas, que, no contexto de certos problemas, têm um desempenho significativamente melhor que qualquer sistema computacional clássico. Isto é exemplificado com os algoritmos de Shor e de Grover, usados respectivamente na factorização de inteiros e em procuras não estruturadas. Para além disso, a computação quântica tem aplicações na área da comunicação, tendo como exemplos principais o protocolo de teletransporte quântico e o protocolo de comunicação BB84. No entanto devido à sua elevada sensibilidade ao ruído, os computadores quânticos têm um espaço de memória bastante limitado, e portanto costumam integrar uma arquitectura QRAM, em que uma rede de computadores clássicos processam e gerem uma lista geral de tarefas, invocando o computador quântico apenas quando surgem certas tarefas de elevado custo computacional. Isto sublinha a importância de estender a teoria das álgebras de processos ao domínio quântico. De facto, algumas álgebras de processos quânticos já foram propostas nos últimos anos: exemplos incluem qCCS, desenvolvida por Mingsheng Ying et al e que tem por base CCS, e a álgebra CQP, introduzida por Simon Gay e Rajagopal Nagarajan. Relacionado com qCCS, um sistema de tipos foi desenvolvido, onde os processos tipados são exatamente os processos válidos em qCCS. As actuais álgebras de processos quânticos assumem a existência de um sistema quântico ideal, i.e. um sistema quântico insensível ao ruído. Em contraste, o objectivo deste trabalho é o estudo e desenvolvimento de uma álgebra de processos quânticos em que esta assunção seja descartada. Mais especificamente, não assumimos que um estado quântico possa ser guardado indefinidamente, mas que possa tornar-se corrompido ao longo do tempo, ou por outras palavras, que tenha um tempo limitado de coerência. Para tal, 1) desenvolvemos uma nova álgebra de processos quânticos que reúne diversos pontos fortes de qCCS e CQP, em particular recursividade, alocação de memória, e sistemas de tipagem, para que possamos estudar sistemas quânticos complexos e que integrem uma arquitectura QRAM; 2) estendemos a nova álgebra de processos com uma noção de tempo para podermos estudar o efeito deste sobre os estados quânticos; e 3) desenvolvemos uma série de casos de estudo, através da extensão referida, em que o tempo de coerência dos estados quânticos tem um papel central. Isto inclui, por exemplo, uma versão simplificada da IBM Cloud, que providencia acesso a um computador quântico via web.