Алексей Китаев, Александр Шень, Михаил Вялый.
Классические и квантовые вычисления.
М.: МЦНМО, ЧеРо, 1999. - 192 с., библ. 48 назв., 1500 экз.
Книга очень трудна и требует высокой математической культуры, являясь, впрочем, стимулом для овладения таковой. В 192 страницы авторы сумели втиснуть обширный материал теории классических и квантовых вычислений. Мало того, в каждом из четырнадцати разделов есть серия задач (с решениями!). Классическая часть посвящена иерархии сложностных классов, вероятностным алгоритмам, элементам алгоритмической теории чисел (все это на сорока страницах!). Квантовая часть рассказывает о важнейших квантовых алгоритмах, квантовых кодах и квантовых сложностных классах.
Авторский коллектив на редкость удачен. А. Китаеву (Microsoft Research Center) принадлежат яркие результаты в теории квантовых вычислений. А. Шень и М. Вялый (Независимый Московский университет) известны не только как крупные специалисты в теории сложности, но и как блестящие педагоги. Так что трудное содержание отчасти компенсируется великолепным стилем изложения. Вот, например, отрывок из определения "класса NP": "...имеются два персонажа: король Arthur (Артур), умственные способности которого полиномиально ограничены, и волшебник Merlin (Мерлин), который интеллектуально всемогущ..."
Рискну предположить, что перед нами - один из лучших в мире учебников по квантовым вычислениям (Американское математическое общество начало готовить английский перевод еще до выхода книги на русском языке.) Приятного чтения!