No hay una forma general de mapear un algoritmo particular en las operaciones de computación cuántica; y, en general, uno de los mayores desafíos con la computación cuántica es el desarrollo de algoritmos para ejecutarlos (el otro gran desafío es enredar más de unos pocos qubits se vuelve difícil y para hacer un cálculo útil vamos a necesitar unos pocos miles de qubits).
Sin embargo, la mayor parte de lo que hemos visto en términos de computación cuántica equivale a realizar búsquedas en problemas que tradicionalmente han sido no polinomiales en problemas polinómicos (por ejemplo, el algoritmo de Shor para factorizar números) o problemas polinómicos en el tiempo de registro.
La mayoría de los algoritmos de aprendizaje automático son polinómicos en el tamaño de los datos de entrada. Muchos de estos se reducen a mirar a través de un espacio de hipótesis que es polinómico en la entrada. Pero en algunos casos, se ha demostrado que se ejecutan en computadoras cuánticas; en particular el trabajo de Seth Lloyd (véase [1307.0411] Algoritmos cuánticos para el aprendizaje automático supervisado y no supervisado); y en una presentación reciente a Google:
- ¿Qué propiedades de la inteligencia humana existen que se sabe que las computadoras cuánticas no pueden procesar en un nivel de complejidad matemática más rápido?
- ¿El resultado del experimento de borrador cuántico de elección retardada depende de la razón de probabilidad del divisor de haz?
- ¿Qué influencia tuvo el atomismo lógico en la Ciencia de la Información Cuántica?
- ¿Es posible transmitir energía de forma inalámbrica a través del enredo cuántico?
- ¿Cuál es su opinión sobre la afirmación de Seth Lloyd: 'El universo es una computadora cuántica'?
