From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

Este artigo apresenta uma comparação experimental dos algoritmos de fatoração quântica de Shor e de Regev em hardware NISQ real para N=15, analisando como suas distintas abordagens estruturais de codificação aritmética interagem com o ruído do dispositivo e as limitações de amostragem para informar o benchmarking prático de estratégias de fatoração alternativas.

O essencial

O Panorama Geral: Duas Maneiras Diferentes de Quebrar um Código

Imagine que você está tentando decifrar um código secreto (fatoração de um número) usando um novo tipo de supercomputador chamado Computador Quântico. Por muito tempo, todos têm usado um método específico para fazer isso, inventado por um matemático chamado Shor. É como a receita "padrão ouro" para quebrar o código.

No entanto, os computadores quânticos atuais são como cozinhas "barulhentas". Eles são pequenos, cometem erros e se confundem facilmente. Por causa disso, os cientistas estão procurando por receitas alternativas que possam funcionar melhor nessas condições bagunçadas. Uma dessas novas receitas foi inventada por um matemático chamado Regev.

Este artigo é um experimento onde os autores prepararam ambas as receitas (a de Shor e a de Regev) em computadores quânticos reais e barulhentos para ver qual delas lida melhor com o "ruído". Eles não tentaram quebrar um código massivo e real (o que levaria anos); em vez disso, quebraram um número pequeno e fácil (15) apenas para ver como os dois métodos se comportavam.

As Duas Receitas: Uma "Lanterna" vs. Um "Mapa Nebuloso"

Para entender a diferença, imagine que você está tentando encontrar um tesouro escondido em um quarto escuro.

1. O Algoritmo de Shor: A Lanterna

• Como funciona: O método de Shor tenta projetar uma lanterna muito brilhante e nítida sobre o tesouro. Ele concentra toda a sua energia em um ou dois pontos específicos (picos). Se a luz for forte o suficiente, você vê o tesouro imediatamente.
• O Problema: Em uma cozinha barulhenta, a lanterna pisca. Se a luz ficar muito fraca ou trêmula, você não consegue mais dizer onde o tesouro está. O "pico nítido" fica borrado e o sinal se perde.
• A Descoberta do Artigo: No computador da IBM (que era ligeiramente menos barulhento), a lanterna ainda funcionava bem. Mas no computador da QMIO (que era mais barulhento), a luz ficou tão borrada que eles não conseguiram encontrar o tesouro.

2. O Algoritmo de Regev: O Mapa Nebuloso

• Como funciona: O método de Regev não usa uma única lanterna. Em vez disso, ele lança um monte de linhas pontilhadas em um mapa. Nenhum ponto individual aponta diretamente para o tesouro, mas se você olhar para o padrão de todos os pontos juntos, eles formam uma forma que revela a localização. Ele espalha a informação por muitos pontos.
• O Problema: Em uma cozinha barulhenta, a neblina fica mais espessa. Os pontos no mapa ficam espalhados e misturados. Como a informação é distribuída, fica mais difícil ver o padrão quando o ruído interfere.
• A Descoberta do Artigo: O método de Regev criou uma distribuição de pontos mais "plana". No computador barulhento da QMIO, os pontos ficaram tão espalhados que o padrão desapareceu completamente.

O Experimento: O Que Aconteceu?

Os pesquisadores executaram ambas as "receitas" em dois computadores quânticos diferentes (IBM e QMIO) e os compararam com uma simulação perfeita e sem ruído.

• O Mundo "Ideal": Em uma simulação perfeita, o método de Shor mostrou alguns picos muito altos e nítidos (a lanterna). O método de Regev mostrou alguns pontos ligeiramente mais altos espalhados em um padrão (o mapa). Ambos funcionaram perfeitamente.
• O Mundo "Real" (IBM):
  • Shor: Os picos ficaram um pouco mais largos e baixos, mas ainda era possível vê-los. A "lanterna" estava trêmula, mas visível.
  • Regev: Os pontos ficaram mais espalhados, mas alguns ainda estavam ligeiramente mais altos que os outros. O "mapa" estava nebuloso, mas o padrão ainda estava fracamente presente.
• O Mundo "Real" (QMIO - A Máquina Mais Barulhenta):
  • Shor: Os picos achataram-se completamente. A lanterna apagou. O computador não conseguiu distinguir o sinal do ruído.
  • Regev: Os pontos tornaram-se uma nuvem uniforme. O padrão desapareceu por completo. O "mapa" estava tão nebuloso que parecia estática aleatória.

A Conclusão Principal

O artigo conclui que nenhum dos métodos é claramente "melhor" agora para essas máquinas pequenas e barulhentas.

• O método de Shor é como uma ferramenta de alta precisão: funciona muito bem se o ambiente estiver limpo, mas quebra facilmente se houver até mesmo um pouco de sujeira (ruído).
• O método de Regev é como uma rede distribuída: ele utiliza circuitos mais rasos (etapas menos complexas), o que parece bom, mas como ele espalha sua informação, o ruído embaralha o padrão de forma tão eficaz quanto embaralha a lanterna.

O Ponto Central:
Os autores descobriram que a maneira como esses algoritmos armazenam a informação é fundamentalmente diferente. Shor "concentra" a informação (como um laser), enquanto Regev a "distribui" (como um spray). Nos computadores barulhentos de hoje, ambas as estratégias lutam, mas elas falham de maneiras diferentes. Shor perde seu foco nítido, enquanto Regev perde seu padrão geométrico.

Este estudo não diz que podemos quebrar códigos bancários reais ainda. Em vez disso, ele nos diz que, à medida que construímos melhores computadores quânticos, precisamos entender como esses diferentes algoritmos reagem ao ruído, para que possamos escolher o certo para a máquina certa.

Resumo técnico

Resumo Técnico: Da Busca de Período à Amostragem de Rede

Enunciado do Problema
Embora o algoritmo de Shor resolva teoricamente a fatoração de inteiros em tempo polinomial, sua implementação prática em hardware atual de Escala Intermediária com Ruído (NISQ) é severamente limitada pela profundidade do circuito, erros de porta e decoerência. Essas limitações impulsionaram o interesse em algoritmos de fatoração alternativos, como o algoritmo de Regev, que reformula o problema como uma tarefa de amostragem de rede de alta dimensão, em vez de um problema de busca de período unidimensional. No entanto, análises experimentais existentes muitas vezes carecem de comparações sistemáticas entre múltiplos backends sob condições rigidamente controladas para entender como essas distintas estruturas algorítmicas interagem com o ruído realista do hardware. Este estudo aborda essa lacuna ao comparar experimentalmente os algoritmos de Shor e de Regev em hardware quântico real para caracterizar sua robustez relativa e modos de falha.

Metodologia
Os autores conduziram um estudo experimental controlado utilizando a instância de referência $N = 15$. Ambos os algoritmos foram implementados usando Qiskit e executados em dois backends quânticos distintos: o computador quântico QMIO no Centro de Supercomputación de Galicia (CESGA) e um processador quântico de acesso aberto da IBM (ibm_torino). Simulações ideais (sem ruído) serviram como uma linha de base de referência.

• Configuração do Algoritmo:
  • Algoritmo de Shor: Utilizou a base $a=2$ com um registro de controle de $k=3$ qubits para encontrar o período $r=4$. O circuito utilizou construções de exponenciação modular especializada e rasa baseada em permutações, em vez de aritmética genérica, para minimizar a profundidade.
  • Algoritmo de Regev: Configurado como uma instância bidimensional ($d=2$) com bases $a_1=4, a_2=49$. Empregou uma superposição Gaussiana sobre $\mathbb{Z}^d$ seguida de amostragem de Fourier para aproximar vetores na rede dual.
• Compilação e Execução: Os circuitos foram transpilados usando Qiskit com parâmetros ajustados para os conjuntos de portas nativas e conectividade de cada backend. Todas as execuções de hardware utilizaram 4.096 shots.
• Métricas de Avaliação: Para quantificar o impacto do ruído sem depender de uma reconstrução clássica completa para cada execução, os autores introduziram métricas baseadas em distribuição:
  • Entropia de Shannon ($H(p)$): Mede a dispersão da distribuição de probabilidade.
  • Tamanho de Suporte Efetivo ($N_{eff}$): Estima o número de resultados que contribuem significativamente para a distribuição.
  • Massa Top-K ($M_4$): A fração da probabilidade total contida nos quatro resultados mais frequentes.

Principais Contribuições

1. Benchmark Experimental Controlado: O artigo fornece uma comparação direta e de baixo nível dos algoritmos de Shor e de Regev na mesma instância de problema ($N=15$) através de múltiplas plataformas de hardware e simulações ideais.
2. Avaliação Multi-Backend: Os resultados são reportados tanto para dispositivos IBM quanto QMIO, oferecendo insights sobre como diferentes arquiteturas de hardware afetam o desempenho algorítmico.
3. Interpretação da Codificação de Informação: O estudo interpreta os resultados experimentais através da lente de "concentração de informação" (Shor) versus "distribuição de informação" (Regev). Demonstra como essas diferenças estruturais levam a degradações induzidas por ruído qualitativamente distintas nos histogramas de medição.
4. Reprodutibilidade: Os autores reportam os parâmetros algorítmicos específicos e os pipelines de compilação utilizados para gerar as distribuições experimentais.

Resultos
Os dados experimentais revelam modos de falha distintos para os dois algoritmos sob restrições NISQ:

• Algoritmo de Shor (Concentração de Informação):

  • Em simulações ideais, a massa de probabilidade é altamente concentrada em um pequeno número de picos espectrais (baixa entropia, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • No hardware IBM, a distribuição se alarga, mas retém picos dominantes ($M_4 = 0.921$), permitindo o sucesso parcial na recuperação do período.
  • No dispositivo QMIO, que é mais ruidoso, os picos espectrais são significativamente achatados e obscurecidos ($M_4 = 0.564$, $N_{eff} \approx 7.8$), levando à perda da estrutura periódica necessária para a reconstrução clássica.
  • Observação: O algoritmo de Shor é altamente sensível a erros de fase; uma vez que os picos nítidos são alargados pelo ruído, o algoritmo falha em fornecer informações úteis.

• Algoritmo de Regev (Distribuição de Informação):

  • Em simulações ideais, a distribuição é inerentemente mais dispersa que a de Shor, mas ainda exibe um subconjunto de vetores dominantes consistentes com a rede dual ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • No hardware IBM, a distribuição torna-se mais espalhada ($M_4 = 0.645$), mas um subconjunto de resultados permanece dominante o suficiente para potencialmente suportar a redução de rede.
  • No QMIO, o sinal geométrico é fortemente diluído ($M_4 = 0.29$, $N_{eff} \approx 15.8$), com a massa de probabilidade espalhando-se uniformemente por muitos vetores, obscurecendo efetivamente a estrutura da rede.
  • Observação: O algoritmo de Regev depende de viés estatístico através de múltiplas amostras correlacionadas. Embora utilize circuitos mais rasos (a Tabela 2 mostra que a profundidade compilada de Regev é menor que a de Shor em ambas as plataformas), a etapa de amostragem multidimensional introduz uma sensibilidade ao ruído que causa a rápida dispersão do sinal geomético.

• Profundidade de Circuito vs. Robustez: Apesar de o algoritmo de Regev possuir uma profundidade de circuito compilado mais rasa (ex: 147 vs. 210 no IBM), essa redução não se traduziu em robustez superior no hardware atual. As distribuições de medição de Regev dispersaram-se mais rapidamente sob ruído em comparação com as de Shor.

Significância e Alegações
O artigo alega modestamente que nenhum dos algoritmos demonstra uma vantagem prática sobre o outro no regime de $N$ pequeno ($N=15$) nos dispositivos NISQ atuais. Em vez disso, o estudo destaca um compromisso fundamental:

• O algoritmo de Shor beneficia-se de saídas altamente estruturadas e concentradas quando o ruído é baixo, mas falha catastroficamente quando a coerência de fase é perdida.
• O algoritmo de Regev distribui a informação através de um espaço de maior dimensão, o que pode oferecer propriedades de escala diferentes para problemas maiores, mas atualmente sofre de maior sensibilidade ao ruído na amostragem multidimensional.

Os autores concluem que estes resultados reforçam o valor do benchmarking experimental para compreender as implicações práticas das escolhas de design algorítmico. Eles enfatizam que as relações assintóticas no cenário tolerante a falhas não garantem comportamentos semelhantes no hardware NISQ, onde a codificação específica da informação aritmética (concentração vs. distribuição) dita como o ruído se manifesta e como os algoritmos falham. Propõe-se que trabalhos futuros estendam esses benchmarks para $N$ maiores e explorem estratégias de mitigação de erro direcionadas a esses compromissos específicos.