Los algoritmos de optimización cuántica son algoritmos cuánticos que se utilizan para resolver problemas de optimización. [1] La optimización matemática se ocupa de encontrar la mejor solución a un problema (de acuerdo con algunos criterios) a partir de un conjunto de posibles soluciones. Principalmente, el problema de optimización se formula como un problema de minimización, donde se intenta minimizar un error que depende de la solución: la solución óptima tiene el error mínimo. Se aplican diferentes técnicas de optimización en diversos campos, como la mecánica , la economía y la ingeniería , y a medida que aumenta la complejidad y la cantidad de datos involucrados, se necesitan formas más eficientes de resolver los problemas de optimización. El poder deLa computación cuántica puede permitir resolver problemas que no son prácticamente factibles en los ordenadores clásicos, o sugerir una aceleración considerable con respecto al algoritmo clásico más conocido.
Ajuste de datos cuánticos
El ajuste de datos es un proceso de construcción de una función matemática que se adapta mejor a un conjunto de puntos de datos. La calidad del ajuste se mide mediante algunos criterios, generalmente la distancia entre la función y los puntos de datos.
Ajuste cuántico de mínimos cuadrados
Uno de los tipos más comunes de ajuste de datos es resolver el problema de mínimos cuadrados , minimizando la suma de los cuadrados de las diferencias entre los puntos de datos y la función ajustada.
El algoritmo se da como entrada puntos de datos y funciones continuas . El algoritmo encuentra y da como salida una función continua.que es una combinación lineal de:
En otras palabras, el algoritmo encuentra los coeficientes complejos, y así encuentra el vector .
El algoritmo tiene como objetivo minimizar el error, que viene dado por:
donde definimos para ser la siguiente matriz:
El algoritmo cuántico de ajuste por mínimos cuadrados [2] utiliza una versión del algoritmo cuántico de Harrow, Hassidim y Lloyd para sistemas lineales de ecuaciones (HHL) y genera los coeficientes y la estimación de la calidad de ajuste . Se compone de tres subprogramas: un algoritmo para realizar una pseudo inversa operación, una rutina para la estimación de la calidad en forma, y un algoritmo para el aprendizaje de los parámetros de ajuste.
Debido a que el algoritmo cuántico se basa principalmente en el algoritmo HHL, sugiere una mejora exponencial [3] en el caso en quees escasa y el número de condición (es decir, la relación entre los valores propios más grandes y más pequeños ) de ambos y es pequeño.
Programación cuántica semidefinida
La programación semidefinida (SDP) es un subcampo de optimización que se ocupa de la optimización de una función objetivo lineal (una función especificada por el usuario para minimizar o maximizar), sobre la intersección del cono de matrices semidefinidas positivas con un espacio afín . La función objetivo es un producto interno de una matriz. (dado como entrada) con la variable . Denotamos por el espacio de todos matrices simétricas. La variable debe estar en el cono (convexo cerrado) de matrices simétricas semidefinidas positivas . El producto interno de dos matrices se define como:
El problema puede tener restricciones adicionales (dadas como entradas), también generalmente formuladas como productos internos. Cada restricción fuerza el producto interno de las matrices (dado como entrada) con la variable de optimización ser menor que un valor especificado (dado como entrada). Finalmente, el problema SDP se puede escribir como:
No se sabe que el mejor algoritmo clásico se ejecute incondicionalmente en tiempo polinomial . Se sabe que el problema de viabilidad correspondiente se encuentra fuera de la unión de las clases de complejidad NP y co-NP, o en la intersección de NP y co-NP. [4]
El algoritmo cuántico
Las entradas del algoritmo son y parámetros relacionados con la traza , la precisión y el valor óptimo de la solución (el valor de la función objetivo en el punto óptimo).
El algoritmo cuántico [5] consta de varias iteraciones. En cada iteración, resuelve un problema de factibilidad , es decir, encuentra cualquier solución que satisfaga las siguientes condiciones (dando un umbral):
En cada iteración, un umbral diferente se elige, y el algoritmo genera una solución tal que (y las otras restricciones también se satisfacen) o una indicación de que no existe tal solución. El algoritmo realiza una búsqueda binaria para encontrar el umbral mínimo. para lo cual una solución todavía existe: esto da la solución mínima al problema SDP.
El algoritmo cuántico proporciona una mejora cuadrática sobre el mejor algoritmo clásico en el caso general, y una mejora exponencial cuando las matrices de entrada son de rango bajo .
Optimización combinatoria cuántica
El problema de la optimización combinatoria tiene como objetivo encontrar un objeto óptimo a partir de un conjunto finito de objetos. El problema puede expresarse como una maximización de una función objetivo que es una suma de funciones booleanas . Cada función booleana obtiene como entrada el cadena de bits y da como salida un bit (0 o 1). El problema de optimización combinatoria de bits y cláusulas es encontrar un cadena de bits que maximiza la función
La optimización aproximada es una forma de encontrar una solución aproximada a un problema de optimización, que a menudo es NP-difícil . La solución aproximada del problema de optimización combinatoria es una cadena que está cerca de maximizar .
Algoritmo de optimización aproximada cuántica
Para la optimización combinatoria, el algoritmo de optimización aproximada cuántica (QAOA) [6] tuvo brevemente una mejor relación de aproximación que cualquier algoritmo clásico de tiempo polinomial conocido (para un determinado problema), [7] hasta que se propuso un algoritmo clásico más eficaz. [8] La aceleración relativa del algoritmo cuántico es una cuestión de investigación abierta.
El corazón de QAOA se basa en el uso de operadores unitarios que dependen de ángulos , dondees un número entero de entrada. Estos operadores se aplican iterativamente en un estado que es una superposición cuántica de igual ponderación de todos los estados posibles en la base computacional. En cada iteración, el estado se mide en base computacional yes calculado. Después de un número suficiente de repeticiones, el valor de es casi óptimo, y el estado que se mide también está cerca de ser óptimo.
En 2020, se demostró que QAOA exhibe una fuerte dependencia de la relación entre una restricción de problemas y variables (densidad de problemas), lo que establece una restricción limitante en la capacidad de los algoritmos para minimizar una función objetivo correspondiente . [9]
En el artículo ¿Cuántos qubits se necesitan para la supremacía computacional cuántica presentado a arXiv, [10] los autores concluyen que un circuito QAOA con 420 qubits y 500 restricciones requeriría al menos un siglo para ser simulado utilizando un algoritmo de simulación clásico que se ejecuta en estado- supercomputadoras de última generación, por lo que sería suficiente para la supremacía computacional cuántica .
Ver también
- Computación cuántica adiabática
- Recocido cuántico
Referencias
- ^ Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S .; Chow, Jerry M .; Cruz, Andrew; Egger, Daniel J .; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M .; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, John; Tavernelli, Ivano; Temme, Kristan (2018). "Optimización cuántica mediante algoritmos variacionales en dispositivos cuánticos a corto plazo". Ciencia y Tecnología Cuántica . 3 (3): 030503. arXiv : 1710.01022 . Código bibliográfico : 2018QS & T .... 3c0503M . doi : 10.1088 / 2058-9565 / aab822 . S2CID 56376912 .
- ^ Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2 de agosto de 2012). "Algoritmo cuántico para el ajuste de datos". Cartas de revisión física . 109 (5): 050505. arXiv : 1204.5242 . Código Bibliográfico : 2012PhRvL.109e0505W . doi : 10.1103 / PhysRevLett.109.050505 . PMID 23006156 .
- ^ Montanaro, Ashley (12 de enero de 2016). "Algoritmos cuánticos: una descripción general". Información cuántica de Npj . 2 : 15023. arXiv : 1511.04206 . Código Bibliográfico : 2016npjQI ... 215023M . doi : 10.1038 / npjqi.2015.23 . S2CID 2992738 .
- ^ Ramana, Motakuri V. (1997). "Una teoría de la dualidad exacta para la programación semidefinida y sus implicaciones de complejidad" . Programación matemática . 77 : 129-162. doi : 10.1007 / BF02614433 . S2CID 12886462 .
- ^ Brandao, Fernando GSL; Svore, Krysta (2016). "Aceleraciones cuánticas para programación semidefinida". arXiv : 1609.05537 [ quant-ph ].
- ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "Un algoritmo de optimización aproximada cuántica". arXiv : 1411,4028 [ quant-ph ].
- ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "Un algoritmo de optimización aproximada cuántica aplicado a un problema de restricción de ocurrencia acotada". arXiv : 1412,6062 [ quant-ph ].
- ^ Barak, Booz; Moitra, Ankur; O'Donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John (2015). "Superar la asignación aleatoria en problemas de satisfacción de restricciones de grado acotado". arXiv : 1505.03424 [ cs.CC ].
- ^ Akshay, V .; Philathong, H .; Morales, MES; Biamonte, JD (5 de marzo de 2020). "Déficits de accesibilidad en optimización cuántica aproximada". Cartas de revisión física . 124 (9): 090504. arXiv : 1906.11259 . Código Bibliográfico : 2020PhRvL.124i0504A . doi : 10.1103 / PhysRevLett.124.090504 . PMID 32202873 .
- ^ Dalzell, Alexander M .; Harrow, Aram W .; Koh, Dax Enshan; La Placa, Rolando L. (11 de mayo de 2020). "¿Cuántos qubits se necesitan para la supremacía computacional cuántica?" . Quantum . 4 : 264. arXiv : 1805.05224 . doi : 10.22331 / q-2020-05-11-264 . ISSN 2521-327X .