¿Qué tipo de problemas del mundo real (excluyendo la criptografía) se pueden resolver de manera eficiente mediante un algoritmo cuántico?

11

Esta pregunta es muy similar a ¿Hay alguna declaración general sobre qué tipos de problemas se pueden resolver de manera más eficiente utilizando una computadora cuántica?

Pero las respuestas proporcionadas a esas preguntas lo miraron principalmente desde un punto de vista teórico / matemático .

Para esta pregunta, estoy más interesado en el punto de vista práctico / de ingeniería . Por lo tanto, me gustaría entender qué tipo de problemas pueden resolverse de manera más eficiente mediante un algoritmo cuántico que lo que actualmente podría hacer con un algoritmo clásico. ¡Así que realmente asumo que no tienes todo el conocimiento sobre todos los algoritmos clásicos posibles que podrían resolver de manera óptima el mismo problema!

Soy consciente de que el zoológico cuántico expresa una colección completa de problemas para los cuales existe un algoritmo cuántico que se ejecuta de manera más eficiente que un algoritmo clásico, pero no puedo vincular estos algoritmos a problemas del mundo real .

Entiendo que el algoritmo de factorización de Shor es muy importante en el mundo de la criptografía, pero he excluido deliberadamente la criptografía del alcance de esta pregunta, ya que el mundo de la criptografía es un mundo muy específico que merece sus propias preguntas.

2n2n2n2n2n2n

2n×2n

Con un problema del mundo real me refiero a un problema real que podría resolverse mediante un algoritmo cuántico, no me refiero a un dominio en el que podría haber un uso potencial del algoritmo cuántico.

JanVdA
fuente

Respuestas:

7

No daré ninguna declaración precisa sobre qué problemas se pueden resolver de manera más eficiente utilizando algoritmos cuánticos (en comparación con los algoritmos clásicos existentes ), sino más bien algunos ejemplos :

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

κO(log(N)κ2)NO(Nκ)O(Nκ)

Es probable que una de las primeras y más importantes aplicaciones de una computadora cuántica sea la simulación de sistemas de mecánica cuántica. Hay sistemas cuánticos para los que no se conoce una simulación clásica eficiente, pero que podamos simular en una computadora cuántica universal. ¿Qué significa "simular" un sistema físico? Según el DEO, la simulación es "la técnica de imitar el comportamiento de alguna situación o proceso (ya sea económico, militar, mecánico, etc.) por medio de una situación o aparato adecuadamente análogo". Lo que tomaremos como simulación aquí es aproximar la dinámica de un sistema físico. En lugar de adaptar nuestro simulador para simular solo un tipo de sistema físico (que a veces se denomina simulación analógica),

Para los detalles, consulte el capítulo 7 de las notas de la conferencia de Ashley Montaro.

Los algoritmos híbridos cuánticos / clásicos 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 cuántica aproximada [1] es un modelo de juguete de recocido cuántico que se puede utilizar para resolver problemas en la teoría de grafos. El algoritmo utiliza la optimización clásica de las operaciones cuánticas para maximizar una función objetivo.

Eigensolver cuántico variacional

El algoritmo VQE aplica la optimización clásica para minimizar la expectativa de energía de un estado ansatz para encontrar la energía del estado fundamental de una molécula [2] . Esto también se puede extender para encontrar energías excitadas de moléculas. [3] .

Puede encontrar muchos más ejemplos de este tipo en Wikipedia . Además de esos, hay muchos algoritmos recientes que se pueden usar en el aprendizaje automático y la ciencia de datos. Esta respuesta será demasiado larga si agrego los detalles de todos esos. Sin embargo, vea esto y esto y las referencias allí.

[1]: Un algoritmo de optimización cuántico aproximado Farhi et al. (2014)

[2]: Un solucionador de valor propio variacional en un procesador cuántico Peruzzo et al. (2013)

[3]: Computación cuántica variacional de estados excitados Brierley et al. (2018)

Sanchayan Dutta
fuente
1
Gracias por la extensa respuesta. Entonces, la respuesta es para mí lo suficientemente clara para los puntos de la simulación hamiltoniana y el algoritmo cuántico para los sistemas lineales de ecuaciones, pero para los otros puntos falta el vínculo con un problema del mundo real. Para mí, la mayoría de esos algoritmos cuánticos son muy teóricos y no veo cómo se pueden usar para un problema del mundo real. Vincularlos a un problema real del mundo real (incluso muy simple) ya lo haría mucho más claro.
JanVdA
1
@ JanVdA Ya mencioné el uso en el mundo real de las transformadas discretas de Fourier. Por favor, lea eso de nuevo. Los problemas en la teoría de grafos son extremadamente relevantes tanto para la informática como para la física estadística (QAOA). VQE sería relevante para la química computacional. Si ese no es el "mundo real", no sé qué es.
Sanchayan Dutta
Pensé que el primer punto no es sobre DFT sino sobre QFT. Los enlaces sobre QFT explican lo que no es, pero no explica cómo se puede usar para un problema del mundo real. VQE aborda de hecho un problema del mundo real, perdón por no mencionarlo en mi comentario (lo había clasificado en Hamiltonian Simulation). Soy consciente de que un algoritmo cuántico puede mejorar varios problemas en la teoría de gráficos, pero todavía estoy buscando el primer problema del mundo real que puede ser abordado por dicho algoritmo.
JanVdA
@JanVdA QFT podría usarse para los mismos fines que se usa DFT. Sería simplemente más eficiente.
Sanchayan Dutta
@ JanVdA Otro uso común de QFT es en la Estimación de fase cuántica, que se utiliza en particular para el algoritmo cuántico "Sistema de ecuaciones lineales". Ahora estoy un poco ocupado, pero si insistes en ello, explicaré un poco más sobre la respuesta.
Sanchayan Dutta