Autômato quântico

Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica do autômato probabilístico. Autômatos probabilísticos 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 submudanças de tipo finito, 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

Autômato quântico de uma direção foi introduzido por Moore e Crutchfield. 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 PU_{\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

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

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

Measure-many automata foram introduzidos por Kondacs e Watrous em 1997.. 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}}_{\text{accept}}\oplus {\mathcal {H}}_{\text{reject}}\oplus {\mathcal {H}}_{\text{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_{\text{acc}}\subset Q$ e $Q_{\text{rej}}\subset Q,$ tais que

${\mathcal {H}}_{\text{accept}}=\operatorname {span} \{|q\rangle :|q\rangle \in Q_{\text{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_{\text{acc}},$ $P_{\text{rej}}$ e $P_{\text{non}},$ cada projetando o respectivo subespaço:

$P{\text{acc}}:{\mathcal {H}}_{Q}\to {\mathcal {H}}_{\text{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}}_{\text{accept}}$ ou ${\mathcal {H}}_{\text{reject}}$ ou ${\mathcal {H}}_{\text{non-halting}}.$ A probabilidade do colapso é dado por

$\operatorname {Pr} _{\text{acc}}(\sigma )=\Vert P_{\text{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_{\text{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_{\text{acc}};Q_{\text{rej}}).$ Aqui, $Q,$ $\Sigma ,$ $Q{\text{acc}}$ e $Q{\text{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

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 é $\mathbf {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

• Cadeias de Markov quânticas

Referências

• L. Accardi (2001), «Quantum stochastic processes», in: Hazewinkel, Michiel, Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer  (Provides an intro to quantum Markov chains.)
• Alex Brodsky, Nicholas Pipenger, "Characterization of 1-way Quantum Finite Automata", SIAM Journal on Computing 31(2002) pp 1456–1478.
• Vincent D. Blondel, Emmanual Jeandel, Pascal Koiran and Natacha Portier, "Decidable and Undecidable Problems about Quantum Automata", SIAM Journal on Computing 34 (2005) pp 1464–1473.