VedecDaniel Nagaj
Názov projektuLokálne Hamiltoniány v Kvantovej Zložitosti
Hostiteľská organizáciaFyzikálny ústav SAV
Dĺžka projektu01.09.2015 - 31.12.2018

Abstrakt
Čo nám príroda dovolí vypočítať a prečo sú niektoré fyzikálne úlohy výpočtovo zložitejšie ako iné? Tieto otázky na hraniciach teoretickej fyziky a informatiky majú svoje korene na mikroskopickej úrovni. Lokálne interakcie v kvantovom mnohočasticovom systéme určujú základný stav - a môžu byť dôvodom, že tento stav je zaujímavý z troch pohľadov. Pre svoj vzťah k optimalizačným úlohám, kvôli neklasickým koreláciám, a nakoniec vďaka (ne)možnosti jednoduchej aproximácie tohto stavu. V tomto projekte je naším prvým cieľom porozumenie výpočtovej zložitosti (alebo jednoduchosti) simulácie týchto systémov a rozvoj teórie kvantovej informácie pre Hamiltonovské systémy. Náš druhý cieľ je využiť a zovšeobecniť zákon plochy (area law) pre základné stavy lokálnych Hamiltoniánov s medzerou v spektre - použiť ho ako výpočtový nástroj, mieriac na numerické aplikácie v mnohočasticovej fyzike. Treťou úlohou je preskúmať robustnosť týchto výsledkov za prítomnosti šumu a rôznych priblížení a prispieť tak k jednej z najhorúcejších tém v kvantovej teórii zložitosti: kvantovej PCP domnienke.

Zhrnutie projektu s priebežnými výsledkami

Čo nám príroda dovolí vypočítať? Prečo sú niektoré fyzikálne úlohy výpočtovo náročné? Presná kontrola škálovateľných plne kvantovomechanických počítačov by nám dovolila riešiť niektoré bežne nezvládnuteľné úlohy. Na druhej strane, vhľady z fyziky nám umožnili objaviť hlboké výsledky o zložitosti v teoretickej informatike, a motivovali praktické algoritmy (napr. žíhanie). V tomto projekte, ktorý v sebe spája otázky z fyziky a informatiky, chceme objaviť a porozumieť novej fyzike a zložitosti lokálnych Hamiltonovských systémov. Práca na vývoji matematických opisov, základných hypotéz pre nové oblasti a efektívnych nástrojov bude rozdelená na tri oblasti: základné stavy a optimalizácia, zákony typu area law a aproximácie.


Lokálne modely, základné stavy a dynamika. Prvým objektom nášho výs­ku­mu sú základné stavy a dynamika kvantových mnohočasticových sys­témov s lokálnymi interakciami. Budeme skúmať základné vlastnosti a štruk­túru stavov týchto kvantových modelov. Cieľom je objasniť a porozumieť ich výpočtovej zložitosti, alebo ukázať, že sa predsa len tieto systémy dajú simulovať.



Zákony o okraji (area laws): zjednodušené popisy reality. Náš druhý poh­ľad sa zameriava na zákon o okraji (area law) pre základné stavy lokálnych Hamil­toniánov s medzerou v spektre. Ak tento zákon platí, miera previazania rastie ako veľkosť okraja (povrch = area) a nie objemu sledovanej oblasti. To motivuje ansatzy, koré sa dajú použiť v nových numerických výpočtoch. Na druhej strane nám to dovoľuje porozumieť, ako sa v takých systémoch vyvíjajú excitácie a prerozdeľujú korelácie. Náš konečný zámer je formulovať zákon o okraji pre všeobecné geometrie, a použiť ho ako výpočtový nástroj.


Sila priblížení: smerom ku kvantovej PCP vete. Treťou úlohou projektu je vystavať, alebo zrúcať motivácie a dôkazy pre kvantovú PCP domnienku (qPCP). Je to mocné tvrdenie o možných priblí­že­niach popisujúcich kvantové mnohočasticové systémy. Preskúmame, kedy lokálne pri­blí­že­nia ničia bohatú štruktúru našich modelov. Zameriame sa hlavne na odkrytie zložitého sprá­vania sa previazania za prítomnosti šumu, a na možné lokálne testy overi­teľných dôkazov (základných stavov) v kvantovej teórii zložitosti.

V prvom roku projektu sme spravili pokrok vo všetkých troch navrhovaných oblastiach. Objavili sme a zanalyzovali rodinu translačne invariantných spinových reťazcov s prekva­pivými vlastnosťami previazania. Tieto modely majú vzťah ku klasickým výpočtovým modelom, a preto prinášajú nový uhol pohľadu na zákon o okraji. Ďalej sme formulovali nové otázky o translačne invariantnej verzii problému konzistencie lokálnych redukovaných matíc hustoty. Tretím výstupom je rozvoj teórie kvantových hodiniek pre výpočty a použitie techniky analýzy kvantových kráčaní na polynomiálne vylepšenie ohraničenia na presnosť pre QMA-úplnú úlohu Lokálny Hamiltonián. Nakoniec, ale nie bez významu, sme otvorili aj uzavreli mnohé neúspešné otázky (možnosť amplifikácie úspešnosti dôkazov pre triedu QMA(2), interaktívne dôkazy pre túto triedu, pomôcku na zníženie grafovej mohutnosti zapojenosti častíc do interakcií), vďaka čomu ideme do ďalších rokov projektu poučení a s novými nápadmi.