Семинар ЛФВЭ 30 января 2015 г., 11:30, ЛФВЭ, Большой конференц-зал корпус 215

С.Г. Басиладзе (НИИЯФ МГУ) «Необходим ли квантовый компьютер в реализации алгоритма Ленстры по факторизации чисел. Макро и микро состояния и информация» Аннотация Рассматривается переход от реальных – прямо регистрируе-мых состояний к случайным вероятным состояниям, требующим для своего определения набора статистики. Показано сходство и подчеркивается различие состояний в макромире и в микромире, как носителей содержательной информации. Обсуждается обладает ли аналоговый квантовый компьютер функциями обычного компьютера (арифметические и логические операции и др.). Какие особенности состояний, которыми он оперирует, сужают диапазон его применения? Преимущество квантового компьютера в скорости решения обычно демонстрируется на задаче факторизации больших чисел (нахождения сомножителей). Ключевым в (наилучшем) алгоритме факторизации Ленстры является нахождения периода повторяющейся функции. Именно эта часть алгоритма поручается квантовому компьютеру, который находит решение с помощью преобразования Фурье. Анализируются ограничения и погрешности аналогового преобразования Фурье, приводящие к длительным вычислениям. Показано, что цифровой метод нахождения периода существенно упрощает реализацию этой части алгоритма Ленстры и делает ее доступной для обычного компьютера.