Shorren algoritmoa

Ordenagailu kuantikoak teknologikoki iraultzaileak (izango) direla esaten dugunean, honengatik da. Albisteetan Donostian instalatuko duten¹ ordenagailu kuantikoaren inguruan entzuten duzun aldiro, honengatik da. Erraldoi teknologikoek ordenagailu kuantikoen aldeko apustua egitearen atzean, hein handi batean, hau dago. Konputazio kuantikoaren algoritmo garrantzitsuena. La crème de la crème. Zuekin: Shorren algoritmoa.

Algoritmoak

Shorrenarekin hasi aurretik, orokorrean algoritmoetaz hitz egingo dugu.  Algoritmo hitzak, seguruenik Youtube, Instagram edo antzeko plataformek edukiak gomendatzeko erabiltzen duten sistema ekarriko dizue burura, edo adimen artifizalarekin lotutako zerbait agian. Bada algoritmo eta logaritmo hitzak nahasten dituenik ere. Baina funtsean algoritmoak oso gauza sinpleak dira: problema bat ebazteko eman beharreko pausuen deskribapen zehatz eta ordenatuak.

Ikus dezagun adibide bat:

Problema: Esan n zenbaki osoa lehena den edo ez

• Algoritmoa:

  1. Izan bedi m = 2.

  2. m=n betetzen bada, n lehena da. Bestela jarraitu hurrengo pausura.

  3. Kalkulatu n zati m.

  4. Hondarra 0 bada, n ez da lehena. Bestela, jarraitu hurrengo pausura.

  5. m aldagaiari gehitu 1 eta itzuli b) pausura.

Sinplea ezta? Pare bat ohar: Alde batetik, planteatutako problemak edozein n zenbaki oso barnebiltzen du eta proposatutako algoritmoak kasu guztietarako balio behar du. Adibidez, n=1312  zenbakia lehena den edo ez asmatzea gure problemaren instantzia bat besterik ez da.

Horrez gain, azpimarratzekoa da, n-ren balioaren baitan, algoritmoak emaitza aurkitzeko eman behar dituen pausu kopurua asko aldatzen dela. n bikoitia bada, iterazio bakarrean aurkituko du emaitza, baina  n zenbaki lehena bada, n-1 iterazio beharko ditu emaitzara heltzeko. Beraz, kasurik okerrenean, algoritmoak eman beharreko pausu kopurua n-ren tamainarekin handitzen da.

Azkenik, baliteke irakurle azkar hori ohartu izana proposatutako algoritmoa ez dela eraginkorrena. Izan ere, m aldagaiak n baino txikiagoak diren zenbaki lehenen balioak hartzearekin aski da. Horrela, algoritmoaren kasurik okerreneko pausu kopurua nabarmenki jaisten da. Honekin argitu nahi dudana honakoa da: problema bera ebazteko algoritmo anitz existitu daitezke, batzuk besteak baino azkarragoak, baina normalki, sarrerako zenbakiaren tamainaren baitakoa da eman beharreko pausu kopurua.

Konputazioaren zientzietan algoritmoen efizientzia konparatzeko konplexutasun konputazionala [1] erabiltzen da, hau da, problema bat ebazteko algoritmo batek behar duen baliabide kopurua (denbora edo memoria). Gehienetan, emaitza aurkitzeko eman beharreko pausu kopurua sarrerako zenbakiaren tamainarekin nola handitzen den aztertzen da. Honek balio konstante bat izan dezake, funtzio polinomikoa izan daiteke, logaritmikoa, exponentziala…

1.Irudia: konplexutasun konputazionala neurtzen duten funtzio klase batzuk. Iturria: esteka.

Hortaz, algoritmoen konplexutasuna aztertzerakoan ez da nahikoa problemaren instantzia jakin baterako behar den denbora kalkulatzea, tamainaren arabera denbora horren hazkuntza deskribatzen duen funtzio mota da aztertzen dena (Ikus 1. irudia).

Kriptografia apur bat

Atal honetan kriptografiaz, aritmetika modularraz eta RSA protokoloaz idatzi behar nuen, baina denon zorionerako, Mikel aurreratu zait eta nik egingo nukeena baino askoz argiago azaldu du dena honako artikuluan. Bertatik ideia hau berreskuratuko dut: Gaur egungo enkriptazio sistema erabilienak zenbaki osoen faktorizazioan oinarritzen du haren segurtasuna.

Hau da, demagun n zenbaki osoa bi zenbaki lehenen biderkadura dela: n=pq. Faktore lehen horiek aurkitzea oso lan zaila da ordenagailu klasikoentzat. Ez da ezinezkoa, baina denbora luzea behar dute. Zenbat? Ba, horretarako ezagutzen den algoritmo klasikorik azkarrenak denbora superpolinomiala behar du [2], edo hobeto ulertzeko, 1.irudiko grafikoan, kurba horiaren eta berdearen arteko funtzio bat irudikatuko luke. Gaur egun RSA sisteman erabiltzen diren giltzak 2048 bit-ekoak izaten dira, gutxi gorabehera 600 zifrako zenbakiak, eta algoritmo klasiko horren bitartez halako giltzak faktorizatzeak milioika urte hartuko lituzke. Hortaz, faktorizazio problema ebazten zaila den bitartean, enkriptazio sistema hau segurua dela esan dezakegu.

Faktorizazio kuantikoa

Bueno, iritsi da ordua, Shorren algoritmoarekin jarriko gara. Algoritmo honek bere egileari, Peter Shorri, zor dio izena eta 1994 urtean aurkeztu zen lehenengo aldiz [3]. Aurreko atalean azaldutako problema modu efizientean ebazten du, zenbaki oso baten faktore lehenak bilatzeko balio du alegia. Algoritmoa nahiko konplexua da, hainbat atal ditu eta hauetako bakoitza xehetasun guztiekin ulertzea nahiko lan zaila da. Irakurleak aspertu nahi ez ditudanez, algoritmoaren ideia orokorra azaltzen saiatuko naiz.

Algoritmo honek faktorizazio problema funtzio baten periodoa aurkitzeko probleman bilakatzen du eta azken hau da ebazten duena. Aritmetika modularrean a zenbaki oso baten M moduloko ordena (r>0) hurrengo erlazioa betetzen duen zenbakirik txikienari deitzen zaio: 

Hau da, r ordenak esaten digu zenbat aldiz biderkatu behar den zenbaki hori bere buruarekin, 1 hondarra eduki dezan M tamainako modulu batean. Baliteke a zenbakiak ez edukitzea ekuazio hori betetzen duen  r baliorik, eta kasu horretan, ordena infinitua dela esaten da. Ordena hau bilatzea oso erabilgarria da, bikoitia bada², honako adierazpena lor baidezakegu [4]:

Ordena ezaguna bada, p eta q zenbakien biderkadura M zenbakiaren multiploa izango da. Beraz, edo p eta q M zenbakiaren faktore lehenak dira, edo gutxienez bietako bat faktore lehen baten multiploa da. Bigarren kasu horretan segituan aurkitu dezakegu faktore hori, p edo q zenbakiek M-rekin duten zatitzaile komun handiena (ZKH) bilatuz.

Orain, demagun honako funtzioa definitzen dugula:

Funtzio honek a zenbakia bere buruarekin k aldiz biderkatuta, M tamainako modulan duen hondarra itzultzen du. Funtzio hau periodikoa izango da, a zenbakiak r ordena finitua badu:

Hau guztia azalduta, Shorren algoritmoak honakoa proposatzen du:

• Problema: Aurkitu M zenbakiaren faktore lehenak

• Algoritmoa:

  1. Aukeratu a zenbaki osoa ausaz.

  2. Ordenagailu kuantiko baten bitartez kalkulatu f(k) funtzioaren periodoa

  3. Periodoa finitua eta bikoitia bada, faktore lehenak bilatu ZKH bidez

  4. Bestela, itzuli a) pausura.

Beraz, b) pausua soilik da ordenagailu kuantiko batek burutzen duena, baina algoritmo osoaren zatirik zailena da. Periodo hori aurkitzeko, fasearen estimazio kuantikoa [5] deituriko prozedura erabili ohi da. Ikus dezagun ze forma hartzen duen hori burutzen duen zirkuitu kuantikoak:

2. irudia: Shorren algoritmoan periodoaren estimaziorako zirkuitu kuantikoaren eskema. Iturria: Wikipedia

Zirkuitu honek hainbat atal ditu: Hasteko, qubit guztiak bi multzo edo erregistrotan banatzen dira; lehen erregistroan |0> egoeran hasieratutako qubitak izango ditugu eta bigarren erregistroan |1> egoeran hasieratutakoak. Ondoren, lehen erregistroko qubitak gainezarmen ekiprobablean jarriko ditugu Hadamard ateen bidez. Segidan, kontrolatutako hainbat ate aplikatuko dira. Xehetasunetan sartu gabe, eta intuizioa garatzeko, demagun k egoeren gainezarmena sortu dugula lehenengo erregistroan. Orduan, ate kontrolatu horien bitartez, egoera horietako bakoitzari f(k) funtzioa aplikatzea lortuko dugu, non f(k) aurretiaz definitu dudan funtzioa den.

Amaitzeko, QFT deituriko operazio bat aplikatzen da. Operazio hau Fourierren Transformatu Kuantikoa da eta existitzen den algoritmo klasiko garrantzitsuenetariko baten bertsio kuantikoa da; hain garrantzitsua non nire hurrengo artikulua hari buruz idatziko dudan! Operazio honek zirkuitu kuantikoan honako papera jokatzen du: gainezarmen ekiprobablean dauden f(k) egoera ezberdinen probabilitateak eraldatzen ditu, neurketaren ondorengo emaitza f(k) funtzioaren periodoarekin zuzenki lotuta egon dadin.

Baliteke honezkero irakurlea nazkatu izana, eta onartzen dut, ez da ulertzeko batere erraza. Ni ere ez nago oso ziur ea ongi ulertzen dudan! Baina azken puntu bat bota nahiko nuke: Zirkuitu kuantiko honek egiten dituen pausuak ordenagailu klasiko batek ere egin ditzake, horretarako f(k) funtzioa k-ren hainbat baliotarako ebaluatu besterik ez du egin behar. Periodikotasuna ikusi ahal izateko, ordea, burutu beharreko ebaluazio kopurua izugarri handia izan daiteke, M giltza handia bada. Ordegailu kuantikoak aldiz, gainezarmena erabiliz, aldi berean ebaluatu dezake f(k) funtzioa k-ren balio guztietarako, eta Fourierren Transformatu Kuantikoaren bitartez, interferentzia probabilistikoak sor ditzakegu, neurketaren emaitza periodoari loturikoa izan dadin.

Egoeren gainezarmena eta interferentzia probabilistikoak. Fenomeno guztiz kuantikoak dira algoritmo hau funtzionarazten dutenak eta konputazio klasikoarekiko abantaila nabarmena ekartzen dutenak. 

Algoritmoaren praktikotasuna gaur egun

Orain arte algoritmoak egiten duenaren ideia orokor bat eraiki dugu, baina gutxi aipatu dugu zerren ongi egiten duen. Ikus hurrengo irudia konparaketa azkar bat egiteko:

3.Irudia: Algoritmo klasiko onenak (GNSF) eta Shorren algoritmoak faktorizazio problema ebazteko behar duten denbora, giltzaren tamainaren baitan. Iturria: Journal of Applied Physics.

Shorren algoritmoaren bitartez minutu gutxitan apur daitezke gaur egun erabiltzen diren RSA giltzak, eta hortaz, RSA ez da segurua ordenagailu kuantikoen erasoean aurrean. Baina, horrelakoa bada dakarren arriskua, zergatik jarraitzen da RSA erabiltzen? Kontua da Shorren algoritmoa ezin dela inplementatu gaur egungo ordenagailu kuantikoetan, eta arrazoi nagusiak bi dira:

1. Existitzen diren makina kuantikoek oraindik ez dituzte behar adina qubit.

2. Existitzen diren qubitak zaratatsuak³ dira eta qubit perfektuak behar ditugu algoritmoa inplementatzeko.

   
   

Izan ere, oso neurtuta daude faktorizazio algoritmo hau inplementatzeko behar diren baliabideak, izatez algoritmoa 1994 urtetik ezagutzen da. Adibidez, Google-n ikerkuntza talde bateko artikulu honek [6], 2048 biteko RSA giltza 8 ordutan faktorizatzeko miloi bat qubit behar direla dio. Baina tamalez (edo agian zorionez), oraingoz ditugun ordenagailu kuantiko handienek ehundaka qubit besterik ez dituzte. Oraindik badugu lana!

Hala ere, teknologia hau ikaragarri azkar ari da garatzen eta ordenagailu kuantikoen qubit kopurua urtetik urtera handitzen dabil. Baita qubit hauen kalitatea ere. Asko eztabaidatzen da Shorren algoritmoa inplementatzeko falta zaigun denboraren inguruan, baina gauza bat argi dago: denbora kontua da puntu horretara iristea. Gainera, nahiz eta oraindik ezin desenkriptatu, egunen batean RSA bitartez kodifikatutako mezuak irakurtzeko gai izango garela jakitea dagoeneko arrisku bat da, enkriptatuako mezuak gordetzen hasten bagara, etorkizunean sekretu guztiak azaleratu ahal ditzakegulako. Hori buruan izanda hobeto uler daiteke zer arrisku eta zer botere suposa dezakeen ordenagailu kuantiko bat kontrolpean edukitzeak. Horrela hobeto uler daiteke enpresa multinazional handiek eta potentzia mundial diren herrialdeek horrelako apostu estrategikoa egin izana teknologia kuantikoetan. Dagoeneko lasterketa abiatu da, nor izango ote da garaile?

Honaino irakurlerik iritsi bada, zorionak! Tori meme bat, merezi duzu eta:

Oin-Oharrak

_^1- Artikulu hau argitaratu eta bi egunetara inauguratuko dute/zuten donostiako IBM-ren ordenagailu kuantikoa. https://irutxulo.hitza.eus/2025/03/14/donostian-jarriko-dute-ibm-quantum-system-two-ordenagailu-kuantikoa/

_^2- Hurrengo artikulu batean azalduko dut zer den zarataren kontu hau.

_^3- Ordena bakoitia bada, prozedurak ez du balio eta beste a batekin probatu behar da.

Erreferentziak

[1] Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.

[2] https://en.wikipedia.org/wiki/General_number_field_sieve

[3] Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2), 303-332.

[4] Rieffel, E. G., & Polak, W. H. (2011). Quantum computing: A gentle introduction. MIT press.

[5] Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.

[6] Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433.