Algoritmos cuánticos: modelos de consulta, complejidad y primitivas computacionales

El modelo estándar de computación cuántica se sustenta en el paradigma de circuitos cuánticos, introducido por Deutsch (1989) y formalizado por Yao (1993), quien demostró su equivalencia polinómica con la máquina de Turing cuántica. En este modelo, un cómputo se describe como la aplicación sucesiva de compuertas unitarias —operaciones lineales que preservan la norma del vector de estado— sobre un registro de \(n\) cúbits inicializado en el estado \(|0\rangle^{\otimes n}\). El espacio de Hilbert asociado tiene dimensión \(2^n\), y el estado del sistema en cualquier instante es un vector unitario \(|\psi\rangle \in \mathbb{C}^{2^n}\).

La evolución temporal del registro viene dictada por la ecuación de Schrödinger. En el marco discreto de circuitos, cada paso corresponde a la aplicación de una compuerta unitaria \(U_k\), de modo que el estado final antes de la medición es:

donde \(T\) es la profundidad total del circuito. La universalidad del modelo se garantiza con un conjunto finito de compuertas: típicamente las rotaciones de un cúbit \(R_x(\theta), R_y(\theta), R_z(\theta)\) junto con una compuerta de entrelazamiento como CNOT o CZ. El teorema de Solovay-Kitaev asegura que cualquier unitario de \(n\) cúbits puede aproximarse con precisión \(\epsilon\) usando \(O(\text{poly}(n) \cdot \log^c(1/\epsilon))\) compuertas del conjunto universal, con \(c \approx 3.97\).

Tras la evolución unitaria, se realizan mediciones proyectivas en la base computacional \(\{|0\rangle, |1\rangle\}^{\otimes n}\). La probabilidad de obtener la cadena de bits \(x \in \{0,1\}^n\) viene dada por la regla de Born:

Las salidas medidas se procesan clásicamente para producir el resultado del algoritmo. Es fundamental notar que la medición es irreversible y destruye la superposición: el estado colapsa al autoestado correspondiente al resultado observado. Este hecho impone restricciones profundas en el diseño algorítmico, pues la información cuántica no puede ser copiada (teorema de no-clonación) y la extracción de información requiere interferencia constructiva cuidadosamente orquestada.

El modelo de circuitos admite extensiones importantes. La computación cuántica basada en mediciones (measurement-based quantum computation, MBQC), introducida por Raussendorf y Briegel (2001), parte de un estado altamente entrelazado —el estado cluster— y realiza el cómputo exclusivamente mediante mediciones adaptativas de un cúbit, donde la elección de la base de medición de cada paso depende de los resultados anteriores. Aunque conceptualmente distinto, este modelo es polinómicamente equivalente al de circuitos. De manera análoga, la computación cuántica adiabática, basada en el teorema adiabático y la evolución lenta de hamiltonianos, también ha sido demostrada equivalente en poder computacional bajo condiciones técnicas apropiadas.

Comparado con la máquina de Turing clásica determinista, el modelo cuántico introduce tres capacidades fundamentales: (1) superposición, que permite codificar amplitudes complejas sobre exponencialmente muchas configuraciones simultáneamente; (2) entrelazamiento, que establece correlaciones no locales entre subsistemas imposibles de reproducir clásicamente; y (3) interferencia, que permite cancelar amplitudes correspondientes a soluciones incorrectas y amplificar las correctas. La combinación de estas tres propiedades es lo que subyace a toda aceleración cuántica conocida.

La clase de complejidad central en computación cuántica es BQP (Bounded-Error Quantum Polynomial Time), definida como el conjunto de lenguajes \(L\) para los cuales existe una familia uniforme de circuitos cuánticos polinómicos \(\{C_n\}\) tal que para toda entrada \(x\) de longitud \(n\):

La constante \(2/3\) es arbitraria: mediante amplificación por repetición y voto mayoritario, la probabilidad de error puede reducirse exponencialmente con overhead polinómico. La relación de BQP con las clases clásicas fundamentales se resume en las contenciones conocidas:

La contención \(\mathsf{BPP} \subseteq \mathsf{BQP}\) es inmediata: todo circuito clásico probabilista puede simularse cuánticamente usando compuertas Toffoli y cúbits ancilla. La contención \(\mathsf{BQP} \subseteq \mathsf{PSPACE}\) fue demostrada por Bernstein y Vazirani (1997), utilizando el hecho de que un circuito cuántico de tamaño polinómico puede simularse clásicamente en espacio polinómico (aunque potencialmente con tiempo exponencial). Las separaciones estrictas entre estas clases permanecen como problemas abiertos de primera magnitud en teoría de la complejidad.

En el mundo relativizado —es decir, en presencia de oráculos— se conocen separaciones más fuertes. Bernstein y Vazirani (1997) demostraron la existencia de un oráculo \(A\) tal que \(\mathsf{BQP}^A \not\subseteq \mathsf{BPP}^A\), y posteriormente Aaronson y Ambainis establecieron oráculos que separan BQP de la jerarquía polinómica. El resultado de Raz y Tal (2019) —construyendo un oráculo bajo el cual \(\mathsf{BQP} \not\subseteq \mathsf{PH}\)— constituyó un hito al demostrar que, al menos en el mundo relativizado, la computación cuántica trasciende toda la jerarquía polinómica.

Otras clases relevantes incluyen QIP (protocolos interactivos cuánticos), donde Jain, Ji, Upadhyay y Watrous (2011) demostraron que \(\mathsf{QIP} = \mathsf{PSPACE}\), un resultado sorprendente que muestra que la interacción cuántica no añade poder sobre PSPACE. La clase QCMA restringe QMA requiriendo que el testigo sea clásico; se sabe que \(\mathsf{QCMA} \subseteq \mathsf{QMA}\), pero la separación estricta es un problema abierto. Finalmente, la clase PostBQP (BQP con post-selección) fue demostrada igual a PP por Aaronson (2005), un resultado con implicaciones profundas para la simulabilidad clásica de circuitos cuánticos.

La estructura de estas clases tiene consecuencias directas para la criptografía post-cuántica. Si \(\mathsf{NP} \subseteq \mathsf{BQP}\), todos los problemas NP-completos —incluyendo SAT, el problema de la mochila y la programación lineal entera— serían resolubles eficientemente por computadoras cuánticas, colapsando la criptografía basada en complejidad computacional. Aunque esta contención se considera improbable (y equivaldría a un colapso radical de la estructura de complejidad), la mera posibilidad motiva la investigación activa en esquemas criptográficos resistentes a ataques cuánticos, como los basados en retículas, códigos y funciones hash.

El modelo de consultas (query model) es el marco formal predominante para demostrar aceleraciones cuánticas. En este modelo, el algoritmo no tiene acceso directo a la descripción de la función \(f: \{0,1\}^n \to \{0,1\}^m\), sino que la evalúa mediante un oráculo cuántico \(O_f\) que actúa coherentemente sobre superposiciones:

donde \(\oplus\) denota la suma módulo \(2^m\). La complejidad de consultas cuántica, denotada \(Q(f)\), es el número mínimo de aplicaciones de \(O_f\) necesarias para resolver el problema computacional asociado con probabilidad de error acotada. Análogamente, la complejidad de consultas clásica determinista \(D(f)\) y la probabilista \(R(f)\) cuentan el número mínimo de evaluaciones clásicas de \(f\).

El llamado «paralelismo cuántico» —término que, aunque popular, puede inducir a confusión— se refiere a la capacidad de evaluar el oráculo sobre una superposición de todas las entradas posibles en una sola consulta. Preparando el registro de entrada en superposición uniforme mediante compuertas de Hadamard:

y aplicando el oráculo, se obtiene:

Sin embargo, la mera creación de esta superposición no constituye por sí misma una ventaja computacional. La restricción fundamental es que una medición en la base computacional extraerá un único par \((x, f(x))\) aleatorio, destruyendo el resto de la superposición. La verdadera potencia de los algoritmos cuánticos reside en la interferencia: la aplicación cuidadosa de transformaciones unitarias posteriores al oráculo que modifican las amplitudes de modo que las soluciones deseadas interfieran constructivamente (sus amplitudes se sumen) mientras que las no deseadas interfieran destructivamente (sus amplitudes se cancelen).

El método de los polinomios, introducido por Beals, Buhrman, Cleve, Mosca y de Wolf (2001), establece cotas inferiores en la complejidad de consultas cuántica. Si \(f: \{0,1\}^n \to \{0,1\}\) es una función booleana y \(\widetilde{\deg}(f)\) denota el grado polinómico aproximado de \(f\), entonces \(Q(f) \geq \widetilde{\deg}(f)/2\). Esto demuestra, por ejemplo, que la aceleración cuadrática de Grover es óptima: cualquier algoritmo cuántico para búsqueda no estructurada requiere \(\Omega(\sqrt{N})\) consultas.

Las separaciones entre complejidad de consultas clásica y cuántica dependen crucialmente de la estructura del problema. Para funciones booleanas totales, la separación máxima conocida es polinómica: \(D(f) = O(Q(f)^6)\) por el resultado de Aaronson, Ben-David y Kothari (2021), mejorando la cota anterior de cuarto poder. Para funciones parciales —donde la promesa restringe las entradas válidas— las separaciones pueden ser exponenciales, como demuestran los algoritmos de Deutsch-Jozsa y Simon.

El algoritmo de Deutsch-Jozsa (1992) constituye la primera demostración de una separación exponencial entre complejidad de consultas determinista clásica y cuántica exacta. El problema se formula como sigue: dada una función \(f: \{0,1\}^n \to \{0,1\}\) con la promesa de que es o bien constante (toma el mismo valor para todas las entradas) o bien balanceada (toma el valor 0 en exactamente la mitad de las entradas y 1 en la otra mitad), determinar cuál de los dos casos se verifica.

Clásicamente, en el peor caso determinista, se requieren \(2^{n-1} + 1\) evaluaciones de \(f\): es necesario consultar más de la mitad de las entradas antes de poder garantizar una respuesta correcta. Un algoritmo probabilista puede resolver el problema con alta probabilidad usando \(O(1)\) consultas (muestreando unas pocas entradas y verificando si obtiene valores distintos), pero con una probabilidad de error no nula. El algoritmo cuántico de Deutsch-Jozsa resuelve el problema con certeza —probabilidad de error exactamente cero— usando una única consulta al oráculo.

El circuito procede en cuatro pasos. Primero, se preparan \(n+1\) cúbits: los \(n\) primeros en \(|0\rangle\) y el último (cúbit ancilla) en \(|1\rangle\). Se aplica la compuerta de Hadamard a todos los cúbits:

A continuación se aplica el oráculo \(O_f\). Dado que el cúbit ancilla está en el estado \(|{-}\rangle = (|0\rangle - |1\rangle)/\sqrt{2}\), la acción del oráculo produce el efecto de phase kickback:

El estado del registro de trabajo (excluyendo la ancilla) es entonces:

Finalmente, se aplica \(H^{\otimes n}\) al registro de trabajo. La amplitud del estado \(|0\rangle^{\otimes n}\) tras esta transformación es:

Si \(f\) es constante, esta suma vale \(\pm 1\), por lo que la medición del registro produce \(|0\rangle^{\otimes n}\) con probabilidad 1. Si \(f\) es balanceada, la suma se anula exactamente (la mitad de los términos contribuyen \(+1\) y la otra mitad \(-1\)), de modo que la probabilidad de obtener \(|0\rangle^{\otimes n}\) es 0. Por tanto, una única medición distingue los dos casos con certeza.

Aunque el problema de Deutsch-Jozsa carece de aplicaciones prácticas directas, su importancia es conceptual: demuestra que la interferencia cuántica puede extraer propiedades globales de una función con un número de consultas exponencialmente menor que cualquier algoritmo determinista. Este principio se extiende y amplifica en los algoritmos de Simon y Shor.

El algoritmo de Simon (1994) resuelve el siguiente problema: dada una función \(f: \{0,1\}^n \to \{0,1\}^n\) con la promesa de que existe un \(s \in \{0,1\}^n\) tal que \(f(x) = f(y)\) si y solo si \(x = y\) o \(x = y \oplus s\), encontrar la cadena oculta \(s\). Simon demostró que este problema requiere \(\Omega(2^{n/2})\) consultas clásicas (incluso probabilistas), mientras que su algoritmo cuántico lo resuelve con \(O(n)\) consultas, estableciendo la primera separación exponencial para un problema computacional (no meramente de decisión con promesa trivial).

El circuito cuántico de Simon prepara el estado \(|0\rangle^{\otimes n} |0\rangle^{\otimes n}\), aplica \(H^{\otimes n}\) al primer registro, y luego el oráculo \(O_f\). El estado resultante es:

Si medimos el segundo registro y obtenemos un valor \(z = f(x_0)\), el primer registro colapsa a la superposición \((|x_0\rangle + |x_0 \oplus s\rangle)/\sqrt{2}\) (asumiendo \(s \neq 0\)). Aplicando \(H^{\otimes n}\) al primer registro y midiendo, se obtiene una cadena \(y\) uniformemente aleatoria del subespacio ortogonal a \(s\), es decir, \(y \cdot s = 0 \pmod{2}\). Tras \(O(n)\) iteraciones independientes, acumulamos suficientes ecuaciones lineales para resolver el sistema y determinar \(s\) mediante eliminación gaussiana clásica.

Más precisamente, tras \(n - 1\) consultas, obtenemos \(n - 1\) vectores \(y_1, \ldots, y_{n-1}\) satisfaciendo \(y_i \cdot s = 0\). Si estos vectores son linealmente independientes (lo cual ocurre con probabilidad al menos \(\prod_{k=1}^{n-1}(1 - 2^{-k}) \geq 1/4\)), determinan unívocamente \(s\) (módulo el vector nulo). En la práctica, \(O(n)\) iteraciones bastan para obtener un sistema de rango completo con alta probabilidad.

El algoritmo de Simon es el precursor directo del algoritmo de Shor. Ambos comparten la estructura de problema del subgrupo oculto (Hidden Subgroup Problem, HSP): dada una función \(f: G \to S\) que es constante en las coclases de un subgrupo \(H \leq G\) y distinta entre coclases distintas, encontrar \(H\). El algoritmo de Simon resuelve el HSP para \(G = \mathbb{Z}_2^n\), mientras que el de Shor lo resuelve para \(G = \mathbb{Z}_N\). Para grupos no abelianos, el HSP permanece abierto en general y su resolución tendría implicaciones para problemas como el isomorfismo de grafos.

Desde el punto de vista de la complejidad, el problema de Simon define un oráculo relativo al cual \(\mathsf{BQP} \not\subseteq \mathsf{BPP}\), proporcionando evidencia fuerte (aunque no una demostración absoluta) de que la computación cuántica es estrictamente más poderosa que la clásica probabilista. La reducción de Shor demuestra que este poder se manifiesta en problemas concretos de la teoría de números con implicaciones criptográficas devastadoras.

La estimación de fase cuántica (Quantum Phase Estimation, QPE) es una subrutina fundamental que subyace a múltiples algoritmos cuánticos, incluyendo el de Shor, la simulación hamiltoniana y los algoritmos para problemas de álgebra lineal. Introducida por Kitaev (1995) y elaborada por Cleve, Ekert, Macchiavello y Mosca (1998), QPE resuelve el siguiente problema: dado acceso a un operador unitario \(U\) y a un autoestado \(|\phi\rangle\) tal que \(U|\phi\rangle = e^{2\pi i \theta}|\phi\rangle\), estimar la fase \(\theta \in [0, 1)\) con \(t\) bits de precisión.

El circuito de QPE emplea dos registros: un registro de \(t\) cúbits de «precisión» inicializado en \(|0\rangle^{\otimes t}\) y un registro de «eigenestado» preparado en \(|\phi\rangle\). El algoritmo consta de tres etapas:

Etapa 1: Superposición. Se aplica \(H^{\otimes t}\) al registro de precisión, obteniéndose la superposición uniforme \(\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t - 1} |k\rangle |\phi\rangle\).

Etapa 2: Aplicación controlada de potencias de \(U\). Para cada cúbit \(j\) del registro de precisión (contando desde 0), se aplica la operación controlada \(C\text{-}U^{2^j}\). El efecto acumulado sobre el estado es:

Etapa 3: Transformada cuántica de Fourier inversa. Se aplica \(\text{QFT}^{\dagger}\) al registro de precisión. Si \(\theta = j / 2^t\) para algún entero \(j\), la QFT inversa produce el estado \(|j\rangle\) exactamente. En el caso general, la medición produce un valor \(\tilde{j}\) tal que \(|\theta - \tilde{j}/2^t| \leq 2^{-t}\) con probabilidad al menos \(1 - \epsilon\), donde usar \(t + \lceil\log(2 + 1/(2\epsilon))\rceil\) cúbits de precisión garantiza esta cota.

La complejidad del circuito está dominada por las aplicaciones controladas de \(U\): la potencia máxima aplicada es \(U^{2^{t-1}}\), que requiere \(2^{t-1}\) aplicaciones secuenciales de \(U\) (o menos si se dispone de cuadratura eficiente). La profundidad total del circuito es \(O(2^t)\) aplicaciones de \(U\) más \(O(t^2)\) compuertas para la QFT (o \(O(t \log t)\) con la versión aproximada).

Las aplicaciones de QPE son ubicuas en algoritmia cuántica. En el algoritmo de Shor, QPE se utiliza para extraer el período de la función modular. En simulación cuántica, QPE permite estimar energías del estado fundamental de hamiltonianos moleculares. En el algoritmo HHL para sistemas lineales, QPE extrae los valores propios de la matriz del sistema. En todos estos casos, la eficiencia de QPE es el cuello de botella que determina la complejidad global del algoritmo.

Cuando el estado de entrada no es un autoestado exacto de \(U\), sino una superposición \(|\psi\rangle = \sum_j \alpha_j |\phi_j\rangle\), QPE produce una superposición correlacionada \(\sum_j \alpha_j |\tilde{\theta}_j\rangle |\phi_j\rangle\), donde \(\tilde{\theta}_j\) es la estimación de la fase asociada al autoestado \(|\phi_j\rangle\). Este hecho es explotado en los algoritmos de simulación cuántica, donde la medición del registro de fase proyecta el sistema en un autoestado particular del hamiltoniano.

El algoritmo de Shor (1994) es, probablemente, el resultado más célebre de la computación cuántica. Demuestra que un computador cuántico puede factorizar un entero \(N\) de \(n = \lceil\log_2 N\rceil\) bits en tiempo \(O(n^2 \log n \log\log n)\) con alta probabilidad, frente al mejor algoritmo clásico conocido —la criba general del cuerpo de números (GNFS)— cuya complejidad es subexponencial: \(\exp\!\big(O(n^{1/3} (\log n)^{2/3})\big)\). Esta separación superpolinómica tiene implicaciones directas para la seguridad de los criptosistemas RSA, Diffie-Hellman y de curva elíptica, que fundamentan la infraestructura de comunicaciones seguras actual.

El algoritmo de Shor se descompone en dos etapas: una reducción clásica del problema de factorización al problema de hallar el período (u orden) de una función modular, y un algoritmo cuántico para la búsqueda de período. La reducción clásica procede como sigue: se elige aleatoriamente \(a \in \{2, \ldots, N-1\}\) con \(\gcd(a, N) = 1\). Se define la función \(f(x) = a^x \bmod N\), que es periódica con período \(r\) (el orden de \(a\) en el grupo multiplicativo \(\mathbb{Z}_N^*\)). Si \(r\) es par y \(a^{r/2} \not\equiv -1 \pmod{N}\), entonces \(\gcd(a^{r/2} \pm 1, N)\) produce un factor no trivial de \(N\). Se demuestra que un \(a\) aleatorio satisface estas condiciones con probabilidad al menos \(1/2\).

La parte cuántica —la búsqueda de período— utiliza QPE aplicada al operador unitario de multiplicación modular \(U_a |x\rangle = |ax \bmod N\rangle\). Los autoestados de \(U_a\) son:

con autovalores \(e^{2\pi i s/r}\). Crucialmente, la superposición uniforme de estos autoestados es accesible:

Por lo tanto, al inicializar el segundo registro en \(|1\rangle\) y aplicar QPE con \(t = 2n + \lceil\log(2 + 1/(2\epsilon))\rceil\) cúbits de precisión, se obtiene una superposición sobre las estimaciones de \(s/r\) para \(s\) aleatorio. La medición produce un valor \(\tilde{\theta}\) cercano a \(s/r\), del cual se extrae \(r\) mediante el algoritmo de fracciones continuas: se busca la fracción irreducible \(p/q\) con \(q < N\) más cercana a \(\tilde{\theta}/2^t\), y se verifica si \(q\) (o un múltiplo pequeño) es el período buscado.

La implementación de Shor requiere circuitos de multiplicación modular eficientes. La exponenciación modular \(a^x \bmod N\) se descompone en \(O(n)\) multiplicaciones modulares controladas, cada una implementable con \(O(n^2)\) compuertas elementales usando aritmética reversible. El circuito total requiere \(O(n^3)\) compuertas y \(O(n)\) cúbits (más ancillas para la aritmética). Variantes más sofisticadas, como la de Beauregard (2003), reducen el número de cúbits a \(2n + 3\) a costa de mayor profundidad de circuito.

La transformada cuántica de Fourier (QFT) es el componente central de QPE en el algoritmo de Shor. La QFT sobre \(2^t\) elementos se define como:

Se implementa con \(O(t^2)\) compuertas usando rotaciones controladas de fase, o con \(O(t \log t)\) compuertas usando la versión aproximada de Coppersmith (1994). La QFT cuántica es exponencialmente más eficiente que la transformada de Fourier discreta clásica (que requiere \(O(2^t t)\) operaciones mediante FFT), pero esta comparación no es directa, pues la QFT opera sobre amplitudes que no pueden leerse directamente.

El algoritmo de Grover (1996) resuelve el problema de búsqueda no estructurada: dado un oráculo \(O_f\) para una función \(f: \{0,1\}^n \to \{0,1\}\) con exactamente \(M\) soluciones marcadas (es decir, \(|\{x : f(x) = 1\}| = M\)) entre \(N = 2^n\) candidatos, encontrar una solución con alta probabilidad. Clásicamente, esto requiere \(\Theta(N/M)\) evaluaciones de \(f\) en el peor caso; el algoritmo de Grover lo logra con \(O(\sqrt{N/M})\) consultas cuánticas.

El algoritmo se basa en la iteración del operador de Grover \(G = D \cdot O_f\), donde \(O_f\) es el oráculo de fase (\(O_f |x\rangle = (-1)^{f(x)}|x\rangle\)) y \(D\) es el operador de difusión (o inversión sobre la media):

La geometría del algoritmo se comprende elegantemente en el subespacio bidimensional generado por los estados \(|w\rangle\) (superposición uniforme de soluciones) y \(|w^{\perp}\rangle\) (superposición uniforme de no-soluciones). Definiendo el ángulo \(\sin\theta = \sqrt{M/N}\), el estado inicial \(|s\rangle = \cos\theta\,|w^{\perp}\rangle + \sin\theta\,|w\rangle\) y cada iteración de \(G\) es una rotación de ángulo \(2\theta\) en este plano:

La probabilidad de medir una solución tras \(k\) iteraciones es \(\sin^2\!\big((2k+1)\theta\big)\). Esta probabilidad se maximiza cuando \((2k+1)\theta \approx \pi/2\), lo que da el número óptimo de iteraciones:

Un aspecto sutil del algoritmo es que la probabilidad de éxito oscila: si se itera más allá del óptimo, la amplitud de la solución comienza a decrecer. Esto contrasta con los algoritmos clásicos de búsqueda, cuya probabilidad de éxito crece monótonamente. Cuando \(M\) es desconocido, la técnica de estimación del conteo cuántico (quantum counting), basada en QPE aplicada al operador de Grover, permite estimar \(M\) y ajustar el número de iteraciones.

La optimalidad de Grover fue demostrada por Bennett, Bernstein, Brassard y Vazirani (1997) usando el método híbrido (polynomial method): cualquier algoritmo cuántico para búsqueda no estructurada con \(M = 1\) solución requiere \(\Omega(\sqrt{N})\) consultas. Esto establece que la aceleración cuadrática de Grover es la máxima posible en ausencia de estructura adicional.

Las aplicaciones de la búsqueda de Grover y la amplificación de amplitud se extienden mucho más allá de la búsqueda en bases de datos. En criptografía, Grover implica que una clave simétrica de \(n\) bits ofrece solo \(n/2\) bits de seguridad frente a un atacante cuántico, motivando la duplicación de longitudes de clave (AES-256 en lugar de AES-128). En optimización combinatoria, la búsqueda de Grover acelera cuadráticamente los algoritmos de fuerza bruta y backtracking. En estimación de Monte Carlo cuántico, Montanaro (2015) demostró una aceleración cuadrática sobre los métodos clásicos, con aplicaciones potenciales en finanzas computacionales y evaluación de riesgo.

Los algoritmos variacionales cuánticos constituyen el paradigma dominante en la era de dispositivos cuánticos ruidosos de escala intermedia (NISQ). A diferencia de los algoritmos cuánticos «puros» como Shor o Grover, que requieren circuitos profundos con corrección de errores, los métodos variacionales emplean bucles híbridos clásico-cuánticos: un circuito cuántico parametrizado de profundidad moderada prepara un estado de prueba, un procesador clásico evalúa una función de costo a partir de las mediciones, y un optimizador clásico actualiza los parámetros del circuito para minimizar dicha función.

El Variational Quantum Eigensolver (VQE), introducido por Peruzzo et al. (2014), busca la energía del estado fundamental de un hamiltoniano \(H\). El principio variacional cuántico garantiza que para todo estado normalizado \(|\psi(\vec\theta)\rangle\):

donde \(E_0\) es la energía del estado fundamental y \(C(\vec\theta)\) es la función de costo evaluada experimentalmente. El ansatz —la forma funcional del circuito parametrizado— determina la expresividad del espacio variacional. Los ansätze comunes incluyen el Unitary Coupled Cluster (UCC), inspirado en la química cuántica, y las arquitecturas de hardware-efficient ansatz, diseñadas para minimizar la profundidad del circuito a costa de mayor variabilidad en el paisaje de optimización.

El Quantum Approximate Optimization Algorithm (QAOA), propuesto por Farhi, Goldstone y Gutmann (2014), aborda problemas de optimización combinatoria codificados en un hamiltoniano de costo \(H_C = \sum_{\alpha} C_\alpha\). El circuito QAOA de profundidad \(p\) aplica \(p\) capas alternadas de evolución bajo \(H_C\) y un hamiltoniano de mezcla \(H_M\) (típicamente \(H_M = \sum_i X_i\)):

En el límite \(p \to \infty\), QAOA converge al estado fundamental de \(H_C\) (por el teorema adiabático discretizado). Para \(p\) finito, se optimizan los \(2p\) parámetros \(\{\gamma_l, \beta_l\}\) clásicamente. Farhi y Harrow (2016) demostraron que QAOA con \(p\) suficiente puede superar cualquier algoritmo clásico local, bajo ciertas conjeturas de complejidad.

Un desafío central de los métodos variacionales es el fenómeno de los barren plateaus (mesetas estériles), identificado por McClean et al. (2018). En circuitos suficientemente expresivos y aleatorios, el gradiente de la función de costo decrece exponencialmente con el número de cúbits:

Esto hace que la optimización sea exponencialmente difícil en la práctica, pues el gradiente es indistinguible del ruido estadístico de las mediciones. Las estrategias de mitigación incluyen: (1) inicializaciones inteligentes cercanas a estados clásicos, (2) ansätze con estructura local que preservan la localidad del gradiente, (3) funciones de costo locales, y (4) técnicas de «parameter shift rule» con pre-entrenamiento clásico.

La evaluación de la función de costo requiere descomponer \(H\) en una suma de operadores de Pauli: \(H = \sum_i c_i P_i\), donde cada \(P_i \in \{I, X, Y, Z\}^{\otimes n}\). El valor esperado de cada término se estima independientemente mediante mediciones repetidas en la base apropiada, lo que introduce un overhead estadístico proporcional al número de términos y la precisión deseada. Técnicas de agrupamiento (grouping) de términos conmutantes y esquemas de medición clásica-sombra (classical shadows) reducen este costo significativamente.

La simulación cuántica es la aplicación más natural e históricamente primera propuesta para los computadores cuánticos. Feynman (1982) argumentó que simular un sistema cuántico de \(n\) partículas en un computador clásico requiere recursos exponenciales en \(n\) (debido al crecimiento exponencial del espacio de Hilbert), mientras que un computador cuántico podría hacerlo eficientemente. Lloyd (1996) formalizó esta intuición demostrando que los hamiltonianos locales pueden simularse eficientemente en un computador cuántico.

El problema central es: dado un hamiltoniano \(H\) actuando sobre \(n\) cúbits y un tiempo de evolución \(t\), implementar una aproximación del operador de evolución temporal \(e^{-iHt}\) con error \(\|U_{\text{approx}} - e^{-iHt}\| \leq \epsilon\) usando un número polinómico de compuertas elementales. Para hamiltonianos que son suma de términos locales, \(H = \sum_{k=1}^{L} H_k\), la descomposición de Trotter-Suzuki proporciona el método fundamental.

La fórmula de Trotter de primer orden aproxima la exponencial de la suma mediante el producto de exponenciales:

donde \(r\) es el número de pasos de Trotter (slices). Para alcanzar un error \(\epsilon\), se requieren \(r = O(L^2 t^2 / \epsilon)\) pasos. La fórmula de Trotter-Suzuki de segundo orden proporciona una mejor convergencia:

con error \(O(L^3 (\Delta t)^3)\), requiriendo \(r = O((Lt)^{3/2}/\sqrt{\epsilon})\) pasos. Las fórmulas de orden superior \(2k\) se construyen recursivamente mediante la fórmula de Suzuki, reduciendo progresivamente el error a costa de un prefactor constante mayor.

Los avances recientes en simulación cuántica incluyen algoritmos basados en qubitización y señalización cuántica (quantum signal processing, QSP), introducidos por Low y Chuang (2017) y generalizados por Gilyén, Su, Low y Wiebe (2019) en el marco de la transformación singular cuántica (Quantum Singular Value Transformation, QSVT). Estos métodos alcanzan la complejidad óptima \(O(\alpha t + \log(1/\epsilon))\) para hamiltonianos con norma \(\alpha\), superando las fórmulas de producto en escalamiento con la precisión \(\epsilon\).

La simulación cuántica se clasifica en dos paradigmas: simulación digital, que discretiza la evolución en compuertas universales (Trotter, QSVT); y simulación analógica, que utiliza un sistema cuántico controlable para emular directamente el hamiltoniano objetivo. Los simuladores analógicos —como átomos fríos en redes ópticas, iones atrapados y arreglos de átomos de Rydberg— han demostrado capacidades impresionantes en la simulación de modelos de Hubbard, de Ising y de espines cuánticos, alcanzando regímenes inaccesibles para métodos clásicos como Monte Carlo cuántico (debido al problema del signo fermiónico).

Desde la perspectiva de la complejidad, el problema de la simulación hamiltoniana es BQP-completo para hamiltonianos locales (Feynman-Kitaev), lo que significa que es la tarea computacional más general que una computadora cuántica puede resolver eficientemente. Esto refuerza la tesis de que la simulación cuántica constituye la aplicación killer de la computación cuántica.

El concepto de ventaja cuántica (o supremacía cuántica, en la terminología original de Preskill, 2012) se refiere a la demostración experimental de que un dispositivo cuántico puede realizar una tarea computacional que ningún computador clásico conocido puede igualar en tiempo razonable. Google reclamó este hito en 2019 con el procesador Sycamore de 53 cúbits superconductores, muestreando distribuciones de circuitos aleatorios en 200 segundos, tarea que estimaron requeriría 10.000 años en el supercomputador clásico más potente de la época.

Posteriormente, IBM cuestionó la estimación clásica, argumentando que técnicas de simulación tensorial y almacenamiento en disco podrían reducir el tiempo clásico a días. El grupo de Pan y Zhang (USTC) demostró simulaciones clásicas eficientes de circuitos ruidosos mediante contracción de redes tensoriales con ruido incorporado. Estas controversias ilustran la dificultad fundamental de demostrar ventaja cuántica: requiere simultáneamente (1) una tarea bien definida, (2) una cota superior en el rendimiento cuántico, y (3) una cota inferior en la dificultad clásica —y esta última es inherentemente difícil de establecer de manera rigurosa.

Experimentos subsecuentes han ampliado el panorama. USTC (2020) reportó ventaja cuántica en boson sampling gaussiano con el fotónico Jiuzhang (76 fotones detectados), y posteriormente con Jiuzhang 2.0 (113 fotones) y Zuchongzhi 2.1 (66 cúbits superconductores). Estos experimentos basados en muestreo tienen la particularidad de que la tarea computacional —generar muestras de una distribución específica— carece de utilidad práctica directa, aunque conjeturalmente es difícil de simular clásicamente (bajo la conjetura de que la jerarquía polinómica no colapsa).

El papel del ruido es central en la discusión de ventaja cuántica. Los dispositivos NISQ operan sin corrección de errores, con tasas de error de compuerta del orden de \(10^{-3}\) a \(10^{-2}\). A medida que aumenta la profundidad del circuito, el ruido degrada la distribución de salida hacia la distribución uniforme, reduciendo la fidelidad del muestreo. Las técnicas de mitigación de errores —como la extrapolación a ruido cero (ZNE), la mitigación probabilística de errores (PEM) y los estimadores twirled readout— pueden mejorar la calidad de los valores esperados estimados, pero con un overhead exponencial en el número de cúbits, lo que limita su escalabilidad.

La cuestión de si existe una ventaja cuántica práctica —es decir, para un problema con utilidad real y no meramente un benchmark artificial— permanece abierta. Los candidatos más prometedores incluyen: (1) la simulación de materiales y moléculas complejas, donde los métodos cuánticos podrían superar a DMRG y las técnicas de Monte Carlo con signo en sistemas fuertemente correlacionados; (2) problemas de optimización combinatoria donde QAOA o recocido cuántico podrían superar a las metaheurísticas clásicas para instancias específicas; y (3) el aprendizaje automático cuántico, donde resultados teóricos recientes de Huang et al. (2022) demuestran separaciones exponenciales en ciertas tareas de predicción de propiedades de estados cuánticos.

En resumen, la ventaja cuántica se encuentra en un estado de transición: ha sido demostrada convincentemente para tareas de muestreo sin utilidad directa, pero aún no se ha logrado para problemas computacionales prácticos. El camino hacia la utilidad cuántica requiere simultáneamente mejoras en hardware (coherencia, conectividad, fidelidad de compuerta), software (compiladores, optimizadores variacionales, técnicas de mitigación) y teoría (nuevos algoritmos que aprovechen la estructura de problemas reales). La computación cuántica tolerante a fallos, cuando se alcance a escala suficiente, transformará radicalmente este panorama.