En computación cuántica , los autómatas cuánticos finitos ( QFA ) o máquinas de estados cuánticos son un análogo cuántico de los autómatas probabilísticos o un proceso de decisión de Markov . Proporcionan una abstracción matemática de las computadoras cuánticas del mundo real . Se pueden definir varios tipos de autómatas, incluidos los de medida una vez y los de medida muchas . Los autómatas cuánticos finitos también pueden entenderse como la cuantificación de subdesplazamientos de tipo finito , o como una cuantificación de cadenas de Markov . Los QFA son, a su vez, casos especiales de autómatas finitos geométricos o autómatas finitos topológicos .
Los autómatas funcionan recibiendo una cadena de letras de longitud finita de un alfabeto finito y asignando a cada una de esas cadenas una probabilidad que indica la probabilidad de que el autómata esté en un estado de aceptación ; es decir, indicar si el autómata aceptó o rechazó la cadena.
Los lenguajes aceptados por las QFA no son los lenguajes regulares de los autómatas finitos deterministas , ni tampoco los lenguajes estocásticos de los autómatas finitos probabilísticos . El estudio de estos lenguajes cuánticos sigue siendo un área de investigación activa.
Existe una forma sencilla e intuitiva de comprender los autómatas cuánticos finitos. Se comienza con una interpretación teórica de grafos de los autómatas finitos deterministas (DFA). Un DFA se puede representar como un gráfico dirigido , con estados como nodos en el gráfico y flechas que representan transiciones de estado. Cada flecha está etiquetada con un posible símbolo de entrada, de modo que, dado un estado específico y un símbolo de entrada, la flecha apunta al siguiente estado. Una forma de representar dicho gráfico es mediante un conjunto de matrices de adyacencia , con una matriz para cada símbolo de entrada. En este caso, la lista de posibles estados de DFA se escribe como un vector de columna . Para un símbolo de entrada dado, la matriz de adyacencia indica cómo cualquier estado dado (fila en el vector de estado) pasará al siguiente estado; una transición de estado viene dada por la multiplicación de matrices .
Se necesita una matriz de adyacencia distinta para cada símbolo de entrada posible, ya que cada símbolo de entrada puede dar como resultado una transición diferente. Las entradas en la matriz de adyacencia deben ser ceros y unos. Para cualquier columna determinada de la matriz, solo una entrada puede ser distinta de cero: esta es la entrada que indica la siguiente transición de estado (única). De manera similar, el estado del sistema es un vector de columna, en el que solo una entrada es distinta de cero: esta entrada corresponde al estado actual del sistema. Denotemos el conjunto de símbolos de entrada. Para un símbolo de entrada determinado , escríbalo como la matriz de adyacencia que describe la evolución del DFA a su siguiente estado. Luego, el conjunto describe completamente la función de transición de estado del DFA. Sea Q el conjunto de posibles estados del DFA. Si hay N estados en Q , entonces cada matriz es N por N -dimensional. El estado inicial corresponde a un vector de columna con un uno en la q 0 'ésima fila. Un estado general q es entonces un vector columna con un uno en la q'ésima fila. Por abuso de notación , sean q 0 y q también denoten estos dos vectores. Luego, después de leer los símbolos de entrada de la cinta de entrada, el estado del DFA vendrá dado por Las transiciones de estado están dadas por una multiplicación de matrices ordinaria (es decir, multiplicar q 0 por , etc. ); el orden de aplicación se "invierte" sólo porque seguimos la notación estándar del álgebra lineal .
La descripción anterior de un DFA, en términos de operadores lineales y vectores, casi pide una generalización, reemplazando el vector de estado q por algún vector general y las matrices por algunos operadores generales. Esto es esencialmente lo que hace un QFA: reemplaza q por un vector unitario y por matrices unitarias . Otras generalizaciones similares también resultan obvias: el vector q puede tener alguna distribución en una variedad ; el conjunto de matrices de transición se convierten en automorfismos de la variedad; esto define un autómata finito topológico. De manera similar, las matrices podrían tomarse como automorfismos de un espacio homogéneo ; esto define un autómata geométrico finito.
Antes de pasar a la descripción formal de una QFA, hay dos generalizaciones dignas de mención que deben mencionarse y comprenderse. El primero es el autómata finito no determinista (NFA). En este caso, el vector q se reemplaza por un vector que puede tener más de una entrada distinta de cero. Dicho vector representa entonces un elemento del conjunto potencia de Q ; es solo una función indicadora en Q. Asimismo, las matrices de transición de estado se definen de tal manera que una columna determinada puede tener varias entradas distintas de cero. De manera equivalente, las operaciones de multiplicación y suma realizadas durante la multiplicación de matrices por componentes deben reemplazarse por operaciones booleanas y/o, es decir, de modo que se trabaje con un anillo de característica 2 .
Un teorema muy conocido establece que, para cada AFD, existe un AFN equivalente, y viceversa . Esto implica que el conjunto de idiomas que pueden reconocer los DFA y los NFA son los mismos; estos son los idiomas regulares . En la generalización a QFA, el conjunto de idiomas reconocidos será diferente. Describir ese conjunto es uno de los problemas de investigación más destacados en la teoría QFA.
Otra generalización que debería resultar inmediatamente evidente es utilizar una matriz estocástica para las matrices de transición y un vector de probabilidad para el estado; esto da un autómata finito probabilístico . Las entradas en el vector de estado deben ser números reales, positivos y su suma es uno, para que el vector de estado se interprete como una probabilidad. Las matrices de transición deben conservar esta propiedad: por eso deben ser estocásticas. Cada vector de estado debe imaginarse especificando un punto en un símplex ; por tanto, se trata de un autómata topológico, siendo el simplex la variedad y las matrices estocásticas automorfismos lineales del simplex sobre sí mismo. Dado que cada transición es (esencialmente) independiente de la anterior (si ignoramos la distinción entre lenguas aceptadas y rechazadas), la PFA se convierte esencialmente en una especie de cadena de Markov .
Por el contrario, en un QFA, la variedad es un espacio proyectivo complejo y las matrices de transición son matrices unitarias. Cada punto corresponde a un estado mecánico cuántico (puro) ; Se puede pensar que las matrices unitarias gobiernan la evolución temporal del sistema (a saber, en la imagen de Schrödinger ). La generalización de estados puros a estados mixtos debería ser sencilla: un estado mixto es simplemente una distribución de probabilidad teórica de medidas en .
Un punto digno de contemplar son las distribuciones que resultan en la variedad durante la entrada de un idioma. Para que un autómata sea "eficiente" en el reconocimiento de una lengua, esa distribución debe ser "lo más uniforme posible". Esta necesidad de uniformidad es el principio subyacente detrás de los métodos de máxima entropía : estos simplemente garantizan un funcionamiento nítido y compacto del autómata. En otras palabras, los métodos de aprendizaje automático utilizados para entrenar modelos ocultos de Markov también se generalizan a los QFA: el algoritmo de Viterbi y el algoritmo de avance-retroceso se generalizan fácilmente a los QFA.
Aunque el estudio de QFA se popularizó en el trabajo de Kondacs y Watrous en 1997 [1] y más tarde por Moore y Crutchfeld [2] , fueron descritos ya en 1971 por Ion Baianu. [3] [4]
Cris Moore y James P. Crutchfield introdujeron los autómatas de medida única . [2] Pueden definirse formalmente de la siguiente manera.
Al igual que con un autómata finito ordinario , se considera que el autómata cuántico tiene posibles estados internos, representados en este caso por un qudit de estado . Más precisamente, el qudit de estado es un elemento del espacio proyectivo complejo de dimensiones , que lleva un producto interno que es la métrica de Fubini-Study .
Las transiciones de estado , matrices de transición o gráficos de Bruijn están representadas por una colección de matrices unitarias , con una matriz unitaria para cada letra . Es decir, dada una letra de entrada , la matriz unitaria describe la transición del autómata desde su estado actual al siguiente estado :
Así, los triples forman un semiautómata cuántico .
El estado de aceptación del autómata viene dado por una matriz de proyección , de modo que, dado un estado cuántico -dimensional , la probabilidad de estar en el estado de aceptación es
La probabilidad de que la máquina de estados acepte una cadena de entrada finita dada está dada por
Aquí, se entiende que el vector representa el estado inicial del autómata, es decir, el estado en el que se encontraba el autómata antes de comenzar a aceptar la entrada de cadena. Se entiende que la cadena vacía es solo la matriz unitaria, de modo que
es solo la probabilidad de que el estado inicial sea un estado aceptado.
Debido a que la acción izquierda de on invierte el orden de las letras en la cadena , no es raro que los QFA se definan usando una acción derecha en los estados de transposición hermitiana , simplemente para mantener el mismo orden de las letras.
Un autómata cuántico finito acepta con probabilidad un idioma sobre el alfabeto (y un estado inicial fijo dado ), si, para todas las oraciones del idioma, se tiene .
Considere el autómata finito determinista clásico dado por la tabla de transición de estados
El estado cuántico es un vector, en notación bra-ket.
con los números complejos normalizados de modo que
Las matrices de transición unitarias son
y
Tomando como estado de aceptación, la matriz de proyección es
Como debería ser evidente, si el estado inicial es el estado puro o , entonces el resultado de hacer funcionar la máquina será exactamente idéntico al de la máquina determinista clásica de estados finitos. En particular, existe un lenguaje aceptado por este autómata con probabilidad uno, para estos estados iniciales, y es idéntico al lenguaje regular para el DFA clásico, y viene dado por la expresión regular :
El comportamiento no clásico ocurre si ambos y son distintos de cero. Un comportamiento más sutil ocurre cuando las matrices y no son tan simples; véase, por ejemplo, la curva de Rham como ejemplo de una máquina cuántica de estados finitos que actúa sobre el conjunto de todas las cadenas binarias finitas posibles.
Kondacs y Watrous introdujeron los autómatas de medidas múltiples en 1997. [1] El marco general se parece al del autómata de medidas únicas, excepto que en lugar de haber una proyección, al final hay una proyección o medición cuántica . se realiza después de leer cada letra. A continuación se presenta una definición formal.
El espacio de Hilbert se descompone en tres subespacios ortogonales
En la literatura, estos subespacios ortogonales suelen formularse en términos del conjunto de vectores de base ortogonales para el espacio de Hilbert . Este conjunto de vectores base se divide en subconjuntos y , de modo que
es el tramo lineal de los vectores base en el conjunto aceptado. El espacio de rechazo se define de manera análoga y el espacio restante se denomina subespacio sin parada . Hay tres matrices de proyección, y , cada una de las cuales se proyecta al subespacio respectivo:
etcétera. El análisis de la cadena de entrada se realiza de la siguiente manera. Considere que el autómata está en un estado . Después de leer una letra de entrada , el autómata estará en el estado
En este punto, se realiza una medición cuyos tres resultados posibles tienen espacios propios ,, en el estado , en cuyo momento su función de onda colapsa en uno de los tres subespacios o o . La probabilidad de colapso en el subespacio de "aceptación" está dada por
y de manera análoga para los otros dos espacios.
Si la función de onda se ha colapsado en los subespacios de "aceptación" o "rechazo", el procesamiento posterior se detiene. De lo contrario, el procesamiento continúa, se lee la siguiente letra de la entrada y se aplica a lo que debe ser un estado propio de . El procesamiento continúa hasta que se lee toda la cadena o la máquina se detiene. A menudo, se añaden símbolos adicionales y $ al alfabeto, para que actúen como marcadores finales izquierdo y derecho de la cadena.
En la literatura, el autómata de muchas medidas a menudo se denota por la tupla . Aquí, , y son como se definen anteriormente. El estado inicial se denota por . Las transformaciones unitarias se indican mediante el mapa ,
de modo que
A partir de 2019, la mayoría de las computadoras cuánticas son implementaciones de autómatas finitos cuánticos de medida una vez, y los sistemas de software para programarlos exponen la preparación del estado de , la medición y una elección de transformaciones unitarias , como la puerta NOT controlada , la transformada de Hadamard y otras. Puertas lógicas cuánticas , directamente al programador.
La principal diferencia entre las computadoras cuánticas del mundo real y el marco teórico presentado anteriormente es que la preparación del estado inicial nunca puede dar como resultado un estado puro puntual , ni se pueden aplicar con precisión los operadores unitarios. Por tanto, el estado inicial debe considerarse como un estado mixto.
para alguna distribución de probabilidad que caracterice la capacidad de la maquinaria para preparar un estado inicial cercano al estado puro inicial deseado . Este estado no es estable, pero sufre cierta cantidad de decoherencia cuántica con el tiempo. Tampoco es posible realizar mediciones precisas y, en su lugar, se utilizan medidas positivas valoradas por el operador para describir el proceso de medición. Finalmente, cada transformación unitaria no es una puerta lógica cuántica única y claramente definida, sino más bien una mezcla
para alguna distribución de probabilidad que describa qué tan bien la maquinaria puede efectuar la transformación deseada .
Como resultado de estos efectos, la evolución temporal real del estado no puede tomarse como un punto puro de precisión infinita, operado por una secuencia de transformaciones arbitrariamente bruscas, sino más bien como un proceso ergódico , o más exactamente, un proceso de mezcla que sólo concatena transformaciones en un estado, sino que también lo difama a lo largo del tiempo.
No existe una analogía cuántica con el autómata de empuje hacia abajo o la máquina apilable . Esto se debe al teorema de no clonación : no hay forma de hacer una copia del estado actual de la máquina, colocarla en una pila para consultarla más adelante y luego volver a ella.
Las construcciones anteriores indican cómo el concepto de autómata cuántico finito puede generalizarse a espacios topológicos arbitrarios . Por ejemplo, se puede tomar algún espacio simétrico de Riemann ( N -dimensional) para reemplazar a . En lugar de las matrices unitarias, se utilizan las isometrías de la variedad de Riemann o, más generalmente, algún conjunto de funciones abiertas apropiadas para el espacio topológico dado. Se puede considerar que el estado inicial es un punto en el espacio. El conjunto de estados de aceptación puede considerarse un subconjunto arbitrario del espacio topológico. Entonces se dice que este autómata topológico acepta un lenguaje formal si el punto, después de la iteración por los homeomorfismos, cruza el conjunto aceptado. Pero, por supuesto, esto no es más que la definición estándar de autómata M. El comportamiento de los autómatas topológicos se estudia en el campo de la dinámica topológica .
El autómata cuántico se diferencia del autómata topológico en que, en lugar de tener un resultado binario (¿el punto iterado está o no en el conjunto final?), uno tiene una probabilidad. La probabilidad cuántica es el (cuadrado de) el estado inicial proyectado sobre algún estado final P ; eso es . Pero esta amplitud de probabilidad es solo una función muy simple de la distancia entre el punto y el punto en , bajo la métrica de distancia dada por la métrica del Estudio Fubini . En resumen, la probabilidad cuántica de que un idioma sea aceptado se puede interpretar como una métrica, siendo la probabilidad de aceptar la unidad, si la distancia métrica entre los estados inicial y final es cero, y en caso contrario la probabilidad de aceptar es menor que uno. si la distancia métrica es distinta de cero. Por lo tanto, se deduce que el autómata cuántico finito es solo un caso especial de un autómata geométrico o un autómata métrico , donde se generaliza a algún espacio métrico , y la medida de probabilidad se reemplaza por una función simple de la métrica en ese espacio.
