Made available in DSpace on 2015-03-04T18:50:52Z (GMT). No. of bitstreams: 1 thesis.pdf: 6097890 bytes, checksum: 7eea019378a8126c37befefac84557cb (MD5) Previous issue date: 2007-06-15 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Caminhos aleatórios clássicos são essenciais para a Física, a Matemática, a Ciência da Computação e muitas outras áreas. Há uma grande expectativa que a sua versão quântica seja ainda mais poderosa, uma vez que o caminhante quântico se espalha quadraticamente mais rápido que o seu análogo clássico. Neste trabalho, estudamos o comportamento do caminhante quântico em uma e duas dimensões, além de generalizarmos o formalismo de ligações interrompidas para duas ou mais dimensões. Em uma dimensão, analisamos o comportamento do caminhante quântico, que além das duas possibilidades de deslocamento usuais, direita e esquerda, também permanece na posição atual. Em duas dimensões, apresentamos um estudo detalhado do comportamento do caminhante no plano e quando há descoerência gerada pela quebra aleatória das ligações para as posições vizinhas com uma certa probabilidade para cada uma das direções. Quando essa probabilidade de quebra é diferente nas duas direções encontramos um resultado não trivial que representa uma transição do caso 2-D descorente para o caso 1-D coerente. Também utilizamos o formalismo de ligações interrompidas para modelar o comportamento de um caminhante quântico que passa por uma e por duas fendas. Realizamos simulações com com as principais moedas e observamos conclusivamente os padrões de interferência e difração.

Made available in DSpace on 2015-03-04T18:51:17Z (GMT). No. of bitstreams: 1 thesisMarquezino.pdf: 1984026 bytes, checksum: aab2f346b43ad780233318adb7219d76 (MD5) Previous issue date: 2010-02-26 / Conselho Nacional de Desenvolvimento Cientifico e Tecnologico / Quantum computing is a model of computation based on the laws of quantum mechanics, which can be used to develop faster algorithms. The development of efficient quantum algorithms, however, is a highly challenging task. A recent successful approach is the use of quantum walks. In this work, we have studied the quantum walk on the hypercube, obtaining the exact stationary distribution and analyzing properties of its mixing time both in the ideal and in the noisy set-ups, with noise generated by broken links. We have also studied the walk in a two-dimensional grid, where we have obtained its stationary distribution analytically and have explored the relation between mixing time and the complexity of the search algorithm for this graph. We have developed a computational tool for numerical simulation of quantum walks in one- and two-dimensional grids with several boundary conditions. Finally, we have studied some algorithms for search on graphs and have numerically analyzed the impact of decoherence over their performances. / A computação quântica é um modelo computacional baseado nas leis da mecânica quântica, que pode ser utilizado para desenvolver algoritmos mais eficientes que seus correspondentes clássicos. O desenvolvimento de algoritmos quânticos eficientes, no entanto, é uma tarefa altamente desafiadora. Uma abordagem recente que vem se mostrando bem-sucedida é a utilização de caminhadas quânticas. Neste trabalho, estudamos a caminhada quântica no hipercubo, calculando analiticamente sua distribuição estacionária e analisando propriedades de seu mixing time, tanto na situação ideal como na situação com descoerência gerada por ligações interrompidas. Também estudamos a caminhada na malha bidimensional, calculando sua distribuição estacionária analiticamente e explorando a relação entre o mixing time e a complexidade do algoritmo de busca nesse grafo. Desenvolvemos uma ferramenta computacional para simulação numérica de caminhadas quânticas em malhas uni- e bidimensionais com diversas condições de contorno. Finalmente, estudamos alguns algoritmos de busca em grafos e analisamos numericamente o impacto que a descoerência exerce sobre seus desempenhos.

Submitted by Maria Cristina (library@lncc.br) on 2015-09-23T18:31:34Z No. of bitstreams: 1 tese_pedro.pdf: 954527 bytes, checksum: e9834fab8c799933912f185f0a422658 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-09-23T18:31:58Z (GMT) No. of bitstreams: 1 tese_pedro.pdf: 954527 bytes, checksum: e9834fab8c799933912f185f0a422658 (MD5) / Made available in DSpace on 2015-09-23T18:32:21Z (GMT). No. of bitstreams: 1 tese_pedro.pdf: 954527 bytes, checksum: e9834fab8c799933912f185f0a422658 (MD5) Previous issue date: 2015-04-22 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Optimization algorithms are known to have a wide range of applications in various areas of knowledge. Thus, any improvement in the performance of optimization algorithms generate great impact in solving various problems. Thus, this work indroduces the area of quantum algorithms for global optimization (maximization/minimization) of continuous functions through different quantum search methods and classical local optimization algorithms. In this case, the use of search quantum algorithms is tied directly to performance with respect to the classical method: using a quantum computer can find an element in an unsorted database using only $O(\sqrt{N})$ queries. / Algoritmos de otimização são conhecidos por apresentarem uma vasta gama de aplicações em diversas áreas do conhecimento. Desta forma, qualquer melhoria no desempenho dos algoritmos de otimização gera grande impacto na resolução de diversos problemas. Neste sentido, este trabalho introduz a área de algoritmos quânticos para a otimização global (maximização/minimização) de funções contínuas através de diferentes métodos quânticos de busca e algoritmos clássicos de otimização local. Neste caso, a utilização de algoritmos quânticos de busca está diretamente associada ao desempenho com relação ao método clássico: usando um computador quântico pode-se encontrar um elemento em um banco de dados não-ordenado usando apenas $O(\sqrt{N})$ consultas.

String diagrams turn algebraic equations into topological moves that have recurring shapes, involving the sliding of one diagram past another. We individuate, at the root of this fact, the dual nature of polygraphs as presentations of higher algebraic theories, and as combinatorial descriptions of "directed spaces". Operations of polygraphs modelled on operations of topological spaces are used as the foundation of a compositional universal algebra, where sliding moves arise from tensor products of polygraphs. We reconstruct several higher algebraic theories in this framework. In this regard, the standard formalism of polygraphs has some technical problems. We propose a notion of regular polygraph, barring cell boundaries that are not homeomorphic to a disk of the appropriate dimension. We define a category of non-degenerate shapes, and show how to calculate their tensor products. Then, we introduce a notion of weak unit to recover weakly degenerate boundaries in low dimensions, and prove that the existence of weak units is equivalent to a representability property. We then turn to applications of diagrammatic algebra to quantum theory. We re-evaluate the category of Hilbert spaces from the perspective of categorical universal algebra, which leads to a bicategorical refinement. Then, we focus on the axiomatics of fragments of quantum theory, and present the ZW calculus, the first complete diagrammatic axiomatisation of the theory of qubits. The ZW calculus has several advantages over ZX calculi, including a computationally meaningful normal form, and a fragment whose diagrams can be read as setups of fermionic oscillators. Moreover, its generators reflect an operational classification of entangled states of 3 qubits. We conclude with generalisations of the ZW calculus to higher-dimensional systems, including the definition of a universal set of generators in each dimension.

The decline of Moore's law has catalyzed a significant effort to identify beyond-CMOS devices and architectures for the coming decades. A multitude of classical and quantum systems have been proposed to address this challenge, and spintronics has emerged as a promising approach for these post-Moore systems. Many of these architectures are tailored specifically for applications in combinatorial optimization and machine learning. Here we propose the use of spintronics for such applications by exploring two distinct but related computing paradigms. First, the use of spin-currents to manipulate and control quantum information is investigated with demonstrated high-fidelity gate operation. This control is accomplished through repeated entanglement and measurement of a stationary qubit with a flying-spin through spin-torque like effects. Secondly, by transitioning from single-spin quantum bits to larger spin ensembles, we then explore the use of stochastic nanomagnets to realize a probabilistic system that is intrinsically governed by Boltzmann statistics. The nanomagnets explore the search space at rapid speeds and can be used in a wide-range of applications including optimization and quantum emulation by encoding the solution to a given problem as the ground state of the equivalent Boltzmann machine. These applications are demonstrated through hardware emulation using an all-digital autonomous probabilistic circuit.

<p>The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated.</p><p>Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can.</p><p>Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N^3/2 , where N is the list length. We consider success probabilities p<1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit.</p><p>Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances. </p>

The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated. Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can. Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N3/2 , where N is the list length. We consider success probabilities p&lt;1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit. Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use. The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e &lt; d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm. The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution. Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

This thesis aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grovers algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grovers algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.