Autômato quântico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation to english arrow.svg
A tradução deste artigo 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 verbete 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 ou letras de um alfabeto finito e assinalando para cada uma dessas strings uma probabilidade 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 Crutchfield[1]. Eles definiram da seguinte maneira.

Como em um autômato finito qualquer, podemos considerar que o autômato quântico tem estados internos possíveis, representado neste caso por um qubit de -estados Mais precisamente, o qubit de -estados é um elemento de um espaço complexo projetivo de dimensão munido de um produto interno 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 com uma matriz unitária para cada letra Isto é, dado uma letra de entrada a matriz unitária descreve a transição do autômato do estado corrente para o próximo estado

Então, a tripla forma um semi-autômato quântico.

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

A probabilidade de um estado aceitar uma determinada string finita é dado por

Aqui, o vetor é 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 é entendida como uma matriz unitária, isto é

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

Porque uma operação a esquerda de em inverte a ordem das letras na string é 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 por um autômato finito quântico, se, para todas as sentenças na linguagem, ( e um dado estado inicial ), ela tenha

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

com os números complexos normalizados da seguinte forma

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

e

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

As should be readily apparent, se o estado inicial é um estado puro ou 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:

O comportamento não clássicas ocorre se ambos e são não nulos. O comportamento mais sutil ocorre quando as matrises e 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 é decomposto em três espaços ortogonais

Na literatura, esse subespaços ortogonais são usualmente formulados em termos do conjunto dos vetores da base ortogonal do espaço de Hilbert Este conjunto de vetores base é dividido em subconjuntos e tais que

é 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, e cada projetando o respectivo subespaço:

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

Neste ponto, a measurement é calculada para o estado usando os operadores de projeção a cada instante as funções de onda colapsão em um dos três subespaços ou ou A probabilidade do colapso é dado por

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 O processo continua até que toda a string seja lida, ou que a máquina pare. Freqüentemente, símbolos adicionais 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 Aqui, e são como definidos acima. O estado inicial é denotado por Como transformações unitárias são denotadas pelo mapa

logo,

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 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 é Mas esta amplitude de probabilidade é uma simples função da distância entre o ponto e o ponto em 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 é 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