Quantum Spectral Clustering Framework via Compact Circuit Structures

Resumo Técnico: Estrutura de Agrupamento Espectral Quântico via Estruturas de Circuitos Compactos

Definição do Problema
Métodos de aprendizado de máquina espectral, fundamentados na teoria espectral de grafos, são ferramentas poderosas para agrupamento (clustering) e aprendizado de variedades (manifold learning). No entanto, sua aplicação prática é dificultada pelos altos custos computacionais. A construção de uma matriz de kernel (adjacência) para $M$ amostras requer tipicamente $O(M^2)$ de tempo, e resolver o problema de autovalores associado exatamente custa $O(M^3)$. Embora existam métodos de aproximação clássicos (ex: Nyström, Random Fourier Features, Lanczos), eles ainda podem exigir o acesso explícito a matrizes de kernel parciais ou totais. No contexto do aprendizado de máquina quântico, onde as entradas do kernel são estimadas via sub-rotinas quânticas (ex: testes SWAP), em vez de serem lidas diretamente, o acesso elemento a elemento torna-se proibitivamente caro, escalando como $O(\epsilon^{-2}M^4)$ para a estimativa da matriz completa. Os autores identificam uma lacuna na execução eficiente de agrupamento espectral usando kernels quânticos sem construir a matriz de kernel ou estimar entradas individuais.

Metodologia
O artigo propõe uma estrutura variacional para agrupamento espectral que evita completamente a construção da matriz de kernel. Em vez disso, estima as quantidades necessárias diretamente através de formas quadráticas agregadas via circuitos quânticos compactos.

1. Função Objetivo: Os autores formulam uma função objetivo de quociente de Rayleigh normalizada derivada do Laplaciano de grafo simétrico ($L_{sym}$). O objetivo é maximizar:
   $$J(\alpha) = \frac{\alpha^\dagger A \alpha - \xi \alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha}{\alpha^\dagger D \alpha}$$
   onde $A$ é a matriz de adjacência, $D$ é a matriz de grau, $\mathbf{1}$ é o vetor de todos os uns e $\xi > 0$ é um parâmetro de penalidade. O numerador inclui um termo de penalidade projetado para suprimir o autovetor trivial (o vetor constante), garantindo soluções de agrupamento não triviais.

2. Design do Circuito Quântico: A estrutura utiliza três estimadores quânticos específicos para avaliar os termos da função objetivo sem construir a matriz:

   • $q_a(\alpha)$: Estima a forma quadrática de adjacência ($\alpha^\dagger A \alpha$).
   • $q_d(\alpha)$: Estima a forma quadrática ponderada pelo grau ($\alpha^\dagger D \alpha$).
   • $q_p(\alpha)$: Estima o termo de penalidade do projetor ($\alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha$).

   Esses estimadores baseiam-se em uma unitária de incorporação de dados $U_{\phi, D}$ que prepara uma superposição indexada de pontos de dados e um estado de ponderação treinável $|\alpha_\theta\rangle$ em um registro de índice. Os circuitos utilizam sub-rotinas do tipo teste SWAP para computar fidelidades (similaridade) entre estados quânticos.

3. Inferência (Teste): Para pontos de dados não vistos $\hat{x}$, uma função de pontuação é definida com base na fase da sobreposição entre o estado de teste e o estado de ponderação treinado. A fase $\hat{\phi}(\hat{x}, \hat{\alpha})$ é extraída via circuitos de interferência (medindo qubits ancila nas bases $\sigma_x$ e $\sigma_y$) e é utilizada para atribuir rótulos de agrupamento via limiarização ou agrupamento circular.

4. Fluxo de Trabalho de Treinamento: Os parâmetros do estado de ponderação $|\alpha_\theta\rangle$ são otimizados usando um otimizador clássico (descida de gradiente) guiado pelos estimadores quânticos. O gradiente é computado usando a regra de deslocamento de parâmetro (parameter-shift rule).

Principais Contribuições

• Estruturas de Circuitos Compactos: Os autores apresentam uma família de circuitos quânticos que estimam os componentes do quociente de Rayleigh diretamente. Esta abordagem evita a construção da matriz de kernel total ou parcial e a estimativa individual das entradas do kernel, que são gargalos em outros métodos espectrais quânticos.
• Análise Rigorosa de Complexidade de Disparos (Shot Complexity): Uma análise teórica demonstra que a complexidade de amostragem para o termo de penalidade ($q_p$) é tratável. Contrariando a intuição de que o termo de penalidade, por ter menor magnitude, exigiria exponencialmente mais disparos, os autores provam, usando desigualdades de concentração, que o número de disparos necessário cresce, no máximo, de forma quase polinomial em relação à probabilidade de falha. Isso valida que o estimador de penalidade não domina o orçamento total de amostragem.
• Fluxo de Trabalho Unificado de Treinamento-Teste: O framework fornece um pipeline completo, desde a otimização variacional até a inferência em dados não vistos usando um mecanismo de pontuação baseado em fase.

Resultados
Os autores validaram a estrutura usando simulações quânticas sem ruído em conjuntos de dados canônicos:

• Datasets: O conjunto de dados Iris (agrupamento binário de Setosa vs. Versicolor/Virginica) e o conjunto de dados MNIST (agrupamento binário de dígitos '0' e '1', reduzido para 4 dimensões via PCA).
• Desempenho:
  • Iris: Com um circuito relativamente raso (4 camadas, 24 parâmetros), o modelo alcançou uma acurácia média de teste de 98,7%. Aumentar para 6 camadas ou mais estabilizou a acurácia em $\ge 99,8\%$.
  • MNIST: O desempenho confiável começou com 6 camadas, estabilizando em uma acurácia média de 97,2% para 8+ camadas.
• Comportamento de Disparos Finitos: As simulações confirmaram que o estimador de penalidade se comporta conforme previsto. A média amostral do termo de penalidade convergiu rapidamente para zero, e a variância contraiu-se adequadamente. Crucialmente, o termo de penalidade pôde ser estimado de forma confiável com um número relativamente pequeno de disparos (ex: 256–1024), consistente com a análise teórica de que ele não exige um orçamento de disparos significativamente maior do que os outros termos.

Significância e Alegações
O artigo posiciona este trabalho como uma "prova de conceito" para uma estrutura de agrupamento espectral que é compatível com circuitos quânticos rasos e eficientes em termos de hardware. A principal significância reside em:

1. Evitar Gargalos de Matriz de Kernel: Ao operar em formas quadráticas agregadas, o método contorna os custos de $O(M^2)$ ou $O(M^4)$ associados à estimativa elemento a elemento do kernel em contextos quânticos.
2. Mitigar o Descompasso de Escala: A análise rigorosa mostra que o termo de penalidade, frequentemente uma fonte de instabilidade numérica ou alto custo de amostragem, pode ser estimado eficientemente, tornando o objetivo variacional prático.
3. Contexto de Aprendizado Não Supervisionado: Os autores observam que, embora os métodos de kernel quântico sejam bem estudados no aprendizado supervisionado, sua aplicação ao agrupamento espectral não supervisionado é menos explorada. Este trabalho une a teoria de grafos espectrais com algoritmos quânticos variacionais neste domínio específico.

Os autores mantêm-se modestos quanto a alegações mais amplas, declarando explicitamente que não abordam se o próprio kernel de fidelidade quântica proporciona uma vantagem quântica sobre kernels clássicos para tarefas gerais. Em vez disso, o foco é fornecer uma implementação eficiente assumindo que o kernel quântico seja a medida de similaridade escolhida. Eles sugerem que trabalhos futuros poderiam estender esta abordagem de análise de penalidade para outros algoritmos variacionais com termos de penalidade (ex: problemas QUBO) e investigar ainda mais as propriedades teóricas de codificações quânticas em configurações não supervisionadas.