Certified Optimal Measurement Reduction over Quantum Context Landscapes

Resumo Técnico: Redução de Medição Ótima Certificada sobre Paisagens de Contextos Quânticos

Enunciado do Problema
Estimar o valor de expectativa $\langle H \rangle$ de um Hamiltoniano quântico em dispositivos quânticos de curto prazo (near-term) requer a decomposição de $H$ em fragmentos mensuráveis (contextos) e a alocação de disparos (shots) de medição para minimizar a variância. Estratégias existentes — que variam desde o agrupamento por comutação qubit-a-qubit (QWC) até sombras clássicas (classical shadows) e fragmentos fermiônicos — frequentemente produzem cronogramas de medição sem um limite inferior rigoroso para o custo de disparos para um modelo de medição específico declarado. Consequentemente, é difícil distinguir se uma melhoria observada decorre de um ponto melhor em uma paisagem fixa, de um alargamento da paisagem (novos contextos) ou simplesmente de uma divisão de coeficientes não otimizada dentro de um quadro existente. O artigo aborda a necessidade de um "certificado" que responda: dentro de um conjunto declarado de contextos de medição e um modelo de covariância, qual é o custo mínimo inevitável de disparos, e quão próximo um determinado cronograma está desse ótimo?

Metodologia
Os autores propõem um arcabouço que divide o problema da redução de medição em duas camadas de otimização distintas: uma camada interna contínua e uma camada externa não convexa.

1. Camada Interna (Otimização Convexa): Para um dicionário fixo de contextos de medição $\mathcal{D} = \{(V_\ell, c_\ell)\}$ e um modelo de covariância declarado $\Gamma_\ell$, o problema de encontrar o estimador estratificado linear ótimo (decompondo $H$ em fragmentos $F_\ell \in V_\ell$ e alocando disparos $N_\ell$) é formulado como um Programa de Cone de Segunda Ordem (SOCP).

   • O objetivo minimiza a constante de disparo principal $\Phi = \min \sum \sqrt{c_\ell} \|F_\ell\|_\rho$ sujeito à restrição de reconstrução $\sum F_\ell = H$.
   • Esta formulação subsume todas as liberdades de divisão de coeficientes (incluindo divisão sobreposta e uso de covariância dependente do estado) em um único gauge convexo.

2. Certificados Duais: O SOCP possui um dual cônico que fornece uma testemunha de limite inferior ($L$).

   • Uma solução primal produz um limite superior ($U$) representando o custo de um cronograma específico.
   • Um vetor dual viável $y$ certifica que nenhum estimador estratificado linear não enviesado sobre o mesmo dicionário pode alcançar um custo menor que $L$.
   • O hiato $U/L$ fornece um certificado verificável por máquina de otimalidade. Se $U=L$, o cronograma é globalmente ótimo para o cenário declarado.

3. Camada Externa (Busca Combinatória): O design do próprio dicionário (selecionando quais contextos incluir) e a calibração dos modelos de covariância são problemas não convexos. Os autores utilizam o RANGE, um otimizador global robusto de natureza adaptativa (hibridizando colônia de abelhas artificiais e algoritmos genéticos), para:

   • Buscar sub-dicionários ótimos (compressão).
   • Realizar geração de colunas (column generation): usando a testemunha dual como um "oráculo de precificação" para identificar contextos ausentes que violam a restrição dual (ou seja, contextos que provaria reduzir o custo).
   • Calibrar modelos de raio de covariância usando dados piloto.

4. Robustez: Para lidar com a incerteza no modelo de covariância (por exemplo, de medições piloto ou estados de aproximação), o arcabouço constrói intervalos de confiança simultâneos (sanduíches) para as matrizes de covariância. Isso resulta em certificados robustos baseados em dados ($L_{rob} \le \Phi \le U_{rob}$) que se mantêm com alta probabilidade sem exigir o conhecimento do estado verdadeiro $\rho$.

Principais Contribuições

1. Ótimo Exato com Pedigree Clássico: O artigo estabelece que o valor mínimo da constante de disparo principal para qualquer dicionário finito é o valor de um SOCP. Esta é uma especialização de design experimental $c$-ótimo multiresposta para contextos quânticos, fornecendo o fechamento convexo global do espaço de design de divisão de coeficientes.
2. Certificados Independentemente Verificáveis: Ao contrário de trabalhos anteriores que relatam cronogramas e variâncias estimadas, este arcabouço exporta uma testemunha dual. Um verificador pode reparar resíduos de viabilidade e recomputar limites sem confiar no otimizador, garantindo que o hiato relatado seja conservador e válido.
3. Validade sob Incerteza de Covariância: O Teorema 4 fornece certificados robustos de alta confiança usando dados piloto, elevando certificados baseados em oráculos para certificados baseados em dados.
4. Certificação de Dicionário via Geração de Colunas: A testemunha dual atua como um oráculo de precificação. Se um contexto ausente viola a restrição dual, ele é adicionado ao dicionário. Isso permite que o arcabouço certifique a otimalidade sobre uma paisagem maior do que a inicialmente resolvida ou identifique quando uma paisagem deve ser ampliada.
5. Instrumento de Graduação: O certificado distingue três regimes: heurísticas que já são ótimas em sua própria paisagem, heurísticas que deixam "liberdade de gauge" (divisão não otimizada) na mesa, e paisagens que são fundamentalmente subótimas e requerem ampliação.

Resultos Numéricos
O arcabouço foi validado através de paisagens sintéticas, Hamiltonianos moleculares (H$_2$, LiH, BeH$_2$, H$_2$O) e Hamiltonianos de escala de produção de elementos f (CeO, NdO, UO$_2^+$, UO$_2^+$) com 29–35 qubits.

• Hiatos de Otimalidade: Para sistemas pequenos como H$_2$, estratégias padrão (ex: inserção ordenada) foram encontradas como exatamente ótimas. No entanto, para sistemas maiores como H$_2$O, as estratégias padrão deixaram fatores de 2,1–7,7 em custos de disparos não otimizados dentro de seus próprios contextos.
• Compressão de Dicionário: Usando busca global, os autores comprimiram dicionários de contextos moleculares em 4,3–6,1$\times$, aumentando o custo de disparo certificado em apenas 0,2–2,1%. Isso revelou um "joelho" agudo no compromisso entre o tamanho do dicionário e o custo.
• Impacto de Configurações de Entrelaçamento: Adicionar contextos totalmente comutativos (FC) (configurações entrelaçadas) reduziu o ótimo certificado em 25–56% para sistemas moleculares. Para Hamiltonianos de elementos f de escala de produção, esse alargamento economizou 31–70% de disparos em comparação com dicionários apenas QWC.
• Compressão vs. Amostragem: O estudo demonstrou que técnicas de compressão projetadas para reduzir normas de codificação de blocos (block-encoding) não necessariamente reduzem o custo de amostragem. Por exemplo, mudanças de simetria reduziram significativamente a norma de codificação de bloco, mas tiveram impacto mínimo na constante de medição certificada, enquanto o tapering de qubits reduziu significativamente a contagem de disparos.
• Escala de Produção: O método gerou com sucesso certificados para Hamiltonianos com $\sim 2 \times 10^4$ termos e $\sim 10^4$ contextos (aprox. $2 \times 10^6$ variáveis de cone) em 8–15 minutos em um único nó de CPU, com hiatos certificados abaixo de $10^{-1}\%$.

Significância e Alegações
O artigo afirma estabelecer um padrão comum para reivindicações de redução de medição. Ao separar as escolhas de design não convexas (seleção de dicionário) do núcleo convexo (alocação ótima), o arcabouço garante que a busca global seja reservada para problemas puramente combinatórios, enquanto a otimização convexa fornece garantias prováveis para a alocação.

Os autores enfatizam que o arcabouço não substitui as heurísticas existentes (como ShadowGrouping ou cobertura de clique mínimo), mas fornece uma camada de certificado sobre elas. Uma vez que uma heurística propõe um dicionário ou cronograma, o programa cônico otimiza a liberdade restante, e a testemunha dual certifica o quão próximo o resultado está do limite teórico. O artigo conclui que a redução de medição deve ser vista como "geometria mais otimização", onde a geometria da paisagem é definida pelos contextos permitidos, e o certificado fornece os limites rigorosos necessários para avaliar o progresso.

Os autores explicitamente observam limitações: o certificado é condicional ao modelo de covariância declarado (covariâncias erradas geram afirmações rigorosas sobre dados errados), e a garantia é relativa à paisagem declarada (a precificação exata sobre todos os possíveis contextos de estabilizadores permanece um problema combinatório difícil). O arcabouço é projetado para estimadores não enviesados estratificados de alvos conhecidos, não para protocolos adaptativos ou informacionalmente completos, embora possa graduar os estimadores induzidos por tais protocolos.