Algoritmet kuantike pushtojnë një lloj të ri problemi

Në vitin 1994, një matematikan kuptoi se si ta bënte një kompjuter kuantik të bënte diçka që asnjë kompjuter i zakonshëm klasik nuk mund ta bënte. Puna zbuloi se, në parim, një makinë e bazuar në rregullat e mekanikës kuantike mund të thyente në mënyrë efikase një numër të madh në faktorët e saj kryesorë – një detyrë kaq e vështirë për një kompjuter klasik sa që përbën bazën për pjesën më të madhe të sigurisë së internetit të sotme.

Pasoi një rritje e optimizmit. Ndoshta, menduan studiuesit, ne do të jemi në gjendje të shpikim algoritme kuantike që mund të zgjidhin një gamë të madhe problemesh të ndryshme.

Por progresi ngeci. “Ka qenë një trajektore paksa e keqe,” tha Ryan O’Donnell nga Universiteti Carnegie Mellon. “Njerëzit thanë: “Kjo është e mahnitshme, jam i sigurt që do të marrim të gjitha llojet e algoritmeve të tjera të mahnitshme.” Jo.” Shkencëtarët zbuluan përshpejtime dramatike vetëm për një klasë të vetme, të ngushtë problemesh nga brenda një grupi standard të quajtur NP, që do të thotë se ata kishin zgjidhje efikase të verifikueshme – si faktorizimi.

Kështu ishte për gati tre dekada. Më pas, në prill, studiuesit shpikën një lloj problemi thelbësisht të ri që një kompjuter kuantik duhet të jetë në gjendje ta zgjidhë në mënyrë eksponenciale më shpejt se ai klasik. Ai përfshin llogaritjen e inputeve për një proces të komplikuar matematikor, bazuar vetëm në rezultatet e tij të ngatërruara. Nëse problemi qëndron i vetëm apo është i pari në një kufi të ri të shumë të tjerëve, ende nuk është përcaktuar.

“Ka një ndjenjë eksitimi,” tha Vinod Vaikuntanathan, një shkencëtar kompjuteri në Institutin e Teknologjisë në Massachusetts. “Shumë njerëz po mendojnë se çfarë tjetër ka atje”.

Shkencëtarët e kompjuterave përpiqen të kuptojnë se çfarë bëjnë më mirë kompjuterët kuantikë duke studiuar modelet matematikore që i përfaqësojnë ata. Shpesh, ata imagjinojnë një model të një kompjuteri kuantik ose klasik të çiftuar me një makinë llogaritëse të idealizuar të quajtur orakull. Orakulat janë si funksione të thjeshta matematikore ose programe kompjuterike, që marrin një hyrje dhe nxjerrin një dalje të paracaktuar. Ata mund të kenë një sjellje të rastësishme, duke nxjerrë “po” nëse hyrja bie brenda një diapazoni të caktuar të rastësishëm (të themi, 12 deri në 67) dhe “jo” nëse nuk është. Ose ato mund të jenë periodike, kështu që një hyrje midis 1 dhe 10 kthen “po”, 11 deri në 20 jep “jo”, 21 deri në 30 prodhon përsëri “po” dhe kështu me radhë.

Le të themi se keni një nga këto orakuj periodikë dhe nuk e dini periudhën. E tëra çfarë mund të bëni është ta ushqeni me numra dhe të shihni se çfarë nxjerr. Me këto kufizime, sa shpejt mund ta gjejë një kompjuter periodën? Në vitin 1993, Daniel Simon, atëherë në Universitetin e Montrealit, zbuloi se një algoritëm kuantik mund të llogariste përgjigjen për një problem të lidhur ngushtë në mënyrë eksponenciale më shpejt se çdo algoritëm klasik.

Rezultati i mundësoi Simonit të përcaktojë një nga sugjerimet e para se ku mund të pritej epërsia dramatike për kompjuterët kuantikë. Por kur ai dorëzoi punimin e tij në një konferencë udhëheqëse, ajo u refuzua. Megjithatë, gazeta i interesoi një anëtari të ri të komitetit të programit të konferencës – Peter Shor, i cili në atë kohë ishte në Bell Laboratories në New Jersey. Shor vazhdoi të zbulonte se ai mund të përshtatte algoritmin e Simonit për të llogaritur periudhën e një orakulli, nëse do të kishte një të tillë. Më pas ai kuptoi se mund ta përshtatte edhe një herë algoritmin, për të zgjidhur një ekuacion që sillet në mënyrë të ngjashme me një orakull periodik: ekuacioni që përshkruan faktorizimin, i cili është periodik.

Rezultati i Shor ishte historik. Algoritmi kuantik që ai zbuloi mund të reduktojë me shpejtësi numrat gjigantë në faktorët kryesorë të tyre përbërës, diçka që asnjë algoritëm i njohur klasik nuk mund ta bëjë. Në vitet që pasuan, studiuesit zbuluan algoritme të tjera kuantike efikase. Disa prej tyre, si algoritmi i Shor-it, madje siguruan avantazh eksponencial, por askush nuk mund të provonte një avantazh dramatik kuantik në çdo problem NP që nuk ishte periodik.

Kjo mungesë progresi bëri që dy shkencëtarë kompjuterikë, Scott Aaronson nga Universiteti i Teksasit, Austin dhe Andris Ambainis nga Universiteti i Letonisë, të bënin një vëzhgim. Provat e avantazhit kuantik dukeshin gjithmonë të varura nga orakujt që kishin një lloj strukture jo të rastësishme, siç është periodiciteti. Në vitin 2009, ata supozuan se nuk mund të kishte përshpejtime dramatike në problemet e NP që ishin të rastësishme ose të pastrukturuara. Askush nuk mund të gjente një përjashtim.

Hamendja e tyre vendosi një kufi në fuqitë e kompjuterëve kuantikë. Por ai tha vetëm se nuk kishte përshpejtime dramatike për një lloj specifik problemi të pastrukturuar NP – ato me përgjigje po ose jo. Nëse një problem përfshinte gjetjen e përgjigjeve më specifike, sasiore, që njihet si problem kërkimi, hamendësimi nuk zbatohej.

Me këtë në mendje, studiuesit Takashi Yamakawa nga NTT Social Informatics Laboratories dhe Mark Zhandry i NTT Research dhe Princeton University vendosën të eksperimentojnë me një problem specifik kërkimi, të prezantuar në 2005 nga Oded Regev.

Imagjinoni një grup korsish moti që janë të gjitha të drejtuara në të njëjtin drejtim. Jepini secilit prej tyre një shtytje të matur dhe më pas lëreni një erë të fortë të ndikojë në drejtimin e tyre. Regev donte të përcaktonte, bazuar në drejtimet e tyre përfundimtare, se ku të gjithë treguan fillimisht. Problemet si kjo u quajtën “të mësuarit me gabime”, sepse shtytja dhe era veprojnë si një burim gabimi të rastësishëm në drejtimin origjinal. Ka prova që është e vështirë të zgjidhet si për algoritmet klasike ashtu edhe për ato kuantike.

Yamakawa dhe Zhandry ndryshuan konfigurimin. Ata modifikuan forcën e atyre që nisnin goditjet, duke i bërë ato më të parashikueshme. Ata gjithashtu bënë që era të përcaktohej nga një orakull i rastësishëm në mënyrë që të ishte edhe më e rastësishme në disa raste, por plotësisht e fjetur në të tjera.

Me këto modifikime, studiuesit zbuluan se një algoritëm kuantik mund të gjente me efikasitet drejtimin fillestar. Ata gjithashtu vërtetuan se çdo algoritëm klasik duhet të jetë më i ngadalshëm nga një faktor eksponencial. Ashtu si Shor, ata më pas përshtatën algoritmin e tyre për të zgjidhur një version real të problemit, i cili zëvendëson orakullin me një ekuacion aktual matematik.

Shkencëtarët e kompjuterave janë ende duke punuar për të kuptuar dhe ndërtuar mbi problemin. Vaikuntanathan e krahason atë me një tjetër që lind kur bën kompresimin e të dhënave: Kur informacioni është duke u shtrydhur, dy bit mund të shtrydhen aksidentalisht në të njëjtin vend, duke i mbishkruar ato. Problemi i parashikimit të këtyre përplasjeve paraprakisht, në mënyrë që t’i shmangni ato, ka disa ngjashmëri. “Kjo është një klasë problemesh që në thelb duken kështu,” tha ai. “Ndoshta këto probleme mund të zgjidhen në mënyrë kuantike.”

Kishte shpresa se një problem i pastrukturuar si ai i ri mund të ishte i zgjidhshëm edhe në versionet e reja të sotme të kompjuterëve kuantikë, duke ofruar kështu një mjet për t’i testuar ata. Mendimi ishte se problemet e pastrukturuara mund të kërkojnë më pak burime për t’u programuar, ose të jenë më pak të ndjeshme ndaj zhurmës, pasi ato janë tashmë të rastësishme. Por deri më tani, problemi i ri duket ende shumë i avancuar për t’u zgjidhur nga kompjuterët kuantikë ekzistues. “Është një problem i çuditshëm. Nuk kisha menduar ta përkufizoja”, tha Aaronson. “Por në retrospektivë, ai ka disa karakteristika shumë të bukura.”

Rezultati ofron shembullin e parë të avantazhit kuantik dramatik në një problem NP të pastrukturuar. A mund të ketë shumë probleme të tjera që bota kuantike ndryshon nga praktikisht e pazgjidhshme në të zgjidhshme? Tani ka më shumë arsye për të menduar kështu.

“Ka përmbysur disi bindjet tona për llojet e problemeve në të cilat kompjuterët kuantikë mund të jenë të mirë,” tha O’Donnell.