El algoritmo de factorización numérica de Shor es el que convenció a la prensa popular y al gobierno de los EE. UU. A tomar en serio la computación cuántica. Si alguien descubre cómo construir computadoras cuánticas confiables de tamaño suficientemente grande, el algoritmo de Shor será inmediatamente útil para romper las claves de cifrado RSA que usa su navegador web cuando compra en Amazon. Es teóricamente posible que alguien invente un algoritmo convencional para hacer lo mismo (factorizar grandes números en números primos en un tiempo polinómico bajo), pero pocas personas esperan esto. Sin embargo, esto significa que el algoritmo de Shor no proporciona una aceleración demostrable en el peor de los casos sobre los mejores algoritmos convencionales (que aún no se han descubierto). En el lado positivo, la aceleración sobre los algoritmos más conocidos es enorme (más que el tiempo polinómico).
La búsqueda de Grover es un algoritmo más impresionante para una perspectiva teórica porque proporciona una aceleración demostrable sobre los mejores algoritmos convencionales en un entorno determinado. Sin embargo, logra esto restringiendo lo que pueden hacer los algoritmos convencionales. En la práctica, a menudo puede eludir tales restricciones y hacerlo mejor que Grover utilizando algoritmos convencionales ligeramente especializados. Ver más detalles en [quant-ph / 0405001v1] ¿Es práctica la búsqueda cuántica? (mi trabajo) Si bien se conocen usos adicionales para la búsqueda de Grover, su importancia es principalmente teórica.
Resolviendo grandes sistemas de ecuaciones lineales , vea esta cuenta reciente
[1302.1210] Resolución de sistemas de ecuaciones lineales en una computadora cuántica
(No es el primer artículo sobre el tema). Este es un desarrollo emocionante, pero es fácil de entender mal porque la respuesta se produce como datos cuánticos, por lo que no se puede convertir completamente en bits habituales. Dichas técnicas son útiles en aplicaciones donde necesita conocer alguna característica de la solución que pueda expresarse de manera sucinta.
- ¿Podemos ver visualmente los resultados del experimento cuántico de elección retrasada?
- ¿La computadora cuántica se convertiría en el fin del avance de la computadora?
- ¿Qué consejo le daría un profesor de física a un graduado de último año: para investigar durante un año en computación cuántica o para asistir a un programa de maestría en física?
- ¿Puede un estado cuántico de superposición ser visible a escala macroscópica?
- ¿Qué innovaciones no obvias permitiría la computación cuántica?
Un tercer tipo de algoritmos cuánticos es muy amplio (e incluye algunos usos de la técnica anterior), pero puede ser el más prometedor todavía. La idea es simular efectos a nivel atómico que puedan ayudarnos, por ejemplo, a producir energía a partir de la fotosíntesis artificial. Sin embargo, esto no es algo que puedas ejecutar en tu iPad. Para más detalles, consulte [1203.1331] Introducción a los algoritmos cuánticos para física y química
Hay varios otros algoritmos cuánticos interesantes (al menos en docenas), pero algunos de ellos se centran en tareas muy limitadas / abstractas, o problemas que pueden resolverse perfectamente en las computadoras convencionales (los algoritmos cuánticos proporcionan una pequeña aceleración, que puede ser derrotado por la complejidad, los gastos generales y la poca fiabilidad de las computadoras cuánticas). Puede encontrar documentos sobre algoritmos cuánticos para la búsqueda en la web ([1303.3891] Google cuántico en una red compleja), pero resumen convenientemente algunos detalles que hacen que tales técnicas sean irremediablemente imprácticas.
También hay muchos “límites inferiores”: resultados que descartan la aceleración cuántica para algunos problemas, como la clasificación (que es la razón por la cual no se escucha sobre la clasificación cuántica).
En el primer gráfico, está la lista desordenada. La amplitud roja representa el elemento deseado. El primer paso es voltear esa amplitud. Entonces, en aras de una fácil comprensión, he dibujado dónde estaría ahora el promedio de las amplitudes. Finalmente voltea todas las amplitudes alrededor del promedio. Como se puede ver, hacer esto repetidamente aumentará la amplitud deseada. 
