Esta dissertação explora o problema da Transferência Perfeita de Estado (PST) em grafos, que tem implicações significativas na computação quântica. O objetivo é determinar quais grafos permitem transferir perfeitamente o estado de um qubit (ou vértice) para outro qubit em um determinado tempo. O texto apresenta uma introdução ao tema utilizando técnicas de álgebra linear, discutindo condições necessárias e suficientes para alcançar o PST e enfatizando a transferência de longa distância entre qubits. O objetivo da otimização ´e minimizar o número de componentes quânticos necessários para alcançar a transferência perfeita de estado. Uma classe importante de grafos que admite PST são os caminhos com pesos. Para o PST entre vértices nos extremos, o problema foi completamente resolvido explorando a conexão desses grafos com polinômios ortogonais. No entanto, o problema se torna consideravelmente mais complexo para vértices em outras posições, levando a novos resultados e conexões explorados neste documento. Entre esses resultados, podemos citar uma fórmula que relaciona, de maneira inédita, o polinômio extremo com outro polinômio arbitrário em uma sequência de polinômios ortogonais; como criar uma sequência de polinômios ortogonais que contenha outros dois dados; e como o PST em caminhos com pesos se relaciona com o problema de Prouhet-Tarry-Escott, um problema em aberto na área de teoria dos números. Por fim, o documento apresenta uma abordagem para a construção de grafos com PST, explorando caminhos ponderados e partições equitativas. Também são apresentados novos teoremas nessa ´área, que têm relevância geral para a teoria dos grafos. Entre esses teoremas, destaca-se um critério para dois grafos possuírem um quociente simetrizado em comum; como as matrizes de partições equitativas se relacionam com matrizes projetivas; e como o conjunto de partições equitativas se transforma quando o grafo original é quocientado.
Esta dissertação explora o problema da Transferência Perfeita de Estado (PST) em grafos, que tem implicações significativas na computação quântica. O objetivo é determinar quais grafos permitem transferir perfeitamente o estado de um qubit (ou vértice) para outro qubit em um determinado tempo. O texto apresenta uma introdução ao tema utilizando técnicas de álgebra linear, discutindo condições necessárias e suficientes para alcançar o PST e enfatizando a transferência de longa distância entre qubits. O objetivo da otimização ´e minimizar o número de componentes quânticos necessários para alcançar a transferência perfeita de estado. Uma classe importante de grafos que admite PST são os caminhos com pesos. Para o PST entre vértices nos extremos, o problema foi completamente resolvido explorando a conexão desses grafos com polinômios ortogonais. No entanto, o problema se torna consideravelmente mais complexo para vértices em outras posições, levando a novos resultados e conexões explorados neste documento. Entre esses resultados, podemos citar uma fórmula que relaciona, de maneira inédita, o polinômio extremo com outro polinômio arbitrário em uma sequência de polinômios ortogonais; como criar uma sequência de polinômios ortogonais que contenha outros dois dados; e como o PST em caminhos com pesos se relaciona com o problema de Prouhet-Tarry-Escott, um problema em aberto na área de teoria dos números. Por fim, o documento apresenta uma abordagem para a construção de grafos com PST, explorando caminhos ponderados e partições equitativas. Também são apresentados novos teoremas nessa ´área, que têm relevância geral para a teoria dos grafos. Entre esses teoremas, destaca-se um critério para dois grafos possuírem um quociente simetrizado em comum; como as matrizes de partições equitativas se relacionam com matrizes projetivas; e como o conjunto de partições equitativas se transforma quando o grafo original é quocientado.
Passeios quânticos em tempo contínuo é uma das áreas de pesquisa em teoria algébrica de grafos e computação quântica. Uma das suas sub-áreas de pesquisa é a de transferência de estados entre vértices de um grafo. Transferências de estados são importantes, pois permitem avaliar em quais casos uma rede com comunicação feita através de estados modelados por um grafo permitem que esses estados sejam transmitidos com o máximo possível de probabilidade de maneira eficiente. Em geral, trabalhos sobre transferência de estados lidam com transferências perfeitas ou quase perfeitas entre dois vértices. Transferências perfeitas de estado possuem caracterizações para as matrizes de Adjacência e Laplaciana. Além disso, foi mostrado ser possível verificar transferências perfeitas de estado em um grafo com um algoritmo polinomial. Em relação a transferências quase perfeitas, embora existam caracterizações para sua ocorrência, tais caracterizações demandam um certo trabalho para sua verificação em grafos e nenhum algoritmo exato é conhecido para validar sua existência. Alguns artigos mostram que, devido às restrições que as transferências perfeitas impõem nos autoespaços do grafo, tais transferências são relativamente raras em classes comuns de grafos. Portanto, é natural tentar verificar a ocorrência de transferências quase perfeitas de estados. Nessa dissertação, apresenta-se o primeiro algoritmo exato para conferir a ocorrência de transferências quase perfeita de estados em grafos. Além disso, aplicou-se resultados conhecidos nas matrizes de adjacência e Laplaciana de transferências perfeita e quase perfeita de estados na matriz Normalizada Laplaciana, considerando sua relação com passeios clássicos em grafos.
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.
A fim de obter transferência de estado perfeita entre dois sites em uma rede de qubits interagindo, seus vértices correspondentes no grafo subjacente devem satisfazer uma propriedade chamada cospectralidade forte. Aqui nós determinamos a estrutura dos grafos contendo pares de vértices que são fortemente cospectrais e satisfazem um certo extremo propriedade relacionada ao espectro do grafo. Se o grafo satisfaz essa propriedade globalmente e é regular, também mostramos que a existência de uma partição do conjunto de vértices em pares de vértices na distância máxima admitindo transferência de estado perfeita força o grafo a ser regular em distância. Finalmente, apresentamos alguns novos exemplos de transferência de estado perfeita em grafos simples construídos com nossa tecnologia. Em particular, para distâncias ímpares, melhoramos o trade-off conhecido entre a distância que a transferência de estado perfeita ocorre em grafos simples e o tamanho do grafo.
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.
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.