Simulation of a Quantum Algorithm using Quantum Fourier Transforms

Abstract

Computação quântica é uma área de grande desenvolvimento hoje em dia e isso traz uma necessidade para desenvolver hardware e software. Uma vez que o hardware disponível é muito pouco e o software precisa de ser testado, existe uma necessidade de uma boa plataforma para testar as soluções de software. Simular um computador quântico num computador clássico não é ideal, contudo é uma resposta viável a esta necessidade, para um pequeno número de qubits. Além disso, os computadores quânticos necessitam dos computadores clássicos de forma a criar um sistema real prático, isto apresenta-se como uma excelente oportunidade para testar técnicas de programação clássica para melhorar a programação quântica. Esta tese propõe o uso de programação clássica para melhorar a implementação de um algoritmo de adição modular usando transformadas de Fourier quânticas. Os principais objectivos deste trabalho são: simular um circuito quântico; testar um algoritmo quântico e compará-lo com o seu equivalente clássico; implementar o algoritmo de adição modular, usando as capacidades de aceleração de computação das transformadas de Fourier quânticas e optimizá-lo; Testar e implementar códigos quânticos de correcção de erros; fazer um teste num computador quântico real.De forma a testar a linguagem e comparar um algoritmo quântico com um clássico, fez-se um teste ao algoritmo de Shor que está disponível de raiz na plataforma liquid. Apesar do algoritmo de Shor ter, teoricamente, uma dependência de tipo polinomial com a dimensão do problema, os testes realizados mostraram que o tempo de computação tem um comportamento exponencial. Simular um algoritmo quântico num computador clássico requer tempo de computação que cresce de forma exponencial, pois é necessário armazenar e processar todos os estados do sistema, que é um espaço de Hilbert de dimensão 2^n.O algoritmo de adição modular usando transformadas de Fourier quânticas foi implementado na plataforma liquid. Seguidamente fizeram-se melhorias e optimizações. O número de operações teórico é O(n^2). Contudo, depois de fazer melhorias ao circuito, removendo gates desnecessárias para casos específicos, o número de operações passa a ter um valor mínimo de Omega(n). Com este tipo de alterações o sistema pode apresentar melhorias no que respeito ao tempo de simulação até um factor de ordem 10. Isto mostra que programar um algoritmo quântico tendo em conta casos específicos pode melhorar imenso o desempenho da simulação.Os códigos de correção de erros quânticos foram implementados num circuito simples, com as ferramentas disponíveis na plataforma liquid, e obteve-se um sistema que consegue lidar com erros com probabilidade inferior ou igual a 2%, com uma taxa de sucesso na sua correção de 95%. Contudo são necessários circuitos muito grandes, pouco exequíveis.A plataforma disponibilizada pela IBM para fazer testes num computador quântico real, foi utilizada para testar o algoritmo de adição modular e adição normal (com carry bit). Uma vez que esta plataforma tem um número limitado de gates, reforça a ideia de que se deve otimizar os algoritmos tendo em conta casos particulares. Os resultados destes testes mostram também que é importante utilizar correcção de erros quânticos, mas para que isso seja viável é necessário que haja mais qubits disponíveis ou outro tipo de códigos.

Quantum computation is a great area of development nowadays, so there is a great need to produce hardware and implement and create new software. Since hardware is very limited, and the software needs to be tested, there is a real need for a platform to test software solutions. Simulating a quantum computer in a classical one is not ideal, but is a viable answer to test quantum software with a small number of qubits as input. Also, since quantum computers need classical computers in order to become a real system, this is an opportunity to test techniques using classical and quantum programming together. This master thesis uses classical computation to improve a quantum addition algorithm based on quantum Fourier transforms (QFT). The main objectives of this work are: to simulate a quantum circuit; to test a quantum algorithm and to compare it with a classical equivalent; to implement a modular addition algorithm using the speedup capabilities of QFT and to optimize it; to test Quantum Error Correction (QEC) implementation; to run a simplified version of the modular addition algorithm in a real quantum computer.A test to the Shor's algorithm, available in liquid, was made in order to test the language and compare the algorithm with a classical one. Even though Shor's algorithm has a polynomial dependence with the size of the problem, the tests showed that regarding computing time, it performed in an exponential way. Simulating a quantum algorithm in a classical computer will take exponential time because it needs to store and process all the states of the system, a Hilbert space of dimension 2^n.Using QFT, the algorithm of modular addition was implemented in liquid. It was then improved, and all versions were optimized. The theoretical values for the number of gates is O(n^2). However, improving the circuit by eliminating gates in cases where they are not necessary, can bring the gate number down to Omega(n) in the best cases. This approach can reduce the simulation time by an order of magnitude. This shows that programming a quantum algorithm analysing specific cases can improve considerably the simulation efficiency.QEC codes were implemented in a simple circuit using the tools available in liquid, and we got a system that can handle a probability of errors of 0.02, maximum, with 95% success rate. However, the number of qubits of this circuit will be very significant.The web service IBM Q Experience was used to make a test, in a real quantum computer, with the algorithm for modular addition, as well as the algorithm for normal addition (that is, including a carry bit). Since the IBM Q Experience had a limited set of available gates and entry qubits, it reinforced the idea that it is important to optimize algorithms considering specific cases for which the circuits can be simplified. The results also show the importance of QEC codes, they are fundamental to have a proper functional system. Its implementation, however, requires a much larger number of entry qubits or the development of optimized QEC codes.