Computación adiabática cuántica

La computación adiabática cuántica es un paradigma de computación cuántica, alternativo a los circuitos cuánticos, donde el estado inicial se hace evolucionar lentamente con un Hamiltoniano dependiente del tiempo hasta un estado final. Se fundamenta en el teorema adiabático, que garantiza que si la evolución es lenta y los niveles de energía no se cruzan, el estado fundamental del Hamiltoniano inicial evolucionará al estado fundamental del Hamiltoniano final, tras un tiempo suficientemente largo. La diferencia principal con un circuito de puertas cuánticas es que no se conocen los estados intermedios por los que evoluciona el sistema. Posiblemente saltará a otros niveles de energía durante la evolución, aunque finalmente termine en el estado fundamental. La computación adiabática es útil para atacar problemas en los que el estado fundamental del Hamiltoniano final encapsule la solución a un problema, por ejemplo, un problema de minimización o de satisfacibilidad booleana.^[1]​^[2]​

Teorema adiabático

El origen del teorema adiabático puede trazarse en el artículo de Born y Fock de 1928,^[3]​ en el que se estudia la evolución de un sistema cuántico sometido a una perturbación dependiente del tiempo. Esta perturbación, que se supone lenta, está descrita por un Hamiltoniano ${\displaystyle H(t)}$  dependiente del tiempo y cuyos niveles de energía están separados. Bajo estas hipótesis, el teorema adiabático garantiza que si partimos de un autoestado del Hamiltoniano inicial, tras un tiempo suficientemente largo, la probabilidad de que el estado haya transicionado a otro nivel de energía es cero. Por ejemplo, un sistema que comienza en el estado fundamental de ${\displaystyle H(0)}$  terminará en el estado fundamental de ${\displaystyle H(T)}$ , con ${\displaystyle T}$  un tiempo suficientemente grande. El error en la aproximación respecto del resultado real obtenido resolviendo la ecuación de Schrödinger se puede estimar y es del orden de ${\displaystyle 1/T}$  .^[4]​^[5]​

Para formular el teorema en más detalle, se parte de la ecuación de Schrödinger con un Hamiltoniano dependiente del tiempo. Los autoestados ${\displaystyle |E_{k};t\rangle }$  de ${\displaystyle H(t)}$  cumplen

${\displaystyle H(t)|E_{k};t\rangle =E_{k}(t)|E_{k};t\rangle }$ ,

donde ${\displaystyle k}$  etiqueta el nivel de energía. Sea

${\displaystyle g_{\min }={\underset {0\leq t\leq T}{\min }}\{E_{1}(t)-E_{0}(t)\}}$ 

la mínima diferencia de energía entre el nivel fundamental y el primer estado excitado. Sea, además,

${\displaystyle \langle {\frac {dH}{dt}}\rangle _{1,0}=\langle E_{1};t\,|\,{\frac {dH}{dt}}\,|\,E_{0};t\rangle }$ .

Por el teorema adiabático, si se parte del estado inicial ${\displaystyle |E_{0};0\rangle }$  y se deja evolucionar con ${\displaystyle H(T)}$ , la probabilidad de que el estado final ${\displaystyle |\psi (T)\rangle }$  esté en el estado fundamental es ${\displaystyle 1-\epsilon ^{2}}$ , siempre y cuando se cumpla la condición adiabática.^[6]​

${\displaystyle {\big |}\langle {\frac {dH}{dt}}\rangle _{1,0}{\big |}\,/\,g_{\min }^{2}\leq \epsilon \ll 1}$  .

En general, la probabilidad de transición es de orden ${\displaystyle {\frac {1}{(g_{\min }T\,)^{2}}}}$ ^[7]​ y, bajo hipótesis más fuertes, se puede hacer exponencialmente pequeño con ${\displaystyle T}$ .^[8]​ Por tanto, dejando al sistema evolucionar un tiempo arbitrariamente largo, el estado final estará en el nivel fundamental.

Algoritmo

El esquema de funcionamiento más básico de computación cuántica adiabática puede resumirse en los siguientes pasos.

1. Escoger un Hamiltoniano final ${\displaystyle H_{F}}$  que encapsule el problema que se quiere resolver. Normalmente será un problema de optimización binaria, por la facilidad de modelar estos problemas con un Hamiltoniano.
2. Un Hamiltoniano inicial ${\displaystyle H_{I}}$  con un estado fundamental fácil de preparar.
3. Un Hamiltoniano intermedio ${\displaystyle H(s)}$  que varíe lentamente con ${\displaystyle s}$  y tal que ${\displaystyle H(0)=H_{I}}$  y ${\displaystyle H(1)=H_{F}}$ . En el caso más sencillo, ${\displaystyle H(s)}$  es la interpolación lineal${\displaystyle H(s)=(1-s)H_{I}+sH_{F}}$ .
4. El parámetro ${\displaystyle s}$  se escoge como función del tiempo de forma que se cumpla la condición adiabática ${\displaystyle {\Big |}{\frac {ds}{dt}}{\frac {\langle dH/ds\rangle _{1,0}}{g_{\min }^{2}}}{\Big |}\ll 1}$  (se ha usado la regla de la cadena). Normalmente el parámetro ${\displaystyle s}$  es simplemente ${\displaystyle s=t/T}$  , siendo ${\displaystyle T}$  el tiempo final. En este caso la condición adiabática se puede reescribir como ${\displaystyle T\gg \langle dH/ds\rangle _{1,0}/g_{\min }^{2}}$ .
5. Se evoluciona el estado inicial bajo estas condiciones y se mide tras un tiempo ${\displaystyle T}$ .

Por supuesto, este algoritmo será de utilidad una vez probado que el tiempo ${\displaystyle T}$  que se tarda en alcanzar la solución es polinomial con el número de cúbits, para poder, así, alcanzar una ventaja respecto a los algoritmos clásicos. La condición adiabática da una cota inferior para este tiempo y será diferente para cada problema.^[1]​

Ejemplos

1 cúbit

A continuación se ilustra el algoritmo con un ejemplo sencillo de un solo cúbit. Supongamos que se quiere hallar el estado fundamental del Hamiltoniano

${\displaystyle H_{F}={\frac {1}{2}}I+{\frac {1}{2}}\sigma _{z}}$  ,

con autovalores ${\displaystyle 1}$  y ${\displaystyle 0}$ . Para ello se puede partir del Hamiltoniano

${\displaystyle H_{I}={\frac {1}{2}}I-{\frac {1}{2}}\sigma _{x}}$ 

con autovalores ${\displaystyle 0}$  y ${\displaystyle 1}$  e interpolando linealmente, se obtiene el Hamiltoniano dependiente del tiempo

${\displaystyle H=(1-s)H_{I}+sH_{F}={\frac {1}{2}}{\begin{pmatrix}s+1&s-1\\s-1&1-s{\frac {}{}}\end{pmatrix}}}$  .

Los autovalores del Hamiltoniano ${\displaystyle H}$  son ${\displaystyle 1/2\pm {\sqrt {1-2s+2s^{2}}}/2\,}$ , cuya distancia mínima es ${\displaystyle g_{\min }=0.8535...}$  para ${\displaystyle s=1/2}$  y, por tanto, se puede evolucionar del estado fundamental de ${\displaystyle H_{I}}$  al estado fundamental de ${\displaystyle H_{F}}$  . Nótese que es importante comenzar con un Hamiltoniano ${\displaystyle H_{I}}$  que no sea diagonal, ya que en ese caso los autovalores de ${\displaystyle H}$  serían ${\displaystyle s}$  y ${\displaystyle 1-s}$ , y la distancia mínima entre los niveles se haría cero, impidiendo aplicar la aproximación adiabática.

Se podría ver este problema como una cláusula que se cumple si y solo si ${\displaystyle z=1}$  (autovector ${\displaystyle |1\rangle }$ ), es decir, si ${\displaystyle H_{F}}$  está en el estado fundamental (autovalor ${\displaystyle 0}$ ). Para obtener el estado ${\displaystyle |1\rangle }$  se evoluciona el estado fundamental del Hamiltoniano ${\displaystyle H_{I}}$ , que se supone conocido.^[1]​

Algoritmo de Grover

El algoritmo de Grover permite buscar un elemento en una lista desordenada de modo cuadráticamente más rápido que un algoritmo clásico. Aunque el algoritmo se suele implementar con puertas cuánticas, se puede modelar la evolución adiabática para obtener de nuevo esta mejora cuadrática.

Supóngase que tenemos ${\displaystyle n}$  qubits y por tanto un espacio de Hilbert de dimensión ${\displaystyle N=2^{n}}$  con base ${\displaystyle |z\rangle }$ , ${\displaystyle z\in \{0,1\}^{n}}$ . Si se quiere encontrar un estado ${\displaystyle |m\rangle }$  en una lista desordenada de los ${\displaystyle N}$  estados de la base, se pueden tomar los Hamiltonianos inicial y final^[2]​

${\displaystyle H_{0}=\sum _{\{0,1\}^{n}\setminus \{0\}^{n}}|z\rangle \langle z|}$  y ${\displaystyle H_{f}=\sum _{\{0,1\}^{n}\setminus \{m\}}|z\rangle \langle z|}$  ,

cuyos estados fundamentales son ${\displaystyle |0...0\rangle }$  y ${\displaystyle |m\rangle }$ , el elemento a encontrar. Si se toma como Hamiltoniano una interpolación lineal de ${\displaystyle H_{0}}$  y ${\displaystyle H_{f}}$ ,

${\displaystyle H(s)=(1-s)H_{0}+sH_{m}}$  ,

con ${\displaystyle s=t/T}$  , se obtiene la diferencia instantánea entre el nivel fundamental y el primer estado excitado:

${\displaystyle g(s)={\sqrt {\frac {N+4(N-1)(s^{2}-s)}{N}}}}$  .

El mínimo de esta diferencia es ${\displaystyle g_{\min }=1/{\sqrt {N}}}$  , y se obtiene para ${\displaystyle s=1/2}$  . Puesto que ${\displaystyle |\langle dH/ds\rangle _{1,0}|\leq 1}$ , la condición adiabática se cumplirá si ${\displaystyle T\geq N/\epsilon }$  . Sin embargo, vemos que no se consigue recuperar la ventaja cuadrática del algoritmo de Grover.

Para obtener un tiempo del orden ${\displaystyle {\sqrt {N}}}$  se debe cambiar ligeramente nuestro argumento: podemos dividir el tiempo ${\displaystyle T}$  en intervalos infinitesimales y aplicar en cada uno la condición adiabática

${\displaystyle {\Big |}{\frac {ds}{dt}}{\frac {\langle dH/ds\rangle _{1,0}}{g(s)^{2}}}{\Big |}\ll 1}$  .

Si se toma ${\displaystyle s(t)}$  solución de la ecuación

${\displaystyle {\frac {ds}{dt}}=\epsilon \,g^{2}(s)}$  ,

se satisface la condición. Integrando la ecuación en ${\displaystyle s\in [0,1]}$ , se obtiene el intervalo de tiempo ${\displaystyle [0,T]}$  y, suponiendo que ${\displaystyle N\gg 1}$ , se obtiene que el tiempo que habría que evolucionar adiabáticamente el sistema es ${\displaystyle T={\frac {\pi }{2\epsilon }}{\sqrt {N}}}$  . De hecho, se demuestra que esta mejora es óptima.^[6]​

Computación adiabática y circuitos cuánticos

La computación adiabática cuántica puede implementar la computación cuántica por circuitos cuántico en un tiempo y memoria polinomial con el número de variables.^[9]​ El problema inverso también es cierto, se puede simular la computación adiabática con un circuito cuántico^[2]​ Esto se puede demostrar a partir de Hamiltonianos locales, que mediante una asignación a cadenas de Márkov, se puede encontrar la dependencia polinomial mencionada.

Annealing cuántico

Las condiciones requeridas por la computación adiabática, por ejemplo temperatura cero, son complicadas de obtener físicamente, por lo que han surgido algoritmos inspirados en este tipo de computación que relajan estas condiciones a cambio de perder la universalidad de la computación adiabática. El annealing cuántico es uno de estos procedimientos, y permite encontrar mínimos de Hamiltoniano aprovechando el efecto túnel. Aunque lo ideal es que el sistema evolucione entorno al mínimo de energía, en algunos casos la probabilidad de que permanezca en el mínimo es pequeña (aun así el algoritmo devolverá estados de baja energía que pueden ser útiles). El annealing cuántico se utiliza principalmente para resolver problemas de optimización o muestreo, donde el problema se modela con un Hamiltoniano del que queremos obtener el mínimo, o en su defecto un estado de baja energía, que se aproxima a la solución óptima del problema.^[10]​^[11]​

Véase también

• Teorema adiabático
• Annealing cuántico
• Circuito cuántico

Referencias

1. Farhi, Edward; Gutmann, Sam; Goldstone, Jeffrey; Sipser, Michael (2000). «Quantum Computation by Adiabatic Evolution». arXiv. 
2. van Dam, Wim; Mosca, Michele; Vazirani, Umesh (2001). «How Powerful is Adiabatic Quantum Computation?». Proceedings 42nd IEEE Symposium on Foundations of Computer Science: 279-287. doi:10.1109/SFCS.2001.959902. 
3. Born, Max; Fock, Vladimir (1928). «Beweis des Adiabatensatzes». Z. Physik 51: 165-180. doi:10.1007/BF01343193. 
4. Zwiebach, Barton (Spring 2018). «L16.1 Quantum adiabatic theorem stated». MIT 8.06 Quantum Physics III. 
5. Messiah, Albert (1962). «XVII». Quantum Mechanics. Volume II. p. 747. 
6. Roland, Jérémie; Cerf, Nicolas J. (2002). «Quantum search by local adiabatic evolution». Phys. Rev. A. doi:10.1103/PhysRevA.65.042308. 
7. Galindo, A.; Pascual, P. (1991). «11». Quantum Mechanics II. Springer-Verlag. p. 186. 
8. Lidar, Daniel A.; Hamma, Alioscia; Rezakhani, Ali T. (2009). «Adiabatic approximation with exponential accuracy for many-body systems and quantum computation». J. Math. Phys: 102106. doi:10.1063/1.3236685. 
9. Aharonov, Dorit; Kempe, Julia; van Dam, Wim; Landau, Zeph; Regev, Oded; Lloyd, Seth (2004). «Adiabatic quantum computation is equivalent to standard quantum computation». 45th Annual IEEE Symposium on Foundations of Computer Science. doi:10.1109/FOCS.2004.8. 
10. Grant, Erika K.; Humble, Travis S. (2020). «Adiabatic Quantum Computing and Quantum Annealing». Oxford University Press. doi:10.1093/acrefore/9780190871994.013.32. 
11. D-Wave. «What is Quantum Annealing?». 

Enlaces externos

• Para ver ejemplos de cláusulas con dos o tres cúbits se puede consultar el siguiente artículo.

•   Datos: Q4682635