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]:
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]:
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])
In [ ]:
In [ ]: