Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Declaração do Problema

A programação semidefinida (SDP) é um problema de otimização convexa fundamental com aplicações em teoria de controle, estatística, aprendizado de máquina, finanças e informação quântica. No entanto, resolver instâncias de SDP de grande escala continua sendo um desafio computacional para algoritmos clássicos. Os principais gargalos são o alto custo de resolver sistemas lineares e realizar decomposições de autovalores (especificamente, projetar sobre o cone semidefinido positivo) em cada iteração. Embora algoritmos quânticos como o Quantum Matrix Multiplicative Weights Updates (QMWU) e o Quantum Interior Point Methods (QIPM) tenham sido propostos para abordar esses problemas, eles frequentemente enfrentam compensações (trade-offs) em dependência de dimensão, parâmetros de esparsidade ou requisitos de precisão.

Metodologia

Os autores propõem o Quantum Alternating Direction Method of Multipliers (QADMM), um algoritmo híbrido quântico-clássico projetado para resolver SDPs ao aproveitar acelerações quânticas para as sub-rotinas mais caras, mantendo a robustez dos métodos de primeira ordem clássicos.

1. Estrutura de ADMM Inexato:
O núcleo da abordagem é uma estrutura de ADMM inexato adaptada para SDPs. Diferente do ADMM padrão, esta estrutura tolera explicitamente erros introduzidos por sub-rotinas quânticas.

• Atualização da Variável Dual: A atualização para a variável dual $y$ envolve resolver um sistema linear $(AA^*)y = \dots$. No cenário quântico, isso é resolvido usando um Quantum Linear Solver (QLS).
• Atualizações das Variáveis Primais: As atualizações para as variáveis primais $S$ e $X$ envolvem a projeção sobre o cone semidefinido positivo (PSD). Classicamente, isso requer uma decomposição de autovalores. O QADMM substitui isso por um operador proximal polinomial.
• Tolerância ao Erro: A estrutura introduz termos de erro ($\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$, etc.) para contabilizar imprecisões provenientes de aproximações de block-encoding, Quantum Singular Value Transformation (QSVT) e tomografia de estado quântico. Os autores provam que as iterações médias deste esquema inexato ainda convergem para uma solução $\epsilon$-ótima.

2. Operador Proximal Polinomial e QSVT:
Para evitar a custosa decomposição de autovalores na etapa de projeção, os autores projetam uma função polinomial $g(x)$ que aproxima o operador de projeção $\text{Proj}_{S_+}(x) = \max(0, x)$.

• Usando teoria de aproximação, eles constroem um polinômio crescente monótono $g$ de grau $d = O(1/\epsilon)$ que aproxima a função ReLU com erro $\epsilon$.
• Este polinômio é implementado em um computador quântico usando Quantum Singular Value Transformation (QSVT) sob o modelo de block-encoding.
• Uma função de barreira "virtual" $h(S)$ é construída de tal forma que seu operador proximal corresponde a esta transformação polinomial, garantindo a estrutura variacional necessária para a análise de convergência.

3. Fluxo Algorítmico:
O algoritmo procede iterativamente:

1. Atualização de $y$: Computa o mapa linear classicamente, prepara um estado quântico e resolve o sistema linear usando QLS.
2. Atualização de $V$: Computa a variável intermediária $V = C - A^*(y) - \gamma X$ usando Linear Combination of Unitaries (LCU).
3. Atualização de $S$: Aplica a transformação espectral polinomial (aproximando a projeção PSD) a $V$ usando QSVT, seguido de tomografia para reconstruir a matriz clássica.
4. Atualização de $X$: Semelhante à atualização de $S$, aplicando uma transformação polinomial para atualizar a variável dual $X$.
5. Pós-processamento Clássico: As matrizes reconstruídas são projetadas em conjuntos limitados (restrições de norma de Frobenius) para garantir a viabilidade.

Principais Contribuições

1. Estrutura de ADMM Inexato Robusta: O artigo estabelece uma ponte teórica entre a teoria de convergência do ADMM clássico e a computação quântica prática. Eles provam que a iteração média converge para uma solução $\epsilon$-ótima com uma taxa de $O(1/\epsilon)$, mesmo quando as resoluções de subproblemas e atualizações duais contêm erros limitados pelo ruído quântico e limites de aproximação.
2. Mapeamento Proximal Polinomial para SDP: Os autores introduzem um método inovador para substituir a decomposição de autovalores no ADMM por uma transformação de autovalor polinomial. Isso permite o uso de QSVT para lidar com as restrições do cone semidefinido de forma eficiente, evitando o custo de $O(n^3)$ ou $O(n^4)$ das projeções espectrais clássicas.
3. Análise de Complexidade e Comparação: O artigo fornece uma análise rigorosa de complexidade mostrando que o QADMM alcança uma escala favorável em relação à dimensão $n$ comparado ao ADMM clássico e aos solvers quânticos existentes (QMWU e QIPM).

Resultados e Complexidade

Os autores derivam a complexidade computacional total necessária para atingir uma precisão absoluta $\epsilon_{abs}$ no valor do objetivo e no resíduo de viabilidade.

• Complexidade de Iteração: O algoritmo requer $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ iterações, onde $R_X$ e $R_S$ são limites superiores nas normas de Frobenius das soluções primais e duais ótimas.
• Complexidade Total:
  • Operações Clássicas: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$, onde $s_A$ é o número de entradas não nulas nas matrizes de restrição.
  • Complexidade de Portas Quânticas: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$.
  • Aqui, $\kappa_A$ é o número de condição de $AA^*$ e $R_y$ é o limite na norma da variável dual.

Comparação:

• Vs. ADMM Clássico: O QADMM oferece uma dependência melhor em relação à dimensão $n$ (evitando os fatores $O(n^6)$ ou $O(n^4)$ associados às decomposições de autovalores clássicas e multiplicações de matrizes em cada iteração).
• Vs. QIPM: O QADMM evita a alta dependência do número de condição do sistema de Newton ($\kappa_{newt}$) e oferece uma diferença de compensação na dependência de precisão.
• Vs. QMWU: Embora o QADMM tenha uma dependência de dimensão semelhante ao QMWU, ele alcança uma dependência de ordem inferior em relação ao parâmetro de precisão $\epsilon_{abs}$ (cúbica vs. potências maiores em alguns regimes) e é particularmente vantajoso quando a norma de Frobenius da solução $\|X^*\|_F$ é muito menor que seu traço $\text{Tr}(X^*)$ (por exemplo, em incrustações de SDP diagonais).

Significância e Alegações

O artigo afirma que o QADMM fornece uma escala favorável em relação à dimensão para resolver SDPs de grande escala, tornando-o um candidato promissor para problemas onde os solvers clássicos lutam com o custo das decomposições de autovalores.

Os autores enfatizam que sua abordagem:

• Integra Acelerações Quânticas: Ela aproveita com sucesso o QSVT e o QLS para acelerar as partes computacionalmente mais intensivas do algoritmo ADMM.
• Mantém Garantias de Convergência: Ao desenvolver uma estrutura inexata, eles garantem que os erros quânticos não impeçam a convergência para uma solução ótima.
• Depende de Pressupostos Específicos: O algoritmo assume a disponibilidade de QRAM de tamanho polinomial para acesso a dados e block-encoding das matrizes de entrada. Os autores reconhecem isso como um pressuposto forte e observam que trabalhos futuros focarão em relaxar esse requisito.

O artigo conclui que, embora o algoritmo seja limitado pelo pressuposto do QRAM, ele representa um passo significativo no avanço da aplicação da computação quântica à otimização convexa de grande escala, oferecendo especificamente uma alternativa viável tanto para métodos de primeira ordem clássicos quanto para outros solvers de SDP quânticos em regimes específicos de dimensão e precisão.