En computación cuántica , los autómatas finitos cuánticos ( QFA ) o máquinas de estados cuánticos son un análogo cuántico de los autómatas probabilísticos o de un proceso de decisión de Markov . Proporcionan una abstracción matemática de los ordenadores cuánticos del mundo real . Se pueden definir varios tipos de autómatas, incluidos los de medición única y los de medición múltiple . Los autómatas finitos cuánticos 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, indicando si el autómata aceptó o rechazó la cadena.
Los lenguajes aceptados por los 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 activa de investigación.
Existe una forma sencilla e intuitiva de entender los autómatas finitos cuánticos. Se comienza con una interpretación de los autómatas finitos deterministas (AFD) desde la perspectiva de la teoría de grafos . Un AFD se puede representar como un grafo dirigido , con estados como nodos en el grafo 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 un grafo de este tipo 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 AFD se escribe como un vector columna . Para un símbolo de entrada dado, la matriz de adyacencia indica cómo cualquier estado dado (fila en el vector de estado) realizará la transición al siguiente estado; una transición de estado se da mediante 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 dada en 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 columna, en el que solo una entrada es distinta de cero: esta entrada corresponde al estado actual del sistema. Sea el conjunto de símbolos de entrada. Para un símbolo de entrada dado , escriba como la matriz de adyacencia que describe la evolución del DFA a su siguiente estado. El conjunto describe entonces completamente la función de transición de estado del DFA. Sea Q el conjunto de estados posibles del DFA. Si hay N estados en Q , entonces cada matriz es N por N -dimensional. El estado inicial corresponde a un vector columna con un uno en la fila q 0 '. Un estado general q es entonces un vector columna con un uno en la fila q' . Por abuso de notación , sea q 0 y q también denoten estos dos vectores. Entonces, después de leer los símbolos de entrada de la cinta de entrada, el estado del DFA estará dado por Las transiciones de estado se dan por la multiplicación de matrices ordinarias (es decir, multiplicar q 0 por , etc. ); el orden de aplicación se 'invierte' solo porque seguimos la notación estándar del álgebra lineal .
La descripción anterior de un AFD, 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 AFD: reemplaza q por un vector unitario , y por matrices unitarias . Otras generalizaciones similares también se vuelven obvias: el vector q puede ser alguna distribución en una variedad ; el conjunto de matrices de transición se convierte 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 finito geométrico.
Antes de pasar a la descripción formal de un QFA, hay dos generalizaciones notables que deben mencionarse y entenderse. La primera 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 que no sea cero. Dicho vector representa entonces un elemento del conjunto potencia de Q ; es solo una función indicadora en Q . Del mismo modo, las matrices de transición de estado se definen de tal manera que una columna dada puede tener varias entradas distintas de cero. Equivalentemente, las operaciones de multiplicación-suma realizadas durante la multiplicación de matrices componente por componente deben reemplazarse por operaciones booleanas and-or, es decir, de modo que se esté trabajando con un anillo de característica 2 .
Un conocido teorema establece que, para cada DFA, existe un NFA equivalente, y viceversa . Esto implica que el conjunto de lenguajes que pueden ser reconocidos por DFA y NFA son los mismos; estos son los lenguajes regulares . En la generalización a QFA, el conjunto de lenguajes reconocidos será diferente. Describir ese conjunto es uno de los problemas de investigación pendientes en la teoría de QFA.
Otra generalización que debería ser 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 sumar uno, para que el vector de estado se interprete como una probabilidad. Las matrices de transición deben preservar esta propiedad: es por eso que deben ser estocásticas. Cada vector de estado debe imaginarse como especificando un punto en un símplex ; por lo tanto, este es un autómata topológico, donde el símplex es la variedad y las matrices estocásticas son automorfismos lineales del símplex sobre sí mismo. Dado que cada transición es (esencialmente) independiente de la anterior (si ignoramos la distinción entre lenguajes aceptados y rechazados), el AFP 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 en corresponde a un estado mecánico cuántico (puro) ; se puede pensar que las matrices unitarias gobiernan la evolución temporal del sistema (es decir, 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 de teoría de medidas en .
Un punto que vale la pena considerar son las distribuciones que resultan en la variedad durante la entrada de un lenguaje. Para que un autómata sea "eficiente" en el reconocimiento de un lenguaje, 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 al QFA.
Aunque el estudio de los 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]
Los autómatas de medida única fueron introducidos por Cris Moore y James P. Crutchfield . [2] Pueden definirse formalmente de la siguiente manera.
Al igual que 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 dimensión 1 , que lleva un producto interno que es la métrica de Fubini-Study .
Las transiciones de estado , matrices de transición o grafos de De Bruijn se representan mediante una colección de matrices unitarias , con una matriz unitaria por cada letra . Es decir, dada una letra de entrada , la matriz unitaria describe la transición del autómata desde su estado actual a su siguiente estado :
De esta manera, la tripleta forma 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 empezar a aceptar la entrada de cadena. La cadena vacía se entiende simplemente como la matriz unitaria, de modo que
es simplemente 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 utilizando una acción derecha en los estados de transposición hermítica , simplemente para mantener el mismo orden de las letras.
Un lenguaje sobre el alfabeto es aceptado con probabilidad por un autómata cuántico finito (y un estado inicial fijo dado ), si, para todas las oraciones del lenguaje, uno tiene .
Consideremos 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 unitaria 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 ejecutar la máquina será exactamente idéntico al de la máquina de estados finitos determinista clásica. 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 está dado por la expresión regular :
El comportamiento no clásico se produce si tanto y como no son cero. Un comportamiento más sutil se produce cuando las matrices y no son tan simples; véase, por ejemplo, la curva de De Rham como ejemplo de una máquina de estados finitos cuántica que actúa sobre el conjunto de todas las posibles cadenas binarias finitas.
Los autómatas de medida múltiple fueron introducidos por Kondacs y Watrous en 1997. [1] El marco general se asemeja al del autómata de medida única, excepto que en lugar de haber una proyección, al final hay una proyección, o medición cuántica , que 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 base ortogonales para el espacio de Hilbert . Este conjunto de vectores base se divide en subconjuntos y , de modo que
es el espacio lineal de los vectores base en el conjunto aceptado. El espacio rechazado se define de manera análoga y el espacio restante se designa como subespacio sin detención . Hay tres matrices de proyección, , y , cada una de las cuales se proyecta al subespacio respectivo:
y así sucesivamente. El análisis de la cadena de entrada se realiza de la siguiente manera. Supongamos 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 , momento en el que su función de onda colapsa en uno de los tres subespacios o o . La probabilidad de colapsar en el subespacio "aceptar" está dada por
y análogamente para los otros dos espacios.
Si la función de onda ha colapsado en los subespacios "aceptar" o "rechazar", entonces el procesamiento posterior se detiene. De lo contrario, el procesamiento continúa, con la siguiente letra leída de la entrada y aplicada 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 agregan 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 medida múltiple se denota a menudo por la tupla . Aquí, , , y son como se definieron anteriormente. El estado inicial se denota por . Las transformaciones unitarias se denotan por 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 medición única, y los sistemas de software para programarlos exponen la preparación del estado , 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 los ordenadores cuánticos 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 tampoco se pueden aplicar con precisión los operadores unitarios. Por lo tanto, el estado inicial debe tomarse como un estado mixto.
para alguna distribución de probabilidad que caracteriza la capacidad de la maquinaria para preparar un estado inicial cercano al estado puro inicial deseado . Este estado no es estable, sino que sufre cierta cantidad de decoherencia cuántica a lo largo del tiempo. Tampoco es posible realizar mediciones precisas, y en su lugar se utilizan medidas positivas con valores de operador para describir el proceso de medición. Finalmente, cada transformación unitaria no es una única puerta lógica cuántica claramente definida, sino más bien una mezcla
para alguna distribución de probabilidad que describe 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 agudas, 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, pero también difumina el estado a lo largo del tiempo.
No existe un análogo cuántico del autómata de empuje hacia abajo o de la máquina de pila . 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 referencia posterior y luego regresar a ella.
Las construcciones anteriores indican cómo el concepto de un autómata finito cuántico 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, de manera más general, algún conjunto de funciones abiertas apropiadas para el espacio topológico dado. El estado inicial puede tomarse como un punto en el espacio. El conjunto de estados aceptados puede tomarse como algún subconjunto arbitrario del espacio topológico. Entonces se dice que un lenguaje formal es aceptado por este autómata topológico si el punto, después de la iteración por los homeomorfismos, intersecta el conjunto aceptado. Pero, por supuesto, esto no es nada más que la definición estándar de un 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?), se tiene una probabilidad. La probabilidad cuántica es el (cuadrado del) estado inicial proyectado sobre algún estado final P ; es decir . 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 de Fubini-Study . Para recapitular, la probabilidad cuántica de que un lenguaje sea aceptado puede interpretarse 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 de lo contrario la probabilidad de aceptar es menor que uno, si la distancia métrica no es cero. Por lo tanto, se deduce que el autómata finito cuántico 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.
