Autómata finito cuántico

En computación cuántica , los autómatas finitos cuánticos ( AFC ) 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 las computadoras cuánticas del mundo real . Se pueden definir varios tipos de autómatas, incluidos los autómatas de medición única y de medición múltiple . Los autómatas finitos cuánticos también pueden entenderse como la cuantización de subdesplazamientos de tipo finito o como la cuantización de cadenas de Markov . Los AFC son, a su vez, casos especiales de autómatas finitos geométricos o topológicos .

Los autómatas funcionan recibiendo una cadena de longitud finita.${\displaystyle \sigma =(\sigma _{0},\sigma _{1},\dots ,\sigma _{k})}$de letras${\displaystyle \sigma _{i}}$a partir de un alfabeto finito${\displaystyle \Sigma }$y asignando a cada una de esas cadenas una probabilidad${\displaystyle \operatorname {Pr} (\sigma )}$indicando 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 autómatas finitos cuánticos (AFQ) 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.

Hay una forma simple e intuitiva de entender los autómatas finitos cuánticos. Se comienza con una interpretación de teoría de grafos de los autómatas finitos deterministas (AFD). Un AFD se puede representar como un grafo dirigido etiquetado , 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 dicho grafo es mediante un conjunto de matrices de adyacencia , con una matriz para cada símbolo de entrada. En este caso, una lista de posibles estados del 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) hará la transición 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 posible símbolo de entrada, ya que cada símbolo de entrada puede dar lugar a una transición diferente. Las entradas de la matriz de adyacencia deben ser ceros y unos. Para cualquier columna dada 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 columna, en el que solo una entrada es distinta de cero: esta entrada corresponde al estado actual del sistema.${\displaystyle \Sigma }$denotamos el conjunto de símbolos de entrada. Para un símbolo de entrada dado${\displaystyle \alpha \in \Sigma }$, escribir${\displaystyle U_{\alpha }}$como la matriz de adyacencia que describe la evolución del DFA a su siguiente estado. El conjunto${\displaystyle \{U_{\alpha }|\alpha \in \Sigma \}}$entonces describe 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${\displaystyle U_{\alpha }}$es de dimensión N por N. El estado inicial${\displaystyle q_{0}\in Q}$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 ₀ y q también denoten estos dos vectores. Entonces, después de leer los símbolos de entrada${\displaystyle \alpha \beta \gamma \cdots }$A partir de la cinta de entrada, el estado del DFA vendrá dado por${\displaystyle q=\cdots U_{\gamma }U_{\beta }U_{\alpha }q_{0}.}$Las transiciones de estado se dan mediante la multiplicación matricial ordinaria (es decir, multiplicar q ₀ por${\displaystyle U_{\alpha }}$, etc. ); el orden de aplicación se "invierte" únicamente 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 exige una generalización, reemplazando el vector de estado q por algún vector general y las matrices.${\displaystyle \{U_{\alpha}\}}$mediante algunos operadores generales. Esto es esencialmente lo que hace un QFA: reemplaza q por un vector unitario y el${\displaystyle \{U_{\alpha}\}}$mediante matrices unitarias . Otras generalizaciones similares también resultan evidentes: el vector q puede ser una 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 importantes que deben mencionarse y comprenderse. 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 distinta de cero. Dicho vector representa entonces un elemento del conjunto potencia de Q ; es simplemente una función indicadora en Q. De igual modo, las matrices de transición de estado${\displaystyle \{U_{\alpha}\}}$Se definen de tal manera que una columna determinada puede contener varios valores distintos de cero. De forma equivalente, las operaciones de multiplicación y suma realizadas durante la multiplicación de matrices componente a componente deben sustituirse por operaciones booleanas AND-OR para mantener la semántica intacta.

Un teorema bien conocido establece que, para cada autómata finito determinista (AFD), existe un autómata finito no determinista (AFND) equivalente, y viceversa . Esto implica que el conjunto de lenguajes que pueden ser reconocidos por los AFD y los AFND es el mismo; estos son los lenguajes regulares . En la generalización a los autómatas finitos cualitativos (AFQ), el conjunto de lenguajes reconocidos será diferente al de los lenguajes regulares. Describir dicho conjunto es uno de los problemas de investigación más importantes en la teoría de los AFQ.

Otra generalización que debería ser inmediatamente evidente es el uso de una matriz estocástica para las matrices de transición y un vector de probabilidad para el estado; esto da como resultado 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: por eso deben ser estocásticas. Cada vector de estado debe imaginarse como la especificación de un punto en un símplex ; por lo tanto, se trata de 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 PFA se convierte esencialmente en una especie de cadena de Markov .

Por el contrario, en un QFA, la variedad es un espacio proyectivo complejo.${\displaystyle \mathbb {C} P^{N}}$y las matrices de transición son matrices unitarias. Cada punto en${\displaystyle \mathbb {C} P^{N}}$corresponde a un estado cuántico-mecánico (puro) ; las matrices unitarias pueden considerarse como las que rigen la evolución temporal del sistema (véase la imagen de Schrödinger ). La generalización de estados puros a estados mixtos debería ser directa: un estado mixto es simplemente una distribución de probabilidad de la teoría de la medida en${\displaystyle \mathbb {C} P^{N}}$.

Un aspecto importante a considerar son las distribuciones que se generan en la variedad durante la entrada de un lenguaje. Para que un autómata sea eficiente en el reconocimiento de un lenguaje, dicha distribución debe ser lo más uniforme posible. Esta necesidad de uniformidad es el principio fundamental de los métodos de máxima entropía : estos garantizan un funcionamiento preciso 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 autómatas finitos cualitativos (AFC): el algoritmo de Viterbi y el algoritmo de avance-retroceso se generalizan fácilmente a los AFC.

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 ]}

Los autómatas de medición única fueron introducidos por Cris Moore y James P. Crutchfield . ^{[ 2 ]} Se pueden definir formalmente de la siguiente manera.

Al igual que un autómata finito ordinario , se considera que el autómata cuántico tiene${\displaystyle N}$posibles estados internos, representados en este caso por un${\displaystyle N}$-nivel qudit${\displaystyle |\psi \rangle }$. Más precisamente, el${\displaystyle N}$-nivel qudit${\displaystyle |\psi \rangle \in P(\mathbb {C} ^{N})}$es un elemento de${\displaystyle (N-1)}$espacio proyectivo complejo de -dimensiones , que contiene un producto interno${\displaystyle \Vert \cdot \Vert }$Esa es la métrica de Fubini-Study .

Las transiciones de estado , matrices de transición o grafos de De Bruijn están representados por una colección de${\displaystyle N\times N}$matrices unitarias${\displaystyle U_{\alpha }}$, con una matriz unitaria para cada letra${\displaystyle \alpha \in \Sigma }$. Es decir, dada una letra de entrada${\displaystyle \alpha }$La matriz unitaria describe la transición del autómata desde su estado actual.${\displaystyle |\psi \rangle }$a su próximo estado${\displaystyle |\psi ^{\prime }\rangle }$:

${\displaystyle |\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle }$

Por lo tanto, el triple${\displaystyle (P(\mathbb {C} ^{N}),\Sigma ,\{U_{\alpha }\;\vert \;\alpha \in \Sigma \})}$formar un semiautómata cuántico .

El estado de aceptación del autómata viene dado por un${\displaystyle N\times N}$matriz de proyección${\displaystyle P}$, de modo que, dado un${\displaystyle N}$estado cuántico dimensional${\displaystyle |\psi \rangle }$, la probabilidad de${\displaystyle |\psi \rangle }$estar en el estado de aceptación es

${\displaystyle \langle \psi |P|\psi \rangle =\Vert P|\psi \rangle \Vert ^{2}}$

La probabilidad de que la máquina de estados acepte una cadena de entrada finita dada.${\displaystyle \sigma =(\sigma _{0},\sigma _{1},\dots ,\sigma _{k})}$es dado por

${\displaystyle \operatorname {Pr} (\sigma )=\Vert PU_{\sigma _{k}}\cdots U_{\sigma _{1}}U_{\sigma _{0}}|\psi \rangle \Vert ^{2}}$

Aquí, el vector${\displaystyle |\psi \rangle }$Se entiende que representa el estado inicial del autómata, es decir, el estado en el que se encontraba el autómata antes de que comenzara a aceptar la entrada de cadena. La cadena vacía${\displaystyle \varnothing }$se entiende que es simplemente la matriz identidad, de modo que

${\displaystyle \operatorname {Pr} (\varnothing )=\Vert P|\psi \rangle \Vert ^{2}}$

es simplemente la probabilidad de que el estado inicial sea un estado aceptado.

Debido a la acción izquierda de${\displaystyle U_{\alpha }}$en${\displaystyle |\psi \rangle }$invierte el orden de las letras en la cadena${\displaystyle \sigma }$No es raro que los QFA se definan utilizando una acción derecha sobre los estados transpuestos hermitianos , simplemente para mantener el mismo orden de las letras.

Un lenguaje sobre el alfabeto${\displaystyle \Sigma }$es aceptado con probabilidad${\displaystyle p}$por un autómata cuántico finito (y un estado inicial fijo dado)${\displaystyle |\psi \rangle }$), si, para todas las oraciones${\displaystyle \sigma }$en el idioma, uno tiene${\displaystyle p\leq \operatorname {Pr} (\sigma )}$.

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.

${\displaystyle |\psi \rangle =a_{1}|S_{1}\rangle +a_{2}|S_{2}\rangle ={\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}}$

con los números complejos${\displaystyle a_{1},a_{2}}$normalizado de modo que

${\displaystyle {\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}$

Las matrices de transición unitarias son

${\displaystyle U_{0}={\begin{bmatrix}0&1\\1&0\end{bmatrix}}}$

y

${\displaystyle U_{1}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}}$

Tomando${\displaystyle S_{1}}$Para ser el estado aceptado, la matriz de proyección es

${\displaystyle P={\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$

Como debería ser evidente, si el estado inicial es el estado puro${\displaystyle |S_{1}\rangle }$o${\displaystyle |S_{2}\rangle }$, 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 :

${\displaystyle (1^{*}(01^{*}0)^{*})^{*}\,\!}$

El comportamiento no clásico se produce si ambos${\displaystyle a_{1}}$y${\displaystyle a_{2}}$son distintos de cero. Se produce un comportamiento más sutil cuando las matrices${\displaystyle U_{0}}$y${\displaystyle U_{1}}$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 medición múltiple fueron introducidos por Kondacs y Watrous en 1997. ^{[ 1 ]} El marco general se asemeja al del autómata de medición única, excepto que en lugar de una sola proyección, al final se realiza una proyección, o medición cuántica , después de leer cada letra. A continuación se presenta una definición formal.

El espacio de Hilbert${\displaystyle {\mathcal {H}}_{Q}}$se descompone en tres subespacios ortogonales

${\displaystyle {\mathcal {H}}_{Q}={\mathcal {H}}_{\text{accept}}\oplus {\mathcal {H}}_{\text{reject}}\oplus {\mathcal {H}}_{\text{non-halting}}}$

En la literatura, estos subespacios ortogonales se formulan habitualmente en términos del conjunto${\displaystyle Q}$de vectores base ortogonales para el espacio de Hilbert${\displaystyle {\mathcal {H}}_{Q}}$Este conjunto de vectores base se divide en subconjuntos.${\displaystyle Q_{\text{acc}}\subseteq Q}$y${\displaystyle Q_{\text{rej}}\subseteq Q}$, de tal manera que

${\displaystyle {\mathcal {H}}_{\text{accept}}=\operatorname {span} \{|q\rangle$ :|q\rangle \in Q_{\text{acc}}\}}

es el espacio lineal generado por los vectores base en el conjunto de aceptación. El espacio de rechazo se define de forma análoga, y el complemento ortogonal de todos los vectores de aceptación y rechazo se denomina subespacio no estacionario . Hay tres matrices de proyección,${\displaystyle P_{\text{acc}}}$, ${\displaystyle P_{\text{rej}}}$y${\displaystyle P_{\text{non}}}$, cada uno proyectándose al subespacio respectivo:

${\displaystyle P_{\text{acc}}:{\mathcal {H}}_{Q}\to {\mathcal {H}}_{\text{accept}}}$

y así sucesivamente. El análisis de la cadena de entrada procede de la siguiente manera. Consideremos que el autómata se encuentra en un estado${\displaystyle |\psi \rangle }$Después de leer una carta de entrada${\displaystyle \alpha }$, el autómata estará en el estado

${\displaystyle |\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle }$

En este punto, una medición cuyos tres posibles resultados tienen espacios propios${\displaystyle {\mathcal {H}}_{\text{accept}}}$,${\displaystyle {\mathcal {H}}_{\text{reject}}}$,${\displaystyle {\mathcal {H}}_{\text{non-halting}}}$se realiza en el estado${\displaystyle |\psi ^{\prime }\rangle }$, momento en el que su función de onda colapsa en uno de los tres subespacios${\displaystyle {\mathcal {H}}_{\text{accept}}}$o${\displaystyle {\mathcal {H}}_{\text{reject}}}$o${\displaystyle {\mathcal {H}}_{\text{non-halting}}}$. La probabilidad de colapso al subespacio "aceptar" viene dada por

${\displaystyle \operatorname {Pr} _{\text{acc}}(\sigma )=\Vert P_{\text{acc}}|\psi ^{\prime }\rangle \Vert ^{2},}$

y de forma análoga para los otros dos espacios.

Si la función de onda se ha colapsado en los subespacios de "aceptación" o "rechazo", 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 autoestado de${\displaystyle P_{\text{non}}}$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.${\displaystyle \kappa }$y $ se adjuntan al alfabeto, para actuar como marcadores de extremo izquierdo y derecho para la cadena.

En la literatura, el autómata de medida múltiple se suele denotar mediante la tupla${\displaystyle (Q;\Sigma$ ;\delta ;q_{0};Q_{\text{acc}};Q_{\text{rej}})} . Aquí,${\displaystyle Q}$,${\displaystyle \Sigma }$,${\displaystyle Q_{\text{acc}}}$y${\displaystyle Q_{\text{rej}}}$son como se definen anteriormente. El estado inicial se denota por${\displaystyle |q_{0}\rangle }$Las transformaciones unitarias se denotan mediante el mapa${\displaystyle \delta }$,

${\displaystyle \delta :Q\times \Sigma \times Q\to \mathbb {C} }$

de modo que

${\displaystyle U_{\alpha }|q_{i}\rangle =\sum _{q_{j}\in Q}\delta (q_{i},\alpha ,q_{j})|q_{j}\rangle }$

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 programarlas exponen la preparación del estado de${\displaystyle |\psi \rangle }$medición${\displaystyle P}$y una selección de transformaciones unitarias${\displaystyle U_{\alpha }}$, tales 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 resultar en un estado puro puntual , ni los operadores unitarios pueden aplicarse con precisión. Por lo tanto, el estado inicial debe tomarse como un estado mixto.

${\displaystyle \rho =\int p(x)|\psi _{x}\rangle dx}$

para alguna distribución de probabilidad${\displaystyle p(x)}$caracterizar la capacidad de la maquinaria para preparar un estado inicial cercano al estado puro inicial deseado.${\displaystyle |\psi \rangle }$Este estado no es estable, sino que sufre cierta decoherencia cuántica con el tiempo. Tampoco son posibles mediciones precisas, y en su lugar se utilizan medidas con valores de operador positivos para describir el proceso de medición. Finalmente, cada transformación unitaria no es una única puerta lógica cuántica definida con precisión, sino más bien una mezcla.

${\displaystyle U_{\alpha ,(\rho )}=\int p_{\alpha }(x)U_{\alpha ,x}dx}$

para alguna distribución de probabilidad${\displaystyle p_{\alpha }(x)}$describiendo qué tan bien la maquinaria puede efectuar la transformación deseada${\displaystyle U_{\alpha }}$.

Como resultado de estos efectos, la evolución temporal real del estado no puede considerarse como un punto puro de precisión infinita, sobre el que se aplica una secuencia de transformaciones arbitrariamente nítidas, sino más bien como un proceso ergódico , o más precisamente, como un proceso de mezcla que no solo concatena transformaciones sobre un estado, sino que también difumina el estado a lo largo del tiempo.

No existe un análogo cuántico para el autómata de pila o 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, insertarla en una pila para consultarla posteriormente y luego volver a ella.

Las construcciones anteriores indican cómo el concepto de 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${\displaystyle \mathbb {C} P^{N}}$En lugar de las matrices unitarias, se utilizan las isometrías de la variedad riemanniana o, más generalmente, un conjunto de funciones abiertas apropiadas para el espacio topológico dado. El estado inicial puede ser un punto en el espacio. El conjunto de estados aceptados puede ser un subconjunto arbitrario del espacio topológico. Se dice entonces que un lenguaje formal es aceptado por este autómata topológico si el punto, después de la iteración mediante los homeomorfismos, interseca el conjunto aceptado. Pero, por supuesto, esto no es 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 está en el conjunto final?), se tiene una probabilidad. La probabilidad cuántica es el (cuadrado de) el estado inicial proyectado sobre algún estado final P ; es decir,${\displaystyle \mathbf {Pr} =\vert \langle P\vert \psi \rangle \vert ^{2}}$. Pero esta amplitud de probabilidad es simplemente una función muy simple de la distancia entre el punto${\displaystyle \vert P\rangle }$y el punto${\displaystyle \vert \psi \rangle }$en${\displaystyle \mathbb {C} P^{N}}$, bajo la métrica de distancia dada por la métrica de Fubini-Study . En resumen, la probabilidad cuántica de que un lenguaje sea aceptado puede interpretarse como una métrica, donde la probabilidad de aceptación es unitaria si la distancia métrica entre los estados inicial y final es cero, y en caso contrario, la probabilidad de aceptación 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${\displaystyle \mathbb {C} P^{N}}$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.

• Cadena de Markov cuántica
• Máquina Blum-Shub-Smale
• Computadora real