Autômato quântico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Nuvola apps important.svg
A tradução deste artigo ou se(c)ção está abaixo da qualidade média aceitável.
É possível que tenha sido feita por um tradutor automático ou por alguém que não conhece bem o português ou a língua original do texto. Caso queira colaborar com a Wikipédia, consulte Quantum finite automata (inglês) e melhore este artigo conforme o guia de tradução.

Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica dos autômato probabilístico. Eles estão relacionados à computação quântica da mesma maneira que o autômato finito está relacionado à máquina de Turing. Muitos tipos de autômatos podem ser definidos, incluindo measure-once e measure-many autômatos. Autômatos quânticos de estados finitos podem ser entendidos como uma quantização do subshifts of finite type, ou uma quantização das cadeias de Markov. QFA é, de certa maneira, um caso especial de autômato geométrico finito ou autômato topológico finito.

Os autômatos trabalham aceitando uma string de comprimento finito \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k) ou letras \sigma_i de um alfabeto finito \Sigma\ni\sigma_i, e assinalando para cada uma dessas strings uma probabilidade \operatorname{Pr}(\sigma) indica a probabilidade do autômato estar em um estado aceitação, isto é,indicando se o autômato aceita ou rejeita a string.

Autômato quântico de uma direção[editar | editar código-fonte]

Autômato quântico de uma direção foi introduzido por Moore e Crutchfield1 . Eles definiram da seguinte maneira.

Como em um autômato finito qualquer, podemos considerar que o autômato quântico tem N estados internos possíveis, representado neste caso por um qubit de N-estados |\psi\rangle. Mais precisamente, o qubit de N-estados |\psi\rangle\in \mathbb {C}P^N é um elemento de um espaço complexo projetivo de dimensão N, munido de um produto interno \Vert\cdot\Vert que é uma métrica Fubini-Study.

Os estados de transição, a matrix de transição ou um grafo de Bruijn são representados por uma coleção de matrizes unitárias N\times N, U_\alpha, com uma matriz unitária para cada letra \alpha\in\Sigma. Isto é, dado uma letra de entrada \alpha, a matriz unitária descreve a transição do autômato do estado corrente |\psi\rangle para o próximo estado |\psi^\prime\rangle:

|\psi^\prime\rangle = U_\alpha |\psi\rangle

Então, a tripla (\mathbb {C}P^N,\Sigma,\{U_\alpha\vert\alpha\in\Sigma\}) forma um semi-autômato quântico.

O estado de aceitação de um autômato é dado por uma matriz de projeção P N\times N, isto é, dado um estado quântico N-dimensional |\psi\rangle, a probabilidade de |\psi\rangle estar em um estado de aceitação é

\langle\psi |P |\psi\rangle = \Vert P |\psi\rangle\Vert^2

A probabilidade de um estado aceitar uma determinada string finita \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k) é dado por

\operatorname{Pr}(\sigma) = \Vert P U_{\sigma_k} \cdots U_{\sigma_1} U_{\sigma_0}|\psi\rangle\Vert^2

Aqui, o vetor |\psi\rangle é entendido como a representação do estado inicial do autômato, isto é, o estado em que o autômato estava antes do estado de aceitação da string de entrada. A string vazia \varnothing é entendida como uma matriz unitária, isto é

\operatorname{Pr}(\varnothing)= \Vert P |\psi\rangle\Vert^2

é a simplesmente a probabilidade do estado inicial ser um estado de aceitação.

Porque uma operação a esquerda de U_\alpha em |\psi\rangle inverte a ordem das letras na string \sigma, é comum para os QFA's a definição usando a operação a direita nos estados da transposta Hermitiana, simplesmente para manter a mesma ordem das letras da string.

Uma Linguagem regular é aceita com probabilidade p por um autômato finito quântico, se, para todas as sentenças \sigma na linguagem, ( e um dado estado inicial |\psi\rangle), ela tenha p<\operatorname{Pr}(\sigma).

Exemplos[editar | editar código-fonte]

Considere a clássica máquina de estados finitos determinística dado pela tabela de transição de estados

Tabela de transição de estados
  Input
State
1 0
S1 S1 S2
S2 S2 S1
  Diagrama de estados
DFAexample.svg

O estado quântico é um vetor, na notação bra-ket

|\psi\rangle=a_1 |S_1\rangle + a_2|S_2\rangle = 
\begin{bmatrix} a_1 \\ a_2 \end{bmatrix}

com os números complexos a_1,a_2 normalizados da seguinte forma

\begin{bmatrix} a^*_1 \;\; a^*_2 \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} = a_1^*a_1 + a_2^*a_2 = 1

As matriz de transição unitária são

U_0=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}

e

U_1=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

Pegando S_1 como um estado aceito, a matriz de projeção é

P=\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}

As should be readily apparent, se o estado inicial é um estado puro |S_1\rangle ou |S_2\rangle, então o resultado de rodar a máquina será exatamente idêntico ao da áquina determinística de estados finitos clássica. Em particular, existe uma linguagem aceita pelo aotômato com probabilidade um, para este estado inicial, e é idêntico à linguagem regular para o DFZ clássico, e é dado por uma expressão regular:

(1^*(01^*0)^*)^*

O comportamento não clássicas ocorre se ambos a_1 e a_2 são não nulos. O comportamento mais sutil ocorre quando as matrises U_0 e U_1 não são tão simples; veja, por exemplo, a curva de Rham como um exemplo de máquina de estado finito agindo no conjunto de todas as strings binárias possíveis.

Measure-many automata[editar | editar código-fonte]

Measure-many automata foram introduzidos por Kondacs e Watrous em 1997.2 . O modelo geral resembles that of the measure-once automaton, except that instead of there being one projection, at the end, there is a projection, or quantum measurement, performed after each letter is read. Uma definição formal segue.

O espaço de Hilbert \mathcal{H}_Q=\mathbb{C}P^N é decomposto em três espaços ortogonais

\mathcal{H}_Q=\mathcal{H}_\mbox{accept} \oplus \mathcal{H}_\mbox{reject} \oplus \mathcal{H}_\mbox{non-halting}

Na literatura, esse subespaços ortogonais são usualmente formulados em termos do conjunto Q dos vetores da base ortogonal do espaço de Hilbert \mathcal{H}_Q. Este conjunto de vetores base é dividido em subconjuntos Q_\mbox{acc} \subset Q e Q_\mbox{rej} \subset Q, tais que

\mathcal{H}_\mbox{accept}=\operatorname{span} \{|q\rangle : |q\rangle \in Q_\mbox{acc} \}

é a combinação linear dos vetores da base em um conjunto aceito. O espaço de rejeição é definido analogamente, e o remaining space é designado o subespaço de não-halting . Existem três matrizes de projeção, P_\mbox{acc}, P_\mbox{rej} e P_\mbox{non}, cada projetando o respectivo subespaço:

P\mbox{acc}:\mathcal{H}_Q \to \mathcal{H}_\mbox{accept}

and so on. O parsing da string de entrada processa como segue. Considere o autômato esteja no estado |\psi\rangle. Depois da leitura um símbolo da entrada \alpha, o autômato estará no estado

|\psi^\prime\rangle =U_\alpha |\psi\rangle

Neste ponto, a measurement é calculada para o estado |\psi^\prime\rangle, usando os operadores de projeção P, a cada instante as funções de onda colapsão em um dos três subespaços \mathcal{H}_\mbox{accept} ou \mathcal{H}_\mbox{reject} ou \mathcal{H}_\mbox{non-halting}. A probabilidade do colapso é dado por

\operatorname{Pr}_\mbox{acc} (\sigma) = \Vert P_\mbox{acc} |\psi^\prime\rangle \Vert^2

para o subespaço “aceito”, e analogamente para os outros dois espaços.

Se a função de onda tiver colapsado para ambos os subespaços de ”aceitação” ou “rejeição”, então o processo para. De outra maneira, o processo continua, com o próximo símbolo lido da entrada, e aplicado ao que devem ser os autoestados de P_\mbox{non}. O processo continua até que toda a string seja lida, ou que a máquina pare. Freqüentemente, símbolos adicionais \kappa e $ são unidos ao alfabeto, para agir como marcadores finais de esquerda e direita da string.

Na literatura, the meaure-many automaton é freqüentemente denotado por uma tupla (Q;\Sigma; \delta; q_0; Q_\mbox{acc}; Q_\mbox{rej}). Aqui, Q, \Sigma, Q\mbox{acc} e Q\mbox{rej} são como definidos acima. O estado inicial é denotado por |\psi\rangle=|q_0\rangle. Como transformações unitárias são denotadas pelo mapa \delta,

\delta:Q\times \Sigma \times Q \to \mathbb{C}

logo,

U_\alpha |q_1\rangle = \sum_{q_2\in Q} \delta (q_1, \alpha, q_2) |q_2\rangle

Generalizações Geométricas[editar | editar código-fonte]

A construção acima indica como o conceito de autômato finito quântico pode ser generalizado a um espaço topológico arbitrário. Por exemplo, podemos tomar a alguma (N-dimensão) espaço simétrico de Riemann para dar lugar a \mathbb{C}P^N. No lugar de matrizes unitárias, usamos isometries do manifold Riemaniano, ou, de maneira mais geral, podemos construir algum conjunto de funções abertasapropriadas ao dado espaço topológico. O estado inicial pode ser dado por um ponto nesse espaço. O conjunto dos estados aceitos pode ser tomando como um subconjunto arbitrário do espaço topológico. Podemos então dizer que uma linguagem formal aceita por este “autômato topológico” se o ponto, após uma interação pelo homomorfismo, intercepta o conjunto aceito. Mas, é claro que, isso nada mais é que a definição padrão de um M-autômato. O ambiente de um autômato topológico é estudado no campo da dinâmica topológica.

O autômato quântico difere do autômato topológico nisto, em vez de ter um resultado binário (o ponto iterado estará ou não no conjunto final?), o primeiro terá uma probabilidade. A probabilidade quântica é o (quadrado) do estado inicial projetado sobre o estado final P; isto é \bold{Pr} = \vert \langle P\vert \psi\rangle \vert^2. Mas esta amplitude de probabilidade é uma simples função da distância entre o ponto \vert P\rangle e o ponto \vert \psi\rangle em \mathbb{C}P^N, sob a distância metric dado pela métrica Fubini-Study. Recapitulando, a probalidade quântica de uma linguagem ser aceita pode ser interpretada como uma métrica, com a probabilidade de aceitação um (1), se a distância métrica entre o estado inicial e final é zero, e no outro caso a probabilidade de aceitação é menor que um (1), se a distância métrica é diferente de zero. Então, segue que o autômato quântico finito é um caso especial de autômato geométrico ou um autômato métrico, onde \mathbb{C}P^N é generalizado para algum espaço métrico, e a medida de probabilidade é substituída por uma função simples da métrica para o espaço.

Ver também[editar | editar código-fonte]

Referências

  1. C. Moore, J. Crutchfield, "Quantum automata and quantum grammars", Theoretical Computer Science, 237 (2000) pp 275-306.
  2. A. Kondas and J. Watrous, "On the power of quantum finite state automata", Proceedings of the 38th Annual Symposium on Foundations of Computer Science, (1997), IEEE Computer Society, Los Alamitos, pp. 66-75