Authors:

Autores

Person role Person
6849
3058,753,2733
6850
3058,753,2733
6851
3058,753,2733

Informations:

Pesc publication

Title
Characterizing the Inherent Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks on Finite Graphs
Research area
Computer Networks
Publication type
Master's thesis
Identification Number
Date
8/6/2020
Resumo

Passeios quânticos em grafos são ubíquos na Computação Quântica, possuindo uma miríade de aplicações importantes. De forma similar, passeios aleatórios em grafos são fundamentais na descrição de muitos algoritmos com diversas aplicações. Ainda que a relação entre passeios quânticos e passeios aleatórios tenha sido explorada em trabalhos recentes, esta dissertação estabelece uma equivalência entre os dois passeios em grafos finitos, sobre condições gerais dos operadores quânticos e do passeio aleatório. Tal equivalência demanda empoderar passeios aleatórios com heterogeneidade no tempo, de forma que as probabilidades de transição sejam não-uniformes e dependam do instante de tempo. Essa equivalência é obtida ao se igualar, a cada instante e para todos os vértices do grafo, a probabilidade do caminhante clássico estar no vértice com a probabilidade desse mesmo vértice ser resultado da medição do passeio quântico. O resultado apresentado possui duas vertentes similares. A primeira aparece sob a forma de um procedimento para construir a sequência de matrizes estocásticas capaz de gerar um passeio aleatório com a mesma evolução de probabilidade de um dado passeio quântico qualquer, incluindo o cenário de múltiplos caminhantes quânticos que interagem entre si. A segunda vertente apresenta um procedimento na direção oposta, partindo de um aleatório e construindo um passeio quântico equivalente. Nesse contexto, a sequência de matrizes obtida pelo primeiro procedimento permite uma abordagem inédita para a simulação de passeios quânticos onde as amostras da posição do caminhante respeitam a vizinhança dos vértices dando origens a trajetórias quânticas. A convergência da simulação é garantida através da lei dos grandes números, permitindo a amostragem eficiente (em tempo polinomial) de trajetórias quânticas do grafo. Em complemento, a complexidade computacional do procedimento de construção dessas matrizes é discutida para o caso geral.

Abstract

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

JSN_TPLFW_GOTO_TOP