Kvantesimulator tilbyder hurtigere rute til primfaktorisering

At indregne meget store tal i deres primære "byggeklodser" er ekstremt vanskeligt for klassiske computere, og denne vanskelighed ligger til grund for sikkerheden i mange kryptografiske algoritmer. Selvom det er nemt at faktorisere tallet 20 som produktet af primtallene 2 x 2 x 5, for eksempel, Faktorering af større tal bliver eksponentielt vanskeligere, når man bruger klassiske factoring-algoritmer.

I et nyt blad udgivet i Fysisk gennemgang A , fysikerne Jose Luis Rosales og Vicente Martin har udviklet en metode, der kan gøre det meget nemmere at faktorisere meget store tal, der vides at have præcis to primfaktorer. Den nye metode bestemmer sandsynligheden for, at ethvert primtal er en af ​​de to primfaktorer for et givet tal. Efter at have bestemt disse odds, de mest sandsynlige primfaktorkandidater kan testes først, gør det muligt at identificere de primære faktorer meget hurtigere end før.

"Teorien viser ikke kun, hvor primtallene er placeret, men også sandsynligheden for, at et primtal er en faktor af et givet tal, " fortalte Rosales Phys.org . "Selvfølgelig, dette har implikationer i kryptografi, fordi [kryptosystemet] RSA ignorerer denne regelmæssighed."

En af de interessante ting ved den nye metode er, at den ikke bruger nogen form for computer, enten klassisk eller kvante. I stedet involverer det et fysisk kvantesystem - en "kvantesimulator" - der, når den er kodet med tallet til faktor, udviser en sandsynlighedsfordeling af energiværdier, der svarer til sandsynlighedsfordelingen af ​​primfaktorkandidaterne for det kodede tal.

"Vores mål er at udvikle en ny kvanteteori om faktoriseringsproblemet ved hjælp af en kvantesimulator, " sagde Rosales. "Vores tilgang har opdaget en ejendom uden klassisk analogi i talteori. Hvert primtal, der løser problemet, omarrangerer sig selv for at danne et regulært mønster:kvantesimulatorens båndspektrum."

Den generelle idé bag kvantesimulatoren er noget, der kaldes "faktoriseringsensemblet, " som forskerne introducerede tidligere. Det er baseret på ideen om, at primtallene er ordnet fra mindst til størst (f.eks. 2 er det første primtal, 3 er det andet primtal, og 101 er den 26 ^th prime). Det er også muligt at tage kvadratroden af ​​ethvert tal, og sammenlign derefter resultatet med det nærmeste primtal. For eksempel, kvadratroden af ​​27 er lidt mere end 5, hvilket er det tredje primtal. Ved definitionen af ​​et faktoriseringsensemble, det betyder, at 27 tilhører faktoriseringsensemblet af 3.

Fysikerne viste derefter, at de kunne transformere faktoriseringsensemblefunktionen til en funktion fra kvantefysikken (den omvendte harmoniske-oscillatorfunktion). Efter mange flere trin, de viste til sidst, at det forudsagte energispektrum for et kvantesystem svarer til fordelingen af ​​primtal i et tals faktoriseringsensemble. Ud fra disse oplysninger, forskerne kan bestemme sandsynligheden for, at et primtal er en faktor af dette tal. For at teste validiteten af ​​deres metode, fysikerne testede visse tal og sammenlignede deres resultater med de faktiske fordelinger opnået ved hjælp af primtalstabeller, og fandt meget lignende fordelinger.

Fysikerne demonstrerede teoretisk, at den foreslåede kvantesimulator kan faktorisere tal, der er mange størrelsesordener større end dem, der er blevet indregnet med kvantecomputere. I deres papir, de rapporterer resultaterne af at bruge deres metode til at bestemme sandsynlighedsfordelingen af ​​primfaktorerne for et tal med 24 cifre. Yderligere, metoden gør dette med langt færre ressourcer end krævet af klassiske factoring-algoritmer.

"I kvanteteorien, den algoritmiske kompleksitet er kun polynomium med antallet af bits af det tal, der skal faktoriseres, " sagde Rosales. "Faktisk, vores første resultater ser ud til at bekræfte, at simulatoren kun kræver (log√N) ³ kvantetilstande til at reproducere dets spektrum af energier, et meget opmuntrende resultat."

Et sidste punkt af interesse er, at den nye metode har stærke forbindelser til Riemann-hypotesen, hvilken, hvis sandt, ville antyde, at primtallene er fordelt på en forudsigelig måde - på samme måde som fordelingen af ​​nullerne i Riemann-zeta-funktionen. At bevise (eller modbevise) Riemann-hypotesen er et af de største uløste problemer i matematik, og et af Clay Mathematics Institutes Millennium Prize-opgaver.

"Primtallene burde opføre sig som kvantetal, hvis Hilbert-Polyas formodning gælder, " sagde Rosales, med henvisning til den mangeårige tilgang til at bevise Riemann-hypotesen.

Fremadrettet, forskerne arbejder i øjeblikket på den eksperimentelle implementering af kvantesimulatoren ved at bruge to sammenfiltrede partikler i en Penning-fælde.

"Den fuldstændige kvantebehandling af simulatoren ville kræve kvanteoptisk analyse af interaktionerne mellem fotoner og to (eller flere) sammenfiltrede ioner i en Penning-fælde, " sagde Rosales. "Denne del af programmet er endnu under udvikling. Målet er eksperimentelt at bygge en kvantefaktoreringssimulator. Hvis implementeret med succes, tal mange størrelsesordener større end dem, der er tilgængelige for dets kvantebehandling ved hjælp af Shor's algoritme, vil blive faktoriseret og, som et biprodukt, Hilbert-Polya-formodningen vil blive testet eksperimentelt."

© 2018 Phys.org