Recozimento quântico - Quantum annealing

O recozimento quântico ( QA ) é uma metaheurística para encontrar o mínimo global de uma determinada função objetivo ao longo de um determinado conjunto de soluções candidatas (estados candidatos), por um processo usando flutuações quânticas (em outras palavras, um meta-procedimento para encontrar um procedimento que encontra um tamanho / comprimento / custo / distância mínimo absoluto de dentro de um conjunto possivelmente muito grande, mas ainda assim um conjunto finito de soluções possíveis usando computação baseada em flutuação quântica em vez de computação clássica). 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 giratório 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 "Quantum annealing in the transversal Ising model" embora uma proposta em uma forma diferente tenha sido feita por AB Finnila, MA Gomez, C. Sebenik e JD Doll, em Quantum annealing é um novo método para minimizar funções multidimensionais ”.

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. Em seguida, o sistema evolui seguindo a equação de Schrödinger dependente do tempo , uma evolução mecânica quântica natural dos sistemas físicos. As amplitudes de todos os estados candidatos continuam mudando, realizando um paralelismo quântico, de acordo com a força dependente do tempo do campo transversal, que causa o tunelamento quântico entre os estados. Se a taxa de variação do campo transversal for lenta o suficiente, o sistema permanece próximo ao estado fundamental do hamiltoniano instantâneo (veja também computação quântica adiabática ). Se a taxa de variação do campo transversal for acelerada, o sistema pode deixar o estado fundamental temporariamente, mas produzir uma maior probabilidade de conclusão no estado fundamental do problema hamiltoniano final, 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 de Ising clássico 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.

Comparação com recozimento simulado

O recozimento quântico pode ser comparado ao recozimento simulado , cujo parâmetro de "temperatura" desempenha um papel semelhante à intensidade do campo de tunelamento do QA. No recozimento simulado, a temperatura determina a probabilidade de se mover para um estado de "energia" mais alta a partir de um único estado atual. No recozimento quântico, a força do campo transversal determina a probabilidade da mecânica quântica de alterar as amplitudes de todos os estados em paralelo. Evidências analíticas e numéricas sugerem que o recozimento quântico supera o recozimento simulado sob certas condições (consulte Recursos para uma análise cuidadosa).

Mecânica quântica: analogia e vantagem

Quant-annl.jpg

O campo de tunelamento é basicamente um termo de energia cinética que não comuta com a parte de energia potencial clássica do vidro original. Todo o processo pode ser simulado em um computador usando Monte Carlo quântico (ou outra técnica estocástica), e assim obter um algoritmo heurístico para encontrar o estado fundamental do vidro clássico.

No caso de recozimento de uma função objetivo puramente matemática , pode-se considerar as variáveis ​​no problema como graus de liberdade clássicos e as funções de custo como a função de energia potencial (hamiltoniano clássico). Em seguida, um termo adequado consistindo em variável (s) não comutável (ou seja, variáveis ​​que têm comutador diferente de zero com as variáveis ​​do problema matemático original) deve ser introduzido artificialmente no Hamiltoniano para desempenhar o papel do campo de tunelamento (parte cinética ) Em seguida, pode-se realizar a simulação com o hamiltoniano quântico assim construído (a função original + parte não comutável) exatamente como descrito acima. Aqui, há uma escolha na seleção do termo de não comutação e a eficiência do recozimento pode depender disso.

Foi demonstrado experimentalmente, bem como teoricamente, que o recozimento quântico pode de fato superar o recozimento térmico (recozimento simulado) em certos casos, especialmente onde a paisagem de energia potencial (custo) consiste em barreiras muito altas, mas finas, circundando mínimos locais rasos. Como as probabilidades de transição térmica (proporcionais a , com a temperatura e a constante de Boltzmann ) dependem apenas da altura das barreiras, para barreiras muito altas, é extremamente difícil para flutuações térmicas tirar o sistema de tais mínimos locais. No entanto, como argumentado anteriormente em 1989 por Ray, Chakrabarti & Chakrabarti, a probabilidade de tunelamento quântico através da mesma barreira (considerada isoladamente) depende não apenas da altura da barreira, mas também de sua largura e é aproximadamente dada por , onde está o campo de tunelamento. Essa alça adicional através da largura , na presença de tunelamento quântico, pode ser de grande ajuda: se as barreiras forem finas o suficiente (isto é ), as flutuações quânticas podem certamente tirar o sistema dos mínimos locais rasos. Para um vidro espelhado, a altura da barreira torna-se obrigatória . Para o valor constante de um fica proporcional ao tempo de recozimento (em vez de proporcional ao recozimento térmico), enquanto pode até se tornar -independente para os casos em que diminui conforme .

Especula-se que em um computador quântico , tais simulações seriam muito mais eficientes e exatas do que em um computador clássico, pois ele pode realizar o tunelamento diretamente, ao invés de precisar adicioná-lo manualmente. Além disso, pode ser capaz de fazer isso sem os controles de erro rígidos necessários para controlar o emaranhamento quântico usado em algoritmos quânticos mais tradicionais. Alguma confirmação disso é encontrada em modelos exatamente solucionáveis.

Cronograma para recozimento quântico em copos Ising Spin:

  • 1981 Modelo de vidro giratório Quantum Ising introduzido e estudado para seu comportamento de transição;
  • 1989 Idea propôs que as flutuações quânticas poderiam ajudar a explorar paisagens de energia acidentada dos óculos clássicos de spin de Ising, escapando de mínimos locais (com barreiras altas, mas finas) usando tunelamento;
  • 1991 Realização experimental do vidro de spin de Ising quântico em LiHoYF;
  • 1998 Primeira simulação de Monte Carlo demonstrando recozimento quântico em sistemas de vidro Ising;
  • 1999 Primeira demonstração experimental de recozimento quântico em ímãs de vidro LiHoYF Ising;
  • 2011 Máquina de recozimento quântico de circuito supercondutor para sistemas de vidro giratório Ising realizada e comercializada pela D-Wave Systems.

Implementações D-Wave

Fotografia de um chip construído pela D-Wave Systems , montado e ligado por fio em um suporte de amostra. O processador do D-Wave One é projetado para usar 128 elementos lógicos supercondutores que exibem acoplamento controlável e ajustável para executar operações.

Em 2011, a D-Wave Systems anunciou o primeiro recozedor quântico comercial do mercado com o nome D-Wave One e publicou um artigo na Nature sobre seu desempenho. A empresa afirma que este sistema usa um chipset de processador de 128 qubit . Em 25 de maio de 2011, a D-Wave anunciou que a Lockheed Martin Corporation celebrou um contrato para comprar um sistema D-Wave One. Em 28 de outubro de 2011 USC 's Information Sciences Institute teve a entrega de Lockheed D-Wave One.

Em maio de 2013, foi anunciado que um consórcio do Google , NASA Ames e a organização sem fins lucrativos Universities Space Research Association comprou um computador quântico adiabático da D-Wave Systems com 512 qubits. Um extenso estudo de seu desempenho como recozedor quântico, em comparação com alguns algoritmos clássicos de recozimento, já está disponível.

Em junho de 2014, a D-Wave anunciou um novo ecossistema de aplicativos quânticos com a empresa de finanças computacionais 1QB Information Technologies (1QBit) e o grupo de pesquisa de câncer DNA-SEQ para se concentrar na solução de problemas do mundo real com hardware quântico. Como a primeira empresa dedicada à produção de aplicativos de software para computadores quânticos disponíveis comercialmente, o braço de pesquisa e desenvolvimento da 1QBit se concentrou nos processadores de recozimento quântico da D-Wave e demonstrou com sucesso que esses processadores são adequados para resolver aplicativos do mundo real.

Com as demonstrações de emaranhamento publicadas, a questão de saber se a máquina D-Wave pode ou não demonstrar a aceleração quântica em todos os computadores clássicos permanece sem resposta. Um estudo publicado na Science em junho de 2014, descrito como "provavelmente o estudo mais completo e preciso que já foi feito sobre o desempenho da máquina D-Wave" e "a comparação mais justa até agora", tentou definir e medir a aceleração quântica. Várias definições foram propostas, pois algumas podem não ser verificáveis ​​por testes empíricos, enquanto outras, embora falsificadas, permitiriam, no entanto, a existência de vantagens de desempenho. O estudo descobriu que o chip D-Wave "não produziu aceleração quântica" e não descartou a possibilidade em testes futuros. Os pesquisadores, liderados por Matthias Troyer no Instituto Federal Suíço de Tecnologia , não encontraram "nenhuma aceleração quântica" em toda a gama de seus testes, e apenas resultados inconclusivos ao olhar para subconjuntos dos testes. Seu trabalho ilustrou "a natureza sutil da questão da aceleração quântica". Trabalhos adicionais aumentaram a compreensão dessas métricas de teste e sua confiança em sistemas equilibrados, perdendo, assim, quaisquer assinaturas de vantagem devido à dinâmica quântica.

Existem muitas questões em aberto sobre a aceleração quântica. A referência ETH na seção anterior é apenas para uma classe de problemas de benchmark. Potencialmente, pode haver outras classes de problemas em que a aceleração quântica pode ocorrer. Pesquisadores do Google, LANL, USC, Texas A&M e D-Wave estão trabalhando duro para encontrar essas classes de problemas.

Em dezembro de 2015, o Google anunciou que o D-Wave 2X supera o recozimento simulado e Quantum Monte Carlo por um fator de 100 milhões em um conjunto de problemas de otimização difíceis.

A arquitetura do D-Wave difere dos computadores quânticos tradicionais. Não se sabe que é polinomialmente equivalente a um computador quântico universal e, em particular, não pode executar o algoritmo de Shor porque o algoritmo de Shor não é um processo de escalada. O algoritmo de Shor requer um computador quântico universal. D-Wave afirma apenas fazer o recozimento quântico.

"Uma introdução interdisciplinar aos algoritmos baseados no recozimento quântico" apresenta uma introdução aos problemas de otimização combinatória ( NP-difícil ), a estrutura geral dos algoritmos baseados no recozimento quântico e dois exemplos deste tipo de algoritmos para resolver instâncias do max- Problemas SAT e Minimum Multicut, juntamente com uma visão geral dos sistemas de recozimento quântico fabricados pela D-Wave Systems. Algoritmos híbridos quânticos-clássicos para problemas de otimização discreta-contínua em grande escala foram relatados para ilustrar a vantagem quântica.

Referências

Leitura adicional