In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.

Thesis (Ph.D.) - Carleton University, 2005. / Includes bibliographical references (p. 168-173). Also available in electronic format on the Internet.

Thèse (M.Eng.) -- Université du Québec à Chicoutimi, 2004. / Bibliogr.: f. [70]-76. Document électronique également accessible en format PDF. CaQCU

Thesis (Ph. D.)--University of Missouri-Columbia, 2002. / Typescript. Vita. Includes bibliographical references (leaves 79-81). Also available on the Internet.

The theme of my diploma thesis is: "Natural Science walks and excursions - the current state and their implementation at the second stage of elementary school." It has two basic parts. The first part defines the different approaches of different authors to the main topic, ie. the conception of walks and excursions and it is associated with major subtopics. The second part involves self-evaluation of realized draft of Natural Science walks. It is based on an analysis of surveys that were used for collecting of data. I drew from the study of specialized literature, Natural Science textbooks for second stage of elementary school, and selected substrates from Elementary school Horažďovice.

L’Internet a complètement révolutionné la façon dont nous communiquons. En parallèle, la croissance importante des réseaux mobiles s'est accompagnée d'une explosion du nombre d’usagers et d'une augmentation exponentielle de la demande. Cependant, l’Internet n'est pas encore, voire n'est pas toujours, universellement accessible. Par exemple, c'est le cas en ce qui concerne l’accès dans les économies émergentes ou dans les régions éloignées, les obstacles physiques empêchant le déploiement de réseaux mobiles et les désastres naturels. C'est dans ce contexte que les réseaux tolérants au délai ont été introduits pour faire face aux environnements caractérisés par des interruptions et des délais de transmission élevés. Ces réseaux, manquent souvent de routes pré-déterminées ou même de toute infrastructure pour permettre une communication de bout-en-bout. Dans ce contexte, tous les nœuds de ces réseaux peuvent interagir en utilisant leurs contacts comme une opportunité de communication. Le paradigme stockage/transport permet à ces nœuds d’exploiter des chemins spatio-temporels créés par ces possibilités de contact afin de livrer des messages au fil du temps. Dans ce travail, nous soulevons ici une question générique : pouvons-nous concevoir une infrastructure mobile et opportuniste qui pourrait aider à transmettre ces messages ? Afin de fournir une telle infrastructure, nous étudions l’application des marches aléatoires temporelles (TRWs) dans réseaux opportunistes. Nous explorons l’application et l’impact de la TRW pour fournir une infrastructure minimale et non-invasive à partir de deux points de vue : le stockage des données et leur transmission. / The Internet has entirely reshaped the way we communicate and interact with one another. The rapid development of the wireless infrastructure by network providers has being accompanied by an exponential growth in the number of mobile users. However, global Internet access and connectivity still face several challenges: scarce or poor quality connectivity in developing countries or places with limited accessibility, physical obstacles limiting the deployment of wireless networks and natural or man-made disasters. Delay tolerant networks (DTNs) were introduced to deal with environments where interruptions or disruptions of service were expected. Such networks usually lack of end-to-end paths or any infrastructure to help communications. In these networks, mobile nodes may interact using their contacts as a communication opportunity. The store-carry-forward paradigm allows nodes to exploit spatio-temporal paths created by contact opportunities in order to deliver messages over time. Instead we raise the question: can we design a mobile and opportunistic infrastructure that could help deliver messages? In the quest to provide such infrastructure, we study the application of temporal random walks (TRW) over the opportunistic networks. We explore the application and impact of TRW as a minimal and non invasive infrastructure from two points of view: data forwarding and data recollection/transmission.

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. / 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.

This dissertation is oriented on how to use interests of my region in our schools. It contents elaboration of naturally orientated topics for teaching at the first grade. This work should be mainly used for pupil 4 and 5 class. Its part are two excursions, two walks and two lessons. For the planned activities are prepared worksheets with exercises.

Propomos o estudo do meio desordenado onde a caminhada determinista parcialmente autorrepulsiva (CDPA) é desenvolvida e o estudo da caminhada aleatória autorrepulsiva (SAW) em rede regular. O meio desordenado na CDPA, gerado por um processo Poissônico espacial, é caracterizado pela estatística de vizinhança e de distâncias. A estatística de vizinhança mede a probabilidade de um ponto ser $m$-ésimo vizinho mais próximo de seu $n$-ésimo vizinho mais próximo. A estatística de distâncias mede a distribuição de distância de um ponto ao seu $k$-ésimo vizinho mais próximo. No problema da estatística de distâncias, calculamos a função densidade de probabilidade (pdf) e estudamos os casos limites de alta ordem de vizinhança e alta dimensionalidade. Um caso particular dessa pdf pode verificar se um conjunto de pontos foi gerado por um processo Poissônico. Na SAW em rede regular, um caminhante escolhe aleatoriamente um sítio adjacente para ser visitado no próximo passo, mas é proibido visitar um sítio duas ou mais vezes. Desenvolvemos uma nova abordagem para estudar grandezas conformacionais por meio do produto escalar entre o vetor posição e vetor deslocamento no $j$-ésimo passo: $\\langle\\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}$. Mostramos que para $j=N$ o produto escalar é igual ao comprimento de persistência (projeção do vetor posição na direção do primeiro passo) e que converge para uma constante. Calculamos a distância quadrática média ponta-a-ponta, $\\langle \\vec{R}_{N}^{2}angle_{N}\\sim N^{2 u_{0}}$, como o somatório de $1\\leq j \\leq N$ do produto escalar. Os dados gerados pelo algoritmo de simulação Monte Carlo, codificado em linguagem C e paralelizado em MPI, fornecem o expoente $ u_{0}$ da regra de escala $\\langle \\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}\\sim j^{2 u_{0}-1}$, para $1\\leq j \\leq \\Theta(N)$, próximo ao valor esperado. A partir de $\\Theta(N)\\approx N/2$ para rede quadrada e $\\Theta(N)\\approx N/3$ para rede cúbica, a caminhada torna-se mais flexível devido ao maior número de graus de liberdade disponível nos últimos passos. / We propose the study of disordered media where the deterministic partially self-avoiding walk (DPSW) is developed and the study of self-avoiding random walk (SAW) in regular lattices. The disordered media in the DPSW, generated by a spatial Poissonian process, is characterized by neighborhood and distance statistics. Neighborhood statistics quantifies the probability of a point to be the $m$th nearest neighbor of its $n$th nearest neighbor. Distance statistics quantifies the distance distribution of a given point to its $k$th nearest neighbor. For the distance statistics problem, we obtain the probability density function (pdf) and study the high dimensionality and high neighborhood order limits. A particular case of this pdf can verify if a points set is generated by a Poissonian process. In a SAW in regular lattice, the walker randomly chooses an adjacent site to be visited in the next step, but is forbidden to visit a site two or more times. We developed a new approach to study conformational quantities of SAW by means of the scalar product between the position vector and the displacement vector in the $j$th step: $\\langle\\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}$. We show that for $j=N$ the scalar product is equal to the persistence length (projection of position vector in the direction of the first step) and that converges to a constant. We compute the square end-to-end distance, $\\langle \\vec{R}_{N}^{2}angle_{N}\\sim N^{2 u_{0}}$, as the summation $1\\leq j \\leq N$ of scalar product. The data generated by Monte Carlo simulation algorithm, coded in C language and parallelized in MPI, provides the exponent $ u_{0}$ of the scaling law $\\langle \\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}\\sim j^{2 u_{0}-1}$, for $1\\leq j \\leq \\Theta(N)$, close to the expected value. Starting from $\\Theta(N)\\approx N/2$ for square lattice and $\\Theta(N)\\approx N/3$ for cubic lattice, the walk becomes more flexible due to the large number of degrees of freedom available in the last steps.

Orientadores: Christophe Frédéric Gallesco, Serguei Popov / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-22T17:31:03Z (GMT). No. of bitstreams: 1 VasquezMercedes_ClaudiaEdith_M.pdf: 743991 bytes, checksum: 587d04d1b7b45c75dd5eeea766258b02 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Mestrado / Estatistica / Mestra em Estatística