Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-14T17:27:49Z (GMT). No. of bitstreams: 1 Agudelo_JuanCarlosAgudelo_D.pdf: 1223911 bytes, checksum: 92e4a3e06e1921aefd3476374d0726f2 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho levantamos, e investigamos do ponto de vista conceitual, evidências de que a complexidade algorítmica pode ser vista como relativa à lógica. Propomos, para tanto, novos modelos de computação fundados sobre lógicas não-clássicas, estudando suas características quanto à expressabilidade computacional e eficiência. A partir desta visão, sugerimos um novo caminho para estudar a eficiência dos modelos de computação quântica, enfatizando a análise de uma lógica subjacente a tais modelos. O conteúdo da tese está estruturado da seguinte maneira: no primeiro capítulo apresentamos uma análise conceitual da noção de 'computação', indicando como este conceito tem mudado desde os trabalhos fundacionais da década de 1930, e discutindo se o conceito deve ser considerado como puramente físico, puramente lógicomatemático ou uma combinação de ambos. O Capítulo 2 introduz duas versões de 'máquinas de Turing paraconsistentes', usando sistemas lógicos diferentes e obtendo modelos com diferentes poderes computacionais (quanto à eficiência); tal resultado constitui uma primeira evidência a favor da relatividade lógica da computação que queremos defender. Outra evidência na mesma direção é apresentada no Capitulo 3, através da generalização dos circuitos booleanos para lógicas não-clássicas, em particular para a lógica paraconsistente mbC e para a lógica modal S5, e da análise do poder computacional de tais generalizações. O Capítulo 4 consiste numa introdução à computação quântica, para logo (no Capítulo 5) estabelecer algumas relações entre modelos de computação quântica e modelos de computação paraconsistente, de maneira a propor uma interpretação lógica dos modelos quânticos. No capítulo final (Capítulo 6) descrevemos várias relações entre mecânica quântica e lógica paraix consistente, relações estas que sugerem potencialidades com alto grau de relevância a respeito da abordagem paraconsistente dos fenômenos computacionais quânticos e que incitam a continuar explorando esta alternativa. / Abstract: This work provides evidences to view computational complexity as logic-relative, by introducing new models of computation through non-classical logics and by studying their features with respect to computational expressivity and efficiency. From this point of view, we suggest a new way to study the efficiency of quantum computational models consisting in the analysis of an underlying logic. The contents of the thesis is structured in the following way: the first chapter presents a conceptual analysis of the notion of 'computation', showing how this concept evolved since the decade of 1930 and discussing whether it can be considered a pure physical or a pure logic-mathematical concept, or a combination of both paradigms. Chapter 2 introduces two versions of 'paraconsistent Turing machines', by considering different logic systems and obtaining models with different computational capabilities (with respect to efficiency); such a result constitute a first evidence in favor of the logical relativity of computation that we are defending here. Another evidence in the same direction is presented in Chapter 3 through a generalization of boolean circuits to non-classical logics, particularly for the paraconsistent logic mbC and for the modal logic S5, and by analyzing the computational power of such generalizations. Chapter 4 consists in an introduction to quantum computation. This is used in Chapter 5 to establish some relationships between quantum and paraconsistent models of computation, in order to propose a logic interpretation of quantum models. The final chapter (Chapter 6) describes several connections between quantum mechanics and paraconsistent logic; such relationship suggests highly relevant potentialities in favor of the paraconsistent approach to quantum computation phenomena encouraging to continue exploring this alternative. / Doutorado / Logica / Doutor em Filosofia

A three-level system can be used in a Λ-type configuration in order to construct auniversal set of non-adiabatic quantum gates through the use of non-Abelian non-adiabatic geometrical phases. Such construction allows for high-speed operation times which diminish the effects of decoherence. This might be, however, accompanied by a breakdown of the validity of the rotating wave approximation (RWA) due to the comparable timescale between the counter-rotating terms and the pulse length, which greatly affects the dynamics. Here we investigate the trade-off between dissipative effects and the RWA validity, obtaining the optimal regime for the operation of the holonomic quantum gates.

To reach the error threshold required to successfully perform error-correcting algorithms in quantum computers, geometric quantum gates have been considered because of their natural resilience against noise. Non-cyclic geometric gates have been proposed to reduce the run time of conventional geometric gates, to further guard against decoherence. However, while these proposed gates remove the dynamical phase from the computational basis, they do not in general remove it from the eigenstates of the time evolution operator. For a non-cyclic gate to genuinely be considered geometric the dynamical phase should be removed from both the computational basis and the eigenstates. Here, a scheme for finding genuine non-cyclic geometric gates is proposed. The gates are designed to evolve the computational basis along non-cyclic paths, consisting of two geodesic segments, chosen such that the dynamical phase is removed from the eigenstates. The gates found with this scheme did not have shorter runtimes than cyclic gates, but it was possible to implement any gate with this scheme. The findings are important for the understanding of how general quantum computations can be implemented with geometric gates.

<p>We demonstrate how quantum machine learning might play a vital role in achieving moderate speedups in machine learning problems and might have scope for providing rich models to describe the distribution underlying the observed data. We work with Restricted Boltzmann Machines to demonstrate the same to supervised learning tasks. We compare the relative performance of contrastive divergence with sampling from Dwave annealer on bars and stripes dataset and then on imabalanced network security data set. Later we do training using Quantum Imaginary Time Evolution, that is well suited for the Noisy Intermediate-Scale Quantum era to perform classification on MNIST data set.  </p>

No / We present a demonstrative application of the nonholonomic control method to a real physical system composed of two cold Cesium atoms. In particular, we show how to implement a CNOT quantum gate in this system by means of a controlled Stark field.

<p dir="ltr">We analyze the query complexity of multiple search problems.</p><p dir="ltr">Firstly, we provide lower bounds on the complexity of "Local Search". In local search we are given a graph G and oracle access to a function f mapping the vertices to numbers, and seek a local minimum of f; i.e. a vertex v such that f(v) <= f(u) for all neighbors u of v. We provide separate lower bounds in terms of several graph parameters, including congestion, expansion, separation number, mixing time of a random walk, and spectral gap. To aid in showing these bounds, we design and use an improved relational adversary method for classical algorithms, building on the prior work of Scott Aaronson. We also obtain some quantum bounds using the traditional strong weighted adversary method.</p><p dir="ltr">Secondly, we show a multiplicative duality gap for Yao's minimax lemma by studying unordered search. We then go on to give tighter than asymptotic bounds for unordered and ordered search in rounds. Inspired by a connection through sorting with rank queries, we also provide tight asymptotic bounds for proportional cake cutting in rounds.</p>

Yes / Exterior calculus with its three operations meet, join and hodge star complement, is used for the representation of fermion-hole systems and for fermionic analogues of logical gates. Two different schemes that implement fermionic quantum computation, are proposed. The first scheme compares fermionic gates with Boolean gates, and leads to novel electronic devices that simulate fermionic gates. The second scheme uses a well known map between fermionic and multi-qubit systems, to simulate fermionic gates within multi-qubit systems.

<p dir="ltr">Quantum computing is advancing rapidly, with variational quantum algorithms (VQAs) showing great promise for demonstrating quantum advantage on near-term devices. A critical component of VQAs is the ansatz, a parameterized quantum circuit that is iteratively optimized. However, compiling ansatz circuits for specific quantum hardware is challenging due to topological constraints, gate errors, and decoherence. This thesis presents a series of techniques to efficiently generate and optimize quantum circuits, with a focus on VQAs. We first introduce AccQOC, a framework combining static pre-compilation with accelerated dynamic compilation to transform quantum gates to hardware pulses using quantum optimal control (QOC). AccQOC generates pulses for frequently used gate sequences in advance and stores them in a lookup table. For new gate sequences, it utilizes a Minimum Spanning Tree based approach to find the optimal compilation order that maximizes the similarity between consecutive sequences, thereby accelerating the compilation process. By leveraging pre-computed pulses and employing a similarity-based approach, AccQOC achieves a 9.88×speedup in compilation time compared to standard QOC methods while maintaining a 2.43×latency reduction over gate-based compilation. Building on AccQOC, we propose EPOC, an extended framework integrating circuit partitioning, ZX-calculus optimization, and synthesis methods. EPOC operates at a finer granularity compared to previous coarse-grained approaches, decomposing circuits into smaller sub-circuits based on the number of qubits and circuit depth. It then applies synthesis techniques to identify equivalent representations with reduced gate count. The optimized sub-circuits are then grouped into larger unitary matrices, which are used as inputs for QOC. This approach enables increased parallelism and reduced latency in the resulting quantum pulses. Compared to the state-of-the-art pulse optimization framework, EPOC achieves a 31.74% reduction in circuit latency and a 76.80% reduction compared to gate-based methods. To construct hardware-efficient ansatz for VQAs, we introduce two novel approaches. TopGen is a topology-aware bottom-up approach that generates sub-circuits according to the connectivity constraints of the target quantum device. It starts by generating a library of subcircuits that are compatible with the device topology and evaluates them based on metrics 17 like expressibility and entangling capability. The sub-circuits with the best properties are then selected and progressively combined using different techniques. TopGen also employs dynamic circuit growth, where small sub-circuits are appended to the ansatz during training, and gate pruning, which removes gates with small parameters. Evaluated on a range of VQA tasks, TopGen achieves an average reduction of 50% in circuit depth after compilation compared to previous methods. NAPA takes a more direct approach by utilizing devicenative parametric pulses as the fundamental building blocks for constructing the ansatz. It uses cross-resonance pulses for entangling qubits and DRAG pulses for single-qubit rotations. The ansatz is constructed in a hardware-efficient manner. By using the better flexibility and expressivity of parametric pulses, NAPA demonstrates up to 97.3% latency reduction while maintaining accuracy comparable to gate-based approaches when evaluated on real quantum devices. Finally, we explore error mitigation techniques for VQAs at the pulse level. We develop a fidelity estimator based on reversed pulses, that enables randomized benchmarking of parametric pulses. This estimator compares the final state obtained after applying a sequence of pulses followed by their reversed counterparts to the initial state, using the probability of successful trials as a proxy for fidelity. Furthermore, we adapt the zero-noise extrapolation (ZNE) technique to the pulse level, enabling the error mitigation for quantum pulses. Applied to VQE tasks for H2 and HeH+ molecules, pulse-level ZNE reduces the deviation from ideal expectation values by an average of 54.1%. The techniques developed in this thesis advance the efficiency and practicality of VQAs on near-term quantum devices. The introduced frameworks, AccQOC and EPOC, provide efficient pulse optimization, while TopGen and NAPA can construct hardware-efficient ansatz. Besides, the pulse-level error mitigation techniques presented in this thesis improve the resilience of VQAs against the inherent noise and imperfections of NISQ devices. Together, these contributions help unlock the full potential of quantum computing and realize practical quantum advantages in the near future.</p>

Qubits (quantum bits) are what runs quantum computers, like a bit in classical computers. Quantum gates are used to operate on qubits in order to change their states. As such they are what ”programmes” a quantum computer. An unfortunate side effect of quantum physics is that coupling a quantum system (like our qubits) to an outside environment will lead to a certain loss of information. Reducing this decoherence effect is thus vital for the function of a quantum computer. Geometric quantum computation is a method for creating error robust quantum gates by using so called geometric phases which are solely reliant on the geometry of the evolution of the system. The purpose of this project has been to develop physical schemes of geometric entangling two-qubit gates along the Schmidt sphere, a geometric construct appearing in two-qubit systems. Essentially the overall aim has been to develop new schemes for implementing robust entangling quantum gates solely by means of interactions intrinsic to the computational systems. In order to create this gate four mutually orthogonal states were defined which together spanned the two-qubit state space. Two of the states were given time dependent variables containing a total of two angles,which were used to parameterize the Schmidt sphere. By designing an evolution for these angles that traced out a cyclical evolution along geodesic lines a quantum gate with exclusively geometric phases could be created. This gate was dubbed the ”Schmidt gate” and could be shown to be entangling by analyzing a change in the concurrence of a two qubit system. Two Hamiltonians were also defined which when acted upon the predefined system of states would give rise to the aforementioned evolution on the Schmidt sphere. The project was successful in creating an entangling quantum gate which could be shown by looking at difference in the concurrence of the input and output state of a two-qubit system passing through the gate.

Usamos um modelo exatamente solúvel para calcular a dinâmica da fidelidade de uma computação baseada em medidas projetivas cujo sistema interage com um meio ambiente comum que insere erros de fase. Mostramos que a fidelidade do estado de Cluster canônico oscila como função do tempo e, como consequência, a computação quântica baseada em medidas projetivas pode apresentar melhores resultados computacionais mesmo para um conjunto sequencial de medidas lentas. Além disso, apresentamos uma condição necessária para que a dinâmica da fidelidade de um estado quântico geral apresente um comportamento não-monotônico. / We use an exact solvable model to calculate the gate fidelity dynamics of a measurement-based quantum computation that interacts with a common dephasing environment. We show that the fidelity of the canonical cluster state oscillates as a function of time and, as a consequence, the measurement-based quantum computer can give better computational results even for a set of slow measurement sequences. Furthermore, we present a necessary condition to the fidelity dynamics of a general quantum state presents a non-monotonical shape.