Submitted by Maria Cristina (library@lncc.br) on 2015-11-25T13:28:47Z No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-11-25T13:29:04Z (GMT) No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) / Made available in DSpace on 2015-11-25T13:29:13Z (GMT). No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) Previous issue date: 2015-11-04 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / The development of quantum algorithms is not a easy task. Elements such as entanglement and quantum paralelism, intrinsics to quantum computation, difficult this task. Quantum walks are crucial tools for development of algorithms, mainly search algorithms. There are many types of quantum walks: with coin toss, Szegedy's, using tessellation (grouping of vertices) and the continuous-time quantum walk. To extract statistics data of a quantum walk, we need to perform its simulation. In this work, we develped the simulator Hiperwalk, a new simulator of quantum walks in graphs of one and two dimension for the quantum walk with a coin toss and coinless using tessellation. The Hiperwalk allows the user to perform simulations of quantum walks in graphs using high performance computing (HPC), even though the user does not knowing parallel programming. The user can employ the parallel devices such as CPU, GPGPU and accelerators cards to speedup the overall process of the walk. / O desenvolvimento de algoritmos quânticos não é uma tarefa trivial. Elementos como emaranhamento e paralelismo quântico, intrínsecos à computação quântica, dificultam esta tarefa. As caminhadas quânticas são ferramentas cruciais para o desenvolvimento de algoritmos, principalmente algoritmos de busca. Existem na literatura vários tipos de caminhadas: com lançamento de moeda, de Szegedy, utilizando tesselagem (agrupamento de vértices) e a caminhada a tempo contínuo. Para extrair dados estatísticos de uma determinada caminhada quântica, necessitamos fazer sua simulação. Neste trabalho, desenvolvemos o simulador Hiperwalk, um novo simulador de caminhadas quânticas, em grafos de uma e duas dimensões para as caminhadas com moeda e sem moeda utilizando tesselagem. O Hiperwalk permite ao usuário efetuar simulações de caminhadas quânticas em grafos utilizando processamento de alto desempenho, mesmo que o usuário não saiba programação paralela. O usuário pode empregar os dispositivos de paralelismo como CPU, GPGPU e co-processadores para acelerar o processo geral da caminhada.

Submitted by Maria Cristina (library@lncc.br) on 2017-12-12T11:56:42Z No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-12-12T11:57:36Z (GMT) No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) / Made available in DSpace on 2017-12-12T11:57:45Z (GMT). No. of bitstreams: 1 Tese_Tharso_lncc.pdf: 1174962 bytes, checksum: 554d28620541c6c6dce94f8b4acfdf3c (MD5) Previous issue date: 2017-09-13 / Quantum walks play an important role in the development of quantum algorithms, they can be used to solve efficiently problems such as: elements distinct, boolean formulas evaluation, matrix product verification and group commutativity, and especially, spatial search problems. Falk exemplified a quantum walk model for two-dimensional lattice, that does not require an additional space to the coin, and the evolution operator can be obtained via a tessellation process. However, it was not explicit the definition of the model for generic graphs and nor proven its efficiency. The idea presented by Falk inspired the creation of Staggered Quantum Walk model (SQW). Therefore, the goal of this work is: (1) define the stepped model for generic graphs, (2) demonstrate that an important quantum walk already known and explored in the literature, the Szegedy model, is a particular case of the SQW, (3) show the efficiency of SQW in the search problem in the two-dimensional lattice. / Os passeios quânticos desempenham um papel importante no desenvolvimento de novos algoritmos quânticos, e podem ser usados para resolver eficientemente problemas como: distinção de elementos, avaliação de fórmulas booleanas, verificação de produto de matrizes e comutatividade de grupos e, em especial, problemas de busca espacial em grafos. Falk exemplificou um modelo de passeios quânticos para malha bidimensional, que não necessita de um espaço adicional para representar a moeda, no qual o operador de evolução pode ser obtido via um processo de tesselação. Porém, não foi explicitada a definição do modelo para grafos genéricos e nem comprovada a sua eficiência. A ideia apresentada por Falk inspirou a criação do Passeio Quântico Escalonado (SQW). Sendo assim, as contribuições deste trabalho são (1) definir o modelo escalonado para grafos genéricos, (2) demonstrar que um importante passeio quântico já conhecido e explorado na literatura, o modelo de Szegedy, é um caso particular do modelo escalonado e (3) mostrar a eficiência do passeio quântico escalonado no problema de busca na malha bidimensional.

Quantum information processing (QIP) is an interdisciplinary field concerned with the development of computers and information processing systems that utilize quantum mechanical properties of nature to carry out their function. QIP systems have become vastly more practical since the turn of the century. Today, QIP applications span imaging, cryptographic security, computation, and simulation (quantum systems that mimic other quantum systems). Many important strategies improve quantum versions of classical information system hardware, such as single photon detectors and quantum repeaters. Another more abstract strategy engineers high-dimensional quantum state spaces, so that each successful event carries more information than traditional two-level systems allow. Photonic states in particular bring the added advantages of weak environmental coupling and data transmission near the speed of light, allowing for simpler control and lower system design complexity. In this dissertation, numerous novel, scalable designs for practical high-dimensional linear-optical QIP systems are presented. First, a correlated photon imaging scheme using orbital angular momentum (OAM) states to detect rotational symmetries in objects using measurements, as well as building images out of those interactions is reported. Then, a statistical detection method using chains of OAM superpositions distributed according to the Fibonacci sequence is established and expanded upon. It is shown that the approach gives rise to schemes for sorting, detecting, and generating the recursively defined high-dimensional states on which some quantum cryptographic protocols depend. Finally, an ongoing study based on a generalization of the standard optical multiport for applications in quantum computation and simulation is reported upon. The architecture allows photons to reverse momentum inside the device. This in turn enables realistic implementation of controllable linear-optical scattering vertices for carrying out quantum walks on arbitrary graph structures, a powerful tool for any quantum computer. It is shown that the novel architecture provides new, efficient capabilities for the optical quantum simulation of Hamiltonians and topologically protected states. Further, these simulations use exponentially fewer resources than feedforward techniques, scale linearly to higher-dimensional systems, and use only linear optics, thus offering a concrete experimentally achievable implementation of graphical models of discrete-time quantum systems.

L'objectif de cette thèse est de développer une théorie de types pour le λ-calcul linéaire-algébrique, une extension du λ-calcul motivé par l'informatique quantique. Cette extension algébrique comprend tous les termes du λ-calcul plus leurs combinaisons linéaires, donc si t et r sont des termes, α.t+β.r est aussi un terme, avec α et β des scalaires pris dans un anneau. L'idée principale et le défi de cette thèse était d'introduire un système de types où les types, de la même façon que les termes, constituent un espace vectoriel, permettant la mise en évidence de la structure de la forme normale d'un terme. Cette thèse présente le système Lineal , ainsi que trois systèmes intermédiaires, également intéressants en eux-même : Scalar, Additive et λCA, chacun avec leurs preuves de préservation de type et de normalisation forte. / The objective of this thesis is to develop a type theory for the linear-algebraic λ-calculus, an extension of λ-calculus motivated by quantum computing. This algebraic extension encompass all the terms of λ-calculus together with their linear combinations, so if t and r are two terms, so is α.t + β.r, with α and β being scalars from a given ring. The key idea and challenge of this thesis was to introduce a type system where the types, in the same way as the terms, form a vectorial space, providing the information about the structure of the normal form of the terms. This thesis presents the system Lineal, and also three intermediate systems, however interesting by themselves: Scalar, Additive and λCA, all of them with their subject reduction and strong normalisation proofs.

A computação quântica adiabática tem sua pedra angular no teorema adiabático, cuja eficiência está relacionada tradicionalmente à proporção da variação temporal do Hamiltoniano que descreve o sistema e o gap mínimo entre o estado fundamental e o primeiro excitado. Normalmente, esse gap tende a diminuir quando aumenta o número de recursos (bit quântico: qubit) de um processador quântico, exigindo dessa maneira variações lentas do Hamiltoniano para assim garantir uma dinâmica adiabática. Entre os candidatos para a sua implementação física, estão os qubits baseados em circuitos supercondutores os quais têm um grande potencial, por causa de seu alto controle e escalabilidade promissora. No entanto, quando esses qubits são implementados, eles têm uma fonte intrínseca de ruído devido a erros de fabricação, que não podem ser desprezados. Por isso, nesta tese nós estudamos como os efeitos causados pelas flutuações dos parâmetros físicos do qubit afetam o comportamento da fidelidade da computação, realizando com esse propósito a simulação da dinâmica de cadeias de spin pequenas desordenadas. A partir do análise exaustivo desse estúdio foi possível propor uma estratégia que permite aumentar a fidelidade considerando um sistema ruidoso. Por outro lado, motivados pelo interesse de obter critérios suficientes e necessários para satisfazer uma computação quântica adiabática e pelo fato que ainda não existe uma condição de adiabaticidade geral apesar de existir inúmeras propostas, nós apresentamos um novo critério que manifesta suficiência para sistemas mais gerais e finalmente apresentamos evidências de que tal condição seria um quantificador consistente. / Adiabatic quantum computation has its cornerstone in the adiabatic theorem, whose efficiency is traditionally related to the ratio of the Hamiltonian temporal variation that describes the system and the minimum gap between the ground state and the first excited state. Usually, this gap tends to decrease when the number of quantum resources (quantum bit: qubit) of a quantum processor increases, thus it requires slow variations of the Hamiltonian to ensure an adiabatic dynamic. Among the candidates for its physical implementation are the qubits superconducting circuit-based which have great potential because of their high control and promising scalability. However, when these qubits are implemented, they have an intrinsic source of noise due to manufacturing errors that can not be despised. Therefore, in this thesis we study how the effects caused by the fluctuations of the physical parameters of the qubit affect the behavior of the fidelity of the computation, accomplishing with this purpose the simulation of the dynamics of small disordered spin chains. From the exhaustive analysis of this studio, it was possible to propose a strategy that allows to increase the fidelity considering a noisy system. On the other hand, motivated by the interest of obtaining sufficient and necessary criteria to satisfy an adiabatic quantum computation and the fact that there is still no general adiabaticity condition despite there being numerous proposals, we present a new criterion that manifests sufficiency for more general systems and we finally presented evidence that such a condition would be a consistent quantifier.

Decoherence is a major barrier to the implementation of quantum technologies. Theoretical techniques for understanding decoherence in composite systems have traditionally been focused on systems with distinguishable emission spectra, where measuring the frequency of an emitted photon allows one to determine which process took place. Here the photon contains information about the state of the system. On the other hand, systems with indistinguishable spectra do not necessarily completely reveal information about the state of the system when a photon is emitted. It can be impossible to say for certain which of two nearly degenerate transitions has occurred just by measuring the photon's frequency. It is then possible to preserve information within the system throughout the decay process. In this Thesis we show that indistinguishable spectra can lead to protected coherences within one part of a coupled quantum system, even as another part decays. We develop a zero-temperature exact approach for modelling such systems, and compare it to the microscopically derived Born-Markov master equation. This comparison helps us to understand the range of validity of the Markovian approximation. We use this understanding to extend the master equation approach to finite temperature within the Markovian regime, and we compare its high temperature results to a semiclassical model. We examine the physical conditions required for coherence protection, and remarkably we find that heating the system can improve coherence protection. Similarly, increasing the decay rate of the unprotected part of the coupled system can also enhance the coherence of the protected part. These effects are the results of linewidth broadening and thus greater spectral indistinguishability. The findings in this Thesis are of interest to both those seeking to engineer hybrid quantum systems and those seeking to develop theoretical techniques for dealing with the decoherence of composite quantum systems.

A descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico. Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas). Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão. Para quebrar estes criptossistemas, um computador quântico grande (2000 qubits) é necessário. Todavia, alternativas começaram a ser investigadas. As primeiras respostas vieram da própria mecânica quântica. Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação. Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas. Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento. Dentre os criptossistemas pós-quânticos, destacam-se o McEliece e o Niederreiter. Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandos. Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado. A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico. Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos. Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS. Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99; 7% no tamanho da chave e até 76; 2% em tempo de processamento. Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos. Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício. Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal. / The discovery of the Shor algorithm, which allows polynomial time factoring of integers, motivated efforts towards the implementation of a quantum computer. It is capable of breaking the main current public key cryptosystems used today (RSA and those based on elliptic curves). Those provide a set of security services, such as data confidentiality and integrity and source authentication, and also the distribution of a symmetric session key. To break those cryptosystem, a large quantum computer (2000 qubits) is needed. Nevertheless, cryptographers have started to look for alternatives. Some of which came from quantum mechanics itself. Despite some interesting properties found on quantum cryptography, a complete cryptosystem seems intangible, specially because of digital signatures, necessary to achieve authentication. Cryptosystems based on purely classical problems which are (believed) not treatable by quantum computers, called post-quantum, have them been proposed. Those systems still lacks of practicality, either because of the key size or the processing time. Among those post-quantum cryptosystems, specially the code based ones, the highlights are the McEliece and the Niederreiter cryptosystems. Per se, none of these provides digital signatures, but, the CFS signatures have been proposed, as a complement to them. Even if general purpose quantum computers are still far from our reality, it is possible to imagine a small dedicated quantum circuit. The benefits brought by it could make the deference to allow those signatures, in a truly post-quantum scenario. In this work, a quantum/classical hybrid architecture is proposed to accelerate post-quantum cryptographic algorithms. Two quantum coprocessors, implementing the Grover search, are proposed: one to assist the decoding process of Goppa codes, in the context of the McEliece and Niederreiter cryptosystems; another to assist the search for decodable syndromes, in the context of the CFS digital signatures. The results show that, for some cases, the use of the quantum coprocessor allows up to 99; 7% reduction in the key size and up to 76; 2% acceleration in the processing time. As a specific circuit, dealing with a well defined function, it is possible to keep a small size (300 qubits), depending on what is accelerated), showing that, if quantum computers come to existence, they will make post-quantum cryptosystems practical before breaking the current cryptosystems. Additionally, some implementation technologies of quantum computers are studied, in particular linear optics and silicon based technologies. This study aims to evaluate the feasibility of those technologies as potential candidates to the construction of a complete and personal quantum computer.

Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.

As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing. One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a reversible form. In this thesis, we present and implement a pair of algorithms that extend the best published solution to these problems by taking advantage of Product-Sum EXOR (PSE) gates, the reversible generalization of inhibition gates, which we have introduced in previous work [1,2]. We show that these gates, combined with our novel synthesis algorithms, result in much lower quantum costs over a wide variety of functions as compared to our competitors, especially on incompletely specified functions. Furthermore, this solution has applications for milti-valued and multi-output functions.

The exponential nature of Moore's law has inadvertently created huge data storage complexes that are scattered around the world. Data elements are continuously being searched, processed, erased, combined and transferred to other storage units without much regard to power consumption. The need for faster searches and power efficient data processing is becoming a fundamental requirement. Quantum computing may offer an elegant solution to speed and power through the utilization of the natural laws of quantum mechanics. Therefore, minimal cost quantum circuit implementation methodologies are greatly desired. This thesis explores the decomposition of group functions and the Walsh spectrum for implementing quantum canonical cascades with minimal cost. Three different methodologies, using group decomposition, are presented and generalized to take advantage of different quantum computing hardware, such as ion traps and quantum dots. Quantum square root of swap gates and fixed angle rotation gates comprise the first two methodologies. The third and final methodology provides further quantum cost reduction by more efficiently utilizing Hilbert spaces through variable angle rotation gates. The thesis then extends the methodology to realize a robust quantum circuit synthesis tool for single and multi-output quantum logic functions.