Effektivnye Kvantovye Algoritmy

Dannaya kniga posvyashchena razrabotke effektivnykh kvantovykh algoritmov. Aktual'nost' izucheniya kvantovykh modeley vychisleniy obosnovana, vo-pervykh, neobkhodimost'yu issledovaniya novykh matematicheskikh modeley, opisyvayushchikh vychisleniya posle dostizheniya fizicheskogo poroga razmera tranzistorov, oznachayushchego, chto klassicheskie zakony fiziki ustupayut mesto kvantovym. Vo-vtorykh, issledovanie vozmozhnostey kvantovykh vychisliteley napravleno na vyyavlenie zadach, dlya kotorykh kvantovye modeli dayut zametnoe prevoskhodstvo po sravneniyu s klassicheskimi modelyami. V rabote rassmatrivayutsya metody postroeniya algoritmov v modeli kvantovykh vetvyashchikhsya programm polinomial'noy slozhnosti. V chastnosti, predlagaetsya ispol'zovat' metod otpechatkov (fingerprinting), pozvolyayushchiy predstavlyat' vkhodnye dannye v vide nebol'shoy po pamyati proektsii, sokhranyayushchey v sebe vychislyaemoe svoystvo. S pomoshch'yu etogo metoda postroeny effektivnye po pamyati kvantovye algoritmy dlya individual'nykh funktsiy. Krome togo, issleduetsya struktura effektivnykh kvantovykh algoritmov, sposobnykh na odnoy yacheyke pamyati za polinomial'noe vremya vychislyat' shirokiy klass funktsiy.