Recozimento Quântico

Recozimento Quântico. O recozimento quântico (QA) é um processo de otimização para encontrar o mínimo global de uma determinada função objetivo sobre um determinado conjunto de soluções candidatas (estados candidatos), por um processo que utiliza flutuações quânticas. O recozimento quântico é usado principalmente para problemas onde o espaço de busca é discreto (problemas de otimização combinatória) com muitos mínimos locais, como encontrar o estado fundamental de um vidro de spin ou resolver problemas QUBO, que podem codificar uma ampla gama de problemas como Max-Cut, coloração de gráficos, SAT ou o problema do caixeiro viajante. O termo "recozimento quântico" foi proposto pela primeira vez em 1988 por B. Apolloni, N. Cesa Bianchi e D. De Falco como um algoritmo clássico de inspiração quântica. Foi formulado em sua forma atual por T. Kadowaki e H. Nishimori (ja) em 1998, embora uma variante de tempo imaginário sem coerência quântica tenha sido discutida por A. B. Finnila, M. A. Gomez, C. Sebenik e J. D. Doll em 1994.

Contexto Teórico

O recozimento quântico começa a partir de uma superposição mecânica quântica de todos os estados possíveis (estados candidatos) com pesos iguais. Então o sistema evolui seguindo a equação de Schrödinger dependente do tempo, uma evolução natural da mecânica quântica dos sistemas físicos. As amplitudes de todos os estados candidatos continuam mudando, realizando um paralelismo quântico, de acordo com a força do campo transversal dependente do tempo, o que causa tunelamento quântico entre estados ou essencialmente tunelamento através de picos. Se a taxa de variação do campo transversal for lenta o suficiente, o sistema permanecerá próximo do estado fundamental do hamiltoniano instantâneo (ver também computação quântica adiabática). Se a taxa de mudança do campo transversal for acelerada, o sistema pode deixar o estado fundamental temporariamente, mas produzir uma probabilidade maior de concluir no estado fundamental do problema final hamiltoniano, ou seja, computação quântica diabática. O campo transversal é finalmente desligado e espera-se que o sistema tenha atingido o estado fundamental do modelo clássico de Ising que corresponde à solução do problema de otimização original. Uma demonstração experimental do sucesso do recozimento quântico para ímãs aleatórios foi relatada imediatamente após a proposta teórica inicial. Também foi comprovado que o recozimento quântico fornece um oráculo de Grover rápido para a aceleração da raiz quadrada na resolução de muitos problemas NP-completos.