Las computadoras cuánticas adiabáticas requieren una evolución lenta para mantener el mínimo global: tiempo, donde es brecha espectral: distancia entre dos energías más bajas.
El peligro es que esta brecha espectral pueda disminuir exponencialmente con el tamaño del problema; de esta manera, la evolución necesitaría un tiempo exponencialmente largo y, además, la temperatura tendría que disminuir exponencialmente para distinguir el óptimo global.
Para ver que este peligro es real, veamos el problema de partición (NP-completo): para grandes números naturales, decide si contiene cero? Como es una especie de suma de variables aleatorias binarias, su densidad generalmente se parece asintóticamente a la distribución gaussiana. Mientras crece, el ancho de esta distribución crece linealmente con , mientras que el número de puntos es , por lo tanto, la distancia entre 0 y el primer valor distinto de cero ("brecha espectral") debería caer exponencialmente.
Este problema parece universal al convertir un problema computacional difícil en un problema de optimización global: la cantidad de óptimos locales crece exponencialmente, y el rango de energías crece mucho más lentamente.
Por lo tanto, quería preguntar si existen problemas computacionales difíciles conocidos para los cuales sabemos que la brecha espectral no disminuye exponencialmente, ¿para los cuales tiene sentido el control de calidad adiabático?
La computación cuántica adiabática es equivalente a la computación cuántica digital estándar (es decir, basada en puertas). Por lo tanto, cualquier problema que se pueda resolver de manera eficiente (en tiempo polinomial) usando computación cuántica digital también se puede resolver de manera eficiente usando computación cuántica adiabática.
Básicamente, puede asignar cualquier cálculo basado en puertas a un hamiltoniano cuyo estado fundamental codifique el estado final del cálculo. Para hacer el cálculo adiabático, se introduce un hamiltoniano "conductor" y se interpola lentamente entre los dos hamiltonianos. La brecha inversa mínima ( ) de las escalas hamiltonianas interpoladas polinomialmente con el número de puertas en el cálculo. Entonces, en principio, podrías factorizar números usando este truco: simplemente asigna el algoritmo de Shor a un hamiltoniano equivalente y prepara su estado fundamental.
Admito que esto es un poco una respuesta de evasión. No conozco ninguna aplicación 'nativa' de AQC que muestre una aceleración exponencial, pero probablemente existan.
Jarek Duda