¿Cómo es el diseño de algoritmos para computadoras cuánticas? ¿Funcionarán también los algoritmos estándar para las computadoras cuánticas?

Clint Liddick está hablando de computación cuántica adiabática, y tiene razón al decir que resuelven un problema similar pero que explotan diferentes recursos. En particular, puede codificar respuestas a un problema en un Hamiltoniano particular, y luego resolver las energías de este Hamiltoniano clásicamente usando recocido simulado u otro algoritmo, o puede usarlo como el Hamiltoniano terminal en un esquema de computación cuántica adiabática. Este último esencialmente permitirá hacer túneles a través de barreras de energía, donde en el caso clásico eso no puede suceder.

Para los circuitos cuánticos, puede modelar cualquier circuito clásico en uno cuántico siempre que esté seguro de que es reversible. Si es un circuito clásico irreversible, puede convertirlo en uno reversible con un número polinómico de bits adicionales. En la práctica, esto puede disminuir la eficiencia del circuito cuántico, especialmente cuando observa que cuántico no le da un poco de aceleración mágica solo porque es cuántico. Debes ser inteligente sobre la construcción del algoritmo, específicamente debe explotar la superposición cuántica. Lo mejor que puede obtener de forma gratuita es una aceleración de raíz cuadrada, que proviene del algoritmo de búsqueda de Grover (busca una o algunas soluciones de un espacio de solución completo que crece exponencialmente en la cantidad de bits que tiene). Pero la mayoría de los algoritmos clásicos no se pueden construir de esta manera, por lo que es posible que el circuito cuántico sea más lento (pero no lo suficientemente lento como para ser expulsado de la clase de complejidad del circuito clásico, recuerde que la sobrecarga sigue siendo polinómica).

En un sentido de muy alto nivel, sí. Están tratando de resolver el mismo tipo de problemas (o un subconjunto muy específico de problemas) que todos los demás, y la idea básica (encontrar los mínimos / máximos para una solución óptima) es la misma, pero la forma en que se encuentra la solución usa un algoritmo diferente.

Actualmente, lo mejor que tenemos es la D-Wave, y utiliza el recocido cuántico para tratar de encontrar mínimos / máximos óptimos de funciones de costo complejas sin quedar atrapados en los mínimos / máximos locales (como lo hacen nuestros algoritmos heurísticos deterministas actuales).