Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/60233
Type: | Dissertação |
Title: | Exploring quantum walks: weighted paths and quotient graphs unveiled |
Authors: | Frederico Cançado Pereira |
First Advisor: | Gabriel de Morais Coutinho |
First Co-advisor: | Thomás Jung Spier |
First Referee: | Aldo Procacci |
Second Referee: | Balchandra Digambar Thatte |
Abstract: | This thesis explores the problem of Perfect State Transfer (PST) in graphs, which has significant implications in quantum computing. The goal is to determine which graphs allow for perfect transfer of the state of one qubit (or vertex) to another qubit within a certain time frame. The text provides an introduction to the topic using techniques from linear algebra, discussing necessary and sufficient conditions to achieve PST, and emphasizing long-distance transfer between qubits. The optimization objective is to minimize the number of quantum components required to achieve perfect state transfer. An important class of graphs that admit PST is weighted paths. For PST between vertices at the endpoints, the problem has been completely solved by exploring the connection of these graphs with orthogonal polynomials. However, the problem becomes considerably more complex for vertices in other positions, leading to new results and connections explored in this document. Among these results, we can mention a formula that uniquely relates the extreme polynomial to another arbitrary polynomial in a sequence of orthogonal polynomials, how to create a sequence of orthogonal polynomials containing two given polynomials, and how PST in weighted paths relates to the Prouhet-Tarry-Escott problem, an open problem in number theory. Finally, the document presents an approach to constructing graphs with PST, exploring weighted paths and equitable partitions. New theorems in this are also presented, which have general relevance to graph theory. These theorems include a criterion for two graphs to have a common symmetrized quotient, how equitable partition matrices relate to projective matrices, and how the set of equitable partitions transforms when the original graph is quotiented. |
Abstract: | 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. |
Subject: | Matemática – Teses Teoria dos grafos – Teses Teoria espectral (Matemática) - Teses Polinômios ortogonais - Teses Computação quântica – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE MATEMÁTICA |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Matemática |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/60233 |
Issue Date: | 9-Aug-2023 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis (8).pdf | 3.53 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.