En la década de 1990, Bennett, Bernstein, Brassard y Vazirani demostraron rigurosamente que las computadoras cuánticas no pueden lograr más que una aceleración cuadrática para llevar a cabo la búsqueda de fuerza bruta. Esta aceleración cuadrática se realiza mediante el algoritmo de Grover. Es decir, para buscar en una base de datos no estructurada de tamaño N, puede usar ✓N pasos en una computadora cuántica, mientras que necesita ordenar N en una computadora clásica. Para obtener una aceleración cuántica más sustancial, debe haber más estructura en el problema para que la computadora cuántica pueda explotar.
La parte difícil, algorítmicamente en muchos algoritmos de aprendizaje automático, a menudo se reduce a un problema difícil de optimización. En un problema de optimización, si el panorama de optimización parece completamente aleatorio, con el valor de la función objetivo en un punto completamente sin correlación con el de sus vecinos, la aceleración cuántica máxima es cuadrática. Si el panorama de optimización es totalmente simple y suave como una gran cuenca, entonces el problema ya es fácil para algoritmos clásicos como el descenso de gradiente. La esperanza es que las computadoras cuánticas puedan lograr una aceleración exponencial para el caso intermedio, donde la función objetivo tiene cierta estructura pero también óptimos locales que atraparían los algoritmos clásicos.
- Soy estudiante de informática. ¿Pueden ayudarme a decidir sobre un proyecto de último año que involucre desarrollo de IA y Android?
- ¿Cuáles son algunos errores famosos en el mundo de la informática?
- ¿Cuál es la diferencia entre una cookie y un píxel?
- ¿Cómo determina si está hablando con una computadora o una persona?
- Sistemas de archivos: ¿Cómo se compara exFAT con FAT y NTFS?
