¿Qué puede hacer la computadora cuántica D-Wave?

La máquina DWave provocó una gran controversia en la comunidad cuando se anunció por primera vez. Básicamente, la máquina intenta resolver un problema de optimización NP-completo (MAX-2SAT) codificándolo como un estado fundamental de un hamiltoniano e intenta alcanzar este estado fundamental moviéndose adiabáticamente desde el estado fundamental de un hamiltoniano que se puede enfriar de manera eficiente.

En general, no se sabe que el algoritmo adiabático sea capaz de encontrar estados fundamentales de manera eficiente, ya que la proximidad de los niveles bajos al estado fundamental significa que la transición entre hamiltonianos debe realizarse lentamente, y la velocidad a la que esto puede ocurrir está gobernada por la brecha entre el estado fundamental y los niveles excitados más bajos. Se cree comúnmente dentro de la comunidad, pero no está probado, que ningún algoritmo cuántico puede resolver de manera eficiente problemas NP-completos.

En general, el estado fundamental de un hamiltoniano se puede utilizar para codificar una variedad más amplia de problemas que NP (conozca los problemas completos de QMA), por lo que la decisión de centrarse en los problemas de optimización de NP ha dado lugar a restricciones que impiden que el dispositivo se utilice para fines generales. informática cuántica (incluso si el ruido no fuera un problema). Por lo tanto, no puede ejecutar el algoritmo de Shor en el dispositivo. Además, puede factorizar cualquier número que pueda caber en un dispositivo de 128 qubits por medios clásicos. El tamiz de campo numérico general pone 128 bits al alcance de las computadoras personales modernas.

El ruido es un problema real con el dispositivo de DWave, y aunque ha habido una serie de documentos técnicos de ellos minimizando el problema y tratando de demostrar los efectos cuánticos, los tiempos de coherencia para los qubits individuales son mucho más cortos que la escala de tiempo para el algoritmo. Por lo tanto, la opinión común dentro de la comunidad parece ser que se trata básicamente de una costosa computadora clásica de propósito especial.

Hay una sutileza interesante con respecto al ruido: si agrega ruido al algoritmo adiabático, se degrada con gracia en uno de los mejores algoritmos clásicos para el mismo problema. Por lo tanto, puede obtener el mismo resultado de cualquier manera, y la única diferencia está en las asintóticas para sistemas grandes (que obviamente no son observables). Por lo tanto, incluso si producen una respuesta válida para cada problema que le presente a dicho dispositivo, esta no es información suficiente para determinar si realmente está realizando un cálculo cuántico.

Permítanme agregar que el modelo adiabático puede codificar computación cuántica universal, sin embargo, las limitaciones de la implementación de DWave significan que una máquina específica no puede.

Menciona: Encontrar un mínimo global donde la función de saltar de un mínimo a otro se maneja mediante tunelización cuántica.

Tengo la sensación de que para tener una idea de lo que puede hacer en la práctica, uno podría mirar el ejemplo mencionado de gafas giratorias. En otras palabras, la física de acoplamiento de espín cercana a la implementación real del hardware en sí.

http://en.wikipedia.org/wiki/Spin_glass .

Relevante puede ser el trabajo de Giorgio Parisi (Sí, el de las ecuaciones de evolución del partón de Altarelli-Parisi) y sus colaboradores Mezard y Virasoro.

Ver el texto de la Medalla Boltzmann 1992:

La contribución más profunda de Parisi se refiere a la solución del modelo de campo medio de Sherrington-Kirkpatrick para vidrios giratorios. Después de la crisis provocada por las propiedades inaceptables de las soluciones simples, que utilizaban el "truco de la replicación", Parisi propuso su solución de ruptura de la simetría de la réplica, que parece ser exacta, aunque mucho más compleja de lo previsto. Posteriormente, Parisi y sus colaboradores Mezard y Virasoro aclararon en gran medida el significado físico de las misteriosas matemáticas involucradas en este esquema, en términos de distribución de probabilidad de superposiciones y la estructura ultramétrica del espacio de configuración. Este logro constituye uno de los avances más importantes en la historia de los sistemas desordenados. Este descubrimiento abrió las puertas a vastas áreas de aplicación. por ejemplo, en problemas de optimizacióny en teorías de redes neuronales.

http://en.wikipedia.org/wiki/Giorgio_Parisi#Premios