Embed Size (px)
Citation preview
Um Algoritmo para Transformar Autômatos Finitos Não-
Determinísticos em Autômatos Finitos Quânticos Preservando o Número de Estados e a Linguagem Reconhecida
UFCG – IQuanta – DSC
Cheyenne R. G. [email protected]
Bernardo Lula Jú[email protected]
09/10/2006 WECIQ 2006 2
Motivação Situação e Problema abordado Autômatos Finitos Notação Vetorial Autômato Finito Quântico Algoritmo de Transformação Circuito Quântico para AFQ ancilla Conclusão Bibliografia
Roteiro
09/10/2006 WECIQ 2006 3
Motivação Estudar a Teoria da Computação Clássica no
contexto quântico Iniciar com conceitos simples Mostrar vantagens ao utilizar modelo
quântico Buscar solução “quântica” para problemas
não resolvidos satisfatoriamente no contexto clássico
09/10/2006 WECIQ 2006 4
Situação Implementar soluções construídas a partir de
um AF 1. Construir um AFN que resolve o problema
Descrição de aplicações Tratamento formal (prova de teoremas)
2. Transformar o AFN em um AFD equivalente 3. Implementar o AFD
09/10/2006 WECIQ 2006 5
Problema Transformação pode levar à uma explosão
do número de estados (no pior caso) AFN – n estados AFD – 2n estados
09/10/2006 WECIQ 2006 6
Contexto quântico Com as futuras máquina quânticas,
queremos evitar esse problema Transformar AFN em AFQ diretamente sem
aumento exponencial no número de estados Solução
Algoritmo de transformação AFN para AFQ que preserva a linguagem reconhecida e o número de estados do autômato original
09/10/2006 WECIQ 2006 7
Autômatos Finitos são elementos essenciais tanto na teoria como na prática computacional.
Um Autômato Finito (AF) é uma 5-tupla A = (Q, Σ, δ, qinit, Qac), onde: Q é um conjunto finito de estados; Σ é um alfabeto de entrada; δ : Q x Σ → Q é uma função de transição; qinit ∈ Q é o estado inicial; Qac ⊆ Q é um conjunto de estados de aceitação.
Autômatos Finitos - conceito
09/10/2006 WECIQ 2006 8
Autômatos Finitos - computação Inicia em qinit , A lê símbolo por símbolo da palavra
w = w1w2...wn
No i-ésimo passo, estando A no estado q, A lê o símbolo wi e atualiza seu estado para δ(q, wi) = q’
A aceita w se o autômato pára em um estado de aceitação.
A reconhece a linguagem formada pelas palavras aceitas.
A classe de linguagens reconhecidas por AFs é a classe das linguagens regulares.
09/10/2006 WECIQ 2006 9
Autômatos Finitos - tipos Autômato Finito Determinístico (AFD)
δ(qi, a) = qj
Autômato Finito Não-Determinístico (AFN) δ : Q x Σ → 2Q
δ(qi, a) = qj1, ...,qjk
Um AFN aceita a palavra w se há um caminho de aceitação dentre os caminhos possíveis.
09/10/2006 WECIQ 2006 10
Autômatos Finitos - equivalência
AFD e AFN reconhecem a mesma classe de linguagens.
Problema ao transformar um AFN em um AFD equivalente já mostrado
09/10/2006 WECIQ 2006 11
Notação Vetorial Seja um AF A (AFD ou AFN) com n estados.
δ é descrita por matrizes de transição Ma , de dimensão n x n, uma para cada a∈Σ. (Ma)ij = 1, sse existe a transição δ(qi, a) = qj (Ma)ij = 0, caso contrário
qinit é um vetor coluna de dimensão n onde: (qinit)i = 1, se qi = qinit
(qinit)i = 0, se qi ≠ qinit
09/10/2006 WECIQ 2006 12
Notação Vetorial Qac é o vetor coluna onde:
(Qac)i = 1, se qi ∈ Qac
(Qac)i = 0, se qi ∉ Qac
A quantidade de caminhos de aceitação para uma palavra w é dada por:
f(w) = qinitT . Mw1
. Mw2. ... . Mwn
. Qac
Uma palavra w é aceita se f(w) > 0
09/10/2006 WECIQ 2006 13
Notação Vetorial - exemplo Exemplo: Autômato A
Notação matricial de A
=
=
=
=
1010
Me1011
M,10
Q,01
q 10acinit
Computando a palavra w = 01, temos:
[ ] 210
1010
1011
01QMMq)01(f ac10Tinit =
⋅
⋅
⋅=⋅⋅⋅=
δ(q2, 0) = q2 δ(q2, 1) = q2
qinit = q1Qac = q2
δ(q1, 0) = q1, q2δ(q1, 1) = q2
Q = q1,q2 Σ = 0, 1
09/10/2006 WECIQ 2006 14
Autômato Finito Quântico AFQ é uma 5 tupla B = (Q, Σ, δ, qinit, Qac),
onde: Q é um conjunto finito de estados; Σ é um alfabeto de entrada; δ : Q x Σ x Q → C é uma função de transição; qinit ∈ Q é o estado inicial; Qac ⊆ Q é um conjunto de estados de
aceitação.
09/10/2006 WECIQ 2006 15
Autômato Finito Quântico Os estados do AFQ podem estar em superposição!
Superposição é representada por
∑∈
α=Qiq
ii qq
onde αi é a amplitude do estado qi e 1Qi
2i =α∑
∈
A função de transição é definida por δ : Q x Σ x Q → C O valor de δ(q1, a, q2) é a amplitude de |q2⟩ na
superposição de estados que B assume ao ler o símbolo a, estando em |q1⟩.
09/10/2006 WECIQ 2006 16
Autômato Finito Quântico Para a∈Σ, Ua é a matriz complexa, de dimensão
|Q|x|Q|, definida por:
( ) ( )∑∈
δ=Q'q
iia 'q'q,a,qqU
O operador deve ser unitário, logo, deve satisfazer:
∑∈
=
=δ⋅δ∑∈∈∀Qq
jiji
*ji contráriocaso0
qqse1)q,a,q()q,a,q(:a,Qq,q
Para cada símbolo lido da palavra, B aplica a transformação unitária correspondente Uwi
09/10/2006 WECIQ 2006 17
AFQ – modelo MO-AFQ MO-AFQ
Modelo de Moore e Crutchfield define uma única medição no final da computação da palavra
Palavra é aceita se
0qU)w(f 2initwacQ >⋅⋅= Q
09/10/2006 WECIQ 2006 18
AFQ – modelo MM-AFQ MM-AFQ
Modelo de Kondacs e Watrous define múltiplas medições, uma a cada leitura de símbolo da palavra Introduz um sexto elemento na tupla, o conjunto de
estados de rejeição Qrej .
Qac e Qrej são conjuntos de estados de parada Autômato aceita a palavra, se pára em um
dos estados do conjunto Qac com probabilidade > 0
09/10/2006 WECIQ 2006 19
AFQ – MO-AFQ e MM-AFQ Modelos não reconhecem a classe das
linguagens regulares Limitação quanto à unitariedade das matrizes.
MM-AFQ são “mais poderosos” que MO-AFQ MM-AFQ reconhece todas as linguagem que o
MO-AFQ reconhece. Mas o inverso não ocorre.
09/10/2006 WECIQ 2006 20
AFQ – modelo AFQ ancilla AFQ ancilla
Modelo de Paschen utiliza qubits auxiliares para tornar as transformações unitárias.
AFQ ancilla B é uma 6-tupla B = (Q, Σ, Ω, δ, qinit, Qac), onde: Q, Σ, qinit e Qac são semelhantes ao modelo MO-QFA; Ω é um alfabeto auxiliar; δ é estendida para δ:Q x Σ x Q x Ω → C[0,1] com a seguinte
restrição:∑
∈Ω∈ =
=δδ∑∈∈∀Qq*,y
jiji
*ji trário caso con0
q se q1)y,q,a,q().y,q,a,q(:a,Qq,q
09/10/2006 WECIQ 2006 21
AFQ – modelo AFQ ancilla Toda linguagem regular pode ser reconhecida por
um AFQ ancilla Paschen prova partindo de um AFD mínimo e
construindo um AFQ equivalente.
Queremos transformar diretamente um AFN em um AFQ equivalente, preservando o número de estados e a linguagem reconhecida!
09/10/2006 WECIQ 2006 22
Algoritmo Seja A = (Q, Σ, δ, qinit, Qac) um AFN qualquer.
Definimos um AFQ ancilla B = (Q’, Σ, Ω, δ’, q’init, Q’ac), como segue:1.2. 3. Para cada entrada da
função δ’ definir: , para todo d, 1 ≤ d ≤ k, e
, para todo
Qq:q'Q ∈=
q,...,q)a,q( kj1ji =δ
k1)0,q,a,q(' dji =δ
0)0,q,a,q(' si =δ q,...,qQq k1 jjs −∈
1,0=Ω
09/10/2006 WECIQ 2006 23
Algoritmo 4.
5.
6. Para cada a ∈ ∑, definir a matriz Ua como segue:
As outras entradas são preenchidas com vetores ortonormais arbitrários de forma que a U seja unitária.
( ) ∑=
) (δ=k
1djjiiia dd q0,q,a,q'q0qU
acac Qq:qspan'Q ∈=
initinit q'q =
09/10/2006 WECIQ 2006 24
Exemplo AFN A
U0(|0⟩|0⟩) = |0⟩1/√2(|0⟩+|1⟩)
U0(|0⟩|1⟩) = |0⟩1/√2(|0⟩−|1⟩)
U0(|1⟩|0⟩) = |1⟩|0⟩
U0(|1⟩|1⟩) = |1⟩|1⟩
Q' = |0⟩, |1⟩ Σ = |0⟩, |1⟩qinit = |0⟩Qac = |1⟩
U 0=[1 /2 1 /2 0 01 /2 −1 /2 0 00 0 0 10 0 1 0 ] U 1=[0 1 0 0
1 0 0 00 0 0 10 0 1 0 ]
AFQ B equivalente
δ(q1, 0) = q1 δ(q1, 1) = q1
qinit = q0Qac = q1
δ(q0, 0) = q0 ,q1δ(q0, 1) = q1
Q = q0,q1 Σ = 0, 1
U1(|0⟩|0⟩) = |0⟩|1⟩
U1(|0⟩|1⟩) = |0⟩|0⟩
U1(|1⟩|0⟩) = |1⟩|1⟩
U1(|1⟩|1⟩) = |1⟩|0⟩
09/10/2006 WECIQ 2006 25
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
09/10/2006 WECIQ 2006 26
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1Usa n qubits para
representar w
09/10/2006 WECIQ 2006 27
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2k qubits para as entradas das
portas Us
Usa n qubits para representar w
09/10/2006 WECIQ 2006 28
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2k qubits para as entradas das
portas Us
Usa n qubits para representar w
Usa k qubits extras no estado |0⟩ para cada
símbolo da entrada w
09/10/2006 WECIQ 2006 29
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2k qubits para as entradas das
portas Us
Usa n qubits para representar w
Usa k qubits extras no estado |0⟩ para cada
símbolo da entrada w
O número de qubits necessários é
h = (k+1). n + 2k
Ou seja, O(n)
09/10/2006 WECIQ 2006 30
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
09/10/2006 WECIQ 2006 31
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2 portas X para cada símbolo da
entrada
09/10/2006 WECIQ 2006 32
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2 portas X para cada símbolo da
entrada
Usa 2 portas U para cada símbolo da
entrada
09/10/2006 WECIQ 2006 33
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2 portas X para cada símbolo da
entrada
Usa 2 portas U para cada símbolo da
entrada
Usa 2 portas SWAP para cada n - 1
símbolos da entrada
09/10/2006 WECIQ 2006 34
Circuito Quântico para AFQ ancilla
Para |w| = n e Σ = 0,1
Usa 2 portas X para cada símbolo da
entrada
Usa 2 portas U para cada símbolo da
entrada
Usa 2 portas SWAP para cada n - 1
símbolos da entrada
O número de portas necessárias é
p = (2.X + 2.U). n + 2.SWAP.(n - 1)
Que também é O(n)
09/10/2006 WECIQ 2006 35
Conclusão Introduzimos didaticamente a computação
quântica a partir de referências da teoria da computação clássica.
Mostramos uma das vantagens no uso de Autômatos Quânticos Um AFN pode ser implementado diretamente em
hardware quântico sem levar a uma explosão de estados, como acontecia no caso clássico.
O modelo de AFQ com qubits auxiliares preserva a linguagem reconhecida e pode ser implementado com custo em escala polinomial ao tamanho da entrada.
09/10/2006 WECIQ 2006 36
Bibliografia Ambainis, A. and Freivalds, R. (1998) “1-Way
Quantum Finite Automata: Strengths, Weaknesses and Generalizations”, FOCS 1998 Proceedings of the 39 Annual Symposium on Foundations of Computer Science: 332-341
Kondacs, A and Watrous, J. (1997) “On the Power of Quantum Finite State Automata”, FOCS 1997: 66-75
Moore, C and Crutchfield, J. P. (2000) “Quantum automata and quantum grammars”, In: Theor. Comput. Sci 237(1-2): 275-30
09/10/2006 WECIQ 2006 37
Bibliografia Nielsen, M. A. and Chuang, I. L. (2000) Quantum
Computation and Quantum Information. Cambridge University Press
Paschen, K. (2000) “Quantum finite automata using ancilla qubits”, University of Karlsruhe, Technical report
Hopcroft, J. E., Motwani, R. and Ullman, J. D. (2001) Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company
