Квантовые ужасы

Tony

Спецвыпуск Xakep, номер #038, стр. 038-094-3

«Да это же параллельные вычисления!» - воскликнешь ты и будешь абсолютно прав.

Врожденные болезни кубита

Их на этапе исследований возникло как минимум две. Первая, как и положено любой уважающей себя болезни, имеет совершенно непроизносимое название – декогерентизация. Квантовая механика не работает с состояниями, она работает с вероятностями. Т.е. оперирует величинами, которые описывают вероятность нахождения системы в некотором состоянии. Состояния постоянно меняются, т.е. система эволюционирует. И может сложиться такая ситуация, что вычисления еще не были закончены, а кубиты сменят свои состояния сами по себе либо из-за воздействия сторонних помех. Лечится эта болезнь похожими на классические методами, “буферными” кубитами, алгоритмами коррекции ошибок.

Вторая болезнь имеет скорее инженерные истоки, чем научные – это связь между кубитами и компьютерами. Но на эту проблему пока мало обращают внимания, поскольку еще не существует единого подхода к технологии квантового компьютера, а существует множество его реализаций.

Задачи, решаемые квантовым компьютером

Подробно описаны два квантовых алгоритма – алгоритм Шора и алгоритм Гровера. Алгоритм Шора описывает факторизацию числа – разложение числа на простые множители (от 0 до 9). На классическом компьютере факторизация числа с N знаками потребует 2^N операций, квантовый же способен выполнить эти вычисления за N операций. Для того чтобы было нагляднее, вот тебе несколько интересных циферок. Факторизация 155-значного числа (512 бит) на современном компьютере займет около 35 лет, квантовый же справится за пару минут. На основе этой теории строится небезызвестный алгоритм шифрования RSA, который уйдет в небытие одновременно с появлением квантового компьютера.

Алгоритм Гровера описывает, в свою очередь, поиск информации в неупорядоченной базе данных. О классических компьютерах здесь даже говорить не приходится, поскольку все базы данных, во-первых, упорядочены, а во-вторых, индексированы.

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