Эффективные квантовые алгоритмы

Данная книга посвящена разработке эффективных квантовых алгоритмов. Актуальность изучения квантовых моделей вычислений обоснована, во-первых, необходимостью исследования новых математических моделей, описывающих вычисления после достижения физического порога размера транзисторов, означающего, что классические законы физики уступают место квантовым. Во-вторых, исследование возможностей квантовых вычислителей направлено на выявление задач, для которых квантовые модели дают заметное превосходство по сравнению с классическими моделями. В работе рассматриваются методы построения алгоритмов в модели квантовых ветвящихся программ полиномиальной сложности. В частности, предлагается использовать метод «отпечатков» («fingerprinting»), позволяющий представлять входные данные в виде небольшой по памяти проекции, сохраняющей в себе вычисляемое свойство. С помощью этого метода построены эффективные по памяти квантовые алгоритмы для индивидуальных функций. Кроме того, исследуется структура эффективных квантовых алгоритмов, способных на одной ячейке памяти за полиномиальное время вычислять широкий класс функций.