A simulação de algoritmos quânticos a partir de computadores clássicos consiste em uma metodologia de estudo, desenvolvimento e validação que busca complementar a abordagem te orica aplicada nos estágios iniciais de construção dos algoritmos em questão. Entretanto, tal simulação é caracterizada por um elevado custo de processamento e armazenamento, exigindo recursos computacionais em larga escala. Visando a obtenção de soluções para uma simulação mais e ciente, este trabalho propõe uma metodologia de desenvolvimento caracterizada por duas etapas principais: (i) estudo teórico e implementação sequencial das abstrações de Processos Quânticos e Processos Quânticos Parciais de finidos no modelo qGM, visando a redução no consumo de memória associado à transformações quânticas multidimensionais; (ii) implementação paralela dessas abstrações para correspondente execução sobre a arquitetura massivamente paralela das GPUs. Os resultados obtidos neste trabalho contemplam a simulação sequencial de transformações quânticas controladas de até 24 qubits. No âmbito da simulação paralela, transformações Hadamard de até 20 qubits foram simuladas com speedup de 185 sobre uma simulação distribuída com 8 cores, caracterizando uma excelente melhora de desempenho no ambiente VPE-qGM com relação a suas limitações anteriores. Este trabalho estabelece as diretrizes para o desenvolvimento de extensões da biblioteca de simulação do ambiente e das capacidades de simulação paralela para transformações quânticas controladas e operações de medida.
A simulação de algoritmos quânticos a partir de computadores clássicos consiste em uma metodologia de estudo, desenvolvimento e validação que busca complementar a abordagem te orica aplicada nos estágios iniciais de construção dos algoritmos em questão. Entretanto, tal simulação é caracterizada por um elevado custo de processamento e armazenamento, exigindo recursos computacionais em larga escala. Visando a obtenção de soluções para uma simulação mais e ciente, este trabalho propõe uma metodologia de desenvolvimento caracterizada por duas etapas principais: (i) estudo teórico e implementação sequencial das abstrações de Processos Quânticos e Processos Quânticos Parciais de finidos no modelo qGM, visando a redução no consumo de memória associado à transformações quânticas multidimensionais; (ii) implementação paralela dessas abstrações para correspondente execução sobre a arquitetura massivamente paralela das GPUs. Os resultados obtidos neste trabalho contemplam a simulação sequencial de transformações quânticas controladas de até 24 qubits. No âmbito da simulação paralela, transformações Hadamard de até 20 qubits foram simuladas com speedup de 185 sobre uma simulação distribuída com 8 cores, caracterizando uma excelente melhora de desempenho no ambiente VPE-qGM com relação a suas limitações anteriores. Este trabalho estabelece as diretrizes para o desenvolvimento de extensões da biblioteca de simulação do ambiente e das capacidades de simulação paralela para transformações quânticas controladas e operações de medida.
A Computação Quântica (CQ) [7] segue atingindo novos marcos rumo à construção de computadores quânticos. Apesar de todos os esforços, vários desafios técnicos limitam os sistemas atuais a alguns bits quânticos [10]. Pela indisponibilidade de hardware quântico, o estudo e desenvolvimento de aplicações na CQ usualmente é feito estritamente pela especificação matemática das computações ou por meio de ferramentas de simulação. Este último caracteriza a abordagem mais prática, entretanto a complexidade computacional associada a simulação de sistemas quânticos a partir de computadores clássicos limita o tamanho dos sistemas a serem simulados. O projeto no qual este trabalho está inserido busca consolidar a integração de vários esforços de pesquisa, com destaque para: (i) Distribuição das computações em cluster [2]; (ii)Simulação quântica através de GPUs [5]; (iii) Simulação quântica através de CPUs multicore. Atualmente situado sob o contexto do ambiente de simulação quântica VPE-qGM (Visual Programming Environment for the Quantum Geometric Machine Model), este trabalho tem o objetivo de estabelecer o suporte à aceleração da biblioteca de execução do ambiente através de processadores multicore, beneficiando-se dos recursos providos pela biblioteca OpenMP [3]. Consolida-se assim a biblioteca qGMC-Analyzer, com a implementação, desenvolvimento e validação de algoritmo para simulação quântica em arquiteturas multicore, cuja modelagem foi introduzida em [9]. O ambiente VPE-qGM, fundamentado no modelo de processos qGM (Quantum Geometric Machine Model) [8], é constitúıdo de construtores para modelagem e simulação gráfica de aplicações quânticas. De acordo com o modelo qGM, a noção de portas quânticas pode ser substitúıda pelo conceito de sincronização de processos elementares (PEs). No ambiente VPE-qGM, o PE é um elemento estruturado por três atributos: (i) Ação: Corresponde às transformações quânticas aplicadas a diferentes qubits em um mesmo instante de tempo; (ii) Parâmetros: Contém dados auxiliares associados à definição das transformações quânticas; (iii) Posição: Posição de escrita em um espaço de memória global e compartilhada, na qual é armazenado o resultado calculado pelo PE. Neste contexto, uma transformação quântica, aplicada a N qubits, pode ser modelada pela sincronização de 2N PEs, cujas parametrizações satisfazem as condições equivalentes à definição dos vetores componentes da matriz (transformação unitária ou de medida) associada [6]. Bolsista de Iniciação Científica PIBIC/CNPq †Bolsista de PROBIC/FAPERGS Assim, durante a simulação, ocorre a execução (sequencial ou síncrona) dos PEs, os quais têm suas correspondentes computações efetuadas pela biblioteca qGM-Analyzer, manipulando os dados presentes nas posições de memória e simulando o comportamento de um sistema quântico. A biblioteca de execução dos PEs, denominada qGM-Analyzer, implementa otimizações que controlam o aumento exponencial dos vetores componentes das matrizes de definição do operador de múltiplos qubits, conforme introduzido em [4]. Os resultados relacionados comprovam a redução no consumo de memória durante a simulação, suportando algoritmos com 11 qubits. Entretanto, o tempo total de simulação obtido permanece elevado, devido a quantidade de operações necessárias para simular uma transformação quântica. A implementação da biblioteca qGM-Analyzer em C segue as otimizações introduzidas em [4], apenas alterando as estruturas de dados utilizados e fazendo uso de recursos nativos oferecidos pela linguagem visando a otimização da execução. Visando a compatibilidade da biblioteca com o ambiente VPE-qGM, é considerada a biblioteca Boost 1.49.0 [1] para integração das duas linguagens envolvidas. Para a implementação do paralelismo foi utilizada A biblioteca OpenMP [3] implementa o paralelismo. O módulo Boost-Python auxiliou no desenvolvimento da biblioteca qGMC-Analyzer permitindo que sejam reutilizados no código C tipos do Python, como as listas de valores utilizadas no ambiente VPE-qGM, e ainda realizando a conversão destes tipos para tipos da linguagem C. Outra funcionalidade utilizada do módulo Boost-Python foi a geração da biblioteca compartilhada importada pelo ambiente em Python. A implementação em C manteve o mesmo algoritmo desenvolvido em [4], porém a forma de armazenamento dos dados e os algoritmos para acesso a esses dados foram modificados para diminuir a complexidade da biblioteca. Dentre os fatores que contribúıram para um melhor desempenho, destacam-se a utilização de vetores como alternativa as listas do Python e o fato de a linguagem C ser compilada, permitindo ao compilador otimizações no código gerado. Na implementação paralela, cada thread possui uma cópia privada da pilha, e as memórias de escrita e leitura são compartilhadas entre todos os threads, pois cada valor calculado é escrito em uma posição diferente da memória. A divisão dos threads é feita de forma a manter juntos os valores das matrizes necessários para o cálculo de uma posição. Para tal, iterações são divididas levando em conta o número de colunas da primeira matriz envolvida na transformação. Nos casos em que a transformação possui apenas uma matriz, os threads são divididos de forma diferente, para que o trabalho seja distribúıdo de forma balanceada. A definição do número de threads utilizadas pela biblioteca é definida por uma variável de ambiente (OMP NUM THREADS ), gerando uma implementação mais flexível. Ou seja, dependendo da transformação quântica, tem-se um controle da granulosidade visando melhor desempenho da biblioteca. Para validação e análise de desempenho da implementação da qGM-Analyzer em C, foram desenvolvidos estudos de caso envolvendo sincronizações arbitrárias de transformações quânticas, contemplando sistemas entre 13 e 20 qubits. A metodologia dos testes utilizada contempla, para cada estudo de caso, a realização de 15 simulações. A máquina utilizada na simulação possui as seguintes características: processador Intel Core i7-3770 @ 3.4 GHz, 8GB RAM e sistema operacional Ubuntu 12.04 64 bits. A principal comparação de desempenho se dá com a execução da biblioteca em diferentes números de threads. Os testes foram realizados com transformações Hadamards, representada por uma matriz densa de ordem 2n, onde n é o número de qubits e transformações Pauli X, uma matriz esparsa de ordem 2n. Estas execuções compreenderam duas etapas: (i) Geração dos valores não nulos associados ao correspondente vetor componente da matriz de definição da transformação quântica modelada; (ii) Multiplicação desses valores pelas amplitudes obtidas da estrutura de memória que modela o espaço de estados do sistema quântico. Nas simulações das Hadamards, devido ao elevado número de operações, pode-se facilmente observar um desempenho elevado, ou seja, o aumento no número de qubits diretamente relacionado com a diminuição significativa do tempo de execução. Nas transformações controladas Pauli X houve um aumento no tempo de execução. Justifica-se este fato pelo baixo número de operações enFigura 1: Tempos das transformações Hadamard e Pauli X em relação ao número de threads. volvidas. Sendo a Pauli X uma matriz esparsa, seus valores zerados não são computados pelo algoritmo otimizado, tornando o overhead da criação e troca de contexto dos threads o principal custo da transformação, como observado no decremento de desempenho da Figura da Pauli X. Os tempos de simulação, em cada estudo de caso, abrangendo os casos para 1, 2, 4 e 8 threads são descritos na Figura 1. Como analisado, os tempos de execução para as transformações Hadamards obtiveram os melhores desempenhos. As transformações Pauli X tiveram o seu tempo de execução aumentando conforme aumentava o número de threads, pois envolvem poucos cálculos, e seu tempo é dominado pela criação e troca de contexto dos threads. As otimizações realizadas e a implementação paralela representaram um ganho significativo no tempo de execução das transformações quânticas, permitindo a simulação de transformações de 18 qubits com elevado número de operações, como no caso das Hadamards. A continuidade do trabalho consiste na integração da biblioteca qGMC-Analyzer com o ambiente VPE-qGM além da expansão para suporte a transformações multiqubits e na implementação de aplicações em outras bibliotecas disponíveis, para comparação de desempenho entre diferentes ferramentas para suporte a simulação quântica.
Este trabalho visa a extensão do ambiente D-GM para simulação distribuída de algoritmos quânticos via GPUs. A principal contribuição deste trabalho é a otimização do ambiente VirD-GM, concebida em duas etapas: (i) o estudo teórico e implementação das abstrações de Processos Mistos Parcias definidos no modelo qGM, visando a redução no consumo de memória associado à transformações quânticas multidimensionais; (ii) e a implementação distribuída/paralela dessas abstrações para correspondente execução sobre clusters de GPUs. Os resultados obtidos neste trabalho contemplam a simulação distribuída/paralela de transformações Hadamard de até 21 qubits e comprovam o ganho de desempenho com o aumento do número de clientes.
Atualmente situado sob o contexto do ambiente de simulação quântica VPE-qGM (Visual Programming Environment for the Quantum Geometric Machine Model), este trabalho tem o objetivo de estabelecer o suporte à aceleração da biblioteca de execução do ambiente através de processadores multicore, beneficiando-se dos recursos providos pela biblioteca OpenMP [3]. Consolida-se assim a biblioteca qGMC-Analyzer, com a implementação, desenvolvimento e validação de algoritmo para simulação quântica em arquiteturas multicore, cuja modelagem foi introduzida em [5]. O ambiente VPE-qGM, fundamentado no modelo de processos qGM (Quantum Geometric Machine Model) [4], é constituıdo de construtores para modelagem e simulação gráfica de aplicações quânticas. De acordo com o modelo qGM, a noção de portas quânticas pode ser substituıda pelo conceito de sincronização de processos elementares (PEs). No ambiente VPE-qGM, o PE é um elemento estruturado por três atributos: (i) Ação: Corresponde às transformações aplicadas a diferentes qubits em um mesmo instante de tempo; (ii) Parâmetros: Contém dados auxiliares associados à definição das transformações quânticas; (iii) Posição: Posição de escrita em um espaço de memória global e compartilhada, na qual é armazenado o resultado calculado pelo PE. Neste contexto, uma transformação quântica, aplicada a N qubits, pode ser modelada pela sincronização de 2N PEs, cujas parametrizações satisfazem as condições equivalentes à definição dos vetores componentes da matriz (transformação unitária ou de medida) associada. Assim, durante a simulação, ocorre a execução (sequencial ou sıncrona) dos PEs, os quais têm suas correspondentes computações efetuadas pela biblioteca qGM-Analyzer, manipulando os dados presentes nas posições de memória e simulando o comportamento de um sistema quântico. A biblioteca de execução dos PEs, denominada qGM-Analyzer, implementa otimizações que controlam o aumento exponencial dos vetores componentes das matrizes de definição do operador de múltiplos qubits [1]. Entretanto, o tempo total de simulação obtido permanece elevado, devido a quantidade de operações necessárias para simular uma transformação quântica. A implementação da biblioteca qGM-Analyzer em C segue as otimizações introduzidas em [1], apenas alterando as estruturas de dados utilizados e fazendo uso de recursos nativos oferecidos pela linguagem visando a otimização da execução. Para a implementação do paralelismo foi utilizada a biblioteca OpenMP [3]. Na implementação paralela, cada thread possui uma cópia privada da pilha, e as memórias de escrita e leitura são compartilhadas entre todos os threads, pois cada valor calculado é escrito em uma posição diferente da memória. A divisão dos threads é feita de forma a manter juntos os valores das matrizes necessários para o cálculo de uma posição. As iterações são divididas levando em conta o número de colunas da primeira matriz envolvida na transformação. Nos casos em que a transformação possui apenas uma matriz, os threads são divididos de forma diferente, para que o trabalho seja distribuıdo de forma Bolsista de Iniciação Cientıfica PIBIC/CNPq †Bolsista de PROBIC/FAPERGS balanceada. A definição do número de threads utilizadas pela biblioteca é definida por uma variável de ambiente (OMP NUM THREADS), gerando uma implementação mais flexıvel. Ou seja, dependendo da transformação quântica, tem-se um controle da granulosidade visando melhor desempenho da biblioteca. Para validação e análise de desempenho da implementação, foram desenvolvidos estudos de caso de transformações quânticas Hadamard e Pauli X [2], contemplando sistemas entre 13 e 20 qubits. Para cada estudo de caso foram realizadas 15 simulações. A máquina utilizada nas simulações possui as seguintes caracterısticas principais: processador Intel Core i7-3770 @ 3.4 GHz com Hyper-Threading abilitado e Turbo Boost desabilitado, 8GB RAM e sistema operacional Ubuntu 12.04 64 bits. A principal comparação de desempenho se dá com a execução da biblioteca em diferentes números de threads. Os testes foram realizados com transformações Hadamards, representada por uma matriz densa de ordem 2n, onde n é o número de qubits e transformações Pauli X, uma matriz esparsa de ordem 2n. Estas execuções compreenderam duas etapas: (i) Geração dos valores não nulos associados ao correspondente vetor componente da matriz de definição da transformação quântica modelada; (ii) Multiplicação desses valores pelas amplitudes obtidas da estrutura de memória que modela o espaço de estados do sistema quântico. Podemos observar o speedup das simulações em relação a um thread na Figura 1: Speedup das transformações Hadamard e Pauli X em relação a um thread. Figura 1. Nas simulações das Hadamards, observa-se que para as configurações de 2 e 4 threads, o speedup aproxima-se do ideal conforme aumenta-se o número de qubits. Para 8 threads o desempenho não segue o mesmo padrão, justificado pelo uso do hyper-threading. Nas transformações controladas Pauli X o speedup diminui conforme aumenta-se o número de threads. Justifica-se este fato pelo baixo número de operações envolvidas. Sendo a Pauli X uma matriz esparsa, seus valores zerados não são computados pelo algoritmo otimizado, tornando o overhead da criação e troca de contexto dos threads o principal custo da transformação. As otimizações realizadas e a implementação paralela representaram um ganho significativo no tempo de execução das transformações quânticas, permitindo a simulação de transformações de 18 qubits com elevado número de operações, como no caso das Hadamards.
A computação quântica é uma área de pesquisa relativamente nova em que cientistas e empresas de todo o mundo estão investigando suas potenciais aplicações, tanto no contexto científico quanto no contexto industrial. Em particular, a implementação de algoritmos quânticos e a arquitetura de qubits são as tarefas principais para a execução das aplicações de interesse. Apesar das grandes vantagens que computadores quânticos podem proporcionar em relação aos computadores clássicos, existem grandes desafios a serem superados como a decoerência e os ruídos que interferem nos processos investigativos e nos resultados das rotinas empregadas. O trabalho investiga o passeio quântico unidimensional e sua implementação nos computadores quânticos da IBM. Comparamos os principais resultados do passeio clássico com o passeio quântico, em especial foi investigado que o passeio quântico não apresenta uma distribuição de probabilidade normal à medida que o número de passos aumenta, resultado que é observado para o passeio clássico. Além disso, o desvio padrão do passeio quântico é proporcional ao número de passos n, enquanto o desvio padrão do passeio clássico é dado por √n. Através dos computadores quânticos da IBM foram realizados simulações, primeiramente de um passeio quântico de dois qubits e outra de um passeio quântico de três qubits. Os resultados para a simulação do passeio quântico de dois qubits indicam que a simulação efetuada em um computador quântico real obteve um bom desempenho apesar dos fatores de interferência e decoerência não serem desprezíveis. No entanto, os resultados para o passeio quântico de três qubits apresentaram muito ruído.
Neste trabalho, apresentamos o uso de computadores quânticos para implementar, ini- cialmente, passeios quânticos em tempo discreto. Para esse propósito, empregamos o modelo de passeios quânticos escalonados (SQW, na sigla em inglês) em ciclos de 8 e 16 vértices, visando alcançar taxas com a maior fidelidade possível. Além disso, demonstramos resultados para um problema de busca espacial e para uma malha bidimensional. Exibimos resultados para passeios quânticos a tempo discreto. Ademais, a decomposição de portas multicontroladas em portas elementares de qubits demonstra uma estratégia pragmática para a mitigação de erros, contribuindo significativamente para a confiabilidade e reprodu- tibilidade de nossos resultados em computação quântica. Essa abordagem meticulosa é crucial, especialmente ao lidar com algoritmos quânticos complexos nos quais a precisão é fundamental. Utilizando metodologia semelhante, também implementamos passeios quânticos em tempo contínuo para três casos: grafo completo, grafo bipartido completo e hipercubo. Além disso, realizamos uma comparação entre os resultados obtidos pelo simulador quântico e pelo computador quântico em todos os casos. Nosso estudo não apenas contribui para o crescente corpo de pesquisa em algoritmos quânticos, mas também destaca a importância da otimização cuidadosa em nível de portas para a computação quântica prática. À medida que as tecnologias quânticas continuam a avançar, essas descobertas abrem caminho para o desenvolvimento de algoritmos quânticos mais robustos e eficientes com aplicações no mundo real.
A Computacao Quântica surgiu como uma promissora tecnologia alternativa capaz de contornar os problemas previstos para acontecerem em breve com a saturacao da tecnologia atual (Computacao Classica). Estes problemas acontecem quando se trabalha com componentes muito pequenos, da ordem de poucos nanometros, quando os efeitos da Mecânica Quântica comecam a tornar-se mais fortes, gerando resultados aleatorios. A Computacao Quântica toma proveito desses efeitos, resultando numa Computacao nao somente mais rapida, como um novo tipo de Computacao, capaz de realizar tipos novos de computacao impossiveis, em principio, de serem realizadas classicamente. Embora a teoria da Computacao Quântica venha se desenvolvendo com rapidez, a parte experimental ainda enfrenta grandes dificuldades. Embora implementacoes de algoritmos simples e com poucos qubits ja tenham sido realizadas, ainda ha problemas serios de escalabilidade, descoerencia e controlabilidade a serem resolvidos. Devido a esses problemas, torna-se imperativo o uso de simuladores tanto para o desenvolvimento de novos algoritmos quanto para o estudo dos algoritmos existentes. A simulacao, porem, apresenta um problema, no que um sistema quântico so pode ser simulado eficientemente por outro sistema quântico. Um sistema quântico de n qubits levara um tempo O(2n ) para ser simulado por um computador classico. A simulacao, entretanto, mostra-se a alternativa mais viavel em vista da falta de um hardware quântico. Este trabalho apresenta o processo de concepcao e implementacao de um simulador universal de circuitos quânticos, denominado Zeno. O modelo de circuitos quânticos foi escolhido por ser amplamente difundido e de facil assimilacao. O trabalho apresenta uma introducao aos conceitos de Computacao Quântica usados na implementacao do simulador, os requisitos gerais desejaveis para um novo simulador de circuitos quânticos, tanto do ponto de vista funcional quanto do nao-funcional, o processo de desenvolvimento utilizado e uma analise dos resultados obtidos com a implementacao do simulador.