Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Resumo Técnico: Combinação Linear Eficiente de Unitárias Baseada em Fourier e Aplicações em Otimização Quântica

Enunciado do Problema
Algoritmos de otimização quântica, particularmente o Algoritmo Quântico Aproximado de Otimização (QAOA), enfrentam barreiras significativas de implementação em hardware de curto prazo. A estrutura matemática de problemas de otimização, especialmente aqueles envolvendo restrições (por exemplo, restrições de cardinalidade), frequentemente exige circuitos quânticos com alta conectividade (interações todos-para-todos), profundidades de circuito elevadas e inúmeras portas de dois qubits. Esses requisitos frequentemente excedem as capacidades dos atuais processadores quânticos supercondutores. Embora existam estratégias como corte de circuitos ou aproximação de circuitos, elas frequentemente trocam a qualidade da solução pela complexidade ou exigem uma sobrecarga de amostragem substancial sem garantias rigorosas de desempenho.

Metodologia
Os autores propõem uma estrutura de Combinação Linear de Unitárias (LCU) Baseada em Fourier projetada para aproximar circuitos quânticos complexos usando conjuntos de circuitos mais simples e amigáveis ao hardware. A metodologia central envolve:

1. LCU sem Qubit Auxiliar para Amostragem: Ao contrário das implementações padrão de LCU que usam um qubit auxiliar para implementar coerentemente uma combinação linear de unitárias (exigindo operações controladas), este trabalho foca em aplicações baseadas em amostragem. Ao descartar os fatores de sinal associados à decomposição de quasi-probabilidade (QPD) e substituir o qubit auxiliar por aleatoriedade clássica, o método elimina a necessidade de qubits auxiliares e portas controladas. Isso transforma a implementação em uma mistura probabilística de circuitos mais simples, onde a sobrecarga de amostragem é quantificada por um fator $\Gamma$.
2. Decomposição de Fourier para Unitárias Diagonais: Para unitárias diagonais (comuns em funções de custo e termos de penalidade), os autores utilizam a transformada discreta de Fourier. Uma unitária alvo $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ é decomposta em uma combinação linear de unitárias mais simples $V(\theta_j)$, que são frequentemente apenas camadas de portas $R_Z$ de um único qubit. Os coeficientes são derivados da transformada de Fourier da função que define a unitária. Essa abordagem substitui interações complexas de múltiplos qubits (por exemplo, penalidades quadráticas exigindo $O(n^2)$ portas) por camadas de qubits únicos ao custo de uma sobrecarga de amostragem $\Gamma \le m+1$.
3. Extensão para Unitárias Não-Diagonais Invariantes por Permutação: A estrutura é generalizada para unitárias não-diagonais, como o XY-mixer totalmente conectado usado para preservar restrições de peso de Hamming. Aproveitando a dualidade de Schur-Weyl e a teoria da representação de $SU(2)$, os autores expressam unitárias invariantes por permutação como combinações lineares contínuas de rotações coletivas de qubits únicos $R(g)^{\otimes n}$. Isso permite a implementação de misturadores altamente não locais usando apenas portas de qubits únicos, com uma sobrecarga de amostragem teórica limitada por $O(n^3)$.
4. Conexão com Relaxação Lagrangiana: O artigo estabelece um vínculo formal entre penalidades quânticas baseadas em Fourier e relaxação lagrangiana clássica. A otimização de um único ramo da decomposição LCU é mostrada como equivalente à otimização de um parâmetro lagrangiano, fornecendo uma perspectiva unificada sobre o tratamento de restrições.

Principais Contribuições

• Desenvolvimento de Estrutura: Introdução de uma estrutura de LCU baseada em Fourier e sem qubit auxiliar, que decompõe amplas classes de unitárias diagonais e não-diagonais em conjuntos de camadas de portas de qubits únicos.
• Eficiência de Hardware: Demonstração de que operadores complexos e conectados todos-para-todos (como penalidades de cardinalidade e XY-mixers) podem ser substituídos por circuitos significativamente mais simples, trocando profundidade e conectividade do circuito por uma sobrecarga de amostragem polinomial.
• Garantias Teóricas: Fornecimento de limites rigorosos de desempenho, mostrando que a probabilidade de amostrar strings de bits de alta qualidade na abordagem LCU é limitada inferiormente pela probabilidade coerente escalada por $1/\Gamma$. O artigo também conecta a otimização de Valor Condicional em Risco (CVaR) a esses limites.
• Validação de Escalabilidade: Aplicação bem-sucedida da estrutura ao problema do subgrafo $k$ mais denso em instâncias de até 106 qubits em hardware real da IBM Quantum, uma escala anteriormente intratável para implementações totalmente coerentes de tais restrições.

Resultados Experimentais
Os autores validaram sua abordagem através de simulações exatas de vetores de estado em uma instância de 12 nós e experimentos em grande escala em um dispositivo de 106 qubits:

• Simulação de 12 Nós: Comparações entre o QAOA totalmente coerente e a abordagem LCU baseada em Fourier mostraram que, embora os valores esperados brutos dos circuitos LCU fossem menores (devido à sobrecarga de amostragem), a otimização de um único circuito base LCU (um ansatz variacional derivado da LCU) produziu a maior probabilidade de amostrar soluções ótimas, superando a linha de base coerente em métricas específicas.
• Experimento de Hardware de 106 Nós: Em um grafo heavy-hex de 106 qubits (estendido via camadas SWAP), as abordagens LCU baseadas em penalidade e baseadas em XY-mixer foram executadas. Os resultados demonstraram que a sobrecarga de amostragem prática foi significativamente menor que os limites teóricos de pior caso ($\Gamma \approx 10^4$). O ansatz LCU de ramo único encontrou com sucesso soluções de alta qualidade (até 81 arestas no subgrafo mais denso) com probabilidades viáveis variando de 2,7% a 4,8%, indicando a viabilidade do método para problemas em grande escala.
• XY-Mixer vs. Penalidade: A abordagem LCU baseada em XY-mixer geralmente superou a abordagem baseada em penalidade, particularmente ao usar um único circuito base otimizado, sugerindo que misturadores que preservam restrições são mais eficazes quando combinados com essa decomposição.

Significado e Alegações
O artigo alega que a estrutura de LCU baseada em Fourier oferece uma rota sistemática para expandir o alcance prático da otimização quântica de curto prazo. Ao substituir operações coerentes complexas por combinações ponderadas de circuitos mais simples, o método amplia a gama de instâncias de problemas (especificamente aquelas com restrições globais) que podem ser executadas no hardware atual. Os autores enfatizam que essa abordagem não requer a reprodução exata da distribuição alvo, mas sim foca na amostragem de soluções de alta qualidade, um objetivo bem adequado para tarefas de otimização. O trabalho sugere que o trade-off entre complexidade do circuito e sobrecarga de amostragem é favorável, pois os limites teóricos são frequentemente frouxos na prática, e o método permite o estudo de algoritmos e instâncias de problemas que, de outra forma, estariam além das capacidades do hardware. O artigo conclui que isso fornece um princípio de design flexível para algoritmos quânticos mais compatíveis com hardware, particularmente para o tratamento de restrições no QAOA.