Optimising the relative entropy under semidefinite constraints

Resumo Técnico: Otimização da Entropia Relativa sob Restrições Semidefinidas

Enunciado do Problema
O problema central abordado é a minimização da entropia relativa quântica $D(\rho\|\sigma) = \text{tr}[\rho(\log \rho - \log \sigma)]$ sujeita a restrições semidefinidas. Esta otimização surge em diversas tarefas de informação quântica, notadamente na estimativa de taxas de chave secreta para Distribuição de Chaves Quânticas (QKD) a partir de estatísticas de medição de dispositivos reais. A formulação matemática busca encontrar:
$$\inf D(\rho\|\sigma) \quad \text{s.t.} \quad h_i(\rho, \sigma) \ge 0, \quad \mu\sigma \le \rho \le \lambda\sigma, \quad \rho, \sigma \in \mathcal{S}(\mathcal{H})$$
onde $h_i$ são mapas afins que representam restrições de medição. Embora o problema seja convexo, ele é altamente não linear devido ao logaritmo de matriz, tornando os solvers de otimização convexa padrão ineficazes para instâncias gerais. Métodos existentes frequentemente lutam com estabilidade numérica, carecem de garantias de convergência prováveis ou são restritos a tipos específicos de restrições (por exemplo, apenas restrições de igualdade).

Metodologia
Os autores propõem um método baseado em uma representação integral recentemente introduzida para a entropia relativa quântica (Frenkel, 2023; Jenčová, 2015). Para estados que satisfazem $\mu\sigma \le \rho \le \lambda\sigma$, a entropia relativa é expressa como:
$$D(\rho\|\sigma) = \int_{\mu}^{\lambda} \frac{ds}{s} \text{tr}_+[\sigma s - \rho] + \log \lambda + 1 - \lambda$$
onde $\text{tr}_+[A]$ denota o traço da parte positiva de $A$. A principal inovação técnica é a discretização desta integral para transformar o problema não linear em uma sequência de Programas Semidefinidos (SDPs).

1. Discretização e Formulação de SDP: A integral é aproximada sobre uma grade $t = (t_1, \dots, t_r)$. Ao utilizar a propriedade de que $\text{tr}_+[A]$ pode ser formulado como um SDP (especificamente, $\text{tr}_+[A] = \sup_{0 \le P \le 1} \text{tr}[PA]$), os autores derivam um limite inferior para a entropia relativa. Isso resulta em um problema de minimização sobre variáveis auxiliares $\mu_k$ sujeito a desigualdades matriciais lineares.
2. Limites Superior e Inferior: O método fornece tanto limites inferiores ($c_l(t)$) quanto limites superiores ($c_u(t)$) sobre o valor ótimo.
   • Limite Inferior: Derivado via interpolação convexa (retas secantes) do integrando, formulado como um SDP.
   • Limite Superior: Derivado via interpolação convexa por cima, também formulado como um SDP.
3. Estimativa de Gap: A diferença $\Delta(t) = c_u(t) - c_l(t)$ serve como uma estimativa rigorosa do gap para o ótimo em qualquer estágio de iteração.
4. Refinamento de Grade: Os autores estabelecem uma estratégia de construção de grade recursiva (Corolário 1) que garante convergência sublinear. Os pontos da grade são escolhidos de tal forma que o erro diminui como $O(\sqrt{\lambda/\epsilon})$, onde $\epsilon$ é a precisão desejada.

Principais Contribuições

• Limites Prováveis: O trabalho fornece uma sequência de SDPs que geram limites superiores e inferiores rigorosos e prováveis para o problema de minimização da entropia relativa.
• Garantias de Convergência: O artigo prova a convergência sublinear do esquema de discretização. Especificamente, demonstra que o número de pontos de grade necessários para atingir um erro $\epsilon$ escala como $O(\sqrt{\lambda/\epsilon})$.
• Quantificação de Gap: Diferente de muitos heurísticas numéricas existentes, este método permite o cálculo explícito do gap para o ótimo em cada etapa, permitindo critérios de terminação baseados na precisão desejada.
• Generalização para f-Divergências: A metodologia é generalizada para arbitrary $f$-divergências, não apenas a entropia relativa de Umegami, aproveitando as propriedades de convexidade da função $g(s) = \text{tr}_+[\sigma s - \rho]$.
• Eficiência de Recursos: A abordagem mantém a eficiência em termos de dimensões de matriz do SDP, evitando a escala $d^2 \times d^2$ exigida por métodos que computam diretamente logaritmos de matriz.

Resultos
Os autores validam seu método através de benchmarks numéricos:

• Taxas de Chave QKD: Aplicado a cenários de QKD baseados em emaranhamento, o método computa com sucesso a aleatoriedade extraível (taxas de chave) para dimensões locais de até 8 (3 qubits por parte). Os resultados são alcançados em segundos em um computador pessoal padrão.
• Comportamento de Convergência: Experimentos numéricos confirmam a taxa de convergência sublinear prevista. O erro diminui conforme o número de pontos de grade aumenta, consistente com os limites teóricos derivados no Corolário 1.
• Desempenho Comparativo: Quando comparado a métodos de estado da arte (especificamente [12] e [14]):
  • O método atinge precisão comparável a [12] para instâncias pequenas, mas é estritamente superado em precisão pelo solver especializado [14] para programação de entropia relativa.
  • Em termos de tempo de execução, o método proposto mostra uma clara melhoria sobre [12], mas permanece mais lento que [14].
  • Uma vantagem distinta é a capacidade de fornecer tanto limites superiores quanto inferiores e quantificar o gap, enquanto [12] fornece apenas limites superiores e [14] é restrito a cones específicos e carece da flexibilidade da representação integral para certos cenários independentes de dispositivo.

Significância e Alegações
O artigo alega que sua principal significância reside em fornecer uma ferramenta prática e eficiente em recursos que preenche a lacuna entre ferramentas numéricas executáveis e limites teóricos. Ao converter a difícil otimização não linear em uma sequência de SDPs com convergência provável, o método permite provas de segurança confiáveis para QKD e outras tarefas de informação quântica onde limites rigorosos inferiores de aleatoriedade extraível são essenciais.

Os autores enfatizam que, embora seu método possa não ser o mais rápido em termos de tempo de execução bruto comparado a solvers especializados como [14], sua capacidade de lidar com restrições afins gerais (desigualdades) e fornecer estimativas de gap rigorosas o torna unicamente adequado para aplicações que exigem limites certificados, como QKD independente de dispositivo e a estimativa de capacidades de canal. O trabalho também abre as portas para algoritmos numericamente aplicáveis para limitar a entropia relativa de canais, um problema aberto em teorias de recursos.