¿El recocido cuántico sirve para algo?

He leído sobre el recocido cuántico, y particularmente sobre la forma en que lo hacen compañías como D-wave. Creo que entiendo cómo funciona y cómo aprovecha los túneles para encontrar un óptimo global en un potencial energético dado.

Pero el elefante en la habitación es: ¿Cómo puede ser de alguna utilidad? ¿De qué sirve buscar un óptimo en un potencial que tú mismo has creado? Si el potencial fuera una caja negra, entonces podría ver algún uso. Pero claramente el potencial se prepara de manera controlable, por lo que parece frustrar el propósito.

Por favor aclara mi confusión.

¿Estás preguntando por qué es útil encontrar el mínimo de una función que creaste tú mismo? Suponga que está tratando de descubrir cómo construir una casa con la cantidad mínima de dinero. Puede escribir una función para la cantidad de dinero necesaria donde los materiales de construcción son los insumos. Esa es una función que creaste, pero obviamente te gustaría minimizarla.

Respuestas (2)

Está pensando que el "potencial" toma la forma de una función completamente arbitraria y no estructurada de toda la configuración del campo. Encontrar el mínimo de este tipo de función es un ejemplo de lo que en informática teórica se denomina "búsqueda no estructurada". De hecho, el recocido cuántico no acelera mucho la búsqueda no estructurada; se ha demostrado que el algoritmo de Grover brinda la mejor aceleración cuántica posible para la búsqueda no estructurada, que es "solo" una raíz cuadrada en lugar de una aceleración exponencial.

(En realidad, esto no es realmente correcto. Encontrar el mínimo de una función no estructurada completamente arbitraria es aún más difícil que la formulación habitual del problema de decisión de la búsqueda no estructurada, porque se encuentra incluso fuera del equivalente de búsqueda de la clase de complejidad NP. Eso es porque incluso si una computadora cuántica le diera una respuesta, la única forma posible de verificarla sería repetir efectivamente toda la búsqueda nuevamente. Entonces, en el mundo real, tal computadora cuántica podría no ser muy útil, porque no habría forma práctica de verificar si su respuesta fue correcta o si la computadora tenía un error. Además, si el espacio de búsqueda fuera exponencialmente grande, incluso cargar la declaración del problema enla computadora podría tomar más tiempo que la edad del universo, y mucho menos que la computadora lo resuelva).

Pero este no es el tipo de potencial que se construye en el recocido cuántico. El potencial no es arbitrario sino que está altamente estructurado. El problema prototípico que ataca QA es el problema del vidrio giratorio de Ising . Los detalles no son importantes, pero el punto es que solo una fracción exponencialmente pequeña de todos los potenciales posibles se puede formular como un vidrio giratorio de Ising. (Concretamente, especificando un hamiltoniano de vidrio giratorio de Ising en un sistema de norte los giros solo requieren especificar ( norte  elegir  2 ) = ( 1 / 2 ) norte ( norte − 1 ) ∼ norte 2 diferentes parámetros, mientras que un hamiltoniano completamente arbitrario requiere 2 norte parámetros para especificar.) Dado que ha especificado el ∼ norte 2 diferentes acoplamientos pero no el explícito ∼ 2 norte diferentes energías posibles, realmente no "tienes un control exacto" del potencial, aunque formalmente lo conoces con exactitud.

Como analogía, considere el problema del viajante de comercio: si tuviera que enumerar un montón de viajes completos y sus longitudes, y le pidiera que encontrara el más corto, entonces esta (búsqueda no estructurada) no es un problema muy interesante matemáticamente. Claramente, la única solución posible es revisar cada viaje uno por uno y quedarse con el más corto que haya encontrado hasta ahora. Como era de esperar, las computadoras cuánticas (de cualquier tipo, no solo recocidas) no pueden acelerar mucho un problema sin estructura. Pero si, en cambio, te doy una lista de distancias entre ciudades y te pido que encuentres la ruta más corta que las conecta a todas (la formulación habitual del problema), entonces (a) la información solo necesita indicarel problema (búsqueda estructurada) se puede comprimir exponencialmente, (b) hay muchas más herramientas matemáticas que podemos usar para atacarlo, y (c) las computadoras cuánticas pueden ser mucho más eficientes que las computadoras clásicas para encontrar el camino más corto. (Digo "podría" porque, a diferencia del problema del vidrio giratorio de Ising, prácticamente nadie en la comunidad teórica de CS piensa que las computadoras cuánticas podrán resolver de manera eficiente el problema del viajante de comercio).

Gracias por la respuesta detallada, pero me temo que todavía no responde a mi pregunta. No estoy suponiendo si la función potencial es arbitraria o estructurada. Además, ¿a qué nos referimos con "estructurado"? ¿De qué métrica estamos hablando? ¿Entropía? ¿Pureza cuántica? Todavía no veo cómo nada de eso importa. La "computadora" de ondas D prepara un potencial (estructurado o no) de manera controlable . "Sabe" exactamente cómo distribuir las intensidades y, por lo tanto, la ubicación de todos los óptimos. ¿Ves lo que quiero decir?
@Tfovid No preparan el potencial directamente. Preparan directamente los acoplamientos en el hamiltoniano. Esto determina de manera única el potencial, pero solo a través de un cálculo increíblemente difícil que no se puede hacer en la práctica. Por lo tanto, no conocen las ubicaciones de los óptimos en todo momento.
@Tfovid Debe distinguir conceptualmente entre la longitud- norte 2 lista de acoplamientos hamiltonianos, que le da la fórmula para calcular el potencial, y el potencial mismo, considerado como una lista de 2 norte diferentes energías. Son matemáticamente isomorfos, porque dado uno, en principio, puede encontrar el otro con suficiente tiempo de cálculo. Pero en la práctica son completamente diferentes, porque el tiempo para hacer la conversión es poco práctico. Los programadores de D-Wave solo conocen lo primero. Tener la lista de acoplamientos no permite conocer los valores de sus mínimos en la práctica.
@Tfovid Quizás deberíamos retroceder y aclarar una pregunta más básica. ¿Entiende el concepto general de que puede ser difícil encontrar el mínimo de una función conocida? (No estoy tratando de ser sarcástico, esa es una pregunta honesta). Si lo hace, entonces la respuesta a su pregunta parece clara.
Entiendo la dificultad de encontrar el mínimo de una función conocida. El hecho de que tenga una expresión de forma cerrada y bien definida de alguna función no significa que pueda leer fácilmente su mínimo global. Dicho esto, si codifico esa función en un sistema físico, entonces sé su valor en cada punto. Por ejemplo, conozco el potencial de cada átomo en mi red ya que los he preparado yo mismo. El punto clave que estoy tratando de transmitir es que tengo control total sobre cada átomo en mi sistema. lo he preparado Sé dónde están todos los óptimos para empezar.
@Tfovid No tengo ni idea de por qué cree que "tener el control total sobre" una función y "haberla preparado" usted mismo haría más fácil "saber dónde están todos los valores óptimos para comenzar" que en el caso de un general función conocida (de la cual, por definición, también "conoces el valor en cada punto" pero sobre la que afirmas que de alguna manera no "tienes control total"). Después de todo, no puede construir un potencial arbitrario en el recocido cuántico, sino solo uno extremadamente restringido. Tal vez deberíamos darnos por vencidos y esperar a que alguien más intervenga y entienda mejor tu confusión.
@Tfovid Entiendes que este "potencial" no es una función V ( X → ) en el espacio de posición? El potencial asigna una energía a cada configuración de espín posible. V ( s 1 , s 2 , … , s 1024 ) . Si bien es fácil de calcular V ( … ) para una configuración de espín dada, de hecho es difícil saber dónde están los óptimos, aunque conozca la función V muy bien. Dices que "sabes dónde están los óptimos para empezar"; prepara una función de este tipo V y muéstrame dónde están ;)
@Noiralef Creo que nos estamos acercando: de hecho, pensé en el potencial como una función sobre algún tipo de espacio de posición. En mi imagen (simplificada) se veía como una red de espines 2D, cada uno de los cuales está preparado a un cierto potencial. ¿Es eso incorrecto?
Tenía esta imagen en mente, donde claramente los giros se preparan en un arreglo espacial determinado. Si dejas que la esquina inferior izquierda sea el origen, preparo el giro hacia abajo y luego preparo el giro en la posición (0, 1) hacia arriba, etc.
@Tfovid Sí, eso está muy mal. No sé lo que significa tener un giro individual "en un potencial". ¿Quieres decir que cada espín experimenta un campo magnético diferente en el z -¿dirección? En este caso, el estado fundamental es simplemente que cada espín apunta a lo largo de su campo local, y no hay nada que minimizar.
@Tfovid La razón por la que el vidrio giratorio de Ising no es trivial de resolver es que los giros en diferentes sitios están acoplados , por lo que no puede pensar en el sistema de un giro a la vez.
@Tfovid En el recocido cuántico, no preparas el estado inicial de los giros en absoluto, preparas el hamiltoniano.

El problema de encontrar el estado fundamental de un vidrio giratorio Ising (el problema que supuestamente resuelve D-Wave) es NP-completo , por lo que si podemos resolverlo, entonces podemos adaptar nuestra solución de manera eficiente para resolver cualquier problema en la clase de complejidad NP - lo que constituye una enorme variedad de problemas útiles. Vea aquí algoritmos concretos para traducir una solución al vidrio giratorio de Ising en soluciones a problemas más útiles.

Lo entiendo, pero todavía no explica por qué necesitaríamos optimizar una función (es decir, potencial) que nosotros mismos hemos preparado de manera controlable . Si voy a dibujar el x^2 como mi potencial, presumiblemente, ya sé que será el más pequeño en x = 0 y eso anula el propósito de minimizarlo.
@Tfovid Si la función es tan simple como X 2 , entonces seguro. Pero como dijo DanielSank, para funciones más complicadas, el mínimo puede estar lejos de ser obvio, incluso si conocemos la función exactamente. Los problemas de optimización pueden ser extremadamente desafiantes. Considere que en el problema del viajante de comercio, un ejemplo canónico de un problema computacional "difícil", la función de costo se conoce exactamente.
No veo cómo la complejidad de la función tiene algo que ver con eso. Si va a crear de forma controlada una función potencial (a través de sistemas de giros o lo que no), entonces claramente debe saber dónde debe estar cada potencial, incluido el más bajo/el más alto. Si no lo hace, entonces no es el maestro de su propia función potencial y entonces estamos hablando de otra cosa.
@Tfovid Sí, de hecho "sabe exactamente dónde [se encuentra] cada potencial, incluido el más bajo/el más alto". Pero no sabes cuál es el más bajo/el más alto. El dominio de la función potencial es tan enormemente grande que simplemente verificar cada valor uno por uno podría llevar más tiempo que la edad del universo. La dificultad de encontrar el valor mínimo de una función conocida no tiene nada que ver con cuán "controlablemente" se realizó experimentalmente esa función.
Me temo que estamos "hablando entre nosotros" aquí. La "enormedad" o complejidad de la función potencial es irrelevante para el problema. Usted mismo ha creado la función potencial; ha modificado cada espín/átomo/lo que sea usted mismo para crearlo y, por lo tanto, sabe su valor en cada punto en primer lugar. ¿De qué sirve entonces buscarlo a posteriori mediante tunelización o cualquier otro método? Como mencioné en mi publicación original, si el potencial fuera una caja negra, entonces el recocido para la optimización tendría sentido. Pero eso no es lo que deduzco de lo que hace D-wave.
@Tfovid Ah, creo que entiendo tu confusión ahora. Crearé una respuesta separada.
¿El recocido cuántico sirve para algo?
RespuestasAquíPolítica de privacidad1y, 0v