Sample efficient graph classification using binary Gaussian boson sampling

Resumo Técnico: Classificação de Grafos Eficiente em Amostragem usando Amostragem de Bosons Gaussianos Binários

Declaração do Problema
A classificação de grafos é uma tarefa crítica em aprendizado de máquina com aplicações em bioinformática, ciência de redes e visão computacional. No entanto, representar dados estruturados em grafos para classificadores padrão de aprendizado de máquina é desafiador porque os grafos são tipicamente representados como matrizes de adjacência, enquanto os classificadores exigem entradas de valor vetorial. Isso necessita definir um mapa de características $\phi$ que projete grafos em um espaço de Hilbert, frequentemente utilizando métodos de kernel para medir similaridade.

Propostas recentes sugeriram o uso de Amostragem de Bosons Gaussianos (GBS) para construir kernels de grafos. Embora a GBS ofereça uma potencial "vantagem quântica" ao amostrar de distribuições de probabilidade governadas pelo Hafniano de uma matriz (um problema #P-completo), algoritmos existentes de classificação de grafos baseados em GBS enfrentam obstáculos significativos. Especificamente, eles dependem de detectores de resolução de número de fótons (PNR). A complexidade de amostragem necessária para aproximar a distribuição de probabilidade de eventos de detecção PNR cresce superexponencialmente com o número de modos, tornando a abordagem intratável para grafos maiores. Além disso, detectores PNR são tecnologicamente complexos, frequentemente exigindo temperaturas criogênicas.

Metodologia
Os autores propõem uma variação do algoritmo de kernel de grafos GBS que utiliza detectores binários (sensíveis a fótons únicos, mas não resolutivos) em vez de detectores PNR. Neste arranjo, um evento de detecção é registrado como uma string binária $n_{bin} = (n_1, ..., n_M)$ onde $n_i \in \{0, 1\}$, indicando se pelo menos um fóton foi detectado no modo $i$.

1. Fundamentação Teórica: A probabilidade de um evento de detecção binária é caracterizada pela função matricial Torontônio, que também é classicamente intratável. Os autores estabelecem a conexão entre GBS binária e teoria dos grafos, mostrando que a probabilidade de um evento binário é proporcional à soma dos Hafnianos ao quadrado de todos os subgrafos possíveis do grafo de entrada que correspondem ao padrão de detecção específico.
2. Estratégias de Extração de Características: Para abordar o problema de complexidade de amostragem inerente às probabilidades de detecção brutas, os autores introduzem duas estratégias de granulação grosseira para construir vetores de características:
   • Granulação grosseira $\mu$: Agrupa eventos de detecção pelo número total de "cliques" de detectores (uns). Isso resulta em um vetor de características de tamanho $N+1$ (onde $N$ é o número máximo de cliques), escalando linearmente com o número de modos.
   • Granulação grosseira $\nu$: Agrupa eventos de detecção com base no padrão dos primeiros $k$ modos (por exemplo, os primeiros 5 modos). Isso resulta em um vetor de características de tamanho constante ($2^k$), independente do tamanho total do grafo.
3. Implementação do Algoritmo: Os grafos são codificados no dispositivo GBS através de suas matrizes de adjacência usando a decomposição de Takagi para determinar os parâmetros de compressão e as configurações do interferômetro. Amostras são geradas, granuladas grosseiramente em vetores de características e alimentadas em uma Máquina de Vetores de Suporte (SVM) com um kernel RBF para classificação.

Principais Contribuições

• Simplificação Tecnológica: O algoritmo substitui detectores PNR por detectores binários (por exemplo, SPADs), que são tecnologicamente mais simples e podem operar perto da temperatura ambiente, reduzindo significativamente a complexidade e o custo de implementação.
• Eficiência de Amostragem: Ao empregar estratégias de granulação grosseira ($\mu$ e $\nu$), os autores demonstram que a complexidade de amostragem é reduzida de superexponencial (no caso de PNR) para linear ($O(M)$) ou constante ($O(1)$) em relação ao número de modos, tornando o algoritmo viável para tamanhos de problema maiores.
• Conexão Teórica: O artigo elucida a relação entre GBS binária e a função Torontônio, estendendo os argumentos para intratabilidade clássica a este regime de detectores.

Resultados
Os autores avaliaram seu kernel GBS binário em dez conjuntos de dados de grafos padrão (por exemplo, AIDS, MUTAG, ENZYMES) e compararam-no com quatro kernels de grafos clássicos (Correspondência de Subgrafos, Amostragem de Grafletos, Caminhada Aleatória, Caminho Mais Curto) e o kernel GBS original baseado em PNR.

• Desempenho: O kernel GBS binário alcançou precisão competitiva ou superior em comparação com kernels clássicos na maioria dos conjuntos de dados. Notavelmente, no conjunto de dados ENZYMES, o kernel GBS binário com granulação grosseira $\nu$ alcançou uma precisão de 48,10%, superando significativamente os kernels de Caminhada Aleatória (19,50%), Caminho Mais Curto (22,15%) e Correspondência de Subgrafos (37,38%). Também superou o kernel baseado em PNR (que exigiu deslocamento para atingir ~40% neste conjunto de dados).
• Robustez: O kernel performou bem em conjuntos de dados com desequilíbrios significativos de tamanho entre classes (por exemplo, AIDS, MUTAG), sugerindo que características baseadas em GBS são sensíveis a propriedades de tamanho do grafo.
• Análise de Características: A Análise de Componentes Principais (PCA) revelou que a característica correspondente à detecção de vácuo (nenhum fóton) nos primeiros modos contribui mais significativamente para a classificação, ligando o desempenho ao Hafniano de subgrafos com vértices específicos removidos.

Significado e Alegações
O artigo alega que um kernel GBS utilizando apenas detectores binários pode alcançar alta precisão de classificação enquanto é eficiente em amostragem e tecnicamente viável. Os autores enfatizam que esta abordagem remove a necessidade de detectores PNR criogênicos e dos tamanhos de amostra proibitivos associados a eles.

O significado reside em demonstrar que a "vantagem quântica" para tarefas de aprendizado de máquina não necessariamente requer o hardware quântico mais avançado e difícil de implementar (detectores PNR). Em vez disso, dispositivos mais simples, de curto prazo, usando detectores binários, combinados com estratégias apropriadas de granulação grosseira, podem fornecer kernels de grafos úteis e competitivos. Os autores concluem que, embora a amostragem exata dessas distribuições permaneça classicamente difícil, as versões específicas com granulação grosseira usadas aqui oferecem um caminho prático para aplicar métodos inspirados em quântica a dados estruturados em grafos. Eles também observam que mais investigação é necessária quanto à dificuldade clássica de amostrar dessas distribuições específicas com granulação grosseira.