Resource-Efficient Digitized Adiabatic Quantum Factorization

Resumo Técnico: Fatoração Quântica Adiabática com Eficiência de Recursos

Declaração do Problema
O artigo aborda o desafio de implementar a fatoração quântica adiabática eficiente em computadores quânticos digitalizados (baseados em portas). As abordagens padrão, como o método proposto por Peng et al. [1], formulam a fatoração de inteiros como uma busca pelo estado fundamental de um Hamiltoniano de problema derivado de uma função de Otimização Binária Não Restrita Polinomial (PUBO). Esta formulação resulta em um Hamiltoniano que contém termos de interação não locais de três e quatro qubits ($Z^3$ e $Z^4$). Em dispositivos digitalizados, essas interações de ordem superior exigem a decomposição em múltiplas portas de dois qubits nativas (por exemplo, CNOTs), levando a circuitos profundos com alta contagem de portas. Essa complexidade limita severamente a fidelidade e a escalabilidade do algoritmo, com probabilidades de sucesso caindo drasticamente para números maiores que 91, mesmo empregando técnicas de aprendizado de máquina.

Metodologia
Os autores propõem um novo algoritmo adiabático digitalizado que reformula o problema de fatoração utilizando uma estrutura de Otimização Binária Não Restrita Quadrática (QUBO). A mudança metodológica central envolve duas alterações principais:

1. Codificação de Subespaço de Núcleo (Kernel Subspace Encoding): Em vez de codificar a solução como o estado fundamental (mínimo de energia zero) de uma função ao quadrado $F^2$, os autores definem o Hamiltoniano do problema $\hat{H}_{LP}$ como a própria função linear $F(N, \hat{p}', \hat{q}')$. Nesta formulação, a solução corresponde ao autoestado de energia zero (o subespaço do núcleo ou kernel) do Hamiltoniano, que é um estado excitado em relação ao espectro global, em vez de ser o estado fundamental.
2. Formulação QUBO: Ao utilizar a função linear, o Hamiltoniano resultante contém apenas interações de dois corpos, classificando-o como um problema QUBO. Isso elimina a necessidade das reduções polinomiais NP-difíceis e das variáveis auxiliares tipicamente requeridas para mapear problemas PUBO para QUBO.

O algoritmo é implementado usando um Algoritmo Quântico Variacional (especificamente QAOA). O protocolo inicializa o sistema em um estado de superposição uniforme (especificamente $|+\rangle|-\rangle\dots$ para alinhar-se com o nul-subespaço de $\hat{H}_{LP}$) e o evolui usando unitários alternados derivados do Hamiltoniano de custo ($\hat{H}_{LP}$) e de um Hamiltoniano de mistura ($\hat{H}_M$). A função de custo minimizada pelos otimizadores clássicos é definida como o valor esperado do valor absoluto do Hamiltoniano, $C_{LP} = \langle |\hat{H}_{LP}| \rangle$, para garantir a convergência para a solução de autovalor zero.

Principais Contribuições

• Simplificação de Circuito: A abordagem QUBO proposta reduz o Hamiltoniano do problema para interações de dois corpos. Isso elimina a necessidade de decompor portas complexas de múltiplos qubits, reduzindo significamente a profundidade do circuito.
• Nova Estratégia de Codificação: O artigo demonstra que a fatoração adiabática pode ser realizada com sucesso ao visar o subespaço do núcleo (estado excitado de energia zero) em vez do estado fundamental, contornando as limitações das formulações PUBO.
• Análise de Robustez: Os autores analisam a densidade espectral dos Hamiltonianos, mostrando que a formulação QUBO oferece uma densidade de estados mais esparsa ao redor do subespaço da solução comparada à formulação PUBO, o que auxilia na prevenção de mínimos locais e barren plateaus durante a otimização.

Resultos
Os autores testaram o algoritmo baseado em QUBO contra a abordagem PUBO padrão para fatorar inteiros de até 8 bits (especificamente $N=25, 119, 143$).

• Complexidade de Portas: Para uma única camada do circuito QAOA, a abordagem QUBO requer significativamente menos portas CNOT. Por exemplo, fatorar $N=25$ requer 8 CNOTs por camada para o método QUBO, comparado a 34 CNOTs para o método PUBO (após a decomposição de portas de 3 e 4 qubits).
• Fidelidade e Confiança: O algoritmo QUBO demonstra uma fidelidade substancialmente maior na identificação dos fatores corretos. Para números maiores como $N=119$ e $N=143$, a abordagem PUBO falha em concentrar a amplitude de probabilidade no estado correto, resultando em baixos índices de confiança e alta entropia de Shannon. Em contraste, a abordagem QUBO popula com sucesso os estados da solução correta.
• Convergência da Função de Custo: O algoritmo QUBO alcança uma redução mais profunda na função de custo (até 3 ordens de magnitude para $N=143$) comparado à abordagem PUBO (até 2 ordens de magnitude), indicando uma otimização mais eficaz.
• Análise Espectral: A análise dos espectros de energia revela que o Hamiltoniano PUBO possui uma alta densidade de estados próximo à solução, criando um cenário "plano" que dificulta os otimizadores clássicos. O Hamiltoniano QUBO exibe um espectro mais amplamente espalhado com lacunas de energia (energy gaps) maiores perto do subespaço do núcleo, facilitando a preparação do estado.

Significância e Alegações
O artigo afirma que este trabalho fornece um caminho de eficiência de recursos para a fatoração quântica adiabática digitalizada. A principal significância reside na redução substancial da complexidade do circuito e no aumento correspondente da fidelidade algorítmica, tornando a fatoração de inteiros maiores viável em dispositivos de curto prazo (near-term devices).

Os autores enfatizam que, embora visar um estado excitado (o núcleo) seja desafiador para recozedores quânticos (quantum annealers) devido à falta de proteção por decoerência do estado fundamental, é vantajoso para recozedores quânticos digitalizados. Em sistemas baseados em portas, onde a decoerência é frequentemente governada pelo decaimento local de um único qubit, a contagem reduzida de portas do método QUBO minimiza o tempo de execução total e a exposição a erros. Os resultados sugerem que formulações baseadas em QUBO podem superar as baseadas em PUBO em otimização via QAOA, desafiando a literatura anterior que assumia que o PUBO era necessário ou superior para certas estruturas de problemas. O trabalho motiva a exploração adicional de protocolos adiabáticos digitalizados para problemas mais amplos de teoria dos números e Hamiltonianos complexos.