⚛️ quantum physics

Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

O artigo apresenta o SamBa-GQW, um algoritmo quântico não variacional que utiliza um protocolo de amostragem clássica offline para guiar uma caminhada quântica de tempo contínuo em direção a soluções de alta qualidade para problemas de otimização combinatória, demonstrando desempenho comparável a métodos variacionais como o QAOA sem a necessidade de otimizadores clássicos.

Autores originais: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Publicado 2026-10-02

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo da computação, alguns problemas são como tentar encontrar um grão de areia específico em uma praia que dobra de tamanho cada vez que você dá um passo. Estes são conhecidos como problemas de otimização combinatória, onde um computador deve escolher o melhor arranjo entre um vasto número de possibilidades, como a rota mais eficiente para um caminhão de entregas ou a melhor mistura de ações para um portfólio de investimentos. À medida que o número de escolhas cresce, o tempo necessário para um computador tradicional verificar cada opção aumenta tão rapidamente que mesmo os supercomputadores mais poderosos levariam mais tempo do que a idade do universo para encontrar a resposta. Os computadores quânticos, que utilizam as estranhas regras da física para processar informações, oferecem um atalho potencial. Eles podem explorar muitas possibilidades de uma só vez, mas as máquinas atuais são ruidosas e imperfeitas, muitas vezes exigindo um ajuste complexo para funcionar corretamente. Isso levou pesquisadores a buscar novas maneiras de guiar essas máquinas quânticas sem a necessidade de um ser humano ajustar constantemente as configurações.

Uma equipe de pesquisadores introduziu um novo método chamado SamBa-GQW, uma técnica projetada para resolver esses quebra-cabeças difíceis sem depender de um computador clássico para refinar o processo quântico. Em vez de usar uma abordagem de tentativa e erro que exige que um computador clássico verifique e corrija constantemente as configurações da máquina quântica, este novo método utiliza uma etapa de preparação inteligente e única. Os pesquisadores primeiro pegam uma amostra pequena e gerenciável do cenário do problema em um computador regular. Essa amostra atua como um mapa, revelando a forma geral do espaço de solução e onde as melhores respostas provavelmente se escondem. Usando esse mapa, eles configuram a máquina quântica para realizar uma jornada específica, um fluxo contínuo de probabilidade que naturalmente deriva em direção às melhores soluções. A máquina quântica então segue esse caminho pré-calculado, guiada por um ritmo variável que desacelera à medida que se aproxima da resposta ideal, permitindo efetivamente que a física do sistema realize o trabalho pesado.

Os pesquisadores testaram essa abordagem em uma variedade de problemas desafiadores, incluindo encontrar a melhor maneira de dividir uma rede em dois grupos, selecionar o maior grupo de itens que não conflitem entre si e otimizar portfólios de investimento. Eles simularam o processo em problemas envolvendo até trinta variáveis, um tamanho significativo para a tecnologia quântica atual. Os resultados mostraram que o método consistentemente encontrou soluções de alta qualidade, frequentemente chegando à melhor resposta possível ou a algo muito próximo dela. Em muitos casos, o estado quântico tornou-se altamente focado na solução correta, o que significa que, se você medisse a saída do computador, teria uma probabilidade muito alta de obter a resposta certa. A equipe descobriu que precisava apenas amostrar uma fração minúscula do total de decisões possíveis para construir um mapa eficaz, provando que uma busca exaustiva completa do cenário do problema não era necessária para guiar o caminhante quântico.

Quando comparado com outros métodos quânticos populares, como o Algoritmo de Aproximação Quântica (QAOA), a nova técnica se manteve à altura, embora com uma troca diferente. O método QAOA padrão depende de um computador clássico para ajustar repetidamente as configurações da máquina quântica para encontrar o melhor desempenho, um processo que pode ser lento e propenso a ficar preso em armadilhas locais. Em contraste, o método SamBa-GQW não requer tal ajuste; ele executa uma sequência única e predeterminada. Embora o método padrão muitas vezes alcance resultados ligeiramente melhores quando fornecido com circuitos muito profundos e complexos, o novo método apresenta um desempenho tão bom quanto quando a profundidade do circuito é permitida para crescer o suficiente. Isso sugere que, para futuros computadores quânticos mais poderosos, esta abordagem não variacional poderia ser uma maneira altamente eficiente de resolver problemas complexos, contornando a necessidade dos loops de otimização difíceis e demorados que atualmente limitam muitos algoritmos quânticos.

O estudo também explorou como o método se comporta com diferentes tipos de problemas e níveis variados de dificuldade. Para alguns problemas, como maximizar o número de condições satisfeitas em um quebra-cabeça lógico, o método encontrou as melhores soluções com alta probabilidade, mesmo para versões complexas do problema. Para outros, como o problema do caixeiro viajante, o tempo necessário para a máquina quântica completar sua jornada dependeu das distâncias específicas entre as cidades, mas o método ainda guiou com sucesso o sistema para a rota ideal. Os pesquisadores observaram que o estado quântico naturalmente se concentraria nas melhores respostas, encolhendo de uma ampla dispersão de possibilidades para um agrupamento apertado ao redor da solução. Essa localização ocorreu rapidamente em muitos casos, sugerindo que o método é robusto e confiável.

Em última análise, este trabalho apresenta uma alternativa promissora para a próxima geração de computação quântica. Ao substituir a necessidade de um otimizador clássico por um protocolo de amostragem offline simples, os pesquisadores criaram um caminho simplificado para as máquinas quânticas resolverem problemas difíceis. O método não afirma resolver esses problemas instantaneamente ou com um truque de mágica; em vez disso, oferece uma maneira prática e matematicamente fundamentada de navegar nos vastos espaços de busca da otimização combinatória. À medida que o hardware quântico continua a melhorar, indo além da atual era ruidosa, esta abordagem pode se tornar uma ferramenta padrão para enfrentar os desafios logísticos e científicos de grande escala que atualmente sobrecarregam os computadores clássicos. As descobertas sugerem que, com a orientação correta, os sistemas quânticos podem encontrar eficientemente o caminho para as melhores soluções sem precisar de uma mão humana para guiá-los a cada passo.

Resumo Técnico: SamBa–GQW (Guided Quantum Walk Baseado em Amostragem)

Definição do Problema

O artigo aborda o desafio de resolver problemas de otimização combinatória binária de grau arbitrário em computadores quânticos. Esses problemas, frequentemente NP-difíceis, envolvem encontrar um vetor binário $x^* \in \{0, 1\}^n$ que minimize uma função de custo $C(x)$ , potencialmente sujeito a restrições. Embora os computadores quânticos ofereçam uma maneira natural de explorar espaços de solução exponenciais com recursos de qubits lineares, os atuais dispositivos de Escala Intermediária com Ruído Quântico (NISQ) lutam com algoritmos variacionais como o Algoritmo de Otimização Aproximada Quântica (QAOA). Essas abordagens variacionais dependem de um otimizador clássico para ajustar parâmetros, um processo frequentemente assolado por "platôs estéreis" (gradientes evanescentes) e escalonamento exponencial no número de avaliações de circuitos necessárias conforme o tamanho do problema aumenta.

Alternativas não variacionais existentes, como o Caminho Quântico Guiado (GQW), tentam evitar a otimização clássica usando uma taxa de salto dependente do tempo derivada do espectro do Hamiltoniano do problema. No entanto, calcular o espectro exato é exponencialmente custoso, e aproximações anteriores usando curvas paramétricas (por exemplo, curvas de Bézier) ainda exigiam otimização clássica, levando ao escalonamento exponencial no número de iterações.

Metodologia: SamBa–GQW

Os autores propõem o SamBa–GQW (Sampled-Based Guided Quantum Walk), um algoritmo quântico não variacional que elimina a necessidade de um otimizador clássico durante a fase de execução quântica. O algoritmo opera em duas etapas distintas:

1. Protocolo de Amostragem Offline Clássica

Em vez de computar o espectro exato do Hamiltoniano de custo $H_C$ (o que requer $2^n$ avaliações) ou otimizar uma curva paramétrica, o algoritmo emprega um protocolo de amostragem eficiente.

Amostragem: O protocolo seleciona aleatoriamente um número polinomial de estados candidatos, $q = \text{poly}(n)$ (encontrado empiricamente como suficiente com $q=n^2$ ), do espaço de solução $2^n$ .
Estimativa de Gap: Para cada estado amostrado, o algoritmo computa os gaps de energia entre o estado e seus vizinhos (definidos pela conectividade do mixer, por exemplo, o hipercubo para um mixer X).
Aproximação do Espectro: Ele calcula a média dos maiores gaps de energia para níveis de energia específicos. Isso fornece uma aproximação da função $\Gamma(E)$ , que relaciona a taxa de salto com o gap de energia, conforme derivado da literatura anterior de GQW.
Construção do Cronograma: Usando esses pontos amostrados, o algoritmo constrói uma taxa de salto contínua, suave e dependente do tempo $\Gamma(t)$ via interpolação. Este cronograma é projetado para equilibrar o Hamiltoniano de mistura $H_M$ e o Hamiltoniano de custo $H_C$ , maximizando a transferência de amplitude de estados de alta energia para estados de baixa energia.

2. Execução Online Quântica

Uma vez determinado o cronograma de salto $\Gamma(t)$ , o computador quântico executa um caminho quântico no tempo contínuo (CTQW) guiado por este cronograma.

Hamiltoniano: O sistema evolui sob o Hamiltoniano dependente do tempo $H(t) = \Gamma(t)H_M + H_C$ .
Implementação de Circuito: Para executar isso em computadores quânticos baseados em portas, os autores propõem uma estratégia de discretização de dois níveis. O intervalo de tempo é primeiro dividido em períodos onde a taxa de salto é interpolada linearmente. Esses períodos são subdivididos para aplicar a decomposição de Trotter-Suzuki. Isso resulta em um circuito quântico com camadas alternadas de unitários de custo ( $U_C$ ) e de mistura ( $U_M$ ), semelhante na estrutura ao QAOA, mas com parâmetros determinados a priori, em vez de otimizados.
Medição: O algoritmo realiza um único conjunto de medições na base computacional. A melhor solução encontrada entre as medições é selecionada.

Principais Contribuições

Estrutura Não Variacional: O SamBa–GQW é um algoritmo de "etapa única" (one-shot) que não requer um otimizador clássico para ajustar parâmetros quânticos, evitando assim platôs estéreis e o escalonamento exponencial associado a loops variacionais.
Amostragem Eficiente: O artigo demonstra que um número polinomial de amostras ( $q \approx n^2$ ) é suficiente para aproximar a taxa de salto ideal, evitando o custo exponencial da análise espectral exata.
Implementação de Circuito: Os autores fornecem um método concreto para discretizar a evolução de tempo contínuo em um circuito quântico baseado em portas com profundidade polinomial relativa ao número de qubits e amostras.
Ampla Aplicabilidade: O algoritmo é testado em uma diversidade de problemas, incluindo:
- Problemas Quadráticos: MaxCut, Conjunto Independente Máximo (MIS) e Otimização de Portfólio (com restrições).
- Problemas de Ordem Superior: Sequências Binárias de Baixa Autocorrelação (LABS), MAX-k-SAT e uma reformulação quártica do Problema do Caixeiro Viajante (TSP).

Resultados

Os autores apresentam simulações numéricas (tanto baseadas em Hamiltoniano quanto em circuito) para tamanhos de problema de até $n=30$ qubits.

Desempenho: O SamBa–GQW encontra consistentemente soluções aproximadas de alta qualidade. Para muitas instâncias, a probabilidade de medir a solução ótima ou soluções dentro do top 5% dos rankings é muito alta.
Comparação com GQW: Quando comparado ao GQW variacional (que usa um otimizador clássico para ajustar uma curva de Bézier), o SamBa–GQW alcança razões de aproximação comparáveis. Crucialmente, o SamBa–GQW reduz o tempo de execução em pelo menos uma ordem de magnitude porque evita o loop de otimização clássica iterativo.
Comparação com QAOA:
- Circuitos Rasos (regime NISQ): Quando restrito a profundidades de circuito rasas (por exemplo, $p < 20$ ), o QAOA geralmente supera o SamBa–GQW, particularmente para MaxCut ponderado e MIS. Isso é atribuído à capacidade do QAOA de usar a otimização clássica para refinar parâmetros para instâncias específicas do problema.
- Circuitos Profundos (Além do NISQ): Quando a profundidade do circuito é permitida aumentar (até $p \approx 100$ ou mais), o SamBa–GQW performa "em par" com o QAOA em termos de razões de aproximação. O artigo observa que o SamBa–GQW requer circuitos mais profundos para atingir seu pico de desempenho em comparação com a saturação rasa do QAOA, mas alcança uma qualidade final similar sem o overhead variacional.
Escalabilidade: O algoritmo escala razoavelmente bem com o número de qubits. Para problemas como MaxCut e MIS, a razão de aproximação permanece alta mesmo conforme $n$ aumenta, desde que o parâmetro de amostragem $q$ e a profundidade do circuito sejam ajustados apropriadamente.

Significância e Alegações

O artigo posiciona o SamBa–GQW como um heurístico promissor para enfrentar problemas de otimização combinatória além do regime NISQ. Sua principal significância reside em oferecer uma alternativa não variacional que é robusta contra platôs estéreis e não sofre com o escalonamento exponencial das iterações de otimização clássica encontradas em métodos variacionais.

Os autores alegam que, embora o SamBa–GQW possa exigir circuitos mais profundos do que o QAOA para obter resultados ótimos, ele oferece um compromisso favorável entre qualidade de solução e custo computacional ao eliminar a necessidade de repetidas avaliações de circuitos quânticos durante um loop de otimização clássica. O algoritmo é apresentado não como uma solução de tempo polinomial para problemas NP-difíceis, mas como um método onde recursos polinomiais (em termos de amostragem e profundidade de circuito) podem ser suficientes para guiar efetivamente a busca em direção a estados de alta qualidade. O trabalho sugere que, à medida que o hardware quântico melhora e circuitos mais profundos se tornam viáveis, o SamBa–GQW poderá servir como uma abordagem competitiva e escalável para a otimização combinatória de larga escala.