Recozimentos quânticos e o futuro da fatoração primária

Pesquisadores da Universidade de Trento, Itália, desenvolveram uma nova abordagem para fatoração primária por meio de recozimento quântico, aproveitando um paradigma de codificação modular compacto e permitindo a fatoração de grandes números usando dispositivos quânticos D-Wave.

A fatoração primária é o procedimento de decompor um número em seus componentes primos. Todo número inteiro maior que um pode ser expresso exclusivamente como um produto de números primos.

Na criptografia, a fatoração primária tem particular importância devido à sua relevância para a segurança dos algoritmos de criptografia, como o sistema criptográfico RSA amplamente utilizado.

O processo de fatoração em primos torna-se desafiador devido à natureza dos números primos, e fica ainda mais complicado à medida que os números sendo fatorados se tornam maiores, levando a um vasto número de possibilidades a serem consideradas.

A impraticabilidade de fatorar grandes números com eficiência garante a integridade da comunicação criptografada. A robustez destes sistemas criptográficos depende da complexidade computacional da factorização primária, tornando-a uma componente crucial na salvaguarda de informação sensível na era digital.

Se alguém puder fatorar com eficiência o produto de dois grandes números primos, poderá quebrar a segurança dos sistemas criptográficos. A compreensão e o avanço das técnicas de fatoração primária contribuem para garantir a robustez dos protocolos criptográficos e proteger informações confidenciais na comunicação digital.

Em um novo estudo publicado em Relatórios Científicos, pesquisadores liderados pelo Prof. Roberto Sebastiani, da Universidade de Trento, Itália, tiveram como objetivo abordar esse processo usando recozedores quânticos. A equipe também era composta por Jingwen Ding e Giuseppe Spallitta, Ph.D. estudantes da Universidade de Trento.

“Como um cientista da computação que passou uma carreira inteira desenvolvendo procedimentos clássicos para resolver problemas lógicos e computacionalmente difíceis, problemas de otimizaçãofiquei muito intrigado em lidar com uma tecnologia como o recozimento quântico baseado em um paradigma de computação diferente de tudo que eu havia encontrado antes”, disse o professor Sebastiani ao Tech Xplore.

Recozimentos quânticos

Os computadores quânticos são especialmente adequados para problemas de fatoração primária devido à sua capacidade de realizar cálculos paralelos e explorar fenômenos quânticos. Especificamente, os recozidores quânticos, como os da D-Wave, são projetados para resolver problemas de otimização, buscando soluções ideais entre um vasto número de possibilidades simultaneamente.

No contexto da fatoração primária, onde encontrar os fatores primos envolve explorar rapidamente inúmeras combinações, o paralelismo inerente da computação quântica oferece uma vantagem potencial.

Os recozedores quânticos aproveitam fenômenos quânticos como superposição quântica e tunelamento quântico para explorar múltiplas soluções simultaneamente, tornando-os adequados para problemas de fatoração primária. Esta exploração paralela de possibilidades pode aumentar significativamente a eficiência da busca por fatores primos em comparação com algoritmos clássicos.

Codificação compacta

A pesquisa tem dupla natureza. No primeiro aspecto de seu trabalho, os pesquisadores alcançaram um avanço ao desenvolver uma codificação modular compacta de um circuito multiplicador binário de 21 × 12 bits diretamente em um único módulo de 8 qubit dentro da topologia Pegasus dos recozedores quânticos da D-Wave.

Pense na topologia Pegasus como uma web conectando qubits, determinando como os dados fluem.

“A virada de jogo neste trabalho – que foi uma surpresa positiva para nós – foi a codificação bem-sucedida de um subcircuito de somador completo controlado (CFA) em um único módulo de 8 qubit da topologia Pegasus Quantum Annealer, “explicou Prof.Sebastiani.

CFA é um subcircuito quântico que executa operações de adição de 1 bit sob condições de controle específicas, que a equipe codificou em um módulo da topologia do recozimento usando Teorias do Módulo de Otimização (OMT), uma tecnologia que combina raciocínio lógico e otimização.

Ao contrário das abordagens anteriores que ignoravam o layout do sistema, a equipe utilizou OptiMathSAT, sua ferramenta Optimization Modulo Theories, para criar uma codificação bem consciente da topologia. Isto demonstrou a eficiência de sua abordagem e marcou um avanço significativo nas técnicas de codificação para recozimento quântico.

A modularidade de sua abordagem de codificação é uma virada de jogo. Eles demonstraram a capacidade de codificar no recozedor a fatoração de até o número 8.587.833.345 no produto de dois números primos, 2.097.151 e 4.095. Isto marca o maior problema de fatoração já codificado em um recozimento quântico usando seu novo método.

“Observamos dois fatos importantes. Podemos decompor um circuito multiplicador de n × m bits em uma matriz de subcircuitos CFA interconectados e podemos alinhá-lo com a rede Pegasus de módulos de 8 qubits”, explicou o Prof.

Isso permitiu que os pesquisadores criassem uma estrutura que pode ser dimensionada sem esforço com o crescimento dos números de qubit em futuros chips de recozimento quântico.

Recozimentos quânticos e o futuro

Fatoração experimental

Na segunda fase de sua pesquisa, a equipe conduziu uma extensa avaliação experimental em um recozimento quântico D-Wave Advantage 4.1. O objetivo era investigar a solução real de problemas de FP codificados e avaliar as capacidades do recozimento quântico na prática.

“No geral, devido a qubits defeituosos e recursos limitados de tempo QUPU, 8.219.999 = 32.749 × 251 foi o produto principal mais alto que conseguimos fatorar. Até onde sabemos, este é o maior número já fatorado empregando um dispositivo quântico sem depender em busca externa ou procedimentos de pré-processamento executados em computadores clássicos”, explicou o Prof. Sebastiani.

A conquista tem implicações significativas para a computação quântica e suas aplicações. Os pesquisadores demonstraram progresso na resolução de problemas computacionais complexos, provando que avanços substanciais são possíveis mesmo com as limitações do atual hardware de recozimento quântico.

Um dos desafios deste trabalho é que com cada problema de fatoração primária tendo no máximo duas soluções (por exemplo, 35=7×5 ou 35=5×7), o recozimento quântico precisa procurar por esses mínimos globais em uma solução exponencialmente vasta. espaço.

O professor Sebastiani elaborou: “Isso é como encontrar uma agulha em um palheiro. Felizmente, muitas técnicas e truques de recozimento estão disponíveis para lidar com esses problemas, mas foi necessária muita prática para obter resultados satisfatórios.”

Além da fatoração

O professor Sebastiani enfatizou o potencial para estender o uso desses dispositivos além da fatoração primária, prevendo aplicações na codificação e verificação da satisfatibilidade de vários circuitos.

“Acreditamos que recozedores quânticos podem ser usados ​​para codificar e verificar a satisfatibilidade de muitos outros circuitos de interesse. Abordando assim a satisfatibilidade proposicional de circuitos booleanos (SAT) – um problema muito mais geral do que a fatoração primária e permite representar uma variedade de reais -problemas mundiais”, compartilhou o Prof. Sebastiani.

Olhando para o futuro, os pesquisadores enfatizaram a importância do desenvolvimento de procedimentos híbridos quânticos-clássicos, onde o recozimento pode ser invocado por procedimentos clássicos para resolver subproblemas combinatórios pequenos, mas computacionalmente muito difíceis.

No entanto, é crucial notar que, apesar das conquistas notáveis ​​apresentadas no seu artigo, os investigadores são cautelosos quanto às limitações. Eles enfatizam que ainda estão longe de resolver problemas de fatoração de primos significativos o suficiente para comprometer a segurança dos sistemas criptográficos atuais.

© 2024 Science X Network