Kvantfysik tilbyder en ny måde at faktor tal på

(Phys.org) - Ethvert nummer kan, i teorien, skrives som et produkt af primtal. For små tal, dette er let (f.eks. hovedfaktorerne 12 er 2, 2, og 3), men for et stort antal, primfaktorisering bliver ekstremt vanskelig - så vanskelig, at mange af nutidens kryptografialgoritmer stoler på kompleksiteten af ​​primfaktoriseringen af ​​tal med hundredvis af cifre for at holde private oplysninger sikre.

Imidlertid, ingen er helt sikker på, hvor svært det er at nedbryde meget store tal til deres primære faktorer. Dette spørgsmål, kaldet faktoriseringsproblemet, er et af de største uløste problemer inden for datalogi, trods brugen af ​​avancerede matematiske og datalogiske strategier i forsøg på at løse det.

Nu i en ny undersøgelse offentliggjort i Fysisk gennemgangsbreve , forskerne Jose Luis Rosales og Vicente Martin ved det tekniske universitet i Madrid har taget en anden tilgang til problemet.

Forskerne har vist, at den aritmetik, der bruges til at indregne tal i deres primære faktorer, kan oversættes til fysikken i en enhed - en "kvantesimulator" - der fysisk efterligner aritmetikken frem for direkte at forsøge at beregne en løsning, som en computer gør.

Selvom forskerne endnu ikke har bygget en kvantesimulator, de viser, at hovedfaktorerne for store tal svarer til simulatorens energiværdier. Måling af energiværdierne ville derefter give løsningerne på et givet factoring -problem, tyder på, at indregning af store tal i primtal måske ikke er så svært som i øjeblikket antages.

"Arbejdet åbner en ny vej til faktor tal, men vi ved endnu ikke om dens magt, "Fortalte Rosales Phys.org . "Det er meget slående at finde en helt ny måde at faktorere, der kommer direkte fra kvantefysik. Det viser ikke, at factoring tal er let, men at finde nye måder at faktorisere øger bestemt ikke styrken af ​​algoritmer baseret på den formodede kompleksitet. "

For nu, forskerne kender ikke den tekniske kompleksitet ved at bygge sådan en enhed, eller om det overhovedet ville være muligt at faktorere meget store tal.

"Vi har vist, at der findes en kvantesimulator, der kan faktorere tal, og i princippet, det kunne bygges, "Sagde Martin." Om simulatoren er mulig med den nuværende teknologi på en måde, så den kan faktorere tal af samme størrelse som dem, der blev brugt i kryptografi, skal vi se, men alléen er nu åben. Udsigten til at bygge sådan en enhed, før der bygges en kvantecomputer, er noget, der skal overvejes alvorligt. "

Mod en kvantetalsteori

Udover potentialet for praktiske anvendelser, resultaterne er også interessante på et mere grundlæggende plan.

"Efter vores mening, papirets bidrag har to sider:i ren matematik og i anvendt kryptografi, "Sagde Rosales.

Et af de mest matematisk interessante aspekter af det nye værk er, at det indebærer en omdefinering af faktoriseringsproblemet ved at indføre en ny aritmetisk funktion, der derefter kan kortlægges på kvantesimulatorens fysik og svare til energiværdierne. I en vis forstand, forskerne omskriver det matematiske problem med hensyn til fysik.

"Manuskriptet forsøger at bygge bro mellem talteori og kvantefysik, "Sagde Rosales, bemærker, at forskere har forsøgt at gøre dette i flere årtier. "I dag med udviklingen af ​​kvanteinformation og beregning og opdagelsen af ​​Shors algoritme, forbindelsen virker mere spændende og vigtig end nogensinde. "

På lang sigt, denne type undersøgelse kan i sidste ende føre til en kvantetalsteori - en teori om tal, der er baseret på fysiske kvantesystemer.

"For at udvikle en kvantetalsteori, hvad vi har brug for er et kvantesystem (i det mindste et teoretisk) for at kunne gengive primtalene, "Sagde Martin." I avisen, vores mening var at forsøge at få et system, der kunne faktorisere et tal i dets primtal. Metoden er 'analog' i den forstand, at den ikke ligner Shors algoritme, som er programmerbar i en kvantecomputer efter portmodellen. I stedet, det er målingen af ​​et omhyggeligt indstillet kvantesystem, der giver svaret.

"For at gennemføre dette program, vi skal først udtænke en aritmetisk formulering af faktoriseringsproblemet, der kan kvantificeres. Vi skal finde en aritmetisk funktion, til sidst relateret til en Hamilton, og opsæt det kvantemekaniske problem, så dets løsning svarer til løsningen af ​​faktoriseringsproblemet. I arbejdet lykkedes det os at gennemføre disse ideer. Vi fandt den korrekte aritmetiske funktion, definerede faktoriseringssættet til at binde Hamiltonian og opnåede løsningen af ​​det kvantemekaniske problem. Så vidt vi ved, dette er ikke opnået før, selvom vores ikke var det første forsøg.

"Som det altid gøres inden for fysik, for at validere resultaterne, vi er nødt til at bevise dets forudsigelige evner, så vi gjorde forudsigelser med dem:opnåede en faktoriseringsalgoritme, der er helt ny, uden lighed med nogen anden faktoriseringsalgoritme, som vi kender til, og kontrollerede grundigt løsningens statistik i forhold til primtaletningen.

"Resultaterne gjorde os virkelig forbløffede. For at demonstrere dette, i papiret viser vi, hvordan spektret gengiver primtællingsfunktionen og er næsten identisk med Riemann's. Dette opnås som en direkte konsekvens af den kvantemekaniske teori og har ingen modpart i talteori. Bære dette til det ekstreme, dette kunne endda betragtes som den fysik, der ligger til grund for Riemann -hypotesen [et af de vigtigste åbne problemer i talteori] i den forstand, at hamiltoneren naturligt er afgrænset, uden yderligere antagelser. "

Forskerne forklarer, at i denne avis, de antydede bare, at resultaterne har dybere matematiske konsekvenser, og de planlægger at undersøge disse muligheder yderligere i fremtiden. De undersøger også, hvad det ville kræve at bygge en kvantesimulator.

"Vi har løbende forskning i teorien om at bygge en simulator, "Sagde Rosales." Det første indtryk er opmuntrende, selvom intet er besluttet endnu. "

© 2016 Phys.org