⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

Este artigo demonstra que o framework de Codificação de Correlação de Pauli (PCE), uma abordagem variacional eficiente em qubits, resolve eficazmente o problema das Sequências Binárias de Baixa Autocorrelação (LABS) com melhor escalonamento e resiliência ao ruído, superando heurísticas clássicas de última geração enquanto requer significativamente menos recursos quânticos.

Autores originais: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Publicado 2026-01-27

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

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 organizar uma longa fila de pessoas, onde cada pessoa segura uma bandeira vermelha (+1) ou uma bandeira azul (-1). Seu objetivo é organizar as pessoas de modo que, se você olhar para a fila de diferentes ângulos, os padrões de bandeiras vermelhas e azuis não se alinhem acidentalmente de uma forma confusa. Na comunidade científica, isso é chamado de problema das Sequências Binárias de Baixa Autocorrelação (LABS). É um enigma notoriamente difícil usado para testar o quão bons são os computadores ao resolver problemas de otimização complexos.

Este artigo apresenta uma nova e inteligente maneira para computadores quânticos (especificamente os do tipo atual, ruidosos, conhecidos como NISQ) resolverem este enigma melhor do que muitos métodos tradicionais. Aqui está a divisão de sua abordagem:

1. O Problema: Um "Campo de Golfe" de Erros

Pense na busca pela arrumação perfeita das bandeiras como tentar encontrar o ponto mais baixo em uma vasta paisagem nebulosa.

A Paisagem: Na maior parte do tempo, você está caminhando em uma planície com muitos pequenos declives (mínimos locais). Eles parecem o fundo de um vale, mas não são o fundo real.
O Objetivo: A solução verdadeira é um único buraco minúsculo e profundo no meio da planície (o mínimo global).
A Dificuldade: Devendo haver tantos "fundos" falsos, os programas de computador padrão costem ficar presos em um deles e desistem, achando que encontraram a melhor resposta quando não encontraram.

2. A Solução: Um Mapa "Comprimido" (Codificação de Correlação de Pauli)

Normalmente, para resolver um problema com $N$ variáveis (como 45 bandeiras), um computador quântico precisa de 45 bits quânticos (qubits). Mas os computadores quânticos atuais são pequenos e frágeis; eles não conseguem lidar com tantos bits ainda.

Os autores usam um truque chamado Codificação de Correlação de Pauli (PCE).

A Analogia: Imagine que você tem uma enorme biblioteca de livros (as 45 bandeiras), mas possui apenas um caderninho (4 qubits). Em vez de escrever sobre cada um dos livros, você usa um código especial. Você escreve as relações entre os livros.
Como funciona: Eles mapeiam as 45 bandeiras em apenas 4 qubits. É como comprimir um filme de alta definição em um arquivo minúsculo sem perder o enredo. Isso permite que eles abordem problemas enormes (até 45 bandeiras em sua simulação, e até 120 em um experimento real) usando pouquíssimos recursos quânticos.

3. A Estratégia: Escolhendo as "Perguntas" Certas

Para obter o máximo de informação desses 4 qubits, a equipe teve que decidir como fazer perguntas ao computador quântico.

O Conjunto Comutativo: Fazer perguntas que não interferem umas nas outras (como perguntar sobre o clima e a hora do dia).
O Conjunto Não Comutativo: Fazer perguntas que sim, interferem umas nas outras (como tentar medir a posição e a velocidade de uma moeda girando ao mesmo tempo).
O Resultado: Eles descobriram que as perguntas "interferentes" (não comutativas) eram muito melhores. É como sacudir um pote de bolinhas de gude para ver o quadro completo, em vez de apenas olhar para um lado. Este método lhes deu os melhores resultados.

4. O Desempenho: Mais Rápido e Inteligente

Eles testaram seu novo método contra os melhores programas de computador clássicos (regulares) e outros métodos quânticos.

A Corrida: Eles mediram o "Tempo para Solução" (quanto tempo leva para encontrar a resposta perfeita).
O Resultado: O método quântico deles foi mais rápido do que os melhores programas clássicos "heurísticos" (um algoritmo de adivinhação inteligente chamado Busca Tabu) para os tamanhos que testaram.
A Escala: Enquanto outros métodos quânticos precisavam de computadores massivos e perfeitos que ainda não existem, este método funciona em dispositivos pequenos e atuais. Ele escala melhor, o que significa que, conforme o problema aumenta, o método deles permanece competitivo por mais tempo do que os outros.

5. O Teste no Mundo Real: O Parquinho "Ruidoso"

Os autores não apenas rodaram simulações; eles realmente executaram seu algoritmo em um computador quântico real fabricado pela IonQ (chamado de processador Forte).

O Desafio: Computadores quânticos reais são "ruidosos". É como tentar ouvir um sussurro em meio a um furacão. O hardware comete erros.
O Resultado: Eles conseguiram resolver um problema com 120 bandeiras (o maior já mostrado em hardware quântico para este problema específico).
Resiliência: Mesmo com o "furacão" de ruído, a resposta final ainda foi boa. Eles descobriram que não precisavam de milhões de tentativas (shots) para obter uma resposta decente; alguns milhares foram suficientes. No entanto, o ruído fez com que a resposta final fosse ligeiramente menos perfeita do que uma simulação perfeita seria.

Resumo

O artigo afirma que, ao usar uma técnica inteligente de "compressão" (PCE) e fazer o tipo certo de perguntas (operadores não comutativos), eles podem resolver um enigma matemático muito difícil (LABS) em computadores quânticos pequenos e imperfeitos. Seu método é mais rápido do que os melhores métodos de adivinhação clássicos atuais para os tamanhos testados e é robusto o suficiente para funcionar em hardware real e ruidoso hoje. Eles sugerem que isso pode ser uma ferramenta poderosa para resolver problemas difíceis agora mesmo, antes mesmo de termos computadores quânticos perfeitos e livres de erros.

Resumo Técnico: Um Solucionador Competitivo para o Problema LABS em Ambiente NISQ e com Eficiência de Qubits

Definição do Problema
O problema das Sequências Binárias de Baixa Autocorrelação (LABS - Low Autocorrelation Binary Sequences) é um desafio de otimização combinatória NP-difícil bem conhecido, com aplicações em engenharia, comunicações e física estatística. Dado um inteiro $N$ , o objetivo é encontrar uma sequência binária $x \in \{-1, +1\}^N$ que minimize a energia de lóbulos secundários $E(x)$ , definida como a soma dos quadrados das autocorrelações $C_\ell(x)$ para $\ell > 0$ . Equivalentemente, o objetivo é maximizar o fator de mérito $F(x) = N^2 / 2E(x)$ . O problema é caracterizado por um cenário de otimização do tipo "campo de golfe" (golf course), com inúmeros mínimos locais e mínimos globais isolados. Embora soluções exatas sejam conhecidas para $N \le 66$ , encontrar soluções ótimas ou de alta qualidade para $N$ maiores torna-se intratável para métodos clássicos de força bruta, e até mesmo para heurísticas de estado da arte, como a Busca Tabu Memética, que enfrentam desafios significativos de escalonamento.

Metodologia: Codificação de Correlação de Pauli (PCE)
Os autores propõem um solucionador quântico variacional baseado no framework de Codificação de Correlação de Pauli (PCE). Diferente das codificações padrão que exigem um qubit por variável binária, a PCE comprime $N$ variáveis binárias em $n$ qubits onde $N = \text{poly}(n)$ , especificamente $n \ll N$ .

Codificação: As variáveis binárias $x_i$ são codificadas como os sinais dos valores esperados de um conjunto de strings de Pauli de $n$ qubits $\Pi = \{\Pi_i\}_{i \in [N]}$ :
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
onde $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ .
Otimização: O estado quântico $|\Psi\rangle$ é gerado por um circuito de tijolos (brickwork) parametrizado. Os parâmetros são otimizados classicamente para minimizar uma função de perda não linear $L$ . Para facilitar a otimização baseada em gradiente, as variáveis binárias são relaxadas usando uma função tangente hiperbólica: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ . A função de perda inclui um termo de regularização para evitar que os correladores desapareçam.
Seleção do Conjunto de Pauli: O estudo avalia dois conjuntos distintos para $\Pi$ $Π$ :
1. $\Pi(C)$ : Um conjunto de operadores de Pauli selecionados aleatoriamente e mutuamente comutativos.
2. $\Pi(NC)$ : Um conjunto projetado para maximizar o número de operadores de Pauli mutuamente não comutativos. Os autores hipotetizam que a não comutatividade leva a medições mutuamente unbiased, aumentando a expressividade e a independência das variáveis codificadas.

Principais Contribuições e Resultados

Simulações Numéricas ( $N \le 45$ ):
- Os autores simularam o solucionador PCE usando $n=4$ qubits e um profundidade de circuito de 15 camadas (30 portas de dois qubits, 150 parâmetros).
- A variante $\Pi(NC)$ superou consistentemente a variante comutativa.
- Análise de Escalonamento: O Tempo para Solução (TTS), definido como o número de avaliações da função de custo necessárias para encontrar a solução exata, foi comparado com QAOA e Busca Tabu Memética.
  - Escalonamento PCE: $O(1.330^N)$ para instâncias pares e $O(1.326^N)$ para instâncias ímpares.
  - Comparação: Este escalonamento melhora o escalonamento do QAOA de $O(1.46^N)$ e é marginalmente melhor que o escalonamento do estado da arte da Busca Tabu de $O(1.34^N)$ (para instâncias pares) e $O(1.409^N)$ (para instâncias ímpares).
- Os resultados indicam uma vantagem de lei de potência da PCE sobre as bases clássicas dentro do intervalo testado.
Demonstração Experimental (IonQ Forte):
- Os autores realizaram uma demonstração de prova de conceito no processador quântico IonQ Forte para um tamanho de instância de $N=120$ , o maior demonstrado até o momento em hardware quântico.
- Para o experimento, foi utilizado um conjunto específico de correladores de corpo- $k$ ( $k=2$ ) amigáveis ao hardware, exigindo apenas três configurações de medição.
- Resiliência ao Ruído: O estudo descobriu que, embora o ruído de disparos (shot noise) tenha tido um impacto menor (exigindo apenas alguns milhares de disparos), o ruído do hardware degradou significativamente a qualidade da solução final. No entanto, o processo de treinamento em si permaneceu robusto, sugerindo que a mitigação de erros ou taxas de compressão mais altas são críticas para a implantação em regime NISQ.

Significância e Alegações
O artigo afirma que os solucionadores baseados em PCE representam uma abordagem promissora para duas vias distintas:

Heurísticas Clássicas Inspiradas em Computação Quântica: Mesmo quando simulados classicamente, o framework PCE oferece escalonamento competitivo ou superior em comparação com as principais heurísticas clássicas para problemas difíceis como LABS, atuando como um poderoso algoritmo inspirado em computação quântica.
Redução de Recursos NISQ: Ao codificar $N$ variáveis em um número de qubits polinomialmente menor ( $n$ ), a PCE reduz drasticamente os requisitos de qubits para dispositivos de curto prazo. Os autores observam que $n=8$ qubits poderia, teoricamente, lidar com instâncias de até $N=66$ (onde soluções exatas são conhecidas), e $n \le 20$ poderia desafiar as maiores instâncias solucionáveis por heurísticas clássicas.

Os autores mantêm uma postura modesta em relação à "vantagem quântica". Eles reconhecem que o custo de simular vetores de estado quântico completos em benchmarks clássicos atrasa o ponto de cruzamento onde uma verdadeira vantagem de tempo de execução quântica se torna evidente. Além disso, notam que, embora o método mostre um forte desempenho, ele carece atualmente de garantias de desempenho. No entanto, a capacidade de resolver instâncias de $N=120$ no hardware atual com orçamentos de disparos modestos e a observação da resiliência ao ruído destacam o potencial da PCE como uma ferramenta para reduzir os requisitos de recursos em algoritmos quânticos reais.