A computação quântica está prestes a mudar o mundo tal como o conhecemos. Através da exploração das propriedades da teoria quântica para fins computacionais, é esperada uma redução substancial na quantidade de problemas que hoje são considerados intratáveis. Isto significa que os computadores quânticos têm a capacidade de devolver soluções para alguns problemas de interesse prático para os quais um computador clássico não consegue devolver, pelo menos em tempo útil. Isto é ainda mais revolucionário e notável pelo facto de que esses problemas abrangem domínios multidisciplinares como Química, Medicina e, mais relevante no contexto desta dissertação, Finanças.Neste trabalho, vamos focar-nos na utilização da computação quântica para abordar um problema relevante e atual no domínio financeiro. Mais especificamente, um problema de otimização combinatorial, o problema de otimização de portfólios, que consiste em selecionar o melhor portfólio financeiro (combinação de ativos) entre um conjunto de todos os portfólios possíveis, de acordo com uma certa função objetivo, comummente de forma a maximizar o retorno esperado ou minimizar o risco. Devido ao grande número de parâmetros, como o retorno esperado por ativo e as condições de mercado, este problema atinge uma complexidade exponencial e é um problema NP-hard, intratável no contexto da computação clássica.Nós desenvolvemos um estudo empírico acerca da influência dos parâmetros nas soluções devolvidas por um computador quântico para o problema de otimização de portfólios. Em particular, utilizamos um computador quântico da D-Wave e variamos os parâmetros relacionados não só com o computador quântico, mas também com o problema de otimização de portfólios. Acreditamos que as conclusões do estudo são contribuições úteis para qualquer investigador que deseje utilizar computadores quânticos adiabáticos no contexto do problema de otimização de portfólios e também noutros domínios de aplicação.As nossas descobertas sugerem que os parâmetros têm efeito nos resultados, quer sejam relacionados com o problema de otimização de portfólios ou com o computador quântico. Além disso, também descobrimos que alguns dos parâmetros têm um grande impacto, tal como o chain strength, que define a força com a qual os qubits que representam uma variável estão correlacionados, e que outros não têm nenhum efeito estatisticamente significativo, tais como o anneal schedule ou o embedding.
A computação quântica está prestes a mudar o mundo tal como o conhecemos. Através da exploração das propriedades da teoria quântica para fins computacionais, é esperada uma redução substancial na quantidade de problemas que hoje são considerados intratáveis. Isto significa que os computadores quânticos têm a capacidade de devolver soluções para alguns problemas de interesse prático para os quais um computador clássico não consegue devolver, pelo menos em tempo útil. Isto é ainda mais revolucionário e notável pelo facto de que esses problemas abrangem domínios multidisciplinares como Química, Medicina e, mais relevante no contexto desta dissertação, Finanças.Neste trabalho, vamos focar-nos na utilização da computação quântica para abordar um problema relevante e atual no domínio financeiro. Mais especificamente, um problema de otimização combinatorial, o problema de otimização de portfólios, que consiste em selecionar o melhor portfólio financeiro (combinação de ativos) entre um conjunto de todos os portfólios possíveis, de acordo com uma certa função objetivo, comummente de forma a maximizar o retorno esperado ou minimizar o risco. Devido ao grande número de parâmetros, como o retorno esperado por ativo e as condições de mercado, este problema atinge uma complexidade exponencial e é um problema NP-hard, intratável no contexto da computação clássica.Nós desenvolvemos um estudo empírico acerca da influência dos parâmetros nas soluções devolvidas por um computador quântico para o problema de otimização de portfólios. Em particular, utilizamos um computador quântico da D-Wave e variamos os parâmetros relacionados não só com o computador quântico, mas também com o problema de otimização de portfólios. Acreditamos que as conclusões do estudo são contribuições úteis para qualquer investigador que deseje utilizar computadores quânticos adiabáticos no contexto do problema de otimização de portfólios e também noutros domínios de aplicação.As nossas descobertas sugerem que os parâmetros têm efeito nos resultados, quer sejam relacionados com o problema de otimização de portfólios ou com o computador quântico. Além disso, também descobrimos que alguns dos parâmetros têm um grande impacto, tal como o chain strength, que define a força com a qual os qubits que representam uma variável estão correlacionados, e que outros não têm nenhum efeito estatisticamente significativo, tais como o anneal schedule ou o embedding.
Antes restrita a uma área de fronteira da Física, a computação quântica é uma das áreas que mais tem crescido atualmente, justamente por suas aplicações tecnológicas em problemas de otimização, aprendizagem de máquina, segurança da informação e simulações. O objetivo deste artigo é introduzir os fundamentos da computação quântica, tendo como foco um algoritmo quântico promissor e sua aplicação a um problema do mercado financeiro. Mais especificamente, discutimos o problema da otimização de portfólio usando o Quantum Approximate Optimization Algorithm (QAOA). Não somente descrevemos os principais conceitos envolvidos, mas também consideramos exemplos simples práticos, envolvendo ativos financeiros disponíveis na bolsa brasileira, com códigos, tanto clássicos quanto quânticos, dísponíveis livremente em um Jupyter Notebook. Também analisamos em detalhes a qualidade das soluções de otimização combinatória de portfólio por meio do QAOA usando o simulador quântico ATOS QLM do SENAI/CIMATEC.
A teoria dos algoritmos quânticos promete benefícios sem precedentes ao utilizar as leis da mecânica quântica para resolver certos problemas computacionais. Entretanto, alguns desafios impedem que tais vantagens se apliquem a todos os algoritmos quânticos. Entre esses desafios está o desenvolvimento de uma codificação eficiente de dados clássicos em um estado quântico. Em aplicações práticas, o custo para carregar a informação clássica em um dispositivo quân- tico pode dominar o custo computacional assintótico do algoritmo. Foram propostos diversos métodos baseados em circuitos para codificar dados clássicos nas amplitudes de probabilidade de um estado quântico. Entretanto, esses métodos produzem circuitos com complexidade que cresce linearmente com o tamanho do dado, anulando o benefício da aplicação quântica. O objetivo principal deste trabalho é reduzir a complexidade computacional dos circuitos para a inicialização de estados quânticos. As duas estratégias utilizadas para alcançar tal objetivo exploram a troca de complexidade temporal por espacial ou a transferência de complexidade computacional para um computador clássico. A primeira estratégia reinterpreta métodos al- gébricos para a decomposição de estados quânticos como caminhadas ao longo de árvores binárias. A segunda investiga o grau de emaranhamento de bipartições do estado quântico através da decomposição de Schmidt. Os métodos baseados em árvore alcançam uma redução exponencial na profundidade dos circuitos, em comparação às abordagens existentes. Os base- ados na decomposição de Schmidt produzem circuitos de complexidade variável, proporcional ao emaranhamento do estado. A perspectiva é que o resultado desta tese auxilie os profissionais da computação quântica durante a era dos dispositivos ruidosos de escala intermediária.
[pt] A superioridade de desempenho dos algoritmos quânticos, em alguns problemas específicos, reside no uso direto de fenômenos da mecânica quântica para realizar operações com dados em computadores quânticos. Esta característica fez surgir uma nova abordagem, denominada Computação com Inspiração Quântica, cujo objetivo é criar algoritmos clássicos (executados em computadores clássicos) que tirem proveito de princípios da mecânica quântica para melhorar seu desempenho. Neste sentido, alguns algoritmos evolutivos com inspiração quântica tem sido propostos e aplicados com sucesso em problemas de otimização combinatória e numérica, apresentando desempenho superior àquele dos algoritmos evolutivos convencionais, quanto à melhoria da qualidade das soluções e à redução do número de avaliações necessárias para alcançá-las. Até o presente momento, no entanto, este novo paradigma de inspiração quântica ainda não havia sido aplicado à Programação Genética (PG), uma classe de algoritmos evolutivos que visa à síntese automática de programas de computador. Esta tese propõe, desenvolve e testa um novo modelo de algoritmo evolutivo com inspiração quântica, denominado Programação Genética Linear com Inspiração Quântica (PGLIQ), para a evolução de programas em código de máquina. A Programação Genética Linear é assim denominada porque cada um dos seus indivíduos é representado por uma lista de instruções (estruturas lineares), as quais são executadas sequencialmente. As contribuições deste trabalho são o estudo e a formulação inédita do uso do paradigma da inspiração quântica na síntese evolutiva de programas de computador. Uma das motivações para a opção pela evolução de programas em código de máquina é que esta é a abordagem de PG que, por oferecer a maior velocidade de execução, viabiliza experimentos em larga escala. O modelo proposto é inspirado em sistemas quânticos multiníveis e utiliza o qudit como unidade básica de informação quântica, o qual representa a superposição dos estados de um sistema deste tipo. O funcionamento do modelo se baseia em indivíduos quânticos, que representam a superposição de todos os programas do espaço de busca, cuja observação gera indivíduos clássicos e os programas (soluções). Nos testes são utilizados problemas de regressão simbólica e de classificação binária para se avaliar o desempenho da PGLIQ e compará-lo com o do modelo AIMGP (Automatic Induction of Machine Code by Genetic Programming), considerado atualmente o modelo de PG mais eficiente na evolução de código de máquina, conforme citado em inúmeras referências bibliográficas na área. Os resultados mostram que a Programação Genética Linear com Inspiração Quântica (PGLIQ) apresenta desempenho geral superior nestas classes de problemas, ao encontrar melhores soluções (menores erros) a partir de um número menor de avaliações, com a vantagem adicional de utilizar um número menor de parâmetros e operadores que o modelo de referência. Nos testes comparativos, o modelo mostra desempenho médio superior ao do modelo de referência para todos os estudos de caso, obtendo erros de 3 a 31% menores nos problemas de regressão simbólica, e de 36 a 39% nos problemas de classificação binária. Esta pesquisa conclui que o paradigma da inspiração quântica pode ser uma abordagem competitiva para se evoluir programas eficientemente, encorajando o aprimoramento e a extensão do modelo aqui apresentado, assim como a criação de outros modelos de programação genética com inspiração quântica.
A computação quântica é um paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.
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.
Desde a primeira vez que computação quântica foi concetualizada por Feynman, simulação quântica tem estado na vanguarda das possiveis aplicações de interesse. Os custos proibitivos de simular sistemas quânticos com computadores classicos são uma forte motivação para a investigação em computação quântica. Ao longo da última década, tem-se observado um progresso notável no desenvolvimento de hardware quantico. No entanto, os obstáculos entre nos e a era de vantagem quantica util mantem-se essencialmente os mesmos: A informação quântica e fragil, e protegê-la é um desafio. Visto que os dispositivos quânticos atuais são ruidosos e tem um número limitado de qubits, desenvolver algoritmos que possam ser executados neles e uma area de investigação importante. Por resultarem em circuitos de preparação de estado (ansatze) pouco profundos e treinaveis, algoritmos quânticos variacionais (VQAs) adaptativos são uma opção promissora. O primeiro algoritmo nesta classe, o ADAPT-VQE, pode ser utilizado para problemas de estrutura eletronica, otimização combinatoria, materia condensada, sistemas periódicos no tempo, entre outros. Nesta tese, são propostas varias melhorias para VQAs adaptativos, com o objetivo de diminuir os custos e aumentar a viabilidade a curto prazo. Propõe-se um otimizador quasi-Newton para VQAs adaptativos que reduz os custos de medição necessários para implementar estes algoritmos em hardware quântico, bem como o tempo necessario para os simular classicamente. Propõe-se ainda um novo conjunto de operadores — “operatores de intercambio acoplado” (CEOs) — que resulta no menor numero de portas quanticas e na menor profundidade de circuito entre todas as propostas na literatura. Combina-se varios desenvolvimentos-chave e mostra-se uma redução dramatica dos recursos computacionais quânticos necessários em comparação com as primeiras versões do algoritmo ou com ansätze estáticos para VQE. Adicionalmente, propõe-se uma versão codesenhada do ADAPT-VQE (Co-ADAPT-VQE) onde o hardware quântico e tido em consideração na construção do ansatz. Este paradigma pode ser utilizado para otimizar circuitos de preparação de estado em qualquer dispositivo, colmatando limitações como conetividade limitada, tempos de coerencia curtos, e erros nas portas quanticas. Finalmente, propomos estrategia para mitigar “vales de gradientes”, um problema de convergência especifico ao ADAPT-VQE.