Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Título: Amostragem aproximada de interferometria quântica decodificada via métodos de Monte Carlo por cadeias de Markov

Enunciado do Problema
A Interferometria Quântica Decodificada (DQI) é um algoritmo quântico proposto para lidar com otimização combinatória aproximada, especificamente famílias de problemas max-LINSAT (incluindo Max-XORSAT e Interseção Polinomial Ótima, OPI). Embora a DQI ofereça garantias teóricas de desempenho robustas e tenha tido alegações de fornecer uma vantagem quântica superpolinomial sobre algoritmos clássicos conhecidos em regimes de parâmetros específicos (particularmente para OPI), seu desempenho empírico em relação aos métodos clássicos permanece subexplorado. O problema central abordado neste trabalho é se os métodos de amostragem clássicos podem emular as capacidades de otimização da DQI, desafiando ou refinando as alegações de vantagem quântica. Os autores investigam a complexidade da DQI analisando as versões de decisão, busca e amostragem desses problemas de otimização, observando que a DQI resolve nativamente o problema de amostragem, o qual induz uma distribuição enviesada para soluções de alto escore.

Metodologia
Os autores empregam uma abordagem dual combinando caracterização analítica e simulação numérica de larga escala:

1. Caracterização Analítica: Os autores derivam um arcabouço analítico simplificado para o desempenho da DQI. Eles conectam o desempenho esperado da DQI à estatística binomial ao analisar os momentos da função objetivo sob a distribuição DQI. Esta análise baseia-se nas propriedades do código de correção de erros dual associado à instância do problema. Eles também identificam obstruções teóricas para provar a dureza clássica da amostragem da distribuição DQI, especificamente em relação à redução do problema de busca para o de decisão e à aplicabilidade de reduções de contagem padrão.

2. Simulação Numérica (MCMC): Para testar o desempenho empírico, os autores utilizam métodos de Monte Carlo por Cadeias de Markov (MCMC), especificamente a amostragem de Gibbs em blocos (block-Gibbs sampling), para amostrar da distribuição induzida pelo estado DQI.

   • Distribuição Alvo: Uma vez que as probabilidades de saída da DQI são computáveis classicamente de forma eficiente, os autores constroem uma cadeia de Markov cuja distribuição estacionária coincide com a distribuição de saída da DQI $P(x) \propto P^2(f(x))$, onde $P$ é um polinômio de grau $\ell$ e $f(x)$ é a função objetivo.
   • Algoritmos: Eles comparam duas estratégias de amostragem: "restart" (executar cadeias independentes para cada nova amostra) e "keep-going" (continuar uma única cadeia para encontrar múltiplas amostras distintas).
   • Benchmarks: Os métodos são testados em duas famílias de problemas:
     • Max-XORSAT: Instâncias esparsas aleatórias com $p=2$.
     • Interseção Polinomial Ótima (OPI): Instâncias baseadas em códigos Reed-Solomon com $p > 2$.
   • Escalabilidade: Os experimentos escalam para mais de 1000 qubits efetivos para Max-XORSAT e além de 150 qubits efetivos para OPI. O "número equivalente de qubits" ($n_p = n \lceil \log_2 p \rceil$) é usado como o parâmetro de escalonamento para OPI para permitir a comparação direta com estimativas de recursos quânticos.

Principais Contribuições

• Simplificação Analítica: O artigo fornece uma nova derivação dos momentos de desempenho da DQI usando bases monoais em vez de polinômios simétricos ou de Kravchuk. Isso revela que uma condição necessária para o sucesso da DQI (alta distância do código dual) implica que a versão de decisão do problema é classicamente fácil, deslocando o foco da análise de complexidade para as versões de busca e amparagem.
• Identificação de Obstruções: Os autores identificam obstáculos específicos em provar a dureza clássica da amostragem da DQI, incluindo a dificuldade de reduzir o problema de busca para o problema de decisão no contexto das garantias de desempenho da DQI, e a natureza estruturada do conjunto de soluções "boas" $S$.
• Benchmarking Empírico: Este trabalho apresenta o primeiro estudo empírico abrangente de algoritmos de amostragem clássicos emulando a DQI. Demonstra que técnicas padrão de MCMC podem atingir de forma confiável as razões de aproximação esperadas pela DQI em uma ampla gama de tamanhos de problema.

Resultados

• Max-XORSAT: Para Max-XORSAT, o método de amostragem de Gibbs em blocos atinge o limiar de desempenho da DQI com um tempo de execução que escala polinomialmente (aproximadamente $n^5$) com o número de qubits. Isso indica que, para esta classe de problemas, a amostragem clássica pode equiparar-se eficientemente ao desempenho de otimização da DQI.
• Interseção Polinomial Ótima (OPI): Para OPI, onde a DQI alega uma vantagem superpolinomial, o tempo de execução do MCMC escala exponencialmente com o número de qubits ($n_p$). No entanto, a base do crescimento exponencial é pequena, aproximadamente 1.1 (especificamente $1.096^{n_p}$).
• Amostragem vs. Busca: O comportamento de escalonamento qualitativo para o problema de amostragem espelha o do problema de busca. Os autores observam que a estratégia "keep-going" é mais eficiente para Max-XORSAT (sugerindo soluções agrupadas/clustered), enquanto a estratégia "restart" é mais eficiente para OPI (sugerindo falta de agrupamento de soluções ou uma propriedade de hiato de sobreposição/overlap gap property).
• Sensibilidade ao Limiar: Ao reduzir o limiar de desempenho para OPI, observa-se uma transição de fase na qualidade do ajuste (goodness-of-fit) do escalonamento do tempo de execução: ajustes de lei de potência (power-law) são melhores para limiares mais baixos, enquanto ajustes exponenciais tornam-se superiores acima de um limiar de aproximadamente 0.66. O limiar da DQI para OPI situa-se bem dentro do regime exponencial.

Significância e Alegações
Os autores afirmam que seus achados não refutam as alegações existentes de uma vantagem quântica superpolinomial para a DQI, pois o tempo de execução do MCMC clássico para OPI exibe, de fato, crescimento exponencial. No entanto, o artigo argumenta por uma perspectiva mais matizada dessa vantagem:

1. Base Exponencial Pequena: A base exponencial observada de ~1.1 é comparativamente pequena, sugerindo que algoritmos clássicos podem permanecer competitivos com a DQI para uma ampla gama de tamanhos de instâncias praticamente relevantes, potencialmente ficando atrás apenas para instâncias muito grandes.
2. Emulação Clássica: Os resultados demonstram que algoritmos de amostragem clássicos podem aproximar-se de perto o desempenho de otimização da DQI, desafiando a noção de que a vantagem quântica é absoluta ou facilmente acessível para os tamanhos de problema atuais.
3. Paisagem de Complexidade: O trabalho esclarece que a complexidade da DQI está profundamente ligada às versões de busca e amostragem do problema, e não à versão de decisão, e que ferramentas padrão para provar a dureza de amostragem podem não se aplicar diretamente à DQI.

Em conclusão, o artigo fornece evidências empíricas de que, embora a DQI possa oferecer uma aceleração teórica, a vantagem quântica prática é menos acentuada do que anteriormente sugerido, com métodos de MCMC clássicos oferecendo uma alternativa viável e eficiente para muitas tarefas de otimização.