Foundations for quantum algorithms and complexity

Abstract

Recently, quantum computation has been generating a lot of interesting from both industry and academia, due to the first results on quantum supremacy, i.e. the first time quantum computers were able to perform efficiently tasks deemed unfeasible to classical computers, made possible by the state-of-art qubit technology. These achievements, despite the unusefulness of the tasks performed (quantum circuit sampling), provide evidence that real world quantum computation is not only evolving, but also, that full-scale quantum computers may be a reality in the mid-term future. The benefits of quantum computation are well-known to be potentially ground-breaking, from making of RSA cryptography unsecure, to the efficient simulation of quantum systems. On theoretical side, the algorithm body of knowledge has evolved, and nowadays, there is already a huge number of algorithms and techniques, scattered across a vast realm of applications, from solving certain linear equations to optimization. Nonetheless, the progress in the development of new algorithms with an exponential advantage, rather than polynomial, has been quite slow and even the application of the most general quantum computational techniques to new problems is far from a trivial task. The main motivation for this work was to contribute to this problem, and doing so by following a foundational approach, i.e. by the understanding of the structures behind quantum algorithms and the conception of formal methods to aid in their construction. Such an approach has to deal with two somewhat orthogonal dimensions, which correspond to traditionally mutual exclusive fields of study, complexity and semantics, and hence, the contribution of this work is also two-fold: in one hand we try to identify and characterize the structures that carry the so-called quantum advantage, and in the other hand by dealing with the correction of quantum algorithms, in this case a dynamic logic for a particular class of quantum programs: the ones expressible on a fragment of the quantum assembly programming language (QASM). Furthermore, a relevant part of the contribution of this work is the use of the theoretical findings over new fields of application of quantum algorithms. The first one is in the field of quantum biology, including the simulation of the non-radiative effects of electronic transport through a molecular chain in a photosyn thesis system. The other one belongs to the field of quantum chemistry, namely, the calculation of the ground state of the Hydrogen and Lithium-Hydride molecules, under the action of a strong electrical field (the stationary Stark effect). Both applications were carried out in a real world quantum computer, the IBM Q

Recentemente, o interesse em computação quântica tem vindo a aumentar exponencialmente, devido ao facto da meta da ”supremacia quântica”, momento em que os computadores quânticos são capazes de realizar tarefas intratáveis para computadores clássicos, ter sido recentemente atingida por equipas independentes, utilizando arquiteturas de qubits quânticos diferentes. Isto dá evidência da saudável velocidade de evolução da área, e fortalece a ideia de que os computadores quânticos em grande escala, podem vir a ser uma realidade no futuro. Os benefícios, há muito conhecidos, podem ser realmente transformadores, em campos como a crip tografia, ao tornar a criptografia RSA obsoleta, assim como na simulação de sistemas quânticos. Nos últimos anos, o campo das aplicações dos algoritmos quânticos tem vindo a crescer rapidamente, onde já prontificam métodos para a resolução de equações, ou para a resolução de problemas de otimização. Não obstante, o progresso no desenvolvimento de algoritmos quânticos que consigam, à semelhança do algoritmo de Shor, tirar completo proveito da vantagem quântica, que se traduz numa vantagem exponencial, tem sido lento e mesmo a aplicação das técnicas mais gerais a novos problemas, revela-se complexa. A motivação deste trabalho é contribuir para a mitigação deste problema, através de uma abordagem ”fundacional” dos algoritmos e da sua complexidade, ou seja, através da análise e classificação das estruturas que adicionam a vantagem quântica aos programas quânticos, e se possível, a concepção de técnicas formais que permitam ajudar na engenharia de novos algoritmos. Essas técnicas, oferecem o desafio de ter de gerir duas dimensões dos algoritmos quânticos, tradicional mente estudadas em separado: complexidade e semântica. Assim, a abordagem deste trabalho baseou-se também nessas duas dimensões: por um lado, na caracterização dos algoritmos e das estruturas que lhes permitem a chamada vantagem quântica, e por outro na concepção de uma lógica dinâmica para uma classe específica de programas quânticos: aqueles que são exprimíveis num fragmento da linguagem QASM. Uma parte relevante deste trabalho é também a aplicação do conhecimento sobre algoritmos em novos exemplos de aplicação, o que é feito em dois novos exemplos: no campo da biologia quântica, na simulação do transporte electrónico sem recurso a radiação, e no campo da química quântica, no cálculo do estado fundamental da moléculas H2 e LiH, sob acção de um campo elétrico forte (efeito Stark), utilizando um computador quântico real, o IBM Q.