Resumo Técnico: AQKA: Aquisição Ativa de Kernel Quântico Sob Orçamento de Tiros

1. Declaração do Problema

Métodos de kernel quântico, que mapeiam entradas clássicas para um espaço de características quântico para calcular fidelidades $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$, estão entre as cargas de trabalho mais acessíveis para hardware de Escala Intermediária Ruidosa Quântica (NISQ). No entanto, sua implantação prática é limitada pelos custos de medição. Estimar uma matriz de kernel $N \times N$ requer $\Theta(N^2 S)$ execuções de circuito (tiros), onde $S$ é o número de tiros por entrada para alcançar uma precisão desejada. No hardware atual, onde as latências de circuito variam de milissegundos a segundos, essa escalabilidade limita os tamanhos de problemas implantáveis a algumas centenas baixas.

Estratégias existentes de economia de orçamento (por exemplo, Nyström-QKE, ShoFaR, alinhamento kernel-alvo) abordam isso subamostrando quais entradas medir (por exemplo, selecionando colunas de referência ou pontos de treinamento). No entanto, esses métodos geralmente alocam o orçamento de tiros uniformemente dentro de seus subconjuntos escolhidos. Eles falham em levar em conta a heterogeneidade de quanto cada entrada específica de kernel contribui para o desempenho do classificador a jusante. A questão central sem resposta é: dado um orçamento fixo de tiros $B$, como os tiros devem ser alocados no nível de pares para minimizar a perda da tarefa a jusante?

2. Metodologia: AQKA

Os autores formulam o aprendizado de kernel quântico com orçamento de tiros como um problema de otimização que minimiza a perda esperada $\mathbb{E}[L(\hat{K})]$ sujeita a uma restrição de orçamento total de tiros $\sum s_{ij} \leq B$.

Derivação Teórica

Usando uma análise de primeira ordem (método Delta) combinada com as condições Karush-Kuhn-Tucker (KKT), os autores derivam uma regra de alocação ótima em forma fechada. Para uma entrada de kernel $K_{ij}$ estimada com $s_{ij}$ tiros, a variância é $K_{ij}(1-K_{ij})/s_{ij}$. A alocação ótima $s^*_{ij}$ que minimiza a variância do estimador de perda é proporcional à sensibilidade da perda a essa entrada:
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
onde $g_{ij} = \partial L / \partial K_{ij}$ é o gradiente da perda em relação à entrada do kernel.

• Para Regressão de Ridge de Kernel (KRR): O gradiente é derivado explicitamente como $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$, onde $\alpha = (K+\lambda I)^{-1}y$ e $\beta = (K+\lambda I)^{-1}\alpha$.
• Para Máquinas de Vetor de Suporte (SVM): Usando o teorema do envelope (teorema de Danskin), o gradiente é derivado como $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$, onde $\eta^*$ são as variáveis duais ótimas.

Implementação Algorítmica

Os autores propõem AQKA (Aquisição Ativa de Kernel Quântico), um algoritmo implantável que opera em rodadas:

1. Aquecimento: Uma pequena fração do orçamento ($\eta_w B$) é gasta uniformemente para semear uma estimativa inicial de kernel $\hat{K}$.
2. Estimativa de Sensibilidade: O algoritmo resolve o problema KRR (ou SVM) em $\hat{K}$ para calcular as pontuações de sensibilidade baseadas no gradiente $g_{ij}$.
3. Alocação de Preenchimento de Alvo: Em vez de amostrar tiros de uma distribuição multinomial (que pode deixar pares de baixa sensibilidade sem recursos devido a picos estocásticos), a AQKA usa uma abordagem determinística de "preenchimento de alvo". Ela calcula a contagem de tiros alvo $s^*_{ij}$ e adiciona a diferença $\max(0, s^*_{ij} - s_{ij})$ a cada par.
4. Exploração: Uma pequena fração de exploração ($\eta_e B$) é adicionada uniformemente para evitar que o algoritmo ignore completamente pares que podem se tornar importantes devido a efeitos de ordem superior ou ruído de estimativa.

3. Contribuições Principais

1. Decomposição Completa de Regimes

O artigo fornece uma caracterização fundamentada de quando diferentes estratégias de alocação são ótimas:

• AQKA domina no regime limitado por orçamento ($B \lesssim 16 n_{pares}$) em tarefas KRR de sensibilidade esparsa.
• Nyström-QKE (reconstrução de baixo posto) vence em orçamentos saturados em dados plantados esparsos, onde a estrutura de baixo posto pode ser totalmente recuperada.
• Métodos no estilo ShoFaR são competitivos apenas em regimes de orçamento extremamente baixo.

2. Teoria de Aquisição no Nível de Pares em Forma Fechada

• Alocação Ótima KKT: Derivação do gradiente em forma fechada $g_{ij}$ para KRR e SVM sob ruído de tiros.
• Limites Corrigidos Conscientes de Esparsidade: Os autores derivam um limite de Cauchy-Schwarz para a razão de redução de variância alcançável $\rho$. Eles corrigem a escala ingênua $\Theta(m^2/N^2)$ (assumindo que $g$ é suportada em $S \times S$) para uma escala mais precisa $\Theta(m/N)$ ($\rho \leq 2m/N$ para KRR). Isso reflete o fato estrutural de que, mesmo que o vetor de solução $\alpha$ seja esparso, o vetor de sensibilidade $\beta = (K+\lambda I)^{-1}\alpha$ é genericamente denso, o que significa que qualquer par que toca o conjunto de suporte tem sensibilidade não nula.
• Limites de Arrependimento: Um limite de arrependimento de plug-in com constante explícita é fornecido, mostrando que o erro converge para o ótimo oráculo à medida que o orçamento de aquecimento aumenta.

3. Algoritmo de Preenchimento de Alvo Implantável

O artigo demonstra que um esquema determinístico de preenchimento de alvo supera a amostragem multinomial natural, particularmente no regime limitado por orçamento. A amostragem multinomial tende a concentrar-se agressivamente em alguns pares de alta pontuação, deixando outros sem recursos e amplificando o ruído na inversão de matriz; o preenchimento de alvo mantém um piso mínimo de cobertura.

4. Primeira Adaptação Online Multi-Semente em Hardware Quântico

Os autores relatam a primeira demonstração publicada de alocação adaptativa de tiros online em dispositivos atuais da classe IBM Heron de 156 qubits.

• IBM Aachen (N=20): +17,0 ± 4,8 pontos percentuais sobre alocação uniforme (significância de 3,5$\sigma$).
• IBM Berlin (N=30): +14,0 ± 8,5 pontos percentuais em orçamentos mais altos.

4. Resultados Experimentais

Configurações Sintéticas e Simuladas

• KRR Esparsa Plantada: Em dados sintéticos com vetores de solução esparsos, a AQKA (preenchimento de alvo com sensibilidade estimada) alcança +8 a +25 pontos percentuais sobre alocação uniforme à medida que $N$ escala de 225 para 1000.
• Kernels Quânticos sem Ruído: Os ganhos transferem-se para simulações sem ruído de 4 qubits ZZFeatureMap, mostrando +13 a +18 pontos sobre o uniforme.
• Ablação de Resampleamento em Hardware: Usando um kernel medido no IBM Pittsburgh (156 qubits) e resampleado com ruído de tiros, a AQKA alcança +26,3 ± 6,1 pontos em $B = n_{pares}$ e +31,9 ± 7,2 pontos em $B = 4n_{pares}$ sobre o uniforme.

Benchmarks de Dados Reais

• Câncer de Mama ($\alpha$ Denso): Em um conjunto de dados do mundo real onde o vetor de solução é denso (não esparso), a AQKA não domina uniformemente. É competitiva, mas mostra desempenho dependente do regime, destacando que a vantagem do método depende de alta heterogeneidade de sensibilidade no nível de pares.
• SVM vs. KRR: O artigo observa que, embora o quadro teórico se estenda ao SVM, a versão de plug-in é mais frágil devido à instabilidade do conjunto de suporte sob aquecimentos ruidosos. Em regimes de pequeno N e aquecimento ruidoso, a AQKA para SVM pode ter desempenho inferior à alocação uniforme, enquanto a versão KRR permanece robusta.

5. Significância e Alegações

O artigo afirma fechar a lacuna entre a otimização teórica de orçamento de tiros e a implantação prática em hardware NISQ. Sua significância primária reside em:

1. Ir além da alocação uniforme: Demonstrar que a alocação de tiros não uniforme e consciente de sensibilidade é crítica para o aprendizado de kernel quântico a curto prazo, especialmente quando os orçamentos são apertados.
2. Validação em Hardware: Fornecer a primeira validação online multi-semente de uma estratégia de alocação adaptativa de tiros em hardware quântico real, provando que os ganhos teóricos sobrevivem ao ruído do dispositivo e à deriva de calibração.
3. Consciência de Regime: Estabelecer que nenhum método é universalmente superior; a AQKA é especificamente projetada para o regime limitado por orçamento e de sensibilidade esparsa, que é a zona operacionalmente relevante para o hardware atual.

Os autores são modestos em suas alegações, reconhecendo que, para problemas de sensibilidade densa ou orçamentos saturados, outros métodos (como Nyström) ou alocação uniforme podem ser preferíveis. Eles também identificam o ruído do plug-in SVM como uma limitação atual que requer trabalho futuro (por exemplo, aquisição estabilizada por margem).