Pregunta de ejemplo de autómatas finitos cuánticos de 1 vía

8

Estoy tratando de aclarar mi comprensión en el ejemplo presentado en la Sección 2.2 de Autómatas cuánticos finitos de 1 vía: fortalezas, debilidades y generalizaciones (este enlace alternativo también puede ser útil). Este ejemplo proporciona un ejemplo muy simplificado de un 1-QFA con las siguientes reglas de transición:

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

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

,V$|q0=|qrej

V$|q1=|qacc

Por ejemplo, si estoy en y proceso un a como entrada, aplico la primera regla. Tengo entendido que tendría un | El | 1q0a posibilidades de permanecer en el estado| q0, un| El | 1||12||2=14|q0 posibilidades de progresar al estado| q1y una| El | 1||12||2=14|q1 posibilidades de terminar el cálculo y rechazar la cadena.||12||2=12

Me imagino los autómatas para que esto se vea como la siguiente imagen

ingrese la descripción de la imagen aquí

Sin embargo, no estoy completamente seguro de si eso es correcto. Las probabilidades mencionadas en el documento para la aceptación de la cadena es 1aa mientras que la probabilidad de rechazo es314 . Solo me pregunto si alguien podría señalar una falla o validar lo que tengo conceptualmente en mente para el ejemplo.34

Gracias.

Se modificó el modelo de autómatas para reflejar con mayor precisión las probabilidades: ingrese la descripción de la imagen aquí

Vincent Russo
fuente
1
Le sugiero que busque "superposición cuántica". Parece que lo estás interpretando de manera puramente probabilística, lo que ignora la posibilidad de interferencia, que es central en la computación cuántica.
funkstar
q0qrej||12||2
1
Tenga en cuenta que la medición es parcial: no le proporciona un estado exacto a menos que sea un estado final. De esa manera, puede hacer una medición (parcial) después de aplicar una transformación unitaria correspondiente a algún símbolo, y si no colapsa a un estado final, seguirá estando en una superposición adecuada, lo que deja abierta la posibilidad de interferencia.
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

Respuestas:

5

Va|q0|q1|q0q0||q1q1|. En otras palabras, estos números no representan probabilidades, no corresponden a los resultados de la medición a realizar. Por lo tanto, etiquetar las flechas del diagrama con estos números daría una ilustración potencialmente engañosa de cómo está funcionando el proceso de medición.

aVa

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

En otras palabras, la medición tiene tres resultados posibles: ( acc ) el autómata mide un estado de aceptación y se detiene; ( rej ) el autómata mide un estado de rechazo y se detiene; ( no ) el automatismo mide otra cosa, no se detiene y lee el siguiente símbolo (no estados para no detenerse).

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

Teniendo en cuenta todo lo dicho, es fácil seguir el cálculo dado en su referencia principal . Para ilustrar todo lo dicho y, para completar, lo citaré aquí con algunos comentarios menores (aunque agregué algunas modificaciones, no sé si este tipo de cita es aceptable; si no lo es , por favor, permítame saber o editar la respuesta usted mismo):

|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
fuente
1
Una respuesta excelente, muchas gracias por tomarse el tiempo para escribirla en términos más explícitos. Además, en una nota al margen, ¿hay alguna forma obvia o quizás una referencia previa que represente una representación visual de una manera más precisa y no engañosa? Parece que tal vez presentar la evolución en algún tipo de estructura similar a un árbol permitiría una mejor ilustración de la ramificación que ocurre durante la ejecución de los autómatas. De nuevo, gracias por tu ayuda.
Vincent Russo el
1
@VincentRusso: realmente no puedes describirlo de una manera basada en árboles. El punto es que puede haber interferencia destructiva entre las amplitudes en los diversos 'estados' de autómatas finitos; Esta es la principal diferencia entre la computación estocástica y cuántica. La representación gráfica del autómata no es realmente engañosa si te tomas muy en serio que está describiendo amplitudes para vectores, en lugar de transiciones probabilísticas. Por supuesto, tanto para los autómatas cuánticos como para los estocásticos, el modelo trata sobre transformaciones lineales, por lo que la imagen está más allá del punto.
Niel de Beaudrap
Al comienzo del capítulo 6 de Kaye, Laflamme, Mosca, hay una buena discusión sobre las diferencias entre la computación cuántica y probabilística clásica; Los autores ilustran el texto con diagramas de estado. De hecho, discuten que estos diagramas no son del todo adecuados para describir la interferencia cuántica, como señaló y explicó Niel de Beaudrap. Yo personalmente recomiendo esta referencia para leer más.
Juan Bermejo Vega
5

Juan Bermejo Vega ha dado un resumen preciso de lo que se dice en el documento original. Te daré una descripción de nivel superior.

Recomendaré, en su caso, evitar pensar en las amplitudes como probabilidades por completo. Están relacionados con las probabilidades, pero no es especialmente útil pensar en estos autómatas finitos. Sospecho que las cosas serán mucho más claras si piensas en esto como una receta ligeramente abstracta para transformar vectores de valores complejos.

¿Qué vectores estamos transformando? Bueno: suponga que tiene un autómata finito con n estados. El autómata representa un modelo (sí, probabilístico) para transformar vectores, que en cualquier momento puede dar lugar a una decisión de aceptación o rechazo.

  • 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. Proceda a la siguiente carta.
  • Realizamos estas transformaciones para cada letra de la palabra, y también para un símbolo de terminación $ que agregamos al final.

Las únicas probabilidades en que entran en juego es con el eje de aceptación y rechazo . Si bien este modelo de computación está obviamente inspirado en autómatas finitos, es simple no útil interpretar ninguno de los otros coeficientes del vector, en ningún momento (¡incluso al final!), Como probabilidades.

Tenga en cuenta que las probabilidades de aceptar y rechazar en cada paso de tiempo son probabilidades condicionales , es decir  , dependen de que el cálculo aún no se haya detenido; si desea calcular la probabilidad total de aceptación / rechazo, puede hacerlo más fácilmente prescindiendo del paso de "renormalización" en la evolución (la parte donde multiplicamos por el valor de la raíz cuadrada inversa, pero aún estableciendo la aceptación / rechazar los coeficientes a cero si el cálculo continúa), y simplemente sumar todas las contribuciones probabilísticas para aceptar / rechazar que surjan en el camino.

Niel de Beaudrap
fuente
1
Niel, gracias de nuevo por tu comentario también. Fue muy útil obtener una imagen más intuitiva de cómo se realiza este cálculo. Muchas gracias por tomarse el tiempo para explicar, ahora es mucho más claro para mí.
Vincent Russo el
3

Asume incorrectamente que el estado colapsa completamente (a un estado de base computacional) después de leer cada símbolo. La medición en cada etapa es solo parcial.

Shitikanth
fuente
Tenía la impresión de que, dado que esto está utilizando el modelo de "medir muchos", se realiza una medición en cada paso del cálculo, que colapsa la superposición a un valor probabilístico definido.
Vincent Russo
@ Vincent Russo Tiene razón en que el estado se mide para cada símbolo que se lee.
funkstar
Creo que un QFA donde se mide el estado del autómata después de cada paso sería completamente equivalente a una cadena de Markov. Entonces, ¿cuál sería la motivación para estudiarlos?
Shitikanth
3
Solo quería mostrar por qué su "modelo de autómata reelaborado" no describe con precisión el sistema QFA. Esto es, de hecho, porque el autómata no colapsa completamente en la base computacional en cada paso.
Shitikanth
2
En cualquier caso, creo que la pregunta ya ha sido respondida con suficiente claridad. No nos perdamos en tecnicismos.
Shitikanth