Operações Lógicas Quânticas

e

Colorabilidade de Grafos


João P. S. Schüler, Luis O. C. Alvares

Universidade Federal do Rio Grande do Sul, Instituto de Informática Bl. 4,

Porto Alegre – RS, CEP 90000, Brasil


RESUMO

Este artigo introduz noções de computação quântica tais como qubit, correlação e amplitude de probabilidade complexa. Além de introduzir aspectos físicos sobre computação quântica, o presente artigo propõe uma forma simples de implementação das operações lógicas AND e OR com base na operação lógica CNot usando exemplos escritos em QCL. Por fim, é apresentado um algoritmo para computadores quânticos para testar se um grafo é 3-colorível.


Palavras chaves: algoritmos, arquiteturas de computadores, computação quântica, QCL, coloração de grafos.



ABSTRACT

This paper introduces notions of quantum computing such as qubit, quantum entanglement and complex probability amplitudes. Further on introducing physical aspects about quantum computing, the present paper proposes a simple manner of implementing the logic operations AND and OR based on the logic operation CNot using exemples in QCL language. It is also presented a way to test if a graph is 3-colorable on a quantum computer.


Keywords: algorithms, computer architecture, quantum computing, QCL, graph coloring.


1 INTRODUÇÃO

Fazendo uso da física quântica, a computação quântica abre possibilidade para resolver problemas extremamente custosos em termos de tempo de CPU de forma extremamente rápida [4] [5] [6] [7] [13] ; porém, a tecnologia para o desenvolvimento de computadores quânticos não está desenvolvida. Especula-se que os primeiros computadores quânticos serão produzidos em 20 anos [14]. Sendo assim, nesse artigo, usa-se simulação para apresentar operações lógicas quânticas.

O pacote de simulação escolhido é o QCL (Quantum Computer Language) [9] [10] que compreende uma máquina virtual e uma linguagem de programação. Na versão 0.4 da linguagem QCL, não existe nem mesmo a operação lógica quântica OR implementada e pronta para uso. Dificilmente profissionais da área de computação desenvolvem interesse por uma linguagem de programação ou um sistema computacional que não dispõe nem mesmo de operações lógicas do tipo AND ou OR. Para resolver esse problema, o presente artigo apresenta uma forma simples de realizar operações lógicas em computadores quânticos.

No presente artigo, as seções 2 e 3 introduzem respectivamente a computação quântica e a linguagem QCL. As seções 4 e 5 apresentam formas de realizar algumas operações lógicas em QCL. Por fim, a seção 6 apresenta um algoritmo para testar se um grafo é 3-colorível.

2 COMPUTAÇÃO QUÂNTICA

Os computadores existem físicamente no espaço e no tempo. Os computadores fazem o que a física permite. O estado de cada bit de nossos computadores corresponde a um estado físico. Tendo entendido o comportamento dos estados quânticos, pretende-se entender melhor computadores que processam bits quânticos.

Entender a amplitude de probabilidade complexa é importante para entender como um computador quântico representa informação. A amplitude de probabilidade do estado de uma partícula quântica é um número complexo. A probabilidade no nível clássico é o quadrado do módulo da amplitude de probabilidade[12]. Vale lembrar que o módulo do número complexo z=x+iy é |z|=. Para efeito de exemplo, pode-se calcular sobre uma partícula que possui amplitude de probabilidade para o estado K com valor de 0.3 + 0.4i ou (0.3 + 0.4i)|K> :

      1. o módulo da amplitude de probabilidade é:

      2. o quadrado do módulo da amplitude de probabilidade é 0.25. Isso significa que a partícula em medição possui uma probabilidade de ser medida no estado K de 0.25.

Assim como no nível clássico, onde o somatório das probabilidades não pode ultrapassar 1, em um sistema quântico, o somatório dos quadrados dos módulos das amplitudes de probabilidades não pode ultrapassar 1. Módulos de amplitudes de probabilidade são sempre positivos; porém, amplitudes de probabilidade podem ser negativas.

Um bit clássico pode estar somente em um de dois estados básicos mutuamente exclusivos. Ao contrário, um bit quântico pode estar em uma superposição de estados básicos. Descreve-se o estado do spin do elétron na forma como segue: Z|0> + W|1> que deve ser entendido como superposição linear dos autoestados zero e um com amplitudes de probabilidade Z e W respectivamente. Vale observar que |Z|² + |W|² = 1. O estado de um bit quântico é a superposição linear de seus autoestados.

O estado de um conjunto de dois bits quânticos pode ser descrito pela seguinte superposição linear de autoestados: x|00> + y|01> + z|10> + w|11> em que |x|² + |y|² + |z|² + |w|² =1 e x,y,z,w são amplitudes de probabilidade complexas. Bits quânticos são chamados de qubits. Um conjunto de N qubits pode apresentar um estado que é superposição linear de 2N autoestados. De certa forma, um conjunto de N qubits pode estar em 2N estados diferentes ao mesmo tempo.

O estado dos bits de uma máquina clássica ou quântica deve ter uma correspondência física. O spin de um elétron pode ser -1/2 ou +1/2. Sendo assim, o spin de um elétron pode ser descrito pela superposição de autoestados: c1|-1/2> + c2|+1/2 >. Substituindo-se -1/2 e +1/2 por 0 e 1 respectivamente, encontra-se: c1|0> + c2|1> sendo que c1 e c2 são amplitudes de probabilidade.

2.1 Notação

O bit quântico ou qubit é representado por um sistema quântico de dois estados que é constituído por apenas uma partícula. Um sistema quântico de dois estados é descrito por um vetor unitário complexo no espaço de Hilbert C2. O espaço de Hilbert é um espaço vetorial complexo. Os dois estados do sistema quântico são representados por: |0> e |1>. O estado |0> é representado pelo vetor complexo (1,0) em C2 enquanto que o estado |1> é representado pelo vetor (0,1). Os vetores (1,0) e (0,1) ou |0> e |1> constituem a base ortogonal no espaço de Hilbert[2].

Apenas para efeito de exemplo, aborda-se um registrador quântico de 3 qubits que é representado pela superposição linear de seus oito autoestados como segue:

c1|000> + c2|001> + c3|010> + c4|011> + c5|100> +c6|101> + c7|110> + c8|111>.

Para efeito de notação, considera-se: x1 = |000>, x2 = |001>, x3 = |010> ... x8 = |111>. Lembrando que c1..c8 são amplitudes de probabilidade, = 1 . O estado de um registrador quântico de n qubits é a superposição linear de 2n autoestados. Uma superposição uniforme de autoestados é uma superposição linear de estados onde todos os autoestados apresentam a mesma amplitude de probabilidade. A superposição uniforme de autoestados pode ser descrita como:


Uma operação f feita sobre um registrador quântico que apresenta superposição uniforme de autoestados pode ser descrita como:



Apenas para efeito de exemplo, apresenta-se a operação de incremento f:

f (c1 |000> + c2|001> + c3|101>) => c1 |001> + c2 |010> + c3 |110> .

No exemplo anterior, de certa forma, foram feitos três incrementos em paralelo usando apenas um único registrador quântico de três qubits.

Por fim, aborda-se um exemplo com o operador de negação NOT [2]:

NOT |0> = |1>

NOT |1> = |0>

NOT( c1|0> + c2|1> ) = c1|1> + c2|0>

NOT( c1|001> + c2|111> ) = c1|110> + c2|000>

2.2 Correlação

A correlação ( do inglês, entanglement ) de estados surge naturalmente da interação entre partículas. No presente parágrafo, supõe-se que o estado inicial de duas partículas correlacionadas é o que segue: c1|00> + c2|11>. Supondo-se ainda que resulta da medição da primeira partícula o estado |0>, por estarem correlacionadas as duas partículas, o vetor de estados do sistema composto pelas duas partículas entra em colapso caindo no estado |00> com a medição da primeira partícula. Sendo assim, a medição sobre uma partícula de um sistema de partículas correlacionadas provoca o colapso do vetor de estados de todo o sistema de partículas imediatamente mesmo que as partículas estejam separadas espacialmente.

Considerando o exemplo do parágrafo anterior, se, por acaso, a medição da primeira partícula resultasse em |1>, então o estado da segunda cairia obrigatoriamente no estado |1>. A segunda partícula simplesmente não poderia ser fisicamente medida no estado |0> tendo em vista que não existe um estado c3|10> inicial.

A informação quântica é extremamente frágil. É impossível impedir interações entre um sistema quântico e o ambiente em que está inserido. Essa interação provoca perda na natureza quântica em um processo chamado de decoerência [2]. Para manter a computação coerente, é necessário isolar os registradores quânticos impedindo que eles se correlacionem com o ambiente [9]. A decoerência é uma questão de tempo entre outros fatores. Quanto maior for o tempo envolvido, maiores serão as chances de verificarmos decoerência.

Para manter a computação coerente, os registradores quânticos não podem dissipar calor. A dissipação de calor provocaria a correlação entre o registrador quântico e o ambiente causando decoerência. Sendo assim, a entropia do sistema de computação quântica não pode crescer. Lembrando que a entropia é incrementada nos processos irreversíveis, a computação quântica é reversível e adiabática [9].

3 QUANTUM COMPUTING LANGUAGE

Por que simular computadores quânticos em máquinas convencionais? Simulando computadores quânticos pode-se ter uma idéia das dificuldades a serem enfrentadas no desenvolvimento de novos algoritmos destinados a computadores quânticos. É interessante observar que antes do primeiro computador quântico ser construído, estarão prontos diversos algoritmos específicos para computadores quânticos rodando em simulação. Além disso, através de simulações, obtém-se uma idéia muito aproximada do que pode ser esperado de computadores quânticos.

Em geral, vale a pena simular um sistema quando a simulação é imensamente menos custosa e ainda assim permite estudarmos os aspectos de interesse do sistema real. Esse é exatamente o motivo pelo qual trabalha-se com simuladores de máquinas quânticas.

Existem diversos pacotes para simulação de computadores quânticos, entre eles Open Qubit [11] e QCL. A maior desvantagem do Open Qubit frente ao QCL é a sua dificuldade de operação para os novatos tendo em vista que o Open Qubit é uma biblioteca C. Sendo assim, Open Qubit exige muito de seu usuário para implementar seus primeiros programas simples. Por ser interpretada, a linguagem QCL permite que seu usuário entre com comandos e funções de forma iterativa e ainda verifique o estado de cada registrador da máquina virtual. O QCL é ideal para o ensino de linguagem de programação de computador quântico. Na internet, pode-se encontrar os códigos fontes do QCL e excelente bibliografia [9] [10] .

O QCL prevê uma máquina híbrida composta por uma máquina clássica semelhante aos bem conhecidos PCs e uma máquina de estados quânticos. O usuário se comunica somente com a máquina clássica. A máquina clássica requisita operações e medições à máquina de estados quânticos. Traçando uma analogia, os PCs modernos possuem unidades de ponto flutuante (UPF) integradas à CPU. Os comandos de salto e controle não pertencem a UPF. A UPF apenas realiza as instruções relativas as operações de ponto flutuante. Da mesma forma, o QCL prevê uma máquina clássica que realiza os testes, desvios, E/S e possui registradores convencionais em contato com uma máquina de estados quânticos que realiza as operações quânticas.

Para efeito de exemplo, considera-se o programa QCL que segue:

int Teste() {

  int i; // Aloca uma variável inteira na máquina clássica.

  int d; // Aloca uma variável inteira na máquina clássica.

  qureg x[2]; // Aloca um registrador quântico de dois bits na máquina quântica.

  Mix(x); // Força a superposição linear uniforme de

  // autoestados no registrador quântico x.

  for i=1 to 5 { // O controle do laço é feito na máquina clássica.

    Not(x); } // Nega o conteúdo do registrador quântico x na máquina quântica.

  measure x,d; // Mede o valor na máquina quântica do registrador

  // x e envia o resultado a máquina clássica.

  // Na máquina clássica, armazena o valor recebido em d.

  return d;} // Retorna o valor da variável d da máquina clássica.


No exemplo acima, observa-se que os comandos destinados a máquina clássica e a máquina quântica aparecem intercalados. A função Teste nega cinco vezes o conteúdo do registrador quântico x. Isso foi feito apenas para mostrar que o controle de laço é executado na máquina clássica enquanto que as operações quânticas são executadas na máquina quântica.

4 OPERAÇÕES LÓGICAS AND, NAND, OR, NOR EM QCL

A linguagem QCL oferece apenas os operadores lógicos quânticos Not e CNot. Como a maioria dos programadores estão habituados a utilizar os operadores AND e OR, mostra-se a seguir uma forma de realizar estas operações.

Para carregar o programa, digita-se a linha de comando que segue:

wind:~/qcl-0.4.0-bin$ qcl-static --bits=4

[0/4] 1 |0000>

qcl>

A opção -bits=4 especifica uma máquina que possui quatro qubits no total. A mensagem [0/4] significa que zero dos quatro qubits foram alocados. Ao lado, 1|0000> significa que o autoestado da máquina |0000> apresenta amplitude de probabilidade um. O prompt qcl> indica que já pode-se entrar com novos comandos. No próximo passo, aloca-se um registrador quântico de dois qubits.


qcl> qureg x[2]

qcl> dump

: STATE: 2 / 4 qubits allocated, 2 / 4 qubits free

1 |0000>


O comando qureg x[2] aloca o registrador x com dois qubits. O comando dump devolve o estado da máquina. Como pode ser observado na saída do comando dump, 2 / 4 ou dois dos quatro qubits estão alocados e os outros 2 / 4 ou dois dos quatro qubits estão livres. Por fim, observa-se que a máquina continua no estado 1|0000>. No próximo passo, trabalha-se com registradores quânticos:


qcl> Mix(x)

[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>


Os dois qubits mais a direita de cada autoestado correspondem aos dois qubits do registrador x. O comando Mix força a superposição linear uniforme de autoestados no registrador que é passado como argumento quando este está no estado em que todos os qubits estão em zero. Observa-se que todos os autoestados apresentam 0.5 como amplitude de probabilidade. Lembrando que a probabilidade de medição de um autoestado é o módulo quadrado de sua amplitude de probabilidade, a probabilidade de cada um dos quatro autoestados é |0.5|2 = 0.25. No próximo passo, aloca-se mais um registrador.


qcl> qureg y[1]

qcl> dump

: STATE: 3 / 4 qubits allocated, 1 / 4 qubits free

0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>


O comando qureg y[1] aloca o registrador quântico y com 1 qubit. O comando dump revela que três dos quatro bits quânticos estão alocados. Os dois qubits mais a direita de cada autoestado correspondem aos dois qubits do registrador x e o terceiro bit da direita para esquerda é o registrador y. No próximo passo, executa-se uma operação lógica.


qcl> CNot(y,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0111>


O comando CNot(y,x) nega os autoestados y correspondentes aos autoestados em que x possui seus bits todos em 1. O comando CNot é um comando de negação controlada. A semântica do comando CNot é baseada na semântica da porta lógica quântica proposta por Toffoli [3] chamada de Controlled Not ou simplesmente CNot. Se é possível garantir que o registrador y começa em zero, CNot apresenta a mesma semântica da porta lógica AND em que y é a saída e x é a entrada. No exemplo anterior, foram feitas quatro operações em paralelo. Para facilitar o entendimento, os bits referentes ao registrador y foram grafados em negrito. Ao negar-se o resultado encontrado em y, encontra-se o resultado da operação x[0] NAND x[1] em y:


qcl> Not(y)

[3/4] 0.5 |0100> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>


Novamente, os bits referentes ao registrador y foram grafados em negrito. A importância do exemplo anterior deve-se ao fato de que qualquer função lógica pode ser descrita como uma composição de NANDs.

Negando-se o registrador x, encontra-se x[1] OR x[2] em y:

qcl> Not(x)

[3/4] 0.5 |0111> + 0.5 |0101> + 0.5 |0110> + 0.5 |0000>


Negando-se o registrador y, encontra-se x[1] NOR x[2] em y:


qcl> Not(y)

[3/4] 0.5 |0011> + 0.5 |0001> + 0.5 |0010> + 0.5 |0100>

No passo seguinte, declara-se uma variável inteira d para medir o estado de x. Vale lembrar que somente um autoestado sobrevive após a medição.


qcl> int d

qcl> measure x,d

[3/4] 1 |0011>

qcl> print d

: 3


O comando measure x,d mede x e carrega a variável d com o valor medido. O valor do autoestado de x que é medido depende da probabilidade de cada autoestado. Se x estiver em superposição linear uniforme de autoestados, cada autoestado tem a mesma probabilidade de ser encontrado. Sendo assim, pode-se encontrar 0,1,2 ou 3 com a mesma probabilidade. No exemplo anterior, o autoestado medido foi |11>; porém, qualquer outro autoestado de x poderia ter sido medido com a mesma probabilidade.

5 CÓPIA, XOR e IGUALDADE em QCL

Além das operações quânticas vistas na seção anterior, existem outras operações de interesse. Esta seção apresenta uma forma de realizar as operações quânticas de cópia, teste de igualdade e XOR em QCL. Para tanto, segue-se o experimento:

Aloca-se os registradores quânticos.

qcl> qureg x[1]

qcl> qureg y[1]

qcl> qureg z[1]


Com os três comandos acima, foram alocados os registradores quânticos x,y e z com um qubit cada. No próximo passo, a superposição linear uniforme de autoestados para todas as combinações possíveis de x e y é forçada.


qcl> Mix(x&y)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>


Cada autoestado acima tem a seguinte notação: |0zyx>. Conforme mostra a tabela que segue, o comando CNot pode ser usado para copiar o conteúdo de x em z.





TABELA 1 – Usando o comando CNot para cópia.

X

Y

X e Y após CNot(X,Y)

0

0

0 0

0

1

1 1



Para copiar o conteúdo de x em z, é usado o comando CNot(z,x):

qcl> CNot(z,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>

Os bits referentes a z e x foram grifados em negrito. Supondo que x e y sejam registradores quânticos unários, a operação lógica CNot(x,y) é idêntica à operação x:= x xor y. Esta propriedade pode ser observada na tabela que segue.


TABELA 2 – Usando o CNot como operação XOR.

X

Y

X e Y após CNot(X,Y)

X xor Y

0

0

0 0

0

0

1

1 1

1

1

0

1 0

1

1

1

0 1

0


Sendo assim, o comando que segue concluirá o exemplo.

qcl> CNot(z,y)

[3/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>


O conteúdo de z foi grifado em negrito. Pode-se verificar que z = x xor y.

Por si só, a operação lógica xor é um teste que retorna 1 quando seus operandos são diferentes. Sendo assim, a operação lógica xor é um teste de diferença. Para testar se dois operandos são iguais, opera-se z = not ( x xor y ). Apenas por experiência, segue a seqüência de comandos QCL para encontrar z = not ( x xor y ):

qcl> qureg x[1]

qcl> qureg y[1]

qcl> qureg z[1]

qcl> Mix(x&y)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>

qcl> CNot(z,x)

[3/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>

qcl> CNot(z,y)

[3/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>

qcl> Not(z)

[3/4] 0.5 |0100> + 0.5 |0010> + 0.5 |0001> + 0.5 |0111>


Por conveniência, o conteúdo de z foi grifado em negrito. Observa-se que z está no estado 1 quando x e y são iguais.

Pode-se observar que ausência de funções do tipo AND e OR dificulta a programação de funções lógicas em QCL. Por esse motivo, foi implementada a biblioteca boolean.qcl que possui as funções quAnd, quNand, quOr e quNor entre outras. Essa biblioteca pode ser encontrada em http://www.schulers.com/jpss.

6 ALGORITMO PARA DECIDIR SE UM GRAFO É 3-COLORÍVEL EM MÁQUINA QUÂNTICA

Um grafo é dito 3-colorível quando é possível colorir os vértices com apenas três cores de tal forma que dois vértices ligados por uma aresta não apresentem a mesma cor. Usando-se as técnicas discutidas nas seções anteriores, implementou-se um algoritmo para decidir se um grafo é 3-colorível inspirado no algoritmo de Leonard Adleman [1] que resolve esse problema np-completo em tempo polinomial usando computação biológica com DNA.

6.1 Estrutura de Dados

Dado um grafo G de arestas A1, A2 ,.., Az, seja:

n é o número de vértices;

z é o número de arestas;

S = {r1, g1, b1,r2, g2, b2, ..., rn, gn, bn} ;

a entrada do programa T em que

T = { |& = { c1, c2, ..., cn} & [ci = ri ou ci = bi ou ci = gi], i = 1,2, ..., n }

Apenas para efeito de exemplo, a palavra r1b2g3 representa a situação em que o vértice 1 é vermelho (r), o vértice 2 é azul (b) e o vértice 3 é verde (g). A entrada T contém todas as possíveis colorações para o grafo. Tem-se três cores para representar. Cada cor será representada por um autoestado de dois bits de acordo com a tabela que segue:

TABELA 3 – Cores e autoestados correspondentes

Cor

Autoestado

r

|00>

g

|01>

b

|10>

O registrador quântico T representa as cores dos vértices. A cor de cada vértice é representada por dois bits sendo que a cor do vértice i é representada por T[i*2] & T[i*2+1]. Supondo que |00100001> é autoestado de T, então esse autoestado representa um grafo em que o vértice 1 tem cor |10>; o vértice 2, cor |00> e o vértice 3, cor |01>. Os primeiros dois bits do autoestado não são usados.

O registrador ArestaInvalida é um vetor de qubits em que cada elemento de índice k-1 recebe o valor 1 quando a aresta de índice k liga vértices de mesma cor.

6.2 Implementação

A estratégia do algoritmo apresentado aqui é gerar todas as colorações possíveis para um determinado grafo e descartar as colorações inválidas. Esse algoritmo para decidir se um grafo é 3-colorível em máquina quântica pode ser implementado como segue:

  1. qureg T[n*2+2]; //n é o número de vértices;

  2. qureg CorInvalida[n+1]; //z é o número de arestas;

  3. qureg ArestaInvalida[z+1];

  4. qureg GrafoInvalido[1];

  5. Mix(T);

  6. int k;

  7. for k = 1 to z { // elimina as cores |11>

  8.   CNot(CorInvalida[k],T[K*2] & T[K*2+1]);

  9.   CNot(T[K*2],CorInvalida[k]);

  10.   CNot(T[K*2+1],CorInvalida[k]); }

  11. for k = 1 to z {

  12.   Let Ak = <i,j>;

  13.   // Compara se as cores dos vertices i e j são iguais.

  14.   quEqual(ArestaInvalida[k],T[i*2] & T[i*2+1],T[j*2] & T[j*2+1]);

  15.   !Let Ak = <i,j>; }

  16. quVectOr(GrafoInvalido[0], ArestaInvalida);



As linhas 14 e 16 chamam funções quânticas presentes na biblioteca boolean.qcl. O comando da linha 12 não pertence a linguagem QCL, mas pode ser implementado com base na tabela 1.

6.3 Explicação do Funcionamento

A linha 5 gera todas as colorações possíveis para o grafo em superposição linear uniforme de autoestados. O autoestado |11> não possui cor correspondente. Sendo assim, as linhas 7 a 10 transformam os autoestados |11> em autoestados |00> . O trecho principal do programa encontra-se da linha 11 a linha 15.

De forma simples, apenas para efeito de entendimento, as linhas 11 a 15 descrevem o algorítmo que segue:

for k = 1 to z. Let Ak = <i,j>:

Descarta entrada de T quando a cor

do vértice i é igual a cor do vértice j.


No algoritmo acima apresentado, o registrador quântico GrafoInvalido apresenta valor 1 quando o grafo a que está relacionado não é 3-colorível. A medição não foi implementada; porém, ela poderá ser feita com base no algoritmo de Grover[8].

O grafo é válido quando todas as arestas forem válidas. O autoestado |0> de GrafoInvalido está correlacionado ao autoestado de T que representa um grafo 3-colorível.

7 CONCLUSÃO

Introduziu-se sucintamente fundamentos de computação quântica e aspectos da linguagem QCL que possam interessar a profissionais da área de computação. Ainda que a maneira de programar um computador quântico seja bem diferente da maneira de programar um computador clássico, imagina-se que programadores que já programam computadores clássicos aprenderão a programar computadores quânticos despendendo relativamente pouco esforço.

Ao apresentar uma forma simples de implementar funções lógicas quânticas, espera-se que o presente trabalho ajude a popularizar a computação quântica. Espera-se que o presente trabalho sirva como fonte de inspiração para futuros programadores de computadores quânticos.

A forma convencional de programar baseia-se no desenvolvimento da solução manipulando-se a informação de entrada até obter-se a saída esperada. Em máquinas quânticas, a forma de programar mais comum é simplesmente gerar e testar todas as soluções possíveis em paralelo e selecionar a solução válida se ela existir. Na computação quântica, o trabalho do projetista de software é construir um conjunto de operações que verifica a validade de uma solução. Muitos algoritmos construidos para máquinas quânticas podem ser resumidos da forma que segue:

      1. Gerar todas as possíveis entradas.

      2. Selecionar a entrada que atenda a uma condição determinada.

De forma análoga, o algoritmo que testa se um grafo é 3-colorível pode ser resumido à forma que segue:

      1. Gerar todas as colorações possíveis para o grafo em questão usando somente três cores.

      2. Selecionar os grafos que não apresentam vértices adjacentes com as mesmas cores.



REFERÊNCIAS

[1]

ADLEMAN, Leonard M. On Constructing a Molecular Computer. DNA Based Computers, American Mathematical Society, 1996, p. 1-21.

[2]

AHARONOV, Dorit. Introduction to Quantum Computing. Annual Reviews of Computational Physics VI. Edited by Dieterich Stauffer. World Scientific, 1998

[3]

BARENCO, Adriano; BENNET, Charles; CLEVE, Richard; DIVICENZO, David P.; MARGOLUS, Norman; SHOR, Peter; SLEATOR, Tycho; SMOLIN, John A.; WEINFURTER, Harald. Elementary gates for quantum computation. Phys. Rev. A, v. 52, n. 5, p. 3457 - 3467, Nov. 1995.

[4]

BARENCO, Adriano. Quantum physics and computers. Contemporary Physics. v. 38, p. 357 - 389, 1996.

[5]

BERNSTEIN, E.; VAZIRANI,U. Quantum complexity theory. 25th ACM Symposium on the Theory of Computation. New York: ACM Press, p. 11-20, 1993.

[6]

BOYER, Michel; BRASSARD, Gilles , Høyer, Peter; TAPP, Alain. Tight bounds on quantum searching. . Fortschritte Der Physik, Special issue on quantum computing and quantum cryptography, v. 46, n. 4-5, p. 493-505, Jun. 1998.

[7]

DEUTSCH, David. Quantum Theory, the Church-Turing principle and the universal quantum computer. Proceedings of Royal Society of London, A400, p.97-117, 1985.

[8]

GROVER, Lov K. A fast quantum mechanical algorithm for database search. Proceedings STOC, Philadelphia, p. 212 – 219, 1996

[9]

ÖMER, Bernhard. A Procedural Formalism for Quantum Computers. Disponível por WWW em http://tph.tuwien.ac.at/~oemer/qcl.html . (4, janeiro, 2001)

[10]

ÖMER, Bernhard. Quantum Programming in QCL. Disponível por WWW em http://tph.tuwien.ac.at/~oemer/qcl.html . (4, janeiro, 2001)

[11]

Open Qubit Quantum Computing. Disponível por WWW em

http://www.openqubit.org/ (4, janeiro, 2001)

[12]

PENROSE, Roger. A Mente Nova do Rei, editora Campus Ltda, Rio de Janeiro, 1991.

[13]

SIMON, Daniel. On The Power of Quantum Computation. Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, p 124 -134. IEEE, 1994.

[14]

WILLIAMS, Colin P. CLEARWATER, Scott H. Explorations in QUANTUM COMPUTING. Springer-Verlag. New York,1997.