Квантовые и классические модели вычислений

Квантовая информатика сегодня - одна из наиболее интенсивно развивающихся областей компьютерных наук (Computer Science). С тех пор, как были разработаны эффективные квантовые алгоритмы для ряда практически значимых задач, среди которых алгоритм Шора факторизации чисел, алгоритм Гровера поиска в неупорядоченной базе данных, область квантовых вычислений находится под пристальным вниманием как ученых, так и всех, кто интересуется будущим компьютерных технологий. Один из важнейших математических вопросов в этой связи - изучение потенциальных возможностей вычислителей, работающих по законам квантовой механики, сравнение их с существующими на сегодняшний день классическими моделями вычислений. Книга посвящена анализу сравнительной сложности таких известных вычислительных моделей, как ветвящиеся программы, конечные автоматы и их квантовых аналогов. Книга будет полезна студентам и аспирантам, специализирующимся в области квантовых вычислений, а также ученым, проводящим исследования в области квантовой и классической информатики и теории сложности.