Feynman path-sum quantum computer simulator

Abstract

Classical quantum simulators are essential tools for studying quantum systems and simulating quantum algorithms. The hardware limitations of NISQ (Noisy Intermediate Scale Quantum) devices make being able to build, test and run a quantum circuit/algorithm many times, and even test it under various noise scenarios, in a classical computer, extremely useful. Currently, the most prominent technique for classically simulating quantum circuits is known as Schrodinger type simulation. The memory usage of simulations using this technique increases exponentially with the number of qubits in a circuit, reaching prohibitive memory values relatively fast. This serves as motivation to investigate complementary classical quantum simulation techniques. The present work offers an investigation on how to improve the runtime of the Feynman path-sum approach for classical simulation of quantum circuits, taking into account the computational basis input and output states given and the branching structure generated by branching gates in a quantum circuit. The main contributions of this dissertation are two Feynman path-sum based simulation algorithms. These algorithms were able to successfully simulate quantum circuits with a large number of qubits (> 30) using polynomial space and it was demonstrated that the time complexity of these algorithms is more strongly influenced by the circuit structure rather than the circuit size.

Os simuladores quânticos clássicos são ferramentas essenciais para o estudo de sistemas quânticos e simulação de algoritmos quânticos. As limitações de hardware dos dispositivos NISQ (Noisy Intermediate-Scale Quantum) tornam extremamente útil a possibilidade de construir, testar e executar um circuito/algoritmo quântico muitas vezes, e mesmo testá-lo sob vários cenários de ruído, num computador clássico. Actualmente, a técnica mais proeminente de simulação clássica de circuitos quânticos e conhecida como simulação do tipo Schrodinger. A utilização de memoria das simulações que utilizam esta técnica aumenta exponencialmente com o número de qubits num circuito, atingindo valores de memória proibitivos com relativa rapidez. Este facto serve de motivação para investigar técnicas complementares de simulação quântica clássica. O presente trabalho oferece uma investigação sobre a forma de melhorar o tempo de execução do método de soma de caminhos de Feynman para a simulação clássica de circuitos quânticos, tendo em conta os estados, na base computacional, de entrada e saída e a estrutura de ramificação gerada pelas portas de ramificação num circuito quântico. As principais contribuições desta dissertação˜ são dois algoritmos de simulação baseados na soma de caminhos de Feynman. Estes algoritmos foram capazes de simular com sucesso circuitos quânticos com um grande número de qubits (> 30) usando espaço polinomial e foi demonstrado que a complexidade temporal destes algoritmos e mais fortemente influenciada pela estrutura do circuito do que pelo tamanho do circuito.