Puede resolver cualquier función computable con un esquema de optimización global. La prueba de esto proviene del estudio del modelo de Ising o, alternativamente, del problema de optimización binaria cuadrática sin restricciones (QUBO). Brevemente, configura un gráfico con las restricciones que:
- Los vértices pueden tener etiquetas [math] v_i \ in \ {0,1 \} [/ math] o [math] \ {\ pm 1 \} [/ math] si se considera el modelo Ising.
- Los bordes pueden tener un peso arbitrario, positivo, negativo o cero.
Luego escribes una función objetivo (correspondiente a la energía del problema de Ising):
[matemáticas] E (\ mathbf {z}) = \ mathbf {z} ^ TQ \ mathbf {z} [/ math]
- Cómo calcular (la 11ma potencia 10) / (la 10ma potencia 10) sin usar una calculadora
- ¿Cuáles son algunos conceptos en el cálculo lambda que es bueno saber antes de aprender programación funcional?
- Cómo calcular los componentes conectados, sin usar la función nx.connected_components (g) en NetworkX
- En términos simples, ¿qué quieres decir con enmarcar bits?
- Soy un desarrollador, pero me falta mi habilidad matemática. Con un BSc en CS y un MSc en IS, ¿qué debo saber y cómo puedo identificar dónde necesito ayuda?
donde [math] Q [/ math] es la matriz de adyacencia del gráfico Ising / QUBO (donde la diagonal indica ponderaciones de vértices) y [math] \ mathbf {z} [/ math] es un vector que contiene las etiquetas binarias en los vértices . El estado fundamental es la (s) cadena (s) de bits que minimiza la función anterior.
Ahora la tarea es codificar una función booleana arbitraria en este estado fundamental. Parece que debería poder hacer esto, excepto que la descripción anterior solo permite términos de interacción cuadrática, mientras que en general puede tener expresiones booleanas con un orden arbitrariamente alto. En realidad, esto no es un problema, porque siempre se puede reducir una expresión booleana de orden superior en una de orden inferior mediante la introducción de variables secundarias. Por ejemplo, si tiene una función booleana (en forma algebraica) [matemáticas] F (\ vec {b}) = b_1 + b_1b_2b_3 [/ matemáticas], puede introducir una nueva variable [matemáticas] a [/ matemáticas] para sustituir el producto [math] b_1b_2 [/ math]. Luego agrega otro término [math] 3 (a (3-2b_1-2b_2) + b_1b_2) [/ math] para penalizar el caso donde [math] a \ neq b_1b_2 [/ math]. Estas reducciones requieren solo números polinómicos de bits de ancilla.
El resto de la prueba se basa en mostrar que puede construir pequeños gráficos de espín que simulan un conjunto de circuitos capaces de computación universal. Para eso, puede leer la sección IV de este documento:
Codificación de la computación universal en los estados fundamentales de las redes Ising
Luego, los autores toman un problema NP-completo conocido, la satisfacción del circuito (CSAT) y lo mapean en un problema Ising. A partir de esto, puede construir un problema de decisión donde el bit decisivo le dice si el estado fundamental de una configuración de espín particular es mayor que cero (siempre puede agregar un cambio de energía arbitrario al hamiltoniano para que el estado fundamental no sea negativo), y dado que una energía de configuración particular se puede verificar fácilmente, sabemos que el problema de Ising es NP-completo .
Incluso puede mostrar que ciertos tipos de modelos de Ising son capaces de computación cuántica universal mediante un enfoque similar de mapeo de circuitos cuánticos al Hamiltoniano final de una computación cuántica adiabática, y con los grados de libertad apropiados, se puede demostrar que este mapeo puede simular eficientemente circuitos cuánticos, lo que demuestra la universalidad ya que los circuitos cuánticos también son universales. Para una discusión de eso, vea este documento:
Hamiltonianos realistas para computadoras cuánticas adiabáticas universales
