Квантовый компьютер

Евгений Firstborn Рогов

Спецвыпуск: Хакер, номер #055, стр. 055-068-3

Крепкие орешки

И какие это задачи так шустро и ловко решает квантовый компьютер? А возьмем, к примеру, алгоритм разложения числа на простые множители. Сам алгоритм несложен, и при желании ты легко разберешься в нем и реализуешь его на любом языке программирования, однако тут есть одна принципиальная неприятность: этот алгоритм требует достаточно большого времени для своей работы. Если говорить более грамотно, его временная сложность весьма велика, то есть время, необходимое для вычислений, очень быстро растет с увеличением объема исходных данных. В этом конкретном случае исходные данные - это число, подлежащее разложению на множители и его "объем" определяется просто количеством цифр в этом самом числе. Итак, если нам нужно применить алгоритм Шора для разложения числа, состоящего из N цифр, на простые множители, то для этого понадобится процессорное время, пропорциональное двойке в степени N. Попробуй представить себе, насколько стремительно будет расти это время по мере роста количества цифр в числе! Достаточно сказать, что при N больше тысячи это время выражается совсем астрономическими числами. В результате даже для всех классических компьютеров нашей скромной планетки будет невозможно отработать это время по своим классическим алгоритмам факторизации за сколько-нибудь обозримый срок.

А теперь держись крепче. Квантовый компьютер с помощью алгоритма, предложенного Питером Шором, решает эту задачу за полиномиальное время! То есть, по сравнению с классическим вариантом, практически мгновенно, по крайней мере тысячезначные числа он будет щелкать, как семечки. Может возникнуть и такой вопрос: "Что за глупости, кому может понадобиться раскладывать на множители такое ненормальное число? Кому это вообще нужно?" Оказывается, много кому. Для примера, множество современных криптосистем (RSA, например) полагаются на тот факт, что задачу разложения достаточно большого числа на множители невозможно решить за реальное время. Догадываешься, чем пахнет тот факт, что квантовый компьютер сможет это сделать на раз-два-три? То-то же.

Алгоритм Шора и все его криптографические последствия - далеко не единственный пример. Есть и другие. Возьмем, к примеру, очень простой и прагматичный алгоритм поиска в базе данных. Как несложно догадаться, для поиска в базе из N элементов (да, N - моя любимая буква!) понадобится время, пропорциональное этому числу N, то есть это алгоритм с линейной временной сложностью. Ну что здесь еще улучшать?" - предательски шепчет тебе твое консервативное подсознание, привыкшее к скучным классическим компьютерам. И тут бац! Сюрприз! Квантовый компьютер запросто найдет элемент в базе за время порядка квадратного корня из числа элементов N с помощью так называемого алгоритма Гровера. Грубо говоря, если у тебя есть маленькая база данных всего из сотни элементов, то классический компьютер провозится с ней все 100 наносекунд, а квантовый управится всего за десять - прочувствуй разницу!