Supongamos que hemos construido una computadora cuántica universal.
Excepto por cuestiones relacionadas con la seguridad (criptografía, privacidad, ...), ¿qué problemas actuales del mundo real pueden beneficiarse al usarlo?
Estoy interesado en ambos:
- problemas actualmente irresolubles para una entrada práctica,
- problemas que actualmente se están resolviendo, pero una aceleración significativa mejoraría en gran medida su usabilidad.
quantum-computing
application-of-theory
Piotr Migdal
fuente
fuente
Respuestas:
Simulando eficientemente la mecánica cuántica.
fuente
Brassard, Hoyer, Mosca y Tapp mostraron que la búsqueda generalizada de Grover, llamada amplificación de amplitud, puede usarse para obtener una aceleración cuadrática en una gran clase de heurísticas clásicas. La intuición detrás de su idea es que las heurísticas clásicas usan la aleatoriedad para buscar una solución a un problema dado, por lo que podemos usar la amplificación de amplitud para buscar en el conjunto de cadenas aleatorias una que haga que la heurística encuentre una buena solución. Esto produce una aceleración cuadrática en el tiempo de ejecución del algoritmo. Consulte la sección 3 del documento vinculado anteriormente para obtener más detalles.
fuente
¡Simulando sistemas cuánticos!
Noté que en la otra respuesta que mencionaba esto había varios comentarios sobre si esto era cierto, ya que es una afirmación no obvia. Y la gente solicitó referencias. Aquí hay algunas referencias.
Propuesta original de Feynman:
Algoritmos eficientes para todos los sistemas cuánticos definidos por hamiltonianos "locales". (Lloyd también explica que cualquier sistema consistente con la relatividad especial y general evoluciona de acuerdo con las interacciones locales).
Mayor generalización a los hamiltonianos dispersos, que son más generales que los hamiltonianos locales:
Otras lecturas:
fuente
La visión es peligrosa y polémica en este campo, por lo que debemos ser cautelosos con este tema. Sin embargo, algunos algoritmos Q con aceleraciones polinómicas tienen aplicaciones potenciales interesantes.
Se sabe que la búsqueda de Grover se puede utilizar para filtrar polinomialmente la solución a problemas de NP completo [1] . Esto está probado para 3-SAT en [2] . Algunas aplicaciones de SAT, tomadas de [3] , son: verificación de equivalencia de circuitos , generación automática de patrones de prueba , verificación de modelos utilizando lógica de tiempo lineal , planificación en inteligencia artificial y haplotipado en bioinformática . Aunque no sé mucho sobre estos temas, esta línea de investigación me parece bastante práctica.
Además, existe un algoritmo cuántico para evaluar los árboles NAND con una aceleración polinómica sobre la computación clásica [ 8 , 10 , 11 ]. El árbol NAND es un ejemplo de un árbol de juego, una estructura de datos más general utilizada para estudiar partidos de juegos de mesa como Chess and Go. Parece plausible que este tipo de aceleraciones se pueda utilizar para diseñar jugadores de juegos de software más potentes. ¿Podría esto interesar a algunos desarrolladores de videojuegos cuánticos?
Desafortunadamente, jugar juegos en realidad no es exactamente lo mismo que evaluar árboles: hay complicaciones, por ejemplo, si sus jugadores no están usando estrategias óptimas [ 12 ]. No he visto ningún estudio que considere un escenario de la vida real, por lo que es difícil decir cuán beneficioso es la aceleración de [ 8 ] en la práctica. Este podría ser un buen tema de discusión.
fuente
cree que ha planteado una excelente pregunta en las fronteras de la investigación de QM (parcialmente indicada por su falta de respuestas hasta ahora), pero no se ha definido o capturado completamente como un problema. la pregunta está en la línea de "¿qué pueden exactamente los algoritmos de QM calcular eficientemente de todos modos?" y no se conoce una respuesta completa y se busca activamente. algo de esto está relacionado con la complejidad (preguntas abiertas sobre) de las clases relacionadas con QM.
este sería el caso de que haya una pregunta algo formal definida. Si se puede demostrar que las clases de QM son equivalentes a las clases no QM "significativamente poderosas", entonces ahí está su respuesta. El tema general de este tipo de resultado sería una clase "no tan difícil en QM" es equivalente a una clase "difícil en no QM". existen varias separaciones de clase de complejidad abierta de este tipo (tal vez alguien más pueda sugerirlas con más detalle).
Algo extraño sobre el conocimiento actual de QM sobre algoritmos cuánticos es que hay una especie de extraña bolsa de algoritmos que se sabe que funcionan en QM pero aparentemente no hay mucha coherencia / cohesión para ellos. parecen extraños y desconectados de alguna manera. no existe una "regla general" aparente para "los problemas que son computables en QM son generalmente de esta forma" a pesar de una expectativa razonable de que uno podría estar allí.
por ejemplo, contrasta esto con la teoría de la integridad de NP, que es mucho más coherente en comparación. parece que tal vez si la teoría QM está mejor desarrollada obtendría este mayor sentido de cohesión que recuerda a la teoría de completitud NP.
Una idea más fuerte podría ser que, con el tiempo, cuando la teoría de la complejidad QM se desarrolle mejor, la integridad de NP se ajustará "perfectamente" de alguna manera.
para mí, la aceleración de QM más general o la estrategia ampliamente aplicable que he visto parece ser el algoritmo de Grovers porque hay mucho software práctico relacionado con las consultas de db. y de alguna manera cada vez más "no estructurados":
fuente