Kvantovaya informatika segodnya - odna iz naibolee intensivno razvivayushchikhsya oblastey komp'yuternykh nauk (Computer Science). S tekh por, kak byli razrabotany effektivnye kvantovye algoritmy dlya ryada prakticheski znachimykh zadach, sredi kotorykh algoritm Shora faktorizatsii chisel, algoritm Grovera poiska v neuporyadochennoy baze dannykh, oblast' kvantovykh vychisleniy nakhoditsya pod pristal'nym vnimaniem kak uchenykh, tak i vsekh, kto interesuetsya budushchim komp'yuternykh tekhnologiy. Odin iz vazhneyshikh matematicheskikh voprosov v etoy svyazi - izuchenie potentsial'nykh vozmozhnostey vychisliteley, rabotayushchikh po zakonam kvantovoy mekhaniki, sravnenie ikh s sushchestvuyushchimi na segodnyashniy den' klassicheskimi modelyami vychisleniy. Kniga posvyashchena analizu sravnitel'noy slozhnosti takikh izvestnykh vychislitel'nykh modeley, kak vetvyashchiesya programmy, konechnye avtomaty i ikh kvantovykh analogov. Kniga budet polezna studentam i aspirantam, spetsializiruyushchimsya v oblasti kvantovykh vychisleniy, a takzhe uchenym, provodyashchim issledovaniya v oblasti kvantovoy i klassicheskoy informatiki i teorii slozhnosti.