¿Qué es más prometedor para los problemas de optimización: computación cuántica o algoritmos evolutivos?

No está claro en este momento qué tan probable es que la humanidad construya una computadora cuántica pronto. Pero suponiendo que esté construido, será significativamente mejor que la informática clásica (y, por lo tanto, los algoritmos evolutivos) para resolver los siguientes tipos de problemas:

1. Factoraje y problemas relacionados (como el problema del subgrupo oculto). El factoring se usa ampliamente en criptografía y la capacidad de una computadora cuántica para resolverlo mucho más rápido que una computadora clásica es una de las razones por las que las computadoras cuánticas han ganado tanta popularidad.
2. Problemas de optimización que la naturaleza ya está resolviendo eficientemente de manera regular.

Las computadoras cuánticas serán solo un poco mejores que las computadoras clásicas para todos los demás problemas de optimización. En particular, no nos ayudarán a resolver problemas NP-completos mucho mejor que una computadora clásica.

(Tenga en cuenta que todo esto se basa en conjeturas teóricas ampliamente creídas, ninguna de las cuales ha sido probada).

No asumiría que debe haber una respuesta universal, ni que estas posibilidades sean solo estas dos.

Ambos pueden ser subóptimos, para muchos tipos de problemas.

Dicho esto: la computación cuántica, actualmente, es solo una línea plausible de investigación.

Los algoritmos evolutivos, por otro lado (por ejemplo: algoritmos genéticos) tienen la ventaja de ser algo que puede probar usted mismo hoy (aunque, por supuesto, siempre hay más para aprender).

Tampoco está claro si la computación cuántica puede escalar de una manera útil (más allá de los límites de ruido, aunque estoy simplificando demasiado los problemas aquí y, para ser justos, todos los dispositivos informáticos tienen límites de tamaño fijos). El tipo de problemas que parece adaptarse a la computación cuántica son aquellos que experimentan un crecimiento exponencial en las posibilidades a medida que los problemas crecen. Mientras tanto, la computación cuántica parece estar limitada a problemas de tamaño fijo relativamente pequeños. Y necesitará problemas de tamaño fijo razonablemente grandes si desea que el mecanismo sea más eficiente que (por ejemplo) una tabla de búsqueda. Y hay otros problemas y problemas.

En el lado prometedor, es muy posible que los algoritmos evolutivos se puedan implementar en máquinas de computación cuántica, si existieran.

Así que aquí hay un proyecto a considerar: simular una computadora cuántica. Piense en cuestiones como el cableado, el “conjunto de instrucciones” y las aplicaciones. Luego intente programarlo. Los problemas con los que te encuentres te dirán mucho más de lo que podría en una respuesta como esta.

También puede intentar trabajar con algunos ejemplos evolutivos. Una vez más, los problemas con los que te encuentres te dirán mucho más que yo.