Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
требует некоторых временных затрат (при скорости работы, равной 1012
операций в секунду, требуется 42 дня). Однако, если увеличить объем
информации L в два раза, а число шагов s, соответственно, поднять до s ~
1025, задача станет неразрешимой: при современном уровне развития
вычислительной техники ее решение займет миллион лет либо для ее решения
необходимо увеличить быстродействие компьютера в миллион раз. В этом
важном примере показано, что задача, "сложная" с точки зрения вычисления,
является практически не просто трудно решаемой, она является
невычислимой.
Задача разложения на множители имеет большое практическое значение,
поскольку лежит в основе широко распространенных криптографических
систем, подобных системам Ривеста (Rivest), Шамира (Shamir) и Адлемана
(1979) (см. Heilman, 1979). Поскольку, задавшись сообщением М (в виде
большого двоичного числа), можно легко получить его зашифрованный вариант
как: Е = М8 mod с, где sue - тща-
42
Глава 3
тельно подобранные большие целые числа, которые могут быть общедоступны.
Для расшифровки сообщения получатель определяет значение величины: Е1 mod
с, совпадающее со значением М. Причем t легко находится с помощью s и
множителей с (Schroeder, 1984). На практике величина с = pq задается как
произведение двух достаточно простых чисел р и q, известных только тому
пользователю, который задает значение с. Поэтому до тех пор, пока кто-
нибудь не сумеет разложить на множители число с, этот пользователь будет
единственным, кто будет способен прочитать данное сообщение. Следует
отметить, что в подобной системе нет необходимости в распространении
шифров: "шифры" с, s, обеспечивающие кодировку, общедоступны.
3.3. Невычислимые функции
Существуют и более сложные задачи, которые невозможно решить с помощью
компьютера. При необходимости решения некоторых задач можно "прожить" то
время, пока будет выполняться алгоритм. Но что делать в том случае, когда
алгоритма вообще не существует? Подобные задачи называются невычислимыми.
Наиболее ярким и важным примером таких задач является задача об останове.
Характерная черта как программистов, так и компьютеров заключается в том,
что время от времени они в своих действиях начинают двигаться по
замкнутому кругу. В качестве примера рассмотрим следующую информацию:
"Пока х > 2 делить х на единицу" при начальном значении величины х больше
двух. Даже без практической реализации этого алгоритма можно видеть, что
он не имеет завершения. Более интересным с математической точки зрения
является следующий алгоритм: "Пока х равно сумме двух простых чисел,
добавлять к х число два. В противном случае печать х. Останов" при
начальном значении х = 8. Очевидно, данный алгоритм выполним, поскольку
две пары простых чисел, меньших х, могут быть систематически найдены и
сложены. Имеет ли данный алгоритм завершение? Если да, то он опровергает
предположение Гольдбаха. С помощью подобных приемов обширный раздел
математической и физической теории может быть сведен к вопросу: "Сможет
ли тот или иной алгоритм завершиться после его запуска?" Если бы был
известен какой-либо общий метод определения ответа на данный вопрос, то
сам метод являлся бы очень мощным математическим инструментом. Очевидно,
с его помощью можно было бы разрешить все вопросы математики.
3.3. Невычислимые функции
43
Пусть существует возможность нахождения алгоритма общего вида, который
определяет, сможет ли та или иная машина Тьюринга завершить свою работу
при любых входных данных. Такой алгоритм дает ответ на следующий вопрос:
"Даны значения ж и d[T]. Сможет ли машина Тьюринга завершить работу, если
на ее вход подать значение ж?" Здесь d[T] - описание машины Т. Если такой
алгоритм существует, то возможно определить такую машину Тьюринга Тя,
которая будет завершать'работу тогда и только тогда, когда машина T(d[T})
не сможет остановиться, где d[T] - описание машины Т. Здесь на входе
машины Тя находится величина d[T], которая содержит информацию как о
машине Тьюринга Т, так и о ее входных данных. Отсюда следует:
Тя(с/[Т]) имеет останов f* T(d[T]) не имеет останова. (19)
Но что произойдет, если в машину Тя направить описание ее самой с/[Тя]?
Тогда:
Тя(с/[Тя]) имеет останов Тя(с/[Тя]) не имеет останова, (20)
что является противоречивым. Посредством данных рассуждений Тьюринг
показал, что не существует автоматических средств, которые определяют,
сможет ли в общем случае машина Тьюринга завершить работу: таким образом,
задача об останове является неразрешимой. Это значит, что математика и
обработка информации, в общем случае, являются сложным организмом,
состоящим из разнообразных идей, которые невозможно объединить в одном
мощном алгоритме. Вышесказанное напрямую связано с теоремой Геделя.
Глава 4
Квантовая физика против физики классической
Для того чтобы перейти к квантовой теории информации, необходимо
следующим образом определить принципы нерелятивистской квантовой механики
