Matrizes para caminhadas quânticas em grafos regulares

por Franklin Marquezino -- franklin@cos.ufrj.br

Nesse arquivo vou descrever as matrizes que serão necessárias para nossa simulação. Primeiramente, temos que importar algumas bibliotecas do Python. Estou usando o Python 3, mas creio que tudo (ou quase tudo) deve funcionar também no Python 2. Talvez você precise instalar as bibliotecas Networkx, Matplotlib, Numpy, entre outras. Geralmente, isso é feito no Ubunto por meio do comando 'sudo apt-get install python-biblioteca', ou 'sudo apt-get install python3-biblioteca', ou algo parecido.


In [1]:
import numpy as np

In [2]:
import networkx as nw

In [3]:
import matplotlib.pyplot as plt

In [4]:
# esse comando é só para o matplotlib plotar diretamente dentro da linha de comando do ipython notebook
%matplotlib inline

In [5]:
# por enquanto, escolha sempre um grau par, ou seja, da forma 2*d
degree = 2*2

In [6]:
# por enquanto, escolha sempre um tamanho de grafo da forma n**2, pois estamos trabalhando com a malha 2D.
# Depois, quando generalizarmos, vamos poder deixar de lado essa restrição.
size = 5**2

In [28]:
# também é possível ler o grafo a partir de um arquivo que represente uma matriz de adjacencias.
graph = nw.grid_2d_graph(int(np.sqrt(size)),int(np.sqrt(size)), periodic=False)

In [29]:
graph = nw.convert_node_labels_to_integers(graph)

In [30]:
nw.draw_spectral(graph)


O comando abaixo apenas define um estado auxiliar, que é uma superposição uniforme dos estados da base do espaço-moeda. Será útil na hora de definir a moeda de Grover.


In [10]:
diagState = (1/np.sqrt(degree))*np.ones(degree).T; diagState


Out[10]:
array([ 0.5,  0.5,  0.5,  0.5])

Agora sim, definimos a matriz de Grover. Veja a definição na minha tese de doutorado. A vantagem da moeda de Grover, no nosso caso, é que pode ser aplicada a qualquer dimensão, diferentemente de outras moedas, como Fourier ou Hadamard. Além disso, ela é muito importante em algoritmos de busca.


In [11]:
groverCoin = 2*np.outer(diagState, diagState) - np.eye(degree); groverCoin


Out[11]:
array([[-0.5,  0.5,  0.5,  0.5],
       [ 0.5, -0.5,  0.5,  0.5],
       [ 0.5,  0.5, -0.5,  0.5],
       [ 0.5,  0.5,  0.5, -0.5]])

A matriz anterior atua somente no espaço moeda. Para termos o operador moeda que atua no espaço composto, ainda precisamos fazer o produto tensorial (a.k.a., produto de Kronecker) com o operador identidade que atua no espaço posição. Faremos isso a seguir:


In [12]:
Coin = np.kron(groverCoin, np.eye(size))

Agora vamos definir o operador deslocamento. Ele deve ter a forma $$|\Psi \rangle = \sum_{i=0}^{\mbox{size}-1} |c\rangle \langle c| \otimes | x+c \rangle \langle x |,$$ em que $x+c$ denota o vértice que é conectado a $x$ por meio da aresta $c$.


In [13]:
Shift = np.zeros((degree*size, degree*size))

In [36]:
for x in graph.nodes_iter():
    
    #esse if é só um truque para desconsiderar as bordas, pois elas tem grau diferente.
    if nw.degree(graph, nbunch=x) < 4:
        print(x)
        continue
        
    for c in range(degree):
        neigh = graph.neighbors(x)
        print('x=', x, ' n=', neigh[c])


x= 0  n= 24
x= 0  n= 19
x= 0  n= 22
x= 0  n= 6
x= 1  n= 17
x= 1  n= 10
x= 1  n= 22
x= 1  n= 15
2
3
4
5
x= 6  n= 0
x= 6  n= 12
x= 6  n= 5
x= 6  n= 7
x= 7  n= 9
x= 7  n= 22
x= 7  n= 6
x= 7  n= 15
x= 8  n= 24
x= 8  n= 17
x= 8  n= 20
x= 8  n= 22
9
10
11
12
13
14
x= 15  n= 1
x= 15  n= 23
x= 15  n= 21
x= 15  n= 7
16
x= 17  n= 8
x= 17  n= 1
x= 17  n= 3
x= 17  n= 16
18
19
20
21
x= 22  n= 0
x= 22  n= 1
x= 22  n= 8
x= 22  n= 7
23
x= 24  n= 0
x= 24  n= 8
x= 24  n= 11
x= 24  n= 14

In [ ]:


In [ ]: