Thermodynamic significance of QUBO encoding on quantum annealers

Resumo Técnico: Significância Termodinâmica da Codificação QUBO em Recozedores Quânticos

Enunciado do Problema
O recozimento quântico (QA) oferece uma abordagem nativa de hardware para resolver problemas de otimização discreta, mapeando-os para estados de baixa energia de um Hamiltoniano de Ising. No entanto, tarefas do mundo real, como o Problema de Agendamento de Oficinas (JSP), são naturalmente formuladas como problemas de otimização com restrições, enquanto os recozedores quânticos atuais exigem formulações de Otimização Binária Quadrática sem Restrições (QUBO). Para preencher essa lacuna, as restrições são impostas por meio de termos de penalidade com pesos ajustáveis. Um desafio crítico surge porque uma única tarefa com restrições admite muitas codificações QUBO; escolhas distintas na estrutura e magnitude da penalidade remodelam a paisagem energética, afetando tanto a probabilidade de encontrar soluções viáveis quanto o custo dissipativo da dinâmica de recozimento. Embora pesquisas anteriores tenham se concentrado no tempo de execução e na probabilidade de solução, o custo termodinâmico (trabalho, calor, produção de entropia) de diferentes codificações em dispositivos quânticos de escala intermediária ruidosos (NISQ) permanece pouco explorado.

Metodologia
Os autores investigam uma instância específica do Problema de Agendamento de Oficinas utilizando uma família de codificações QUBO de dois parâmetros controlada por pesos de penalidade: $p_{sum}$ (impondo restrições one-hot/soma) e $p_{pair}$ (impondo restrições de precedência). O estudo emprega uma abordagem de análise dupla:

1. Análise Computacional: Os autores varrem o espaço de parâmetros $(p_{sum}, p_{pair})$ para mapear o desempenho do solucionador. Eles utilizam heurísticas inspiradas em recozimento clássico (recozimento simulado, recozimento de integral de caminho e recozimento de modelo de rotor) e execuções experimentais em um processador D-Wave Advantage. O sucesso é medido pela probabilidade de encontrar a solução ótima e pela viabilidade do estado fundamental.
2. Análise Termodinâmica: Tratando o recocedor como um sistema termodinâmico aberto, os autores realizam experimentos cíclicos de recozimento reverso. O processador é inicializado em um estado de Gibbs clássico em $s=1$, recozido até um parâmetro mínimo $\bar{s}$ e retornado a $s=1$. Ao medir a mudança estocástica na energia do processador ($\Delta E_1$) ao longo de muitas execuções, eles aplicam Relações de Incerteza Termodinâmica (TUR) para inferir limites inferiores para a produção média de entropia ($\langle \Sigma \rangle$), trabalho ($\langle W \rangle$) e calor trocado ($\langle Q \rangle$).
3. Simulação: Para complementar os dados experimentais, os autores simulam o processo de recozimento usando uma equação mestra adiabática. Isso permite o cálculo direto de grandezas termodinâmicas e a investigação de características espectrais (por exemplo, cruzamentos de níveis e degenerescências) que podem ser obscurecidas pelo ruído do hardware.

Principais Resultados

• Regimes de Codificação e Transições de Fase: O estudo identifica transições abruptas no espaço de parâmetros $(p_{sum}, p_{pair})$. Essas transições separam regiões onde o estado fundamental QUBO corresponde a uma solução viável de regiões onde é inviável. Um regime "misto" também é identificado, onde estados de baixa energia viáveis e inviáveis são energeticamente degenerados ou misturados.
• Assinaturas Termodinâmicas: As reorganizações da paisagem energética induzidas pela codificação produzem regimes termodinâmicos distintos. Penalidades fracas geram variedades de baixa energia de soluções inviáveis, enquanto penalidades excessivamente fortes suprimem a escala de energia efetiva do problema. Os limites de transição observados na precisão do solucionador coincidem com mudanças bruscas em observáveis termodinâmicos (produção de entropia, trabalho e calor).
• Assimetria das Penalidades: Os resultados demonstram uma assimetria pronunciada entre $p_{sum}$ e $p_{pair}$. O parâmetro $p_{sum}$, que introduz termos diagonais negativos, tem um efeito dominante tanto na dificuldade computacional quanto na dissipação termodinâmica. Pequenos valores de $p_{sum}$ podem ser "anulados" pela função objetivo, levando ao aumento da degenerescência e maior irreversibilidade.
• Correlação de Eficiência: Existe uma anticorrelação sistemática entre a "dificuldade" computacional e a eficiência termodinâmica. Codificações que tornam o problema de otimização difícil (por exemplo, criando variedades densas de baixa energia ou pequenos gaps espectrais) também aumentam a produção de entropia e reduzem a eficiência termodinâmica.
• Experimental vs. Simulação: Embora os resultados experimentais no dispositivo D-Wave mostrem transições alargadas devido a erros de controle analógico e decoerência, a correlação qualitativa entre parâmetros de codificação e custo termodinâmico persiste. Simulações confirmam que essas assinaturas termodinâmicas estão ligadas a características espectrais específicas, como cruzamentos evitados e degenerescências de níveis.

Significância e Alegações
O artigo estabelece que a codificação QUBO não é meramente uma etapa de pré-processamento matemático, mas uma escolha de design com consequências físicas que atua como um "botão de controle termodinâmico". Os autores afirmam que:

1. Termodinâmica como Diagnóstico: Observáveis termodinâmicos servem como um diagnóstico fundamentado no hardware para entender por que certas codificações de problemas têm sucesso ou falham, complementando métricas tradicionais de tempo de execução.
2. Necessidade de Co-Design: A codificação ótima requer uma abordagem de co-design que equilibre as forças das penalidades para impor viabilidade, mantendo ao mesmo tempo uma escala de energia do problema efetiva, resolvível contra flutuações térmicas e ruído.
3. Compensações de Eficiência: A "super-penalização" pode degradar tanto a qualidade da solução quanto a eficiência termodinâmica, isolando a variedade viável no espectro ideal, enquanto a torna indistinguível sob amostragem ruidosa no hardware.
4. Estrutura Operacional: O estudo fornece uma estrutura prática para mapear o espaço de codificação em um diagrama de fase termodinâmico de dissipação e eficiência, motivando estratégias de codificação "conscientes da termodinâmica" para recozedores NISQ.

Os autores concluem que as mesmas transições de codificação que governam a dificuldade computacional também reorganizam a dissipação, sugerindo que a minimização da dissipação de trabalho é uma estratégia viável para selecionar codificações ótimas.