Pergunta unidirecional de exemplo de autômato quântico

8

Estou tentando esclarecer meu entendimento no exemplo apresentado na Seção 2.2 dos autômatos finitos quânticos de 1 via: fortalece as fraquezas e as generalizações (esse link alternativo também pode ser útil). Este exemplo fornece um exemplo muito simplificado de um 1-QFA com as seguintes regras de transição:

,Va|q0=12|q0+12|q1+12|qrej

,Va|q1=12|q0+12|q112|qrej

,V$|q0=|qrej

V$|q1=|qacc

Por exemplo, se eu estou em e eu processar um um como entrada, eu aplico a primeira regra. Meu entendimento é que eu teria um | | 1q0a chance de permanecer no estado| q0, um| | 1||12||2=14|q0 chances de progredir para o estado| q1e uma| | 1||12||2=14|q1 chances de terminar o cálculo e rejeitar a string.||12||2=12

Imagino que os autômatos pareçam com a seguinte imagem

insira a descrição da imagem aqui

No entanto, não tenho certeza se isso está correto. As probabilidades mencionadas no artigo para aceitação da cadeia são 1aa enquanto a probabilidade de rejeição é314 . Apenas imaginando se alguém poderia apontar uma falha ou validar o que eu tenho em mente conceitualmente para o exemplo.34

Obrigado.

Modelo de autômatos reformulado para refletir com mais precisão as probabilidades: insira a descrição da imagem aqui

Vincent Russo
fonte
1
Eu sugiro que você procure "superposição quântica". Parece que você está interpretando de maneira puramente probabilística, o que ignora a possibilidade de interferência, que é central na computação quântica.
Funkstar
q0qrej||12||2
1
Observe que a medida é parcial - ela não fornece um estado exato, a menos que seja um estado final. Dessa forma, você pode fazer uma medida (parcial) após aplicar uma transformação unitária correspondente a algum símbolo e, se ela não entrar em colapso para um estado final, ainda estará em uma superposição adequada, o que deixa aberta a possibilidade de interferência.
Funkstar
a12q0q112|q0+12|q1a|q0|q1
(12q0|+12q1|)(12|q0+12|q1+12|qrej)((12|q0+12|q112|qrej)) =(14q0|q0+14q1|q1)(12|q0+12|q112|qrej) =18|q0+18|q1

Respostas:

5

Va|q0|q1|q0q0||q1q1|. Em outras palavras, esses números não representam probabilidades, eles não correspondem aos resultados da medição a ser realizada. Portanto, rotular as setas do diagrama com esses números daria uma ilustração potencialmente enganosa de como o processo de medição está funcionando.

aVa

{|q0,|q1,|qacc,|qrej}
  • Pacc=|qaccqacc|
  • Prej=|qrejqrej|
  • Pnon=|q0q0|+|q1q1|

Em outras palavras, a medição tem três resultados possíveis: ( acc ) o autômato mede um estado de aceitação e pára; ( reje ) o autômato mede um estado de rejeição e pára; ( não ) o automatizado mede outra coisa, não para e lê o próximo símbolo (não estados para não parar).

(|q0+|q1)/2Pnon|q0|q1

Levando tudo em consideração, é fácil seguir o cálculo fornecido em sua referência principal . Para ilustrar tudo o que foi dito e, para ser completo, citarei aqui alguns comentários menores (embora eu tenha acrescentado algumas modificações, não sei se esse tipo de citação é aceitável; se não for , por favor, deixe-me conhecer ou editar a resposta você mesmo):

|q0

  1. Va12|q0+12|q1+12|qrej(1/2)2=1/2|qrej1/212|q0+12|q1

  2. 12|q0+12|q1Va

  3. V$$12|qrej+12|qacc(1/2)2=1/4qrej1/4qacc

1/41/2+1/4=3/4

Juan Bermejo Vega
fonte
1
Ótima resposta, muito obrigado por dedicar um tempo para escrevê-la em termos mais explícitos. Além disso, em uma nota lateral, existe alguma maneira óbvia ou talvez referência anterior que descreva uma representação visual de uma maneira mais precisa e não enganosa? Parece que talvez expor a evolução em algum tipo de estrutura semelhante a uma árvore permitiria uma melhor ilustração da ramificação que ocorre ao longo da execução dos autômatos. Obrigado novamente por sua ajuda.
Vincent Russo
1
@VincentRusso: você realmente não pode descrevê-lo de uma maneira baseada em árvores. A questão é que pode haver interferência destrutiva entre amplitudes nos vários 'estados' autômatos finitos; sendo esta a principal diferença entre computação estocástica e quântica. A representação gráfica do autômato não é realmente enganosa se você levar a sério o fato de estar descrevendo amplitudes para vetores, em vez de transições probabilísticas. É claro que, para os autômatos quânticos ou estocásticos, o modelo é na verdade sobre transformações lineares, de modo que a imagem está praticamente fora de questão.
Niel de Beaudrap
No início do capítulo 6 de Kaye, Laflamme, Mosca, há uma boa discussão sobre as diferenças entre computação probabilística clássica e computação quântica; os autores ilustram o texto com diagramas de estado. Na verdade, eles discutem que esses diagramas não são inteiramente adequados para descrever a interferência quântica - como Niel de Beaudrap apontou e bem explicou -. Pessoalmente, recomendo esta referência para outras leituras.
Juan Bermejo Vega
5

Juan Bermejo Vega fez um resumo preciso do que é dito no artigo original. Vou lhe dar uma descrição de nível superior.

Eu recomendarei, no seu caso, evitar pensar nas amplitudes como probabilidades por completo. Eles estão relacionados às probabilidades, mas isso não é especialmente útil para pensar nesses autômatos finitos. Eu suspeito que as coisas ficarão muito mais claras se você pensar nisso como uma receita um pouco abstrata para transformar vetores de valor complexo.

Quais vetores estamos transformando? Bem: suponha que você tenha um autômato finito com n estados. O autômato representa um modelo (sim, probabilístico) para transformar vetores, que a qualquer momento pode dar origem a uma decisão de aceitação ou rejeição.

  • HH
  • Vq:HHVqVq=IVcVc=IV$
  • Vce^1Vce^1q0

    1. aVa
    2. vuAuR|uA|2|uR|2
    3. (1|uA|2|uR|2)1/2
    4. Prossiga para a próxima letra.
  • Realizamos essas transformações para cada letra da palavra e também para um símbolo final $, que anexamos ao final.

O único momento em que as probabilidades entram em jogo é com o eixo de aceitação e rejeição . Embora esse modelo de computação seja obviamente inspirado por autômatos finitos, é simples não útil interpretar qualquer um dos outros coeficientes do vetor, em qualquer ponto do tempo (mesmo no final!), Como probabilidades.

Observe que as probabilidades de aceitação e rejeição em cada intervalo de tempo são probabilidades condicionais , isto é  , dependem do cálculo ainda não ter sido interrompido; se você quiser calcular a probabilidade total de aceitação / rejeição, poderá fazê-lo com mais facilidade dispensando a etapa de "renormalização" na evolução (a parte em que multiplicamos pelo valor da raiz quadrada inversa; mas ainda definindo a aceitação / rejeito os coeficientes para zero se o cálculo continuar) e simplesmente some todas as contribuições probabilísticas para aceitar / rejeitar que surjam ao longo do caminho.

Niel de Beaudrap
fonte
1
Niel, obrigado novamente por seu comentário. Foi muito útil obter uma imagem mais intuitiva de como esse cálculo ocorre. Muito obrigado por reservar um tempo para explicar, agora está muito mais claro para mim.
22820 Vincent Vincent
3

Você está assumindo incorretamente que o estado entra em colapso total (para um estado de base computacional) após a leitura de cada símbolo. A medição em cada estágio é apenas parcial.

Shitikanth
fonte
Fiquei com a impressão de que, uma vez que isso está utilizando o modelo "meça muitos", uma medição é executada em cada etapa do cálculo, que reduz a superposição a um valor probabilístico definido.
Vincent Russo
@Vincent Russo Você está certo de que o estado é medido para cada símbolo que é lido.
Funkstar 31/03/12
Penso que um QFA em que o estado do autômato é medido após cada passo seria completamente equivalente a uma cadeia de Markov. Então, qual seria a motivação para estudá-los?
Shitikanth
3
Eu só queria mostrar por que o seu "modelo de autômato retrabalhado" não descreve com precisão o sistema QFA. Isso ocorre, de fato, porque o autômato não entra em colapso completo na base computacional a cada etapa.
Shitikanth 04/04
2
De qualquer forma, acho que a pergunta já foi respondida com clareza suficiente. Não vamos nos perder em detalhes técnicos.
Shitikanth 04/04