Displaced Gaussian Boson Sampling for enhanced max-clique search

Resumo Técnico: Amostragem de Bosões Gaussianos Deslocada para Busca Aprimorada de Máximo Clique

Enunciado do Problema
A Amostragem de Bosões Gaussianos (GBS) emergiu como uma plataforma promissora para demonstrar vantagem quântica na resolução de problemas específicos de grafos, particularmente a busca por máximos cliques (subgrafos completos) em grafos ponderados não direcionados. A distribuição de probabilidade das amostras de GBS está ligada ao hafniano de uma matriz derivada da matriz de adjacência do grafo. No entanto, implementações práticas de GBS enfrentam obstáculos significativos: níveis limitados de compressão e alta perda de fótons degradam o desempenho do dispositivo, frequentemente tornando a tarefa de amostragem simulável classicamente. Embora os estados coerentes (deslocamentos) sejam tipicamente vistos como um recurso clássico devido às suas estatísticas de Poisson, sua utilidade potencial em melhorar o desempenho do GBS sob condições realistas e com perdas permanece uma questão em aberto.

Metodologia
Os autores propõem e analisam uma variante do GBS chamada Amostragem de Bosões Gaussianos Deslocada (D-GBS). Neste esquema, portas de deslocamento são aplicadas a cada modo de saída do interferômetro, efetivamente misturando estados coerentes com os estados de vácuo comprimido.

• Estrutura Teórica: A probabilidade de medir um padrão específico de número de fótons $n$ no D-GBS é governada pela função hafniano de laço ($lHaf$), que generaliza o hafniano padrão. O hafniano de laço incorpora parâmetros de deslocamento ($\gamma$) que modificam os elementos diagonais da matriz usada no cálculo do hafniano.
• Codificação do Grafo: Grafos ponderados são mapeados para o experimento de GBS configurando parâmetros de compressão e uma rede unitária passiva. A matriz de adjacência é reescalonada para garantir realizabilidade física.
• Pós-processamento Clássico: Para extrair o máximo clique das amostras brutas de GBS, os autores empregam uma rotina heurística clássica de duas etapas:
  1. Encolhimento Guloso: Remove aleatoriamente vértices de um subgrafo detectado até que um clique seja formado.
  2. Busca Local: Tenta iterativamente expandir o clique adicionando ou trocando vértices para maximizar o tamanho e o peso do clique.
• Simulação: O estudo utiliza as bibliotecas Python Strawberry Fields e The Walrus para simular amostradores de GBS e D-GBS. O desempenho é avaliado em comparação com o GBS padrão, um amostrador uniforme e o "amostrador de Oh" (um algoritmo clássico inspirado em quântica baseado em interferências de dois fótons).

Principais Contribuições e Resultados

1. Melhoria sob Baixa Compressão: Os autores demonstram que adicionar deslocamento ($\gamma \neq 0$) aumenta significativamente a taxa de sucesso na descoberta de cliques de peso máximo quando a compressão disponível é insuficiente para atingir o regime ótimo de GBS. Em cenários de baixa compressão, a probabilidade de gerar os subgrafos de alta densidade necessários é diminuída; o deslocamento compensa isso aumentando a eficiência de heraldação de números de fótons mais altos.
2. Resiliência a Perdas: O estudo mostra que o D-GBS é resiliente à perda de fótons. Embora a perda geralmente degrade o desempenho do GBS, a adição de deslocamento permite que o sistema mantenha uma alta probabilidade de amostrar o máximo clique mesmo com perdas significativas (por exemplo, 50% por modo). O deslocamento pode ser ajustado para compensar fótons perdidos, preservando a capacidade de recuperar o máximo clique após o pós-processamento clássico.
3. Escalabilidade: Os autores investigam a escalabilidade do D-GBS para grafos maiores. Eles constatam que a vantagem do D-GBS sobre o GBS padrão escala polinomialmente à medida que o tamanho do clique aumenta, desde que a razão entre fótons induzidos por deslocamento e fótons induzidos por compressão seja gerenciada corretamente. Especificamente, o número médio de fótons do deslocamento deve escalar mais lentamente do que o da compressão para manter a vantagem relativa do hafniano de laço.
4. Benchmarks: Em simulações envolvendo grafos Erdős-Rényi, o amostrador D-GBS, quando combinado com busca local, supera tanto o amostrador GBS padrão (sob compressão restrita) quanto amostradores puramente clássicos, como o amostrador de Oh e a amostragem uniforme, em termos de taxa de sucesso na descoberta de máximos cliques.

Significado e Alegações
O artigo afirma que o deslocamento serve como um recurso clássico valioso para aprimorar a utilidade prática do GBS para problemas de grafos na era de Computação Quântica de Escala Intermediária Ruidosa (NISQ).

• Praticidade: Os autores enfatizam que, embora alta compressão seja desejável, ela muitas vezes é inatingível ou acompanhada de alta perda nas configurações experimentais atuais. O D-GBS oferece um caminho para melhorar o desempenho nessas condições realistas e imperfeitas.
• Aceleração Moderada: Os autores afirmam explicitamente que não reivindicam uma aceleração quântica exponencial. Em vez disso, argumentam por uma "provável aceleração polinomial" sobre algoritmos estocásticos clássicos (como amostragem aleatória ou o amostrador de Oh) para encontrar máximos cliques em grafos não negativos.
• Complexidade: A complexidade computacional de simular o D-GBS permanece difícil (relacionada ao #P-difícil hafniano de laço) desde que o número de fótons coerentes ($N_{coh}$) permaneça menor que o número de fótons comprimidos ($N_{sqz}$) em um regime assintótico específico.
• Direções Futuras: O trabalho sugere que a codificação de grafos de peso complexo poderia estender ainda mais o alcance das aplicações, como na análise de dados topológicos, embora isso permaneça uma questão em aberto para pesquisas futuras.

Em resumo, o artigo estabelece que o D-GBS deslocado é uma alternativa robusta ao GBS padrão para busca de máximo clique, oferecendo taxas de sucesso aprimoradas e resiliência a imperfeições experimentais como perda de fótons e compressão limitada, sem exigir recursos exponenciais.