Algoritmo cuántico

En computación cuántica, un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, siendo el modelo más comúnmente utilizado el modelo de computación de circuito cuántico. Un algoritmo clásico (o no cuántico) es una secuencia finita de instrucciones, o un procedimiento paso a paso para resolver un problema, donde cada paso o instrucción se puede realizar en una computadora clásica. De manera similar, un algoritmo cuántico es un procedimiento paso a paso, donde cada uno de los pasos se puede realizar en una computadora cuántica. Aunque todos los algoritmos clásicos también se pueden realizar en una computadora cuántica, el término algoritmo cuántico se usa generalmente para aquellos algoritmos que parecen inherentemente cuánticos o que utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el entrelazamiento cuántico.

Los problemas que son indecidibles con las computadoras clásicas siguen siendo indecidibles con las computadoras cuánticas. Lo que hace que los algoritmos cuánticos sean interesantes es que podrían resolver algunos problemas más rápido que los algoritmos clásicos porque la superposición cuántica y el entrelazamiento cuántico que explotan los algoritmos cuánticos probablemente no puedan simularse de manera eficiente en computadoras clásicas (ver Supremacía cuántica).

Los algoritmos más conocidos son el algoritmo de Shor para factorización y el algoritmo de Grover para buscar en una base de datos no estructurada o en una lista desordenada. Los algoritmos de Shor se ejecutan mucho (casi exponencialmente) más rápido que el algoritmo clásico de factorización más conocido, el tamiz de campo numérico general. El algoritmo de Grover se ejecuta cuadráticamente más rápido que el mejor algoritmo clásico posible para la misma tarea, una búsqueda lineal.

Descripción general

Los algoritmos cuánticos generalmente se describen, en el modelo de circuito de computación cuántica comúnmente utilizado, mediante un circuito cuántico que actúa sobre algunos qubits de entrada y termina con una medición. Un circuito cuántico consta de puertas cuánticas simples que actúan como máximo sobre un número fijo de qubits. El número de qubits debe ser fijo porque un número cambiante de qubits implica una evolución no unitaria. Los algoritmos cuánticos también pueden enunciarse en otros modelos de computación cuántica, como el modelo del oráculo hamiltoniano.

Los algoritmos cuánticos se pueden clasificar según las principales técnicas utilizadas por el algoritmo. Algunas técnicas/ideas comúnmente utilizadas en algoritmos cuánticos incluyen retroceso de fase, estimación de fase, transformada cuántica de Fourier, paseos cuánticos, amplificación de amplitud y teoría de campos cuánticos topológicos. Los algoritmos cuánticos también se pueden agrupar por el tipo de problema resuelto; por ejemplo, consulte la encuesta sobre algoritmos cuánticos para problemas algebraicos.

Algoritmos basados en la transformada cuántica de Fourier

La transformada cuántica de Fourier es el análogo cuántico de la transformada discreta de Fourier y se utiliza en varios algoritmos cuánticos. La transformada de Hadamard es también un ejemplo de transformada cuántica de Fourier en un espacio vectorial de n dimensiones sobre el campo F2. La transformada cuántica de Fourier se puede implementar de manera eficiente en una computadora cuántica utilizando solo un número polinómico de puertas cuánticas.

Algoritmo Deutsch-Jozsa

El algoritmo Deutsch-Jozsa resuelve un problema de caja negra que requiere exponencialmente muchas consultas a la caja negra para cualquier computadora clásica determinista, pero que una computadora cuántica puede resolver con una sola consulta. Sin embargo, al comparar algoritmos clásicos y cuánticos de error acotado, no hay aceleración ya que un algoritmo probabilístico clásico puede resolver el problema con un número constante de consultas con una pequeña probabilidad de error. El algoritmo determina si una función f es constante (0 en todas las entradas o 1 en todas las entradas) o equilibrada (devuelve 1 para la mitad del dominio de entrada y 0 para la otra mitad).

Algoritmo de Bernstein-Vazirani

El algoritmo de Bernstein-Vazirani es el primer algoritmo cuántico que resuelve un problema de manera más eficiente que el algoritmo clásico más conocido. Fue diseñado para crear una separación oráculo entre BQP y BPP.

Algoritmo de Simon

El algoritmo de Simon resuelve un problema de caja negra exponencialmente más rápido que cualquier algoritmo clásico, incluidos los algoritmos probabilísticos de error acotado. Este algoritmo, que logra una aceleración exponencial sobre todos los algoritmos clásicos que consideramos eficientes, fue la motivación para el algoritmo de factorización de Shor.

Algoritmo de estimación de fase cuántica

El algoritmo de estimación de fase cuántica se utiliza para determinar la fase propia de un vector propio de una puerta unitaria dado un estado cuántico proporcional al vector propio y al acceso a la puerta. El algoritmo se utiliza frecuentemente como subrutina en otros algoritmos.

Algoritmo de Shor

El algoritmo de Shor resuelve el problema de logaritmos discretos y el problema de factorización de enteros en tiempo polinomial, mientras que los algoritmos clásicos más conocidos toman tiempo superpolinomial. No se sabe que estos problemas estén en P o NP-completo. También es uno de los pocos algoritmos cuánticos que resuelve un problema que no es de caja negra en tiempo polinómico, mientras que los algoritmos clásicos más conocidos se ejecutan en tiempo superpolinomial.

Problema de subgrupo oculto

El problema de subgrupos ocultos abelianos es una generalización de muchos problemas que pueden resolverse con una computadora cuántica, como el problema de Simon, que resuelve la ecuación de Pell, prueba el ideal principal de un anillo R y factoriza. Existen algoritmos cuánticos eficientes conocidos para el problema de subgrupos ocultos abelianos. El problema de subgrupo oculto más general, donde el grupo no es necesariamente abeliano, es una generalización de los problemas mencionados anteriormente y del isomorfismo gráfico y ciertos problemas de celosía. Se conocen algoritmos cuánticos eficientes para ciertos grupos no abelianos. Sin embargo, no se conocen algoritmos eficientes para el grupo simétrico, lo que daría un algoritmo eficiente para el isomorfismo de grafos y el grupo diédrico, que resolvería ciertos problemas de red.

Estimación de sumas de Gauss

Una suma de Gauss es un tipo de suma exponencial. El algoritmo clásico más conocido para estimar estas sumas requiere un tiempo exponencial. Dado que el problema de los logaritmos discretos se reduce a la estimación de la suma de Gauss, un algoritmo clásico eficiente para estimar sumas de Gauss implicaría un algoritmo clásico eficiente para calcular logaritmos discretos, lo cual se considera poco probable. Sin embargo, las computadoras cuánticas pueden estimar sumas de Gauss con precisión polinómica en tiempo polinómico.

Pesca de Fourier y comprobación de Fourier

Tenemos un oráculo que consta de n funciones booleanas aleatorias que asignan cadenas de n bits a un valor booleano. Estamos obligados a encontrar n cadenas n de bits z₁,..., z_n tal que para la transformada de Hadamard-Fourier, al menos 3/4 de las cadenas satisfacen

${fnMicrosoft Sans Serif} 1}$

y al menos 1/4 satisface

${fnMicrosoft Sans Serif} 2.}$

Esto se puede hacer en tiempo polinomial cuántico de error acotado (BQP).

Algoritmos basados en amplificación de amplitud

La amplificación de amplitud es una técnica que permite la amplificación de un subespacio elegido de un estado cuántico. Las aplicaciones de amplificación de amplitud suelen conducir a aceleraciones cuadráticas con respecto a los algoritmos clásicos correspondientes. Puede considerarse una generalización del algoritmo de Grover.

Algoritmo de Grover

El algoritmo de Grover busca una base de datos no estructurada (o una lista no ordenada) con entradas N, para una entrada marcada, utilizando sólo ${displaystyle O({sqrt {N})}$ consultas en lugar de las ${displaystyle O({N}}$ las consultas requieren clásicamente. Clásicamente, ${displaystyle O({N}}$ las consultas son necesarias incluso permitiendo algoritmos probabilísticos de terror consolidado.

Los teóricos han considerado una hipotética generalización de una computadora cuántica estándar que podría acceder a las historias de las variables ocultas en la mecánica bohmiana. (Tal computadora es completamente hipotética y sería no ser un ordenador cuántico estándar, o incluso posible bajo la teoría estándar de la mecánica cuántica.) Such a hipothetical computer could implement a search of an N-item database at most in ${displaystyle O({sqrt[{3}{N}}} {fn}} {fn}}}}$ pasos. Esto es un poco más rápido que el ${displaystyle O({sqrt {N})}$ pasos tomados por el algoritmo de Grover. Tampoco el método de búsqueda permitiría un modelo de computadora cuántica resolver problemas completos NP en tiempo polinomio.

Conteo cuántico

Cuento cuántico resuelve una generalización del problema de búsqueda. Resolve el problema de contar el número de entradas marcadas en una lista no ordenada, en lugar de simplemente detectar si existe. Específicamente, cuenta el número de entradas marcadas en una ${displaystyle N}$- lista de elementos, con error ${displaystyle varepsilon }$ sólo ${displaystyle Theta left({frac {1}{varepsilon }{sqrt {frac {fn}}right)}$ consultas, dónde ${displaystyle k}$ es el número de elementos marcados en la lista. Más precisamente, el algoritmo produce una estimación ${displaystyle k'}$ para ${displaystyle k}$, el número de entradas marcadas, con la siguiente precisión: ${displaystyle TENK-K'Antesleq varepsilon k}$.

Algoritmos basados en paseos cuánticos

Una caminata cuántica es el análogo cuántico de una caminata aleatoria clásica, que puede describirse mediante una distribución de probabilidad sobre algunos estados. Una caminata cuántica puede describirse mediante una superposición cuántica de estados. Se sabe que los paseos cuánticos dan aceleraciones exponenciales para algunos problemas de caja negra. También proporcionan aceleraciones polinómicas para muchos problemas. Existe un marco para la creación de algoritmos de caminata cuántica y es una herramienta bastante versátil.

Problema de muestreo de bosones

El problema de muestreo de bosones en una configuración experimental supone que una entrada de bosones (por ejemplo, fotones de luz) de un número moderado se dispersa aleatoriamente en una gran cantidad de modos de salida limitados por una unitaridad definida. Cuando se utilizan fotones de luz individuales, el problema es isomorfo a una caminata cuántica de múltiples fotones. El problema es entonces producir una muestra justa de la distribución de probabilidad de la salida que depende de la disposición de entrada de los bosones y la unitaridad. Resolver este problema con un algoritmo informático clásico requiere calcular el permanente de la matriz de transformación unitaria, lo que puede ser imposible o llevar un tiempo prohibitivamente largo. En 2014, se propuso que la tecnología existente y los métodos probabilísticos estándar para generar estados de fotón único podrían usarse como entrada en una red óptica lineal computable cuántica adecuada y que el muestreo de la distribución de probabilidad de salida sería demostrablemente superior utilizando algoritmos cuánticos. En 2015, una investigación predijo que el problema de muestreo tenía una complejidad similar para entradas distintas de los fotones del estado de Fock e identificó una transición en la complejidad computacional de lo clásicamente simulable a tan difícil como el problema de muestreo de bosones, dependiendo del tamaño de las entradas de amplitud coherente.

Problema de distinción de elementos

El problema de la diferencia de elementos es el problema de determinar si todos los elementos de una lista son distintos. Clásicamente, ΩN) consultas son necesarias para una lista de tamaño N. Sin embargo, se puede resolver en ${displaystyle Theta (N^{2/3})}$ consultas en una computadora cuántica. El algoritmo óptimo es de Andris Ambainis. Yaoyun Shi primero demostró un límite inferior ajustado cuando el tamaño de la gama es suficientemente grande. Ambainis y Kutin independientemente (y a través de diferentes pruebas) ampliaron su trabajo para obtener el límite inferior para todas las funciones.

Problema de búsqueda de triángulos

El problema de encontrar triángulos es el problema de determinar si una gráfica dada contiene un triángulo (una camarilla de tamaño 3). El límite inferior más conocido para los algoritmos cuánticos es Ω(N), pero el mejor algoritmo conocido requiere consultas O(N^1.297), un mejora con respecto a las mejores consultas O(N^1.3) anteriores.

Evaluación de fórmulas

Una fórmula es un árbol con una puerta en cada nodo interno y un bit de entrada en cada nodo hoja. El problema es evaluar la fórmula, que es la salida del nodo raíz, dado el acceso de Oracle a la entrada.

Una fórmula bien estudiada es el árbol binario equilibrado con sólo puertas NAND. Este tipo de fórmula requiereN^c) consultas con el azar, donde ${displaystyle c=log _{2}(1+{sqrt {33}})/4approx 0.754}$. Sin embargo, con un algoritmo cuántico, se puede resolver enN^0.5) consultas. No mejor algoritmo cuántico para este caso fue conocido hasta que se encontró uno para el modelo de oráculo no convencional Hamiltoniano. El mismo resultado para el ajuste estándar pronto siguió.

También se conocen algoritmos cuánticos rápidos para fórmulas más complicadas.

Conmutatividad de grupo

El problema es determinar si un grupo de caja negra, dado por k generadores, es conmutativo. Un grupo de caja negra es un grupo con una función de oráculo, que debe utilizarse para realizar las operaciones del grupo (multiplicación, inversión y comparación con la identidad). Nos interesa la complejidad de la consulta, que es el número de llamadas oráculo necesarias para resolver el problema. Las complejidades de las consultas deterministas y aleatorizadas son ${displaystyle Theta (k^{2})}$ y ${displaystyle Theta (k)}$ respectivamente. Un algoritmo cuántico requiere ${displaystyle (k^{2/3})}$ consultas pero el algoritmo más conocido utiliza ${displaystyle O(k^{2/3}log k)}$ consultas.

Problemas de BQP completo

La clase de complejidad BQP (tiempo polinómico cuántico de error acotado) es el conjunto de problemas de decisión que puede resolver una computadora cuántica en tiempo polinómico con una probabilidad de error de como máximo 1/3 para todos los casos. Es el análogo cuántico de la clase de complejidad clásica BPP.

Un problema es bqp -complete si está en bqp y cualquier problema en bqp puede reducirse a él en tiempo polinómico. Informalmente, la clase de problemas bqp y complementos son aquellos que son tan difíciles como los problemas más difíciles en bqp y son de manera eficiente solucionable por una computadora cuántica (con error limitado).

Calcular invariantes de nudos

Witten había demostrado que la teoría de campos cuánticos topológicos de Chern-Simons (TQFT) se puede resolver en términos de polinomios de Jones. Una computadora cuántica puede simular un TQFT y, por lo tanto, aproximarse al polinomio de Jones, que, hasta donde sabemos, es difícil de calcular de manera clásica en el peor de los casos.

Simulación cuántica

La idea de que las computadoras cuánticas podrían ser más poderosas que las clásicas se originó en la observación de Richard Feynman de que las computadoras clásicas parecen requerir un tiempo exponencial para simular sistemas cuánticos de muchas partículas. Desde entonces, la idea de que las computadoras cuánticas pueden simular procesos físicos cuánticos exponencialmente más rápido que las computadoras clásicas se ha desarrollado y elaborado en gran medida. Se han desarrollado algoritmos cuánticos eficientes (es decir, de tiempo polinomial) para simular sistemas bosónicos y fermiónicos y, en particular, la simulación de reacciones químicas más allá de las capacidades de las supercomputadoras clásicas actuales requiere solo unos pocos cientos de qubits. Las computadoras cuánticas también pueden simular eficientemente teorías topológicas de campos cuánticos. Además de su interés intrínseco, este resultado ha llevado a algoritmos cuánticos eficientes para estimar invariantes topológicos cuánticos como los polinomios de Jones y HOMFLY, y el invariante Turaev-Viro de variedades tridimensionales.

Resolver sistemas lineales de ecuaciones

En 2009, Aram Harrow, Avinatan Hassidim y Seth Lloyd formularon un algoritmo cuántico para resolver sistemas lineales. El algoritmo estima el resultado de una medición escalar en el vector solución de un sistema lineal de ecuaciones dado.

Siempre que el sistema lineal es un escaso y tiene un número de baja condición ${displaystyle kappa }$, y que el usuario está interesado en el resultado de una medición de escalar en el vector de solución, en lugar de los valores del vector de solución en sí, entonces el algoritmo tiene un tiempo de ejecución ${displaystyle O(log(N)kappa ^{2}$, donde ${displaystyle N}$ es el número de variables en el sistema lineal. Esto ofrece una velocidad exponencial sobre el algoritmo clásico más rápido, que se ejecuta en ${displaystyle O(Nkappa)}$ (o ${displaystyle O(N{sqrt {kappa }}}}$ para matrices semidefinidas positivas).

algoritmos cuánticos/clásicos híbridos

Los algoritmos cuánticos/clásicos híbridos combinan la preparación y medición del estado cuántico con la optimización clásica. Estos algoritmos generalmente apuntan a determinar el vector propio del estado fundamental y el valor propio de un operador hermitiano.

qaoa

El algoritmo de optimización aproximada cuántica se inspira en el recocido cuántico, realizando una aproximación discretizada del recocido cuántico en un circuito cuántico. Se puede usar para resolver problemas en la teoría de gráficos. El algoritmo utiliza la optimización clásica de las operaciones cuánticas para maximizar una función objetivo.

Eigensolver de eigensolver cuántico variacional

El algoritmo de eigensolver cuántico variacional (VQE) aplica la optimización clásica para minimizar la expectativa energética de un estado Ansatz para encontrar el estado fundamental de un operador, como un hamiltoniano de una molécula. Esto también se puede extender para encontrar energías excitadas de moléculas.

CONTRATADO CUANTUM EIGENSOLVER

El algoritmo CQE minimiza el residuo de una contracción (o proyección) de la ecuación de Schrödinger en el espacio de dos (o más) electrones para encontrar la energía de estado de tierra o excitado y la matriz de densidad reducida de dos electrones de una molécula de una molécula. Se basa en métodos clásicos para resolver energías y matrices de densidad reducida de dos electrones directamente de la ecuación de Schrödinger contratada anti-hermitiana.