A klasszikus komplexitáselmélet határai
Harminc éve használják elméleti keretként a komplexitáselméletet, hogy rámutassanak: vannak olyan problémák, amelyekben a kvantumszámítógépek lényegesen jobbak a klasszikus gépeknél. Mindez azonban még csak a kezdet, hiszen eddig főként olyan problémákra koncentráltak, amelyek klasszikus bitekből álló inputokon és outputokon alapulnak. A valódi kihívás, hogy mit kezdjünk azokkal a problémákkal, amelyeknél már maga az input és az output is kvantumos természetű. Ezek a feladatok ugyanis már teljesen kilógnak a hagyományos elméletek kereteiből.
A klasszikus komplexitáselmélet ezekről a problémákról egyszerűen hallgat. Nem csoda, hogy egyre többen úgy gondolják: egészen új, teljes mértékben kvantumos elmélet megalkotására van szükség.
Bit-elkötelezettség: amikor már az alapok sem működnek
Egy konkrét példa ilyen problémára a kriptográfiában alkalmazott bit-elkötelezettség („bit commitment”), amely nagyjából olyan, mintha egy üzenetet pecsétes borítékba zárnál. Az üzenet rejtve marad, amíg el nem jön a felfedés ideje, és garantált, hogy nem tudod menet közben megváltoztatni. Ilyen eljárásokat használnak például titkos szavazásnál vagy aukcióknál. A klasszikus módszerek azonban azon az előfeltevésen nyugszanak, hogy bizonyos matematikai problémák megoldhatatlanul nehezek. Ha viszont valakinek lenne elég számítási ereje, bármikor fel tudná törni ezeket a rendszereket.
Most képzeld el, hogy a borítékod maga is kvantumos. Itt már nem elég a klasszikus számítástechnikai hatalom: nem biztos, hogy ezzel áttörheted a kvantumboríték adta biztonsági garanciákat. Ez példázza, mennyire idegen a kvantumvilág a klasszikus gondolkodásmódtól, és rámutat: a két világ között logikailag is lehetnek áthidalhatatlan szakadékok.
A kvantumkomplexitás és a klasszikus elmélet lehetséges függetlensége
Felmerül a kérdés: ha mindent tudnánk a klasszikus komplexitáselméletről, abból következne-e bármi a teljesen kvantumos elméletre nézve? Lehetséges, hogy a kvantumos input–output problémák teljesen logikailag függetlenek a klasszikusoktól. Képzeld el, milyen lenne egy korlátlan erejű klasszikus „orákulum”, ami azonnal tud minden klasszikus problémára válaszolni. Vajon ezzel képesek lennénk-e bármilyen tetszőleges kvantumállapot-átalakítást is végrehajtani? Ha a válasz nem, az azt jelenthetné, hogy a kvantumkomplexitás tényleg más törvények szerint működik.
Az Uhlmann-transzformáció és a kvantumbonyolultság csomópontja
Az új kvantumkomplexitás-elmélet kutatása közben kiderült, hogy több, látszólag különböző probléma végső soron egyetlen közös elméleti maghoz kötődik. Ez az „Uhlmann-transzformációs probléma”, amely a kvantuminformáció-elmélet alapköve.
Két összefonódott kvantumrendszer leírásánál Uhlmann tétele azt mondja ki: ha csak az egyik rendszeren végezhetsz műveletet, mekkora a maximálisan elérhető hasonlóság az összehasonlított állapotok között? Ez kvantumkommunikációban, kvantumkriptográfiában és még fekete lyukak dekódolásánál is kulcsfontosságú. A kvantumos input–output problémák hálózatában az Uhlmann-probléma olyan, mint egy csomópont: onnan sugároznak ki az összes többi, hasonló bonyolultságú feladat. Ilyenek a bit-elkötelezettségi protokollok, a fekete lyukakkal kapcsolatos problémák vagy akár a kvantuminformáció tömörítése.
Az életút, ami a kvantumkomplexitásig vezetett
A kvantumelmélet úttörői között akadnak egészen kivételes hátterű kutatók. Yuen például 1989-ben született, szülei a kambodzsai vörös khmerek rémuralma elől menekültek az Egyesült Államokba. Édesanyja családja évekig kényszermunkatáborban sínylődött, míg végül sikerült elmenekülniük, később egy éttermet nyitottak Kaliforniában, ahol Yuen is dolgozott, amíg el nem kezdte az egyetemet.
Nem hétköznapi, hogy valaki ilyen múltból eljut a kvantumfizika olyan elvont csúcsaira, mint a komplexitáselmélet. Jó példája annak, hogy milyen váratlan utak vezethetnek a tudomány világába.
Miért éppen kvantumelmélet?
Yuen eredetileg fizikát és informatikát szeretett volna tanulni, a videojáték-fejlesztés iránt érzett lelkesedése miatt. A laborok azonban nem mentek neki, ezért csak informatikára váltott. 2007–2008 körül szinte véletlenül botlott bele egy blogba, ahol kvantuminformatikai elméletekről olvasott, ez fordította végleg a kvantuminformatika felé. A legnagyobb inspirációt számára egy professzor adta, aki minden hagyománytól függetlenül ösztönözte a hallgatókat: „El kell felejteni a régi dogmákat, más irányt kell vennünk, ahol eddig senki sem járt.”
Egy új elméleti nyelv születése
A kvantumkomplexitás-elmélet kidolgozása során szokatlan munkamódszereket is kellett alkalmazni. Itt senki sem ad kész tételeket meg bizonyítandó állításokat; még azt sem tudjuk, pontosan mik a jó kérdések. A legfontosabb a megfelelő nyelvezet megtalálása – mert ha a fogalmi keret hibás, bizonyos gondolatokat lehetetlen kifejezni vagy végiggondolni. Az új kvantumelmélet így nem egyszerűen a klasszikus elmélet továbbgondolása, hanem egy teljesen új gondolkodásmód legerősebb példája.
