Alguns algoritmos para computa˘c~ao qu^anticaamoreira/lectnotes/ciq.pdf · 1 Um pouco de algebra linear 2 onde ij= (0; se i6= j 1; se i= j representa as componentes da matriz identidade

UBI-DF

Alguns algoritmos para computacaoquantica∗

Luıs J.M. Amoreira

Indice

1 Um pouco de algebra linear . . . . . . . . . . . . . . . . . . . . . . . . 12 Bits e Qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Quanta informacao “cabe” num qubit? . . . . . . . . . . . . . . 53 Circuitos quanticos e portas quanticas . . . . . . . . . . . . . . . . . . 63.1 Operacoes sobre um qubit . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 Operacoes sobre dois qubits . . . . . . . . . . . . . . . . . . . . . . . . 83.3 A porta de Toffoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Computacao Quantica . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.1 Paralelismo quantico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2 Alguns algoritmos ilustrativos . . . . . . . . . . . . . . . . . . . . . . . 11

4.2.1 Algoritmo de procura simples . . . . . . . . . . . . . . . . . . . 114.2.2 Algoritmo de Deutsch . . . . . . . . . . . . . . . . . . . . . . . 144.2.3 Bits multiplos: notacao e algumas definicoes uteis . . . . . . . 154.2.4 O algoritmo de Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . 164.2.5 Algoritmo de Simon . . . . . . . . . . . . . . . . . . . . . . . . 194.2.6 O algoritmo de Grover . . . . . . . . . . . . . . . . . . . . . . . 24

Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1 Um pouco de algebra linear

Consideremos um espaco vectorial (a que nos referiremos tambem como espacode estados) com dimensao N e uma base ortonormada deste espaco, formadapelos vectores (a que tambem nos referiremos como estados ou kets) |1〉, |2〉,. . . , |N〉. Porque estes vectores formam uma base ortonormada sao ortogonaisentre si e tem norma 1, ou seja,

〈i|j〉 = δij ,

∗Este trabalho pode ser copiado, alterado, vendido ou oferecido; mas (1) nao pode distri-buir trabalhos derivados deste restringindo estes direitos e (2) deve manter em tais trabalhosderivados uma referencia a este trabalho e ao seu autor. Ou seja, reconhecendo o devidocredito pelo meu trabalho pode fazer o que quiser com ele, menos impedir terceiros de faze-rem o que eles por sua vez quiserem.email: [email protected]; url: www.dfisica.ubi.pt/~amoreira

1

1 Um pouco de algebra linear 2

onde

δij =

{0, se i 6= j

1, se i = j

representa as componentes da matriz identidade (e comum o nome de sımbolode Kroneker para δij).

Qualquer estado |ψ〉 do espaco estados pode ser escrito como combinacaolinear dos estados da base:

|ψ〉 = ψi |i〉 . (soma sobre ındice repetido i subentendida)

Aos N numeros (complexos, em geral) ψi chamamos componentes ou amplitudesdo ket |ψ〉.

Uma vez que os estados da base sao ortogonais e normalizados, podemosescrever

〈j|ψ〉 = ψi 〈j|i〉 = ψj (soma sobre ındice repetido i subentendida)

ou seja,

ψj = 〈j|ψ〉 . (1)

Multiplicando a direita esta igualdade pelo |j〉 e somando em j, temos

ψj |j〉 = |j〉〈j|ψ〉 =[|j〉〈j|

]|ψ〉 ,

onde se deve subtender uma soma para todos os valores (1,. . . ,N) do ındicerepetido j (daqui em diante deixaremos de chamar a atencao para esta con-vencao da soma sobre ındices repetidos num produto de termos). Mas, no ladoesquerdo desta igualdade temos o |ψ〉 (expresso como combinacao linear dos es-tados da base), e ele tambem aparece no lado direito, fora dos parentesis rectos.Deduzimos assim a relacao de completitude

N∑j=1

|j〉〈j| = 1.

(Usando a notacao de Einstein, de soma sobre ındices repetidos, esta relacaoescreve-se simplesmente como |j〉〈j| = 1.)

Consideremos agora transformacoes lineares “internas” a este espaco vecto-rial (isto e, que transformam estados deste espaco noutros estados ainda perten-centes a este espaco). Uma transformacao linear e uma regra de transformacaodos estados,

|ψ′〉 = U |ψ〉 ,

sujeita a condicao

U(α |ψ〉+ β |φ〉) = αU |ψ〉+ βU |φ〉 .

1 Um pouco de algebra linear 3

Chamamos elementos de matriz da transformacao linear U aos N ×N numeros(em geral complexos)

uij = 〈i|U |j〉 .A matriz uij torna mais facil o calculo dos transformados dos estados. Seja|ψ〉 = ψi |i〉 um estado arbitrario e seja |ψ′〉 o seu transformado por U , isto e,

|ψ′〉 = U |ψ〉 .

Uma vez que |ψ′〉 pertence ao mesmo espaco de estados, pode tambem serdesenvolvido como combinacao linear dos estados da base,

|ψ′〉 = ψ′j |j〉 ,

com

ψ′j = 〈j|ψ′〉 ,

de acordo com a Eq. (1). Mas

ψ′j = 〈j|ψ′〉 = 〈j|U |ψ〉 = 〈j|Uψi |i〉 = 〈j|U |i〉ψi= ujiψi.

Vemos assim que para calcularmos as componentes do ket transformado bastafazer o produto matricial da matriz quadrada N × N que representa a trans-formacao pela matriz coluna que representa o ket a transformar.

Como obter de forma pratica os elementos da matriz de uma transformacaolinear U? O transformado de um ket da base pode escrever-se como combinacaolinar dos kets da base, na forma

U |j〉 = |i〉〈i|U |j〉 = 〈i|U |j〉 |i〉 = uij |i〉 .

Ou, mais concreta e explicitamente, podemos escrever

U |1〉 = u11 |1〉+ u21 |2〉+ . . .+ uN1 |N〉U |2〉 = u12 |1〉+ u22 |2〉+ . . .+ uN2 |N〉

...U |N〉 = u1N |1〉+ u2N |2〉+ . . .+ uNN |N〉

Assim, para obter a matriz uij de uma transformacao linear, escrevemos porextenso os desenvolvimentos dos transformados dos kets da base, como com-binacoes lineares dos kets da base; os elementos que formam a primeira linhada matriz sao os coeficientes que no lado direito dos desenvolvimentos, multipli-cam o primeiro ket da base; os que formam a segunda linha sao os coeficientesque multiplicam o segundo ket da base, etc. Por exemplo, o efeito da chamadatransformacao de Hadamard sobre os vectores da base de um espaco bidimen-sional sao os que aparecem na figura em baixo, a esquerda; a sua representacaomatricial, entao, e a apresentada a direita.

2 Bits e Qubits 4

2 Bits e Qubits

2.1 Bits

Um bit (classico) encontra-se sempre num de dois estados possıveis, represen-tados por “0” e “1”.

Podemos nao conhecer o estado de um bit e atribuir probabilidades as duaspossibilidades. Essas probabilidades traduzem apenas a nossa ignorancia doestado do bit, nao caracterizam o seu estado.

Uma observacao do estado de um bit elimina a nossa eventual ignoranciadesse estado mas nao o altera em nada.

2.2 Qubits

Um qubit (quantum bit) pode encontrar-se em dois estados “puros”, represen-tados por |0〉 e |1〉, mas tambem numa sobreposicao

|ψ〉 = α |0〉+ β |1〉 (2)

Dizemos que os estados (que chamamos “puros” acima) |0〉 e |1〉 formam umabase do espaco de estados de um qubit, no sentido em que qualquer estado deum qubit se pode escrever como combinacao linear destes estados.

Apesar de um qubit poder estar numa infinidade de estados (α e β acimasao numeros complexos quaisquer), uma observacao do seu estado produz ape-nas um de dois resultados possıveis |0〉 ou |1〉, em geral alterando-se de formaincontrolavel o estado do qubit. A teoria nao permite o calculo do resultado daexperiencia, apenas o das probabilidades dos dois resultados, dadas por

P (|0〉) =|α|2

Nψ=α∗α

Nψ

P (|1〉) =|β|2

Nψ

onde Nψ =√|α|2 + |β|2 (mas α e β escolhem-se normalmente de tal forma que

Nψ = 1, sem perda de generalidade). Note bem que estas probabilidades naotraduzem a nossa ignorancia do estado inicial do qubit (que pode em princıpioser conhecido com precisao absoluta), mas apenas a incerteza sobre os resultadosda medicao: conhecer o estado de um qubit (ou, mais em geral, o de qualquersistema quantico) nao garante o conhecimento do resultado de observacoes desse

2 Bits e Qubits 5

sistema, mas apenas o das probabilidades dos varios resultados possıveis dessaobservacao. No instante da observacao, o estado do qubit passa a ser o que foiobservado.

2.2.1 Quanta informacao “cabe” num qubit?

Para responder a esta pergunta de forma cabal terıamos que introduzir umadefinicao de informacao quantica, coisa que nao faremos para ja. A perguntacoloca-se agora mais para ajudar a clarificar a natureza quantica dos qubits. Emprincıpio, e possıvel construir um qubit que contenha em si uma quantidade arbi-trariamente elevada de informacao, bastando para tal codificar essa informacaonas amplitudes. Consideremos, por exemplo, as cinco primeiras palavras desteparagrafo, “Para responder a esta pergunta”. Facamos corresponder a cada ca-ractere um numero de dois algarismos indicando a sua posicao no alfabeto. Asequencia fica entao codificada pela lista [16, 01, 18, 01, 18, 05, 19, 16, 15, 14,04, 05, 18, 01, 05, 19, 20, 01, 16, 05, 18, 07, 21, 14, 20, 01] (foram eliminados osespacos, para se descartarem complicacoes agora irrelevantes). Juntemos todosestes valores num numero real

α = 0,1601180118051916151404051801051920011605180721142001

e tomemos β =√

1− α2. O qubit

|ψ〉 = α |0〉+ β |1〉

com α e β assim definidos e uma representacao unica da sequencia de caracteresconsiderada. Ou seja, ele armazena toda a informacao contida na sequencia (26caracteres). Este processo pode ser levado a cabo com sequencias alfanumericasde qualquer comprimento, ou com sequencias de bits arbitrarias, mesmo as quesao interpretadas como graficos, som, musica ou vıdeo. Concluımos que numunico qubit podemos escrever qualquer quantidade de informacao! Mas pode-remos ler essa informacao? A resposta e nao. Note-se que esta informacao estaescrita nas amplitudes do qubit, e essas sao inobservaveis. Podemos, quandomuito, tentar estimar essas amplitudes a partir das probabilidades p(0) e p(1)se se observar o qubit |ψ〉 em cada um dos estados da base. Mas essa estima-tiva, obtida de forma estatıstica, so pode ser feita a partir de uma repeticao deexperiencias de medida, e so podemos repetir essa medida se dispusermos devarias copias do qubit. Quanto mais informacao escrevermos no qubit do modoque descrevemos, mais precisao sera necessaria na determinacao das amplitu-des, logo mais vezes teremos que repetir a medida, logo, mais copias do qubitsao necessarias. Podemos escrever quantidades arbitrarias de informacao numunico qubit, sim, mas sao precisos muitos qubits identicos para podermos leressa informacao. Infelizmente, o teorema da nao-clonagem impede-nos de fazercopias de qubits, pelo que as fantasticas possibilidades que talvez ja estivessemosa imaginar nao podem ser postas em pratica.

3 Circuitos quanticos e portas quanticas 6

3 Circuitos quanticos e portas quanticas

Os circuitos quanticos implementam algoritmos quanticos.O “input” e um conjunto de qubits em estados conhecidos (por norma, e o

estado |0〉n, onde n e o numero de qubits).O circuito opera um conjunto de transformacoes dos qubits (as operacoes

do algoritmo), realizadas em “componentes” chamados portas quanticas (de-signacao herdada da electronica digital, com as suas portas logicas).

As ligacoes entre as varias portas, isto e, os canais que transportam os qubitsao longo do algoritmo chamam-se ligacoes quanticas e sao representadas por li-nhas nos diagramas. Estas ligacoes nao sao necessariamente fios condutores emimplementacoes praticas dos algoritmos. Podem representar apenas a passagemdo tempo (primeiro realiza-se esta operacao, depois aquela) ou podem represen-tar o transito espacial dos sistemas quanticos que representam os qubits (porexemplo, partıculas como fotoes).

As operacoes fısicas sobre qubits (e sobre sistemas quanticos, em geral) ope-ram linearmente (a excepcao das operacoes de medida). Isto e, dada uma trans-formacao de um qubit U qualquer, verifica-se

U(α |0〉+ β |1〉) = αU |0〉+ βU |1〉 .

Alem disso, deve ser preservada a norma dos estados, ou seja, a soma dasprobabilidades dos varios resultados possıveis de uma operacao de medida devepermanecer constante (e igual a 1, claro). Assim, se |ψ′〉 = U |ψ〉, entao

〈ψ′|ψ′〉 = 〈ψ|U†U |ψ〉 = 〈ψ|ψ〉 ,

ou sejaU†U = I, (3)

onde I representa a transformacao identidade (que ocasionalmente sera tambemrepresentada mais simplesmente por 1). Operacoes com esta propriedade cha-mam-se operacoes unitarias. Assim, concluımos que as operacoes que realizamossobre qubits sao operacoes unitarias (mais uma vez, exceptuam-se as operacoesde medida). Mas as operacoes unitarias sao invertıveis(1). As operacoes que po-demos realizar sobre qubits sao entao necessariamente reversıveis (exceptuando-se as operacoes de medida).

Uma porta quantica transforma o qubit ou sistema de qubits que a atravessa.O seu efeito pode ser caracterizado por um operador quantico (unitario, comovimos) e este pode ser representado por uma matriz. Se numerarmos os estadosda base (no caso de um unico qubit, esses estados sao dois, mas sao mais quandose consideram sistemas de varios qubits) |1〉, |2〉, . . . , |N〉 o elemento ij da

(1) Isto pode verificar-se facilmente considerando a representacao matricial dos operadores:a matriz que representa um operador unitario tem determinante 1 [propriedade que se deduzfacilmente da Eq. (3)], logo, tem inversa, que representa o operadorador inverso daquele comque comecamos.


matriz que representa o efeito de um operador U (isto e, o numero que aparecena i-esima linha e na j−esima coluna) e dado por

Uij = 〈i|U |j〉 .

3.1 Operacoes sobre um qubit

A Figura 1 mostra um circuito (classico) que realiza a operacao de negacao.Transforma o bit 0 no bit 1 e vice-versa, consistindo apenas numa porta NOT.Podemos definir esta operacao ao nıvel quantico? Nao sera muito clara essa

Fig. 1: Circuito classico para a negacao.

correspondencia uma vez que, devido ao princıpio da sobreposicao, um qubitpode estar preparado numa mistura dos dois estados |0〉 e |1〉 para os quais enıtido o significado da operacao. Mas tentemos. Claramente, um representantequantico da operacao de negacao deve transformar o qubit |0〉 no qubit |1〉 evice-versa, o que nos leva a pensar numa porta que implemente um operadorcom representacao matricial

X =(

0 11 0

),

que faz o que se pretende quando actua sobre os estados da base (|0〉 e |1〉).Mas, dado um qubit abitrario(

αβ

)≡ α |0〉+ β |1〉 ,

temos

X

(αβ

)=(βα

).

Corresponde isto a uma negacao? E discutıvel. E a operacao “mais proxima”de uma negacao disponıvel em computacao quantica. Coincide com a negacaoclassica quando aplicada a um qubit da base, e por isso tem o nome de negacaoquantica.

Fig. 2: Circuito que implementa a negacao quantica.

Outros exemplos de portas quanticas que actuam sobre um qubit sao

Y =(

0 −ii 0

)Z =

(1 00 1

)H =

1√2

(1 11 −1

)


3.2 Operacoes sobre dois qubits

As operacoes mais imediatas de dois bits, em computacao classica, sao as re-presentadas pelas portas binarias AND, OR, XOR. Estas operacoes sao irre-versıveis, no sentido em que e impossıvel, a partir apenas do resultado de qual-quer destas operacoes, recuperar os dois bits que lhe foram fornecidos comoinput. Assim, nao ha qualquer analogo directo dessas operacoes na computacaoquantica (elas podem, mesmo assim, ser implementadas de forma reversıvel,como veremos em breve).

O estado (colectivo) de um par de qubits especifica-se indicando o estado doprimeiro e o do segundo. Notacoes usuais para o estado de um par de qubitsem que o primeiro se encontra no estado |µ〉 e o segundo no estado |ν〉 sao |µν〉,|µ〉 ⊗ |ν〉, |µ〉 |ν〉. Quase sempre usaremos a primeira destas convencoes.

Um par de qubits pode ser observado num de quatro estados: |00〉, |01〉,|10〉 e |11〉. No entanto, de acordo com o princıpio da sobreposicao, pode existirnuma sobreposicao arbitraria destes quatro estados de base. Entao constatamosque o espaco de estados de um par de qubits tem dimensao quatro. E comumdesignar como vectores da base do espaco de estados de um par de qubits oskets |00〉, |01〉, |10〉 e |11〉.

Sendo a dimensao do espaco de estados quatro, as matrizes que traduzem oefeito das portas quanticas sao agora matrizes 4 × 4. Por exemplo, a Figura 3mostra um circuito que nega dois qubits e a matriz que traduz o seu efeito

|00〉 → |11〉|01〉 → |10〉|10〉 → |01〉|11〉 → |00〉

N =

0 0 0 10 0 1 00 1 0 01 0 0 0

Fig. 3: Circuito que nega dois qubits e o seu efeito.

Um conjunto importante de portas de dois (e mais) bits sao as operacoes con-troladas. Seja A um operador unitario de um qubit. A operacao A-controlado(representa-se em geral como C-A) consiste na aplicacao da operacao A a umdos qubits (chamado qubit alvo), mas apenas quando o outro qubit (chamadoqubit de controle) esta no estado |1〉. O diagrama para a operacao C-A e oapresentado na Figura 4.

Como exemplo, e facil verificar que o efeito da porta C-NOT (C-X) nos es-tados da base e a matriz unitaria que a representa sao (se o qubit de controle foro primeiro) os ilustrados na Figura (5). Um outro exercıcio, bastante instrutivo,consiste em provar que uma porta C-NOT se pode implementar com uma portaC-Z e com duas portas de Hadamard.


Fig. 4: Operacao A controlada: quando o qubit de controle se encontra no estado|0〉 nenhum dos qubits sofre alteracoes; quando o qubit de controle seencontra no estado |1〉 ao qubit alvo aplica-se a transformacao A.

|00〉 → |00〉|01〉 → |01〉|10〉 → |11〉|11〉 → |10〉

CNOT =

1 0 0 00 1 0 00 0 0 10 0 1 0

Fig. 5: Circuito que implementa a porta CNOT e o seu efeito.

3.3 A porta de Toffoli

Ja vimos que muitas operacoes logicas classicas de dois bits nao se podem imple-mentar com portas quanticas de dois qubits, por serem operacoes irreversıveis.Essa irreversibilidade traduz-se no facto de ser impossıvel reconstruir o inputfornecido a essas operacoes, partindo apenas do seu resultado. No entanto, epossıvel simular o efeito dessas operacoes com circuitos quanticos usando umqubit adicional, numa porta de tres qubits chamada porta de Tofolli. A portade Toffoli e uma porta C-NOT duplamente controlada: quando dois qubits decontrole estao, ambos, nos estado |1〉 a porta de Toffoli aplica a operacao X aoterceiro qubit. A sua representacao esquematica, junto com o seu efeito sobreos estados da base (note que agora temos que considerar o espaco de estadosde um sistema de tres qubits, com dimensao 8) estao apresentados na Figura 6.Quando os qubits de input estao preparados em estados da base (ou seja, seencontram nos estados |0〉 ou |1〉), a porta de Toffoli tem um comportamentoque permite simular varias operacoes classicas. Por exemplo, (1) se o input for|1 q2 0〉 com q2 = 0 ou 1, o output e |1 q2 q2〉, ou seja, a porta Toffoli copia oqubit q2 para o qubit alvo(2); (2) se o input for |1 q2 1〉 entao o output e |1 q2 q2〉,isto e, o qubit alvo fica preparado no estado negado do estado do segundo qu-bit: a porta de Toffoli funciona assim como uma porta classica NOT; (3) se oinput for |q1 q2 0〉, o qubit alvo fica preparado no estado q1 AND q2, etc. Tenteencontrar o input que permite usar a porta de Toffoli como uma porta NAND

(2) Mas verifique que isto nao corresponde a uma violacao do Teorema de nao-clonagem, poisa copia so e fiel se q2 estiver num estado da base. Se |q2〉 tiver amplitudes nao nulas segundoos dois estados da base, entao o qubit alvo nao fica preparado no mesmo estado.

4 Computacao Quantica 10

Input Output0 0 0 0 0 00 0 1 0 0 10 1 0 0 1 00 1 1 0 1 11 0 0 1 0 01 0 1 1 0 11 1 0 1 1 01 1 1 1 1 1

Fig. 6: Porta de Toffoli.

classica.Com estas portas classicas podem descrever-se todas as restantes, usando

as regras elementares da logica(3), logo, concluimos que qualquer circuito logicoclassico se pode implementar num computador quantico usando portas de Tof-foli. Mas a computacao quantica ultrapassa em muito essa possibilidade.

4 Computacao Quantica

4.1 Paralelismo quantico

Num certo sentido, os circuitos quanticos operam sempre em processamentoparalelo, no sentido que todas as componentes do sistema de qubits processadoevoluem, ou sao processadas, simultaneamente. Por exemplo, consideremos umafuncao arbitraria de um bit f(x) : {0,1} → {0,1}(4) e a porta de dois qubitsrepresentada na Figura 7 (verifique que e unitaria). Se alimentarmos esta porta

Fig. 7: Porta de dois bits para o calculo da funcao de um bit arbitraria f(x).O sımbolo a ⊕ b representa a adicao modulo 2, ou seja, actua como aoperacao EXOR classica. Quando no input se tem |y〉 = |0〉, o segundoqubit na saıda esta preparado no estado |f(x)〉.

(3) Por exemplo, aOR b = ˜aAND b.(4) Isto e, uma funcao que transforma os elementos do conjunto {0,1} em elementos desse

mesmo conjunto. Ha apenas quatro possibilidades: f1(x) = 0, f2(x) = 1, f3(x) = x ef4(x) = x, com x = 0,1, 0 = 1, 1 = 0.


com o par de qubits∣∣(|0〉+ |1〉)/

√2,0⟩, o output sera

1√2

(|0,f(0)〉+ |1,f(1)〉

). (4)

Ou seja, com uma unica operacao, calculamos, simultaneamente, os dois valoresda funcao f(x). Processos semelhantes a este podem ser desenhados para ocalculo de funcoes com um domınio mais alargado (funcoes de dois, tres ou maisbits).

E esta possibilidade quantica de calcular varias amplitudes simultaneamenteque se tenta domar na ivestigacao em computacao quantica. Claro que naobasta calcular as amplitudes, e preciso tambem extrair essa informacao que estaarmazenada na combinacao da Eq. (4). Este problema e resolvido de diferentesmaneiras em diferentes situacoes.

4.2 Alguns algoritmos ilustrativos

O poder da computacao quantica e mais facilmente demonstrado na resolucaode problemas simples, mas artificiais, no sentido em que nao sao problemasimportantes, ou cuja resolucao interesse verdadeiramente a alguem. E comesses que vamos comecar o nosso estudo.

4.2.1 Algoritmo de procura simples

Suponhamos que temos um objecto escondido no interior de uma de quatrocaixas e que pretendemos descobrir qual das caixas e essa. Para tal, devemosfazer tentativas, em que abrimos uma das caixas e verificamos se sim ou nao enessa caixa que se encontra o objecto. Classicamente, o numero de tentativas afazer para obter uma resposta certa e, no pior dos casos, quatro. Um algoritmoquantico, que vamos desenvolver ja de seguida, permite obter a resposta comuma tentativa apenas.

Designemos as caixas com os numeros 0,1,2,3 expressos em binario (00,01,10,11) e seja f(x), x ∈ {0,1}2 uma funcao binaria de dois bits que representa oresultado de uma tentativa. Ou seja, f(x) = 1 se x for o numero da caixa ondeo objecto se encontra e f(x) = 0 nos restantes casos. Num circuito quantico, afuncao de dois bits f(x) deve ser implementada como uma porta unitaria de 3qubits (tal como uma funcao de um bit so pode ser implementada quanticamentecomo uma porta unitaria de dois qubits, como discutimos na seccao anterior),sendo o terceiro qubit reservado para armazenar o resultado da operacao, emsoma modulo 2 (ou seja, numa operacao EXOR) com o valor inicial desse qubit(ver a figura 8)

Consideremos o efeito do circuito da Figura 9, e acompanhemos o trio dequbits a medida que vai sofrendo as transformacoes operadas pelo circuito. Oestado de input |ψ0〉 = |0〉 |0〉 |1〉 ≡ |001〉 comeca por alimentar tres portas deHadamard, que o transformam em

|ψ1〉 =12[|00〉+ |01〉+ |10〉+ |11〉

] |0〉 − |1〉√2


Fig. 8: Porta quantica unitaria que calcula o valor de uma funcao binaria dedois qubits f(x), x ∈ {0,1}2.

Fig. 9: Circuito quantico para o algoritmo de procura simples.

Vejamos como a porta Uf transforma cada um dos estados presentes no ladodireito desta igualdade. Note que cada um destes estado se pode escrever naforma |x〉 (|0〉 − |1〉)/

√2, onde x e uma sequencia arbitraria de dois bits. O

transformado deste ket pela porta Uf e

Uf |x〉|0〉 − |1〉√

2=Uf |x〉 |0〉 − Uf |x〉 |1〉√

2=|x〉 |f(x)〉 − |x〉

∣∣f(x)⟩

√2

Sendo f uma funcao binaria, temos f(x) = 0 ou f(x) = 1. No primeiro caso,temos

Uf |x〉|0〉 − |1〉√

2=|x〉 |0〉 − |x〉 |1〉√

2= |x〉 |0〉 − |1〉√

2, se f(x) = 0;

e, no segundo caso,

Uf |x〉|0〉 − |1〉√

2=|x〉 |1〉 − |x〉 |0〉√

2= − |x〉 |0〉 − |1〉√

2, se f(x) = 1.

Em ambos os casos, podemos escrever

Uf |x〉|0〉 − |1〉√

2= (−1)f(x) |x〉 |0〉 − |1〉√

2(5)


Dado este resultado, a porta Uf transforma o estado |ψ1〉 no estado

|ψ2〉 =12

[(−1)f(00) |00〉+ (−1)f(01) |01〉+

(−1)f(10) |10〉+ (−1)f(11) |11〉] |0〉 − |1〉√

2.

Recordemos agora que a funcao f(x) e nula para todos os valores de x ∈ {0,1}2,menos para aquele que corresponde ao numero da caixa que contem o objecto.Ou seja, tres dos quatro termos dentro dos parentesis rectos tem, na soma,sinal positivo, e aquele cujo ındice corresponde a caixa que contem o objectoa encontrar tem sinal negativo. Isto e, o estado dos dois primeiros qubits dotrio (o terceiro nao desempenhara mais papel nenhum, de forma que o vamosdescartar daqui em diante) e um dos seguintes:(5)

|ψ2〉 =

12 (− |00〉+ |01〉+ |10〉+ |11〉) , se f(00) = 112 (|00〉 − |01〉+ |10〉+ |11〉) , se f(01) = 1,12 (|00〉+ |01〉 − |10〉+ |11〉) , se f(10) = 1,12 (|00〉+ |01〉+ |10〉 − |11〉) , se f(11) = 1.

(6)

Note-se bem que estas sao quatro possibilidades alternativas, que nao se trataagora de um estado de sobreposicao das quatro. O estado deste par de qubits eum destes quatro estados, conforme a caixa que contem o objecto. Mais ainda,estes quatro estados sao ortogonais entre si, isto e,

(αβ) 〈ψ2|ψ2〉(α′β′) = δαα′δββ′ ,

onde se representou por |ψ2〉(αβ) o ket |ψ2〉 que resulta quando f(αβ) = 1. Es-tados ortogonais podem ser transformados, mediante operadores unitarios, nosestados da base, que e o que o resto do circuito faz. Vejamo o que acontece aopar de qubits daqui em diante, ao longo do resto do circuito. As quatro pos-sibilidades tem que ser estudadas separadamente. Comecemos com a primeira,que se verifica se o objecto estiver escondido na caixa 00. O estado |ψ2〉, nestecaso, e

|ψ2〉(00) =12[− |0〉

(|0〉 − |1〉

)+ |1〉

(|0〉+ |1〉

)].

As portas de Hadamard, de seguida, vao transformar este estado em

|ψ3〉(00) =12[−(|0〉 − |1〉

)|1〉+

(|0〉+ |1〉

)|0〉]

(7)

As portas Z deixam “passar” os kets |0〉 sem os alterar, mas trocam o sinal aoskets |1〉. Temos entao

|ψ4〉(00) =12[(|0〉+ |1〉

)|1〉+

(|0〉 − |1〉

)|0〉].

(5) O ındice (00) no ket torna explıcito que se esta a tratar o primeiro caso, aquele que severifica quando o objecto esta escondido na caixa 00.


Segue-se uma porta C-Z, que e aplicada ao segundo qubit, mas so quando oprimeiro se encontra no estado |1〉. O resultado e

|ψ5〉(00) =12[(|0〉+ |1〉

)|0〉+

(|0〉+ |1〉

)|1〉]

=|0〉+ |1〉√

2|0〉+ |1〉√

2,

e, por fim, as duas portas de Hadamard transformam este estado no estado dabase

|ψ6〉(00) = |00〉 .

Se medirmos estes qubits, obtemos, com probabilidade 1, o valor 00. E agora umexercıcio trivial (mas faca-o!) verificar os seguintes resultados, correspondentesas restantes possibilidades:

|ψ6〉(01) = |01〉

|ψ6〉(10) = |10〉

|ψ6〉(11) = |11〉

Ou seja, o resultado da medicao e sempre o numero que corresponde a caixaonde o objecto esta escondido. Ficamos assim a conhecer a posicao do ob-jecto, fazendo uma unica tentativa. Trata-se pois de um metodo bastante maiseficiente do que o classico.

No exemplo que aqui estudamos, o objecto a encontrar podia estar em umade quatro caixas. Mas este algoritmo pode ser facilmente generalizavel para umnumero arbitrariamente elevado de caixas, tornando-se ainda mais perceptıvela sua superior eficiencia relativamente ao algoritmo classico.

4.2.2 Algoritmo de Deutsch

O algoritmo de Deutsch (e, sobretudo, a sua generalizacao no algoritmo deDeutsch-Jozsa) mostram duas possibilidades para o aproveitamento do parale-lismo inerente aos computadores quanticos. Seja f(x) : x ∈ {0,1} → {0,1}uma funcao arbitraria de um bit, como a que consideramos na seccao anteriore seja ainda Uf a porta quantica que realiza o seu calculo, nos termos que aıdiscutimos. Considere o circuito representado na Figura 10. Como input aocircuito temos o estado |ψ0〉 = |01〉. As duas portas de Hadamard actuando emparalelo sobre cada um dos qubits do input produzem o estado

|ψ1〉 =|0〉+ |1〉√

2|0〉 − |1〉√

2,

que passa a porta Uf . Como vimos no estudo do algoritmo de procura, o efeitoda porta Uf sobre um estado |x〉 (|0〉 − |1〉)/

√2 e

Uf |x〉|0〉 − |1〉√

2= (−1)f(x) |x〉 |0〉 − |1〉√

2.


Fig. 10: Circuito que implementa o algoritmo de Deutsch. (Note que o estadode input aqui nao e o estado |00〉.)

O output da porta Uf e entao

|ψ2〉 =

(−1)f(0)[|0〉+|1〉√

2

] [|0〉−|1〉√

2

], se f(0) = f(1)

(−1)f(0)[|0〉−|1〉√

2

] [|0〉−|1〉√

2

], se f(0) 6= f(1)

Por fim, a porta de Hadamard transforma o primeiro qubit de |ψ2〉 em |0〉 (noprimeiro caso) ou em |1〉 (no segundo). O resultado final e entao o par de qubits

|ψ3〉 =

(−1)f(0) |0〉[|0〉−|1〉√

2

], se f(0) = f(1)

(−1)f(0) |1〉[|0〉−|1〉√

2

], se f(0) 6= f(1)

Mas x⊕ y vale 0 se x = y e 1 em caso contrario; entao o estado final pode aindaescrever-se, mais simplesmente, como

|ψ3〉 = (−)f(0) |f(0)⊕ f(1)〉[|0〉 − |1〉√

2

].

Fazendo agora uma observacao do primeiro qubit, obtemos o valor da propri-edade global da funcao f(0) ⊕ f(1)(6). E importante realcar este ponto: comeste circuito quantico podemos determinar o valor de uma propriedade globalda funcao (verificamos se a funcao e constante ou se transforma os dois bits embits diferentes), fazendo apenas uma avaliacao. Num algoritmo classico, essaverificacao obrigar-nos-ia a calcularmos separadamente o valor de f(0) e o def(1) para chegarmos a uma conclusao.

4.2.3 Bits multiplos: notacao e algumas definicoes uteis

O algoritmo de Deutsch pode ser generalizado para funcoes binarias de variosbits, funcoes f(x) : x ∈ {0,1}n → {0,1}, tornando-se ainda mais patente a

(6) Note que f(0) e f(1) tem o valor 0 ou 1 (independentemente um do outro, claro). Entaof(0)⊕ f(1) tem o valor 0 ou 1. Isto e, o primeiro qubit esta num dos estados da base, e naonuma sobreposicao desses estados.


sua superior eficiencia. Antes, porem, e util clarificar a notacao que usaremos eintroduzir algumas definicoes.

Representaremos por sk o k-esimo bit de uma sequencia s de n bits. Oconjunto de todas as sequencias de n bits (ou seja, o conjunto dos numerosbinarios com n bits) sera representado como {0,1}n. A sequencia de n bitstodos nulos sera representada como 0n.

Sera usada frequentemente a operacao EXOR (”EXclusive Or”)de duassequencias binarias. Como ja se disse acima, a operacao EXOR entre doisbits vale 0 se eles forem iguais (ambos 0 ou ambos 1) e 1 se eles forem diferen-tes. O k-esimo bit da sequencia resultante tem o valor do EXOR dos dois bitscorrespondentes nas duas sequencias, ou seja

(a⊕ b)k = ak ⊕ bk.

Dadas duas sequencias binarias de n bits x e y, e conveniente introduzir anotacao

x · y =

(n∑k=1

xkyk

)%2,

onde a%b representa (como na linguagem de programacao C) o resto da divisaointeira de a por b.

A operacao EXOR tem algumas propriedades interessantes (verifique o leitora sua validade), que serao largamente usadas mais adiante:

1. x⊕ x = 0n, ∀x ∈ {0,1}n

2. (x⊕ y)⊕ y = y ⊕ (x⊕ y) = x ∀x,y ∈ {0,1}n

3. (x⊕ y) · z = (x · z)⊕ (y · z) ∀x,y ∈ {0,1}n

4.2.4 O algoritmo de Deutsch-Jozsa

Podemos agora estudar a generalizacao do algoritmo de Deutsch para funcoesde varios bits. Seja f(x) uma tal funcao, e suponhamos que ela pertence neces-sariamente a uma das seguintes duas classes:

(C1) A funcao e constante, ou seja, f(x) = b, ∀x ∈ {0,1}2, com b ∈ {0,1};

(C2) A funcao e equibrada, ou seja, para metade dos 2n valores da variavelx ∈ {0,1}n f(x) tem o valor 0 e, para a outra metade, tem o valor 1. Istoe, os dois valores que f pode tomar ocorrem em iguais quantidades.

O problema que pretendemos resolver e determinar a qual destas duas classespertence a funcao f , fazendo o menor numero possıvel de avaliacoes da funcao.

Classicamente, responder a esta questao sem margem de erro obriga, nomaximo, a 2n−1 + 1 avaliacoes da funcao. Com efeito, podemos avaliar a funcaoem metade 2n/2 = 2n−1 dos casos possıveis obtendo sempre o mesmo resultadoe levando-nos a acreditar que a funcao e constante, para obter, na (2n−1 + 1)-esima avaliacao, um resultado diferente, concluindo entao que a funcao (por


pertencer necessariamente a uma destas duas classes) e equilibrada. Quantasavaliacoes da funcao sao necessarias com um algoritmo quantico?

Como nos casos anteriores, supomos que dispomos de uma porta quanticaunitaria de n + 1 qubits para calcular o valor da da funcao f . Os primeirosn qubits fornecem o input; o (n + 1)-esimo qubit armazena o resultado daoperacao, somado modulo 2 ao valor original deste qubit (ver a Figura 11). No

Fig. 11: Porta unitaria para o calculo de uma funcao binaria de n bits x1,x2,. . . ,xn. Como nos casos ja estudados, a condicao de unitaridadeobriga a apresentar o resultado como a soma modulo 2 com o valor ini-cial do (n+1)-esimo qubit. Repare que se usa a notacao x ≡ x1x2 . . . xn.

que se segue, deve tomar-se x ≡ x1x2 . . . xn como uma sequencia de bits.Esta porta unitaria tem um comportamento muito util, que ja foi usada no

algoritmo de pesquisa simples, que se nota quando o qubit auxiliar (o que naFigura 11 designamos y) se encontra no estado |−〉 = H |1〉 = (|0〉 − |1〉)/

√2.

Vejamos:

Uf |x〉 |−〉 = Uf |x〉|0〉 − |1〉√

2= |x〉

|f(x)〉 −∣∣f(x)

⟩√

2,

onde se representou com uma barra sobre o sımbolo a operacao de negacao dessesımbolo: x = 1⊕ x = NOTx. Duas possibilidades se colocam:

Uf |x〉 |−〉 =

{|x〉 |0〉−|1〉√

2= |x〉 |−〉 , se f(x) = 0

|x〉 |1〉−|0〉√2

= − |x〉 |−〉 , se f(x) = 1,

mas ambas as possibilidades se podem escrever numa formula comum:

Uf |x〉 |−〉 = (−1)f(x) |x〉 |−〉 . (8)

Generalizamos assim a Eq. (5) para funcoes de n bits.Com o recurso a uma tal “caixa negra”, o algoritmo de Deutsch-Jozsa (ver

a Figura 12) permite resolver o nosso problema com uma unica iteracao, comoveremos de seguida.

O efeito da porta de Hadamard sobre um qubit num dos estados da base |b〉(b = 0 ou b = 1) pode ser escrito como

H |b〉 =1√2

(|0〉+ (−1)b |1〉) =1√2

1∑a=0

(−1)ab |a〉


Fig. 12: O algoritmo de Deutsch-Jozsa.

Se a porta de Hadamard for aplicada a dois qubits em estados da base, isto e,a um estado do tipo |b〉, com b = b1b2 e b1,b2 ∈ {0,1}, entao temos

H ⊗H |b〉 = H |b1〉 ⊗H |b2〉

=

(1√2

1∑a1=0

(−1)a1b1 |a1〉

)⊗

(1√2

1∑a2=0

(−1)a2b2 |a2〉

)

=12

∑a∈{0,1}2

(−1)a·b |a〉 ,

com a = a1a2, a1,a2 ∈ {0,1} e a · b ≡ (a1b1 + a2b2)%2. Esta expressao eagora facilmente generalizavel para um numero arbitrario de qubits, podendo(e devendo!) o leitor verificar que, se b = b1b2 . . . bn for uma sequencia qualquerde n bits, entao

H⊗n |b〉 =1√2n

∑a∈{0,1}n

(−1)a·b |a〉 , (9)

onde H⊗n = H ⊗H ⊗ . . .⊗H (n vezes) e a · b = a1b1 + a2b2 + · · ·+ anbn.Deduzimos aqui esta expressao porque a primeira operacao do algoritmo

de Deutsch-Jozsa consiste exactamente na aplicacao de n portas de Hadamardaos n primeiros qubits no input. Usando a formula que acabamos de obter,escrevemos o resultado desta primeira operacao como

|ψ1〉 =1√2n

∑a∈{0,1}n

|a〉 1√2

(|0〉 − |1〉

).

Podemos agora calcular o efeito da porta Uf usando a eq. (8), resultando

|ψ3〉 =1√2n

∑a∈{0,1}n

(−1)f(a) |a〉 1√2

(|0〉 − |1〉

).


Por fim, descartamos o ultimo qubit (no estado [|0〉−|1〉]/√

2) e aplicamos portasde Hadamard a cada um dos restantes. De novo, o resultado pode ser calculadousando a Eq. (9), e obtem-se

|ψ4〉 =1√2n

∑a∈{0,1}n

(−1)f(a)

1√2n

∑b∈{0,1}n

(−1)a·b |b〉

=∑b

(12n∑a

(−1)f(a)+a·b

)|b〉 .

Qual a probabilidade de observarmos o estado de n qubits |ψ4〉 no estado |0n〉?Essa probabilidade e o quadrado do modulo do termo correspondente no seudesenvolvimento dado nesta igualdade, ou seja, o termo com b = 0n, ou seja, e

P (0n) =

∣∣∣∣∣ 12n∑a

(−1)f(a)

∣∣∣∣∣2

=

{1, se f(x) for constante;0, se f(x) for equilibrada.

Assim, se observarmos |ψ4〉 e o resultado for o estado |0n〉, concluımos que afuncao f(x) e constante. Caso contrario, a funcao e equilibrada. Ou seja, coomuma unica utilizacao do elemento que calcula o valor da funcao (a porta Uf )demos a resposta ao problema.

Apesar do algoritmo de Deutsch-Jozsa que acima descrevemos ser muito maiseficiente do que o seu analogo classico quando se pretende obter uma respostasem margem de erro, pode argumentar-se que, admitindo a possibilidade de erro,o algoritmo classico permite tambem obter respostas com poucas avaliacoes. Porexemplo, consideremos o caso n = 8, e suponhamos que fizemos cinco avaliacoesda funcao(7) e que obtivemos sempre o mesmo resultado. A probabilidade de issose verificar supondo que a funcao e equilibrada e ' 0,03, sendo pois muito maisprovavel que ela seja constante. Assim, e razoavel argumentar-se que o algoritmoquantico nao representa um tao grande aumento de eficiencia relativamente aometodo classico.

4.2.5 Algoritmo de Simon

Estudaram-se ate agora algoritmos quanticos que demonstravam alguma superi-oridade relativamente a metodos classicos, em termos de eficiencia. No entanto,deve reconhecer-se que os problemas que esses algoritmos resolvem nao sao pro-priamente interessantes, isto e, e difıcil imaginar uma situacao em que a respostaa esses problemas tenha alguma utilidade pratica ou teorica. O problema queagora vamos abordar, que quanticamente se resolve atraves do chamado algo-ritmo de Simon, ainda e dessa categoria, mas tem uma relacao muito proximacom problemas verdadeiramente relevantes.

(7) Muito longe ainda das 2n−1 + 1 = 129 necessarias para se poder dar uma resposta certa.


O problema de Simon

E dada uma funcao f(x) : x,f(x) ∈ {0,1}n de n bits que satisfaz a condicao

f(x) = f(y)⇔ x⊕ y = s, para algum s ∈ {0,1}n.

(Chamaremos a uma tal funcao uma funcao de Simon.) Pretende-se determinaro valor de s.

Tentemos perceber melhor o problema antes de atacarmos a sua solucao.Em primeiro lugar, o que e uma funcao de Simon? Uma funcao de Simon e umafuncao de n bits f : {0,1}n → {0,1}n tal que se apresenta o mesmo valor paradois argumentos x e y, entao necessariamente se tem x ⊕ y = s, onde s e umasequencia de n bits caracterıstica da funcao; no sentido inverso, se x e y saodois elementos do domınio das funcao (ou seja, se x e y sao duas sequencias den bits) tais que x⊕ y = s, entao necessariamente se tem f(x) = f(y).

Vejamos um exemplo. Consideremos a funcao de tres bits apresentada naTabela 1. Quaisquer dois valores x e y da variavel aos quais corresponde o

Tab. 1: Uma funcao de Simon com s = 110. As setas identificam pares deresultados identicos.

mesmo valor da funcao satisfazem x ⊕ y = 110. A sequencia caracterıstica,neste caso, e entao s = 110.

Um caso particular de funcao de Simon que e interessante referir e o das bi-jeccoes, ou funcoes de um para um. Ou seja ainda, uma funcao que, para argu-mentos diferentes, produz resultados diferentes. Consideremos duas sequenciasx e y de n bits e suponhamos f(x) = f(y). Entao x = y, logo x⊕ y = 0n, sendo0n a sequencia de n bits iguais a 0. Entao uma bijeccao e tambem uma funcaode Simon com s = 0n = 0.

E tambem util notar que, qualquer que seja a funcao de Simon com carac-terıstica s, se deve sempre verificar

f(0n) = f(s),

uma vez que, obviamente, 0n ⊕ s = s.


O algoritmo

Na Figura 13 apresenta-se o circuito que implementa o algoritmo de Simon.Como input, fornecemos o estado |ψ0〉 = |0n〉 |0n〉. O array de portas de Hada-

Fig. 13: Algoritmo de Simon.

mard transforma o estado dos primeiros n qubits, formando uma sobreposicaocom iguais pesos de todas os kets da base, ou seja

|ψ1〉 =1√2n

∑x∈{0,1}n

|x〉 |0n〉 ,

e a porta Uf transforma este estado no estado

|ψ2〉 =1√2n

∑x∈{0,1}n

|x〉 |f(x)〉 .

Por fim, o segundo array de portas de Hadamard transforma este estado em

|ψ3〉 =12n

∑x,y∈{0,1}n

(−1)x·y |y〉 |f(x)〉 ,

que se pode tambem escrever como

|ψ3〉 =∑

y∈{0,1}n

|y〉

12n

∑x∈{0,1}n

(−1)x·y |f(x)〉

.

Estamos agora interessados em calcular as probabilidades dos varios resul-tados possıveis do conjunto de medicoes M . Dado o desenvolvimento do estado


|ψ3〉, a probabilidade de se obter a sequencia de bits y e

P (y) =

∣∣∣∣∣∣ 12n

∑x∈{0,1}n

(−)x·y |f(x)〉

∣∣∣∣∣∣2

(10)

O caso s = 0n

Consideremos primeiro o caso s = 0n, isto e, o caso em que a funcao f(x) euma bijeccao. Desenvolvendo o quadrado da soma no lado direito da Eq. (10),reescrevemos a probabilidade de se obter a sequencia y nas medicoes como

P (y) =1

(2n)2∑

x1∈{0,1}n

∑x2∈{0,1}n

(−1)x1·y(−1)x2·y 〈f(x1)|f(x2)〉 .

Mas se a funcao f(x) toma diferentes valores para diferentes argumentos, entaoos kets |f(x1)〉 e |f(x2)〉 sao ortogonais para x1 6= x2. Isto e,

〈f(x1)|f(x2)〉 = δx1x2 ,

e resulta entaoP (y) =

12n

se s = 0n (11)

Assim, se a funcao f e tal que s = 0n, entao todos os resultados possıveis damedicao sao equiprovaveis.

O caso geral s 6= 0n

Se a funcao nao e bijectiva, entao podemos agrupar os elementos de {0,1}n empares {x1,x2 : x1 ⊕ x2 = s}, sendo o valor da funcao o mesmo para os doiselementos de cada par. Seja A o contradomınio de f , ou seja, o conjunto dosvalores de f(x) quando x toma todos os valores de {0,1}n. Entao, dado z ∈ A,devem existir dois elementos xz e x′z de {0,1}n tais que

xz ⊕ x′z = s

f(xz) = f(x′z) = z.

Se no somatorio da Eq. (10) agruparmos os dois valores de x que produzem cadavalor da funcao z, obtemos

P (y) =

∣∣∣∣∣ 12n∑x∈A

[(−1)xz·y + (−1)x

′z·y]|z〉

∣∣∣∣∣2

ou seja, uma vez que xz ⊕ x′z = s ⇒ x′z = xz ⊕ s e que (−1)(xz⊕s)·y =(−1)xz·y(−1)s·y,

P (y) =

∣∣∣∣∣ 12n∑z∈A

[1 + (−1)s·y] (−1)xz·y |z〉

∣∣∣∣∣2


O “produto” s · y pode tomar os valores 1 e 0. No no primeiro caso (s · y = 1),o termo entre parentesis rectos anula-se e obtemos

P (y) = 0, se y · s = 1. (12)

No segundo caso (s ·y = 0), o termo entre parentesis rectos vale 2. Temos entao

P (y) =

∣∣∣∣∣ 12n−1

∑z∈A

(−1)xz·y |z〉

∣∣∣∣∣2

=1

(2n−1)2∑z1∈A

∑z2∈A

(−1)xz1 ·y(−1)xz2 ·y 〈z1|z2〉 , se y · s = 0.

Mas z1 e z2 sao duas sequencias diferentes de {0,1}n, logo, os kets |z1〉 e |z2〉sao ortogonais,

〈z1|z2〉 = δz1z2 ,

logo, ∑z1∈A

∑z2∈A

(−1)xz1 ·y(−1)xz2 ·y 〈z1|z2〉 =2n

2= 2n−1.

Temos entaoP (y) =

12n−1

se y · s = 0.

Pos-processamento classico

Resumindo agora as varias possibilidades, a probabilidade da medicao de umasequencia particular y ∈ {0,1}n e

P (y) =

12n, se s = 0n

12n−1

, se s 6= 0n e s · y = 0

0, se s 6= 0n e s · y = 1.

O que e relevante neste resumo e que, seja qual for o resultado particular yque obtemos na medicao, podemos garantir que verifica y · s = 0 (porque aprobabilidade de medirmos resultados que nao o verifiquem e zero), mesmo naoconhecendo a sequencia s.

E com esta garantia que determinaremos s. Se repetirmos o algoritmo k ≤ nvezes, obteremos k resultados y(1), y(2), . . . ,yk que satisfazem o sistema deequacoes

y(1) · s = 0

y(2) · s = 0...

yk · s = 0


Se, neste conjunto de k equacoes, houver n linearmente independentes, resolve-mos o sistema por elas formado para obter s; caso contrario, devemos repetirmais vezes o algoritmo, ate termos essa condicao satisfeita.

Podemos assim determinar a sequencia s fazendo um numero de avaliacoes dafuncao f da ordem de grandeza de n, o comprimento da sequencia a determinar.

Como o farıamos classicamente? Recordemos o problema. E-nos fornecidauma funcao tal que

∃s ∈ {0,1}n : ∀x,y ∈ {0,1}n, f(x) = f(y)⇔ x⊕ y = s.

A nossa tarefa e determinar a sequencia de n bits s que satisfaz esta condicao.Comecamos por notar que, uma vez que 0n ⊕ s = s qualquer que seja s, entao

f(0n) = f(s).

Ou seja, s e o elemento de {0,1}n cujo transformado pela funcao f e igual ao de0n. Para encontra-lo, devemos avaliar sistematicamente a funcao para diferentesargumentos x, ate que se verifique f(x) = f(0n). O argumento x que satisfizeresta condicao e a incognita s que se quer determinar. Parece simples, mas note--se que ha 2n sequencias de n bits. O numero de vezes que devemos avaliar afuncao sera pois dessa ordem de grandeza, ou seja, muito maior que o numerode vezes que devemos repetir o algoritmo quantico.

4.2.6 O algoritmo de Grover

Discutimos na Seccao 4.2.1 um algoritmo de procura simples, com o qual seconseguia, numa unica avaliacao de uma funcao f(x) : x ∈ {0,1}2 → y ∈ {0,1}que era nula para todos os valores de x ∈ {0,1}2 menos para um, determinarqual era esse x singular que nao anulava a funcao.

Podemos generalizar este algoritmo de pesquisa para funcoes de mais dedois bits (ou seja, nos termos da discussao com que comecamos a Seccao 4.2.1,dispondo de mais do que quatro caixas onde escolher o objecto)?

A resposta e “mais ou menos”. Com funcoes de mais do que dois bits, naoe possıvel obter a solucao com apenas uma avaliacao, sendo necessario “iterar”um processo um certo numero de vezes, dependendo da dimensao do espacode busca (ou seja, do numero de bits). Mas ha aspectos comuns ao que jaestudamos.

Como sempre, precisamos de uma porta que calcule de forma unitaria o valorda funcao para um dado input, como pode ser a representada na Figura 11. Parao calculo de uma funcao de n bits, esta porta deve ter n+1 entradas e saıdas. Asprimeiras n entradas constituem um registo para o input do valor da variavel, epassam atraves da porta sem sofrerem qualquer alteracao; a ultima entrada temum papel auxiliar, e, a saıda, transporta o seu valor inicial, adicionado modulo2 ao valor da funcao.

O circuito comeca de forma semelhante ao do algoritmo de Deusch-Jozsa:um sistema de n qubits no estado |0n〉, com um qubit adicional no estado |1〉,


aos quais e aplicado uma bateria de portas de Hadamard. Gera-se assim, comoja vimos, o estado

|ψ0〉 =1√2n

∑x∈{0,1}n

|x〉 |0〉 − |1〉√2

.

De seguida, aplica-se a este estado um operador unitario (a que chamaremositeracao de Grover) um certo numero de vezes, numero esse que determinaremosmais tarde. Este operador consiste numa aplicacao da porta Uf que calcula afuncao, seguido de uma bateria de portas de Hadamard, mas apenas actuandonos primeiros n qubits, uma transformacao de fase que muda o sinal de todasas componentes do estado a excepcao da componente segundo |0n〉, seguida deuma nova bateria de n portas de Hadamard. O circuito e entao o representadonas figuras 14 e 15.

Fig. 14: Algoritmo de Grover. Deve repetir-se a aplicacao do operador G, apre-sentado na Figura 15.

Fig. 15: Iteraccao de Grover. Z0 e a transformacao de fase que muda o sinala todas as componentes do estado sobre o qual actua, a excepcao dacomponente segundo |0n〉.

Antes de iniciarmos o estudo do efeito de uma iteracao de Grover, e conveni-ente estabelecer ou recordar alguns factos, definir alguma notacao e introduziruma base para um subespaco do espaco de estados no qual e mais facil a des-cricao.

O efeito da porta Uf sobre um estado constituıdo por um ket da base com-putacional de n qubits e por um qubit adicional no estado |−〉 = (|0〉 − |1〉)/

√2


(e uma sobreposicao destes estados que e fornecida a iteraccao de Grover) e odado pela eq. (8):

Uf |x〉 |−〉 = (−1)f(x) |x〉 |−〉 . (13)

Podemos entao representar o efeito da porta Uf sobre este estado como

Uf(|x〉 |−〉

)=(Zf |x〉

)|−〉 ,

onde o operador Zf actua apenas nos primeiros n qubits, transformando umestado da base computacional (do espaco de n qubits) de acordo com

Zf |x〉 = (−1)f(x) |x〉 .

Uma vez que o qubit auxiliar (o n + 1-esimo) nao sofre qualquer alteracao aolongo da iteracao de Grover, nao o vamos considerar daqui em diante. Quantoa sua accao sobre os primeiros n qubits, podemos pois escrever o efeito da portade Grover como

G = H⊗nZ0H⊗nZf

(note que se escrevem da direita para a esquerda os operadores, na sequenciaem que actuam). Recorde que Z0 e a transformacao que muda o sinal a todasas componentes do estado de n qubits, a excepcao da componente segundo |0n〉.Podemos entao escreve-lo como(8)

Z0 = 2 |0n〉〈0n| − I,

onde I representa o operador identidade. Logo, uma vez que H⊗n |0n〉 =(∑x |x〉)/

√2n e que (H⊗n)2 = 1, podemos escrever

H⊗nZ0H⊗n = 2 |h〉〈h| − I, (14)

com|h〉 = H⊗n |0n〉 =

1√2n

∑x∈{0,1}n

|x〉 .

Seja A o conjunto dos valores de x ∈ {0,1}n para os quais f(x) = 1(9) e B oconjunto complementar:

A = {x ∈ {0,1}n : f(x) = 1}B = {x ∈ {0,1}n : f(x) = 0} .

(8) Verifique com um exemplo que este operador opera como descrito, trocando o sinal atodas as componentes de um estado, a excepcao da componente segundo |0n〉: considerandon = 2, calcule o resultado da sua aplicacao a um estado arbitrario, por exemplo, ao estadoα |00〉+β |01〉 (tenha em mente que os estados da base computacional sao ortogonais entre si:〈00|00〉 = 〈01|01〉 = 1, 〈00|01〉 = 0).(9) Admitimos agora a possibilidade de haver varias solucoes para o nosso problema. Na

imagem da procura de um objecto escondido numa de varias caixas, agora consideramos aprobabilidade de haver mais do que um objecto, logo, mais do que uma caixa ocupada; oobjectivo e encontrar um qualquer dos objectos escondidos. Ou ainda, e como se quisessemosencontrar uma agulha num palheiro onde ha varias agulhas escondidas.


Os elementos deA satisfazem os criterios da pesquisa, os deB nao satisfazem(10).Sejam a e b os numeros de elementos dos dois conjuntos e sejam ainda

|A〉 =1√a

∑x∈A|x〉 |B〉 =

1√b

∑x∈B|x〉

dois estados mutuamente ortogonais e normalizados. De acordo com a eq. (13),estes estados verificam as relacoes

Zf |A〉 = − |A〉 Zf |B〉 = |B〉 . (15)

A saıda da primeira bateria de portas de Hadamard no algoritmo de Grover,antes de se iniciarem as iteraccoes de Grover (ver a Figura 14), os primeiros nqubits encontram-se no estado

|h〉 =1√2n

∑x∈{0,1}n

|x〉 .

Este estado pode tambem escrever-se como

|h〉 =1√2n∑x∈A|x〉+

1√2n∑x∈B|x〉 =

√a

2n|A〉+

√b

2n|B〉 , (16)

Ou seja, o estado de n qubits que e fornecido a serie de iteraccoes de Groverpertence ao subespaco gerado pelos kets |A〉 e |B〉. Essa propriedade vai manter-se ao longo do algoritmo, porque as iteracoes de Grover podem ver-se comorotacoes neste subespaco. Com efeito, seja |ψ〉 um estado de n qubits qualquerdeste subespaco. Entao podemos escreve-lo como

|ψ〉 = α |A〉+ β |B〉 ,

com α e β numeros complexos arbitrarios. Dadas as igualdades da Eq. (15), oresultado da actuacao do operador Zf sobre este estado e dado por

Zf |ψ〉 = −α |A〉+ β |B〉 , (17)

que, claramente, ainda pertence ao subespaco. Por outro lado, tendo em contaa Eq. (16), podemos escrever operador H⊗nZfH⊗n [Eq. (14)] na forma

H⊗nZfH⊗n =

2a2n|A〉〈A|+ 2

√2

2n|A〉〈B|+ 2

√2

2n|B〉〈A|+ 2a

2n|B〉〈B| − I,

Com a qual rapidamente verificamos que

H⊗nZfH⊗n |ψ〉 =

[α

(2a2n− 1)

+2β√ab

2n

]|A〉+[

β

(2b2n− 1)

+2α√ab

2n

]|B〉 ,

(10) Os elementos de B sao as palhas do palheiro onde devemos encontrar uma agulha, isto e,um qualquer dos elementos do conjunto A.


ou seja, uma vez que a+ b = 2n,

H⊗nZ0H⊗n |ψ〉 =

α(a− b) + 2β√ab

2n|A〉+

2α√ab− β(a− b)

2n|B〉 , (18)

que e tambem, ainda, um elemento do subespaco gerado pelos kets |A〉 e |B〉.Geometricamente, o efeito do operador Zf pode ser visto como uma reflexaona direccao do ket |B〉, e o operador H⊗nZ0H

⊗n como uma reflexao na di-reccao do vector |h〉 =

√a/2n |A〉 +

√b/2n |B〉(11). A Figura 16 representa

graficamente estes efeitos. Mas a sucessao de duas reflexoes e equivalente a uma

Fig. 16: Representacao grafica do efeito da iteracao de Grover. O estadogenerico |ψ〉 = α |A〉+β |B〉 sofre primeiro uma reflexao no ket |B〉 queo transforma no ket |ψ′〉, pela accao do operador Zf ; em seguida, o ope-rador H⊗nZ0H

⊗n opera uma reflexao de |ψ′〉 no ket |h〉 =∑x |x〉 /2n,

produzindo como resultado o ket |ψ′′〉. O efeito global e o de umarotacao por um angulo φ, aproximando o estado original |ψ〉 da solucao.

rotacao; assim, em cada iteracao, o operador de Grover realiza uma rotacaodo estado, aproximando-o do ket |A〉, ou seja, aumentando a probabilidade de,numa medida, obtermos uma solucao do prblema.

O valor do angulo desta rotacao pode ser determinado escrevendo a repre-sentacao matricial do operador de Grover neste subespaco. Dadas as eqs. (17)e (18) verifica-se facilmente que

Zf =(−1 00 1

)H⊗NZ0H

⊗N =12n

(a− b 2

√ab

2√ab −(a− b)

),

logo,

G = H⊗NZ0H⊗NZf =

12n

(b− a 2

√ab

−2√ab b− a

).

(11) A primeira afirmacao e obvia, uma vez que a componente segundo |A〉 troca de sinal.Para se convencer da segunda, e melhor estudar uns exemplos: escolha a = b e veja o queacontece. Repita para a = 0, b = 2n ou, ao contrario, a = 2n, b = 0.


As rotacoes no plano xy no sentido do movimento dos ponteiros do relogio temrepresentacoes matriciais com a forma

Rz(φ) =(

cosφ sinφ− sinφ cosφ

)o que nos leva a fazer as identificacoes

cosφ =b− a

2nsinφ =

2√ab

2n,

que, expressas em termos de θ = φ/2, assumem uma forma particularmentesimples e simetrica:

cos θ =

√b

2nsin θ =

√a

2n.

O estado de n qubits preparado pela bateria de portas de Hadamard e for-necido ao operador de Grover para a primeira iteracao e, como ja vimos

|h〉 = H⊗n |0n〉 =√

a

2n|A〉+

√b

2n|B〉 = sin θ |A〉+ cos θ |B〉 .

Cada iteracao de Grover “roda” este estado no sentido do movimento dos pon-teiros do relogio um angulo φ = 2θ, de forma que, apos k iteracoes, teremos

Gk |h〉 = sin([2k + 1]θ) |A〉+ cos([2k + 1]θ) |B〉 .

Pretendemos que a probabilidade de medir uma sequencia de bits que corres-ponda a uma das solucoes seja elevada. Mas entao devemos repetir as iteracoesde Grover um numero de vezes k tal que a amplitude do estado resultante se-gundo o ket |A〉 seja proxima da unidade, ou seja, k deve ser tal que

sin([2k + 1]θ) ' 1⇒ k ' 12

[ π2θ− 1]

Por fim, supondo que o numero de solucoes (a) para o problema e pequenoquando comparado com a dimensao do espaco (2n), entao θ e um angulo pequenoe podemos fazer a aproximacao θ ' sin θ =

√a/2n. Nesse caso, o numero de

vezes que o operador de Grover se deve aplicar e

k ' π

4

√2n

a− 1/2 ' π

4

√2n

a.

Um caso particular especialmente interessante e a = 1. Nesse caso, resultak ' π

√2n/4. Isto e, o numero de vezes que e necessario avaliar a funcao para

encontrar o valor da variavel que nao a anula e da ordem de grandeza da raizquadrada do numero de possibilidades, o que representa uma grande melhoriarelativamente ao algoritmo classico, que obriga a um numero de avaliacoes daordem de gradeza do numero de possibilidades.


Bibliografia

• M.A. Nielsen e I.L. Chuang, Quantum Computation and Quantum Infor-mation, Cambridge University Press (2000)

• Apontamentos pelo prof. John Watrous(www.cs.uwaterloo.ca/~watrous/lecture-notes/519/)

Documents

Alguns algoritmos para computa˘c~ao qu^anticaamoreira/lectnotes/ciq.pdf · 1 Um pouco de algebra linear 2 onde ij= (0; se i6= j 1; se i= j representa as componentes da matriz identidade