Квантовые вычисления со времен Демокрита - Скотт Ааронсон

a = 1

b = a + a

c = b²

d = c²

e = d²

f = e — a

g = d — a

h = d + a

i = gh

j = f — i.

Вы можете самостоятельно убедиться (если возникнет такое желание), что j, «выход» приведенной выше программы, равняется нулю. А теперь рассмотрите следующую обобщенную задачу: если дана такая программа, будет у нее на выходе 0 или нет? Как можно это определить?

Ну, один из способов — просто выполнить программу и посмотреть, что получится у нее на выходе! В чем проблема?

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

Что еще можно сделать? Ну, предположим, у нас в программе n операций. Тогда можно попробовать следующий фокус: для начала взять случайное простое число p из n² знаков. Затем смоделировать работу программы, но все вычисления делать по модулю p. Здесь возникает сверхважный момент, который для начинающих часто становится ловушкой: единственное, где нашему алгоритму разрешается использовать случайность, — это в моменты его собственного выбора, в данном случае — в момент выбора случайного простого числа p. Нам не разрешается рассматривать никакие усреднения по возможным программам, поскольку программа является просто входом в алгоритм, а со входом у нас все плохо!

Что мы можем сказать о приведенном выше алгоритме? Ну, он, безусловно, будет эффективен, то есть он будет выполняться за время, полиномиальное по отношению к n. Кроме того, если результат окажется не равен нулю по модулю p, то можно однозначно заключить, что он и вообще не равен нулю. Однако это оставляет без ответа два вопроса:

1. Предполагая, что результат равен 0 по модулю p, насколько уверены вы можете быть в том, что это не просто удачное совпадение и что результат и в самом деле равен 0?

2. Как выбрать случайное простое число?

Что касается первого вопроса, пусть x — результат работы программы. Тогда |x| не может быть больше 22ⁿ, где n — число действий, поскольку самый быстрый доступный нам способ получения больших чисел заключается в последовательном возведении в квадрат. Из этого сразу же следует, что у x может быть не более 2n простых делителей.

С другой стороны, сколько существует простых чисел из n² знаков? Знаменитая теорема о числе простых чисел дает ответ на этот вопрос: примерно 22ⁿ/n². Поскольку 22ⁿ/n² намного больше, чем 2n, на большинство этих простых чисел x, понятно, не разделится. Так что если мы выбираем случайное простое число и x на него делится, мы можем быть весьма и весьма уверены (правда, все же не абсолютно), что x = 0.

С первым вопросом разобрались. Теперь ко второму: как выбрать случайное простое число из n² знаков? Наш старый приятель, теорема о числе простых чисел, говорит нам, что если выбрать просто случайное число из n² знаков, оно окажется простым примерно в одном случае из n². Так что вам нужно всего лишь выбирать раз за разом случайные числа; примерно через n² попыток вы, вероятно, наткнетесь на простое число! Но почему, вместо того чтобы перебирать случайные числа, нельзя просто взять какое-то фиксированное число, а затем прибавлять к нему по единице, пока не дойдешь до простого числа?

Да, конечно, это сработает при условии одного весьма сильного обобщения гипотезы Римана! Нужно лишь, чтобы эти самые n²-значные простые числа были более или менее равномерно распределены по числовой прямой, так чтобы вы не могли в результате чистого невезения угодить на экспоненциально длинный промежуток, где все числа будут составными. Даже обобщенная гипотеза Римана не может вам этого гарантировать; впрочем, существует еще так называемая гипотеза Крамера — вот она может.

Разумеется, мы всего лишь свели задачу выбора случайного простого числа к другой задаче, а именно: как определить, выбрав случайное число, что оно простое? В предыдущей главе я упоминал, что определить, простое число или составное, оказывается, намного проще, чем действительно разложить число на множители. До недавнего времени задача проверки на простоту служила еще одним примером задачи, где, казалось, необходимо использовать случайность, мало того, она была бабушкой всех таких задач.

Идея состояла в следующем. Малая теорема Ферма (не путать с Великой теоремой Ферма!) гласит, что если p — простое число, то xp = x(mod p) для любого целого x. Так что если вы нашли x, для которого xp ≠ x(mod p), то вы можете быть уверены, что p — число составное, хотя по-прежнему ничего не будете знать о его делителях. А потому если вам долго и упорно не удается найти такое x, для которого xp ≠ x(mod p), то можно с высокой степенью уверенности сказать, что p — простое.

Увы, эта простая идея не работает. Оказывается, существуют составные числа p, которые «притворяются» простыми в том смысле, что для них xp = x(mod p) для любого x. Первые несколько таких «притворщиков» (названных числами Кармайкла) — это 561, 1105, 1729, 2465 и 2821. Конечно, если бы «притворщиков» было лишь конечное число и мы бы их все знали, все было бы прекрасно. Но Олфорд, Грэнвилл и Померанс[32] показали в 1994 г., что чисел-«притворщиков» существует бесконечно много.

К счастью, еще в 1976 г. Миллер и Рабин нашли способ разоблачить притворщиков, слегка изменив тот же тест. Иными словами, они нашли такую модификацию теста Ферма, которая всегда проходит при простом p, а вот в случае составного — с высокой вероятностью не проходит. Отсюда был получен рандомизированный алгоритм проверки на простоту за полиномиальное время.

Затем, лет десять назад, произошел прорыв, о котором вы, вероятно, слышали. Аграваль, Кайал и Саксена[33] нашли детерминированный алгоритм полиномиального времени, позволяющий определить, является ли число простым. Это прорывное открытие не имеет совершенно никакого практического применения, поскольку у нас давно есть более быстрые рандомизированные алгоритмы, для которых вероятность ошибки можно без труда низвести до величины меньшей, чем вероятность падения астероида на ваш компьютер в разгар вычислений. Но знать, что такой алгоритм существует, очень