⚛️ quantum physics

Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

Este artigo propõe um método de extrapolação para otimizar os dois parâmetros do QAOA de rampa linear, demonstrando que esta abordagem alcança uma escalabilidade de tempo de execução superior em comparação com algoritmos clássicos para problemas de otimização de portfólio de até 28 qubits.

Autores originais: Vanessa Dehn, Martin Zaefferer, Gerhard Hellstern, Karthik Jayadevan, Florentin Reiter, Thomas Wellens

Publicado 2026-06-01

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Vanessa Dehn, Martin Zaefferer, Gerhard Hellstern, Karthik Jayadevan, Florentin Reiter, Thomas Wellens

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

Imagine que você está tentando resolver um quebra-cabeça massivo e incrivelmente complexo. Você tem uma nova ferramenta de alta tecnologia (um computador quântico) que pode ser capaz de resolver esse problema mais rápido do que o melhor cérebro humano ou supercomputador que temos hoje. Mas há um porém: para fazer essa ferramenta funcionar, você precisa ajustar seus botões perfeitamente. Se você errar os botões, a ferramenta será inútil.

Este artigo trata de um atalho inteligente para ajustar esses botões sem ter que fazer o trabalho árduo de testar cada configuração do zero.

Aqui está a divisão da jornada deles, explicada de forma simples:

1. O Problema: Ajustando o "Rádio Quântico"

A ferramenta que eles estão usando é chamada de QAOA (Algoritmo de Otimização Aproximada Quântica). Pense no QAOA como um rádio tentando encontrar um sinal específico e claro (a melhor solução para um problema) em meio a muito ruído.

O Modo Padrão: Normalmente, para deixar o sinal claro, você tem que girar dezenas de botões (parâmetros) e testá-los repetidamente. À medida que o quebra-cabeça fica maior, o número de botões explode, e o processo de ajuste leva uma eternidade. É como tentar sintonizar um rádio com 100 botões manualmente; você nunca terminaria.
A Nova Ideia (Linear-Ramp): Os pesquisadores descobriram uma maneira de simplificar isso. Em vez de 100 botões, eles perceberam que realmente só precisam ajustar dois ajustes principais (vamos chamá-los de "Velocidade" e "Direção") e um ajuste de "Profundidade" (quanto tempo você ouve). Isso é chamado de método Linear-Ramp. É como ter um rádio com apenas um botão de volume e um dial de sintonia, tornando-o muito mais fácil de usar.

2. A Solução: O Truque do "Quebra-Cabeça Pequeno" (Extrapolação)

Mesmo com apenas dois botões, encontrar a configuração perfeita para um quebra-cabeça enorme (digamos, 28 peças) ainda é difícil. Você não pode apenas adivinhar.

Os autores criaram um truque inteligente: Extrapolação.

A Analogia: Imagine que você quer saber a velocidade de um carro de corrida em uma pista de 100 milhas. Em vez de dirigir o carro pelas 100 milhas completas (o que leva muito tempo e usa muito combustível), você dirige o carro em seções de 4 milhas, 6 milhas e 8 milhas. Você mede a velocidade nessas seções.
A Previsão: Você então desenha uma linha conectando essas velocidades e a estende para prever a velocidade que o carro terá nas 100 milhas completas.
No Artigo: Eles pegaram seus problemas grandes e difíceis (até 28 "bits" ou peças de quebra-cabeça) e os quebraram em versões minúsculas e fáceis (4, 6, 8 ou 10 peças). Eles encontraram as configurações de botões perfeitas para essas versões minúsculas. Então, usaram matemática para "esticar" essas configurações para prever as configurações perfeitas para os problemas maiores de 28 peças.

3. O Teste: O Computador Quântico Pode Vencer?

Eles testaram este método em quatro tipos diferentes de quebra-cabeças do mundo real:

Otimização de Portfólio: Escolher a melhor mistura de ações para maximizar o lucro e minimizar o risco.
Seleção de Atributos (Feature Selection): Escolher os pontos de dados mais importantes para um modelo de aprendizado de máquina.
Agrupamento (Clustering): Agrupar itens semelhantes (como separar bolas de gude vermelhas e azuis).
MaxCut: Dividir uma rede em dois grupos de modo que as conexões entre os grupos sejam o mais fortes possível.

Eles executaram esses quebra-cabeças em um computador quântico simulado (uma versão perfeita e sem ruído rodando em um supercomputador) e compararam o tempo que levou para encontrar a resposta contra os melhores métodos computacionais clássicos (normais).

4. Os Resultados: Uma Vitória para as Ações, Mas Não Para Tudo

Aqui está o que eles descobriram:

O Quebra-Cabeça do Mercado de Ações (Otimização de Portfólio): Foi aqui que a mágica aconteceu. O método quântico, usando o truque de previsão do "pequeno quebra-cabeça", tornou-se mais rápido à medida que o problema aumentava em comparação ao método clássico. Ele mostrou uma vantagem potencial. É como se o carro quântico começasse a ultrapassar o motorista humano conforme a pista ficava mais longa.
Os Outros Quebra-Cabeças: Para os outros três tipos de problemas (escolher dados, agrupar itens e dividir redes), o método quântico foi, na verdade, mais lento ou tão lento quanto os métodos clássicos. O "truque de previsão" funcionou, mas a ferramenta quântica não venceu as ferramentas humanas nesses casos específicos.

5. O Atalho "Universal"

Os pesquisadores notaram que as configurações de botões "perfeitas" para o quebra-cabeça do mercado de ações seguiam um padrão simples. Eles perceberam que nem precisavam calcular as configurações para cada novo quebra-cabeça. Eles poderiam apenas usar uma fórmula universal (uma regra única que funciona para todos).

Quando aplicaram essa regra universal, o desempenho quântico para os outros três problemas melhorou significativamente, tornando-se tão bom quanto os métodos clássicos, embora não melhor.

A Conclusão

O artigo afirma que:

Você pode pular o processo caro e lento de ajustar um computador quântico para grandes problemas testando os pequenos primeiro e adivinhando matematicamente o restante.
Este método funciona bem o suficiente para mostrar que, para a Otimização de Portfólio, um computador quântico pode eventualmente resolver esses problemas mais rápido do que um computador clássico conforme os problemas se tornem gigantescos.
Para os outros problemas testados, o computador quântico ainda não venceu, mas o método o tornou competitivo.

Nota Importante: Os autores são cuidadosos ao dizer que isso é uma simulação em um computador perfeito. Eles ainda não provaram que isso funciona em hardware quântico real e com ruído, nem resolveram problemas maiores do que 28 peças. Mas o truque de previsão "do pequeno para o grande" parece ser uma maneira promissora de tornar os computadores quânticos úteis para o futuro.

Resumo Técnico: Método de Extrapolação para Otimizar Parâmetros de LR-QAOA

Declaração do Problema
O Algoritmo de Otimização Aproximada Quântica (QAOA) é um forte candidato para resolver problemas de otimização combinatória, porém sua forma variacional padrão enfrenta desafios significativos de escalabilidade. A abordagem padrão exige a otimização de um grande número de parâmetros de circuito ( $2p$ parâmetros para profundidade $p$ ) via rotinas clássicas, o que é computacionalmente caro e propenso a ficar preso em mínimos locais. Este gargalo de otimização dificulta a demonstração de potenciais vantagens de tempo de execução quântica. Embora esquemas fixos, como o LR-QAOA (Linear-Ramp QAOA), reduzam o espaço de parâmetros para apenas dois parâmetros livres ( $\Delta\gamma, \Delta\beta$ ) mais a profundidade $p$ , encontrar valores ótimos para esses parâmetros para grandes tamanhos de problema ( $N$ ) continua sendo uma tarefa não trivial.

Metodologia
Os autores propõem um método para determinar parâmetros adequados de LR-QAOA para grandes tamanhos de problema através da extrapolação de otimizações realizadas em subproblemas menores. A metodologia consiste em três componentes principais:

Formulação do Problema: Quatro problemas de otimização combinatória são formulados como problemas de Otimização Binária Não Constrangida Quadrática (QUBO): Otimização de Portfólio, Seleção de Atributos (Feature Selection), Agrupamento (Clustering - usando conjuntos de dados Moons e Blobs) e MaxCut ponderado.
Benchmarking Clássico: O escalonamento do tempo de execução de solvers clássicos (CPLEX, Gurobi, Goemans-Williamson e MQLib/Burer2002) é avaliado. O heurístico MQLib/Burer2002 é selecionado como o principal benchmark clássico devido ao seu baixo tempo de execução absoluto e comportamento de escalonamento consistente, evitando o overhead de limites de otimalidade encontrados em solvers comerciais.
LR-QAOA e Esquema de Extrapolação:
- Ansatz de rampa linear (Linear-Ramp Ansatz): Em vez de otimização variacional, os parâmetros são amostrados de um ansatz linear: $\gamma_j = \Delta\gamma x_j$ e $\beta_j = \Delta\beta(1-x_j)$ , onde $x_j$ é uma variável de rampa linear.
- Otimização de Subproblemas: Para um tamanho de problema alvo $N$ (até 28 qubits), instâncias de subproblemas menores e aleatórios de tamanhos ( $\tilde{N} \in \{4, 6, 8, 10\}$ ) são gerados. Uma busca em grade (grid search) é realizada nessas pequenas instâncias para encontrar os valores ótimos de $\Delta\gamma$ e $\Delta\beta$ .
- Ajuste e Extrapolação: Os parâmetros ótimos encontrados para $\tilde{N}$ são ajustados usando uma função Gaussiana assimétrica multivariada para localizar o centro da região de alta probabilidade. Esses centros são então extrapolados para o tamanho alvo $N$ , assumindo uma relação linear em uma escala log-log ( $\log(\text{parâmetro})$ vs. $\log(N)$ ).
- Otimização de Profundidade: A profundidade do QAOA $p$ é otimizada para minimizar o tempo de execução quântico total, definido como o produto da profundidade do circuito e o número mediano de disparos (shots) necessários para encontrar a solução ótima ( $D = d \cdot N_{shots}$ ).
- Escalonamento Universal: Para melhorar a estabilidade e reduzir outliers, os autores derivam leis de escalonamento de parâmetros "universais" ( $f(N) = a \cdot N^b$ ) baseadas nos dados extrapolados, aplicando essas leis fixas a todas as instâncias de uma determinada classe de problema, em vez de otimizar por instância individual.

Principais Resultados
O estudo avalia o escalonamento do tempo de execução quântico (expressos como profundidade total $D$ ) contra o escalonamento clássico em um emulador quântico sem ruído para tamanhos de problema até $N=28$ .

Otimização de Portfólio: O LR-QAOA com parâmetros extrapolados demonstra um expoente de escalonamento de $\alpha \approx 0,219$ (onde $D \propto 2^{\alpha N}$ ), que é significativamente inferior ao benchmark clássico (MQLib/Burer2002) de $\alpha_{cl} \approx 0,323$ . Isso indica uma potencial vantagem de escalonamento quântico.
Seleção de Atributos, Agrupamento e MaxCut: Inicialmente, esses problemas mostraram expoentes de escalonamento quântico superiores aos seus equivalentes clássicos. No entanto, ao aplicar o escalonamento de parâmetros "universal" derivado dos dados de extrapolação, o escalonamento quântico melhorou significativamente.
- Para Seleção de Atributos e MaxCut, o escalonamento quântico atingiu igualdade com os benchmarks clássicos ( $\alpha \approx 0,202$ vs $0,197 $e$ \alpha \approx 0,163$ vs $0,156$, respectivamente).
- Para Agrupamento (Moons), o benchmark clássico ( $\alpha_{cl} \approx 0,051$ ) permaneceu superior à abordagem quântica ( $\alpha \approx 0,163$ ).
Estabilidade: O uso de parâmetros universais reduziu significativamente a ocorrência de outliers extremos (instâncias com profundidades muito grandes) observados quando os parâmetros eram determinados individualmente para cada instância.
Comportamento de Probabilidade: Para Otimização de Portfólio e MaxCut, a probabilidade de medir a solução ótima ( $P_{opt}$ ) permaneceu constante ou aumentou ligeiramente com $N$ , enquanto a profundidade do circuito escalou algebricamente. Isso sugere um potencial para escalonamento polinomial do tempo de execução mediano para essas classes específicas de problemas.

Significância e Alegações
O artigo afirma apresentar um método escalável para determinar parâmetros de LR-QAOA sem a necessidade de otimização variacional dispendiosa em circuitos grandes. Ao alavancar a extrapolação de subproblemas menores, os autores demonstram que:

Vantagem de Tempo de Execução: Uma vantagem de escalonamento quântico é observada para Otimização de Portfólio em comparação com heurísticas clássicas.
Escalabilidade: O método de extrapolação permite a estimativa eficiente de parâmetros para sistemas maiores ( $N=28$ ) baseando-se em simulações de sistemas muito pequenos ( $N \le 10$ ).
Leis Universais: A identificação de leis de escalonamento algébrico para parâmetros ( $\Delta\gamma, \Delta\beta, p$ ) sugere que esses parâmetros podem ser determinados independentemente de instâncias específicas de problemas, melhorando a robustez do algoritmo.

Os autores concluem modestamente que, embora seus resultados sugiram um potencial para soluções de tempo polinomial para instâncias específicas (indicado por $P_{opt}$ constante e escalonamento de profundidade algébrico), trabalhos futuros são necessários para verificar essas descobertas em tamanhos de problema maiores ( $N > 28$ ) e em hardware quântico tolerante a falhas. Eles enfatizam que seu trabalho aborda o potencial geral do LR-QAOA assumindo que os parâmetros podem ser encontrados eficientemente, em vez de resolver o custo da própria otimização de parâmetros como um componente de tempo de execução.