Текст книги "Квантовые вычисления со времен Демокрита"

Вот что я имею в виду. Возьмите компьютерное доказательство гипотезы о четырех красках, которую я уже мельком упоминал. Это доказательство разрешило великую математическую задачу, державшуюся целый век, но сделало это посредством сведения ее к скучному перечислению тысяч конкретных случаев. Почему некоторые математики недовольны этим доказательством или, по крайней мере, надеются на появление другого, лучшего? Потому что компьютер «мог сделать ошибку»? Ну, это довольно слабый аргумент, поскольку доказательство было проверено несколькими независимыми группами программистов с использованием разного оборудования и программного обеспечения; к тому же человек и сам делает множество ошибок!

Мне кажется, суть разногласий здесь сводится к тому, что есть определенный смысл, в котором гипотеза о четырех красках доказана, и есть смысл, в котором многие математики понимают доказательство, – и смыслы эти не совпадают. Для многих математиков утверждение нельзя считать доказанным в тот момент, когда некий физический процесс (это может быть классический расчет, квантовый расчет, интерактивный протокол или еще что-то) завершается и говорит, что оно доказано, какими бы серьезными ни были причины считать этот физический процесс достоверным. Скорее так: утверждение считается доказанным, когда они (математики) чувствуют, что их разум может непосредственно воспринять его истинность.

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

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

2. Уверенность в том, что если бы они были всего лишь вычислительным процессом, то они не могли бы обладать сознанием в этом смысле.

К примеру, я считаю, что возражения Пенроуза против сильного ИИ базируются именно на этих двух факторах. Я считаю, что его критика теоремы Гёделя – всего лишь занавесочка на окне, добавленная позже.

Для тех, кто думает так (и я сам – в соответствующем настроении), признание за роботом права на сознание представляется в каком-то странном смысле эквивалентным отрицанию собственного сознания. Существует ли достойный выход из этой дилеммы, или, иными словами, хоть какой-нибудь выход, не основанный на совершенно шовинистических двойных стандартах, когда к самим себе применяются одни правила, а к роботам – другие?

Мне больше всего нравится выход, который продвигает философ Дэвид Чалмерс[22]22
  См.: David J. Chalmers, The Conscious Mind: In Search of a Fundamental Theory, Oxford University Press, 1997.


[Закрыть]. Суть того, что предлагает Чалмерс, состоит в «философской редукции NP-полноты», то есть в сведении одной загадки к другой. Он говорит, что если компьютеры когда-нибудь научатся имитировать людей во всех наблюдаемых отношениях, то мы будем вынуждены рассматривать их как обладающие сознанием, в точности по тем же причинам, по которым мы рассматриваем окружающих нас людей как обладающих сознанием. Что же касается того, как они могут обладать сознанием, – ну, мы при этом будем понимать это точно так же хорошо или точно так же плохо, как мы понимаем, как кучка нейронов может обладать сознанием. Да, это загадка, но в данном случае одна загадка, кажется, не так уж сильно отличается от другой.

Загадки

• [Почти хорошо определенная загадка.] Можем ли мы считать без потери общности, что компьютерная программа имеет доступ к собственному исходному коду?

• [Расплывчатая, плохо определенная загадка.] Если бы то, что до XIX века называлось водой, оказалось CH₄, а не H₂O, что это было бы – по-прежнему вода или что-то другое?

Ответы на упражнения из предыдущей главы

Вспомним, что BB(n), или «n-е число Делового Бобра», – это наибольшее число шагов, которые машина Тьюринга с n-состояниями может сделать на чистой первоначально ленте, прежде чем остановится.

Первой задачей было доказать, что BB(n) растет быстрее, чем какая бы то ни было вычислимая функция.

Предположим, что существует вычислимая функция f(n), такая, что f(n) > BB(n) для любого n. Тогда, имея машину Тьюринга M с n-состояниями, мы можем сначала вычислить f(n), а затем смоделировать работу M вплоть до f(n)-го шага. Если M не остановилась до этого момента, то мы можем быть уверены, что она не остановится никогда, потому что f(n) больше максимального числа шагов, которые может сделать произвольная машина с n-состояниями. Но это дает нам способ решить проблему остановки, что, как мы уже знаем, невозможно. Следовательно, функция f не существует.

Таким образом, функция BB(n) растет очень, очень, очень быстро. (На случай, если вам любопытно, приведу несколько ее первых значений, вычисленных неленивыми людьми, у которых слишком много свободного времени: BB(1) = 1, BB(2) = 6, BB(3) = 21, BB(4) = 107, BB(5) ≥ 47 176 870. Разумеется, эти значения зависят от конкретных деталей того, как определены машины Тьюринга.)

Второй задачей было определить, является ли

вычислимым действительным числом. Иными словами, существует ли алгоритм, который на основе положительного целого k выдает рациональное число S', такое, что |S – S'| < 1/k?

Что, эта задача оказалась посложнее для вас? Хорошо, давайте заглянем в ответ. Ответ отрицательный: это число не является вычислимым. Потому что, если предположить его вычислимость, мы получим алгоритм для вычисления самого BB(n), что, как мы знаем, невозможно.

Примем по индукции, что мы уже вычислили BB(1), BB(2),…, BB(n – 1). Тогда рассмотрим сумму «членов высшего порядка»:

Если S вычислимо, то Sn тоже должно быть вычислимым. Но это означает, что мы можем аппроксимировать Sn с точностью до 1/2, 1/4, 1/8 и так далее, до тех пор, пока интервал, в котором мы ограничили Sn, перестанет включать в себя 0. Когда это произойдет, мы получим верхнюю оценку для 1/S_n. Поскольку 1/BB(n + 1), 1/BB(n + 2) и т. п. намного меньше, чем 1/BB(n), любая верхняя оценка для 1/S_n немедленно выдает верхнюю оценку также и для BB(n). Но, получив верхнюю оценку для BB(n), мы можем вычислить и сам BB(n) путем простого моделирования всех машин Тьюринга с n-состояниями. Так что, считая, что мы умеем вычислять S, мы получаем возможность вычислить ВВ(n) (а мы уже знаем, что это невозможно). Следовательно, S не является вычислимым.

5. Палеосложность

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

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

Полезно разбить теорию вычислительной сложности на исторические эпохи:

• 1950-е гг.: поздний тьюрингозой

• 1960-е гг.: заря асимптотического века

• 1971 г.: астероид Кука – Левина; вымирание диагоналозавров

• начало 1970-х гг.: Карпийский взрыв

• 1978 г.: ранний криптозой

• 1980-е гг.: рандомизейская эра

• 1993 г.: извержение вулкана Разборудич; вымирание комбинатавров

• 1994 г.: нашествие квантодактилей

• с середины 1990-х гг. до наших дней: дерандомизейская эра.

Эта глава будет посвящена «палеосложности», то есть теории сложности до появления классов P и NP и NP-полноты, когда на земле царили диагоналозавры. Затем в главе 6 речь пойдет о Карпийском взрыве, в главе 7 – о рандомизейской эре, в главе 8 – о раннем криптозое, а в главе 9 – о нашествии квантодактилей.

Ранее мы говорили о теории вычислимости. Мы видели, что некоторые задачи вычислимыми не являются, к примеру если дано некоторое утверждение о положительных целых числах и требуется сказать, истинно оно или ложно. (Если бы мы могли ответить на этот вопрос, то мы могли бы решить и проблему остановки, что, как мы уже знаем, невозможно.)

А теперь предположим, что у нас есть некоторое утверждение о действительных числах, к примеру такое:

для любых действительных x и y верно

(x + y)² = x² + 2xy + y²,

и мы хотим знать, истинно оно или ложно. В данном случае оказывается, что процедура выяснения ответа на этот вопрос существует, – это доказал Тарский в 1930-е гг., – по крайней мере, когда в утверждении присутствуют только сложение, умножение, сравнение, константы 0 и 1, кванторы общности и существования (но нет экспонент и тригонометрических функций).

Интуитивно понятно, что если все наши переменные принадлежат множеству действительных, а не целых чисел, то все поневоле получится гладким и непрерывным, и невозможно построить такие гёделевские высказывания, как «данное высказывание не может быть доказано».

(Если добавить сюда же экспоненциальную функцию, то, как недавно доказано, у нас по-прежнему не будет способа закодировать гёделевы высказывания с точностью до одной нерешенной задачи в области анализа[23]23
  http://www.ams.org/notices/199607/marker.pdf


[Закрыть]. Но если мы добавим экспоненциальную функцию и к тому же перейдем от действительных чисел к комплексным, то мы снова сможем кодировать гёделевы высказывания – и теория вновь станет неразрешимой! Понимаете, почему? Ну, если у нас будут комплексные числа, мы сможем принудительно сделать n целым, сказав: мы хотим, чтобы e2πin равнялось 1. И тогда мы вернемся к тому, с чего начинали с целыми числами.)

Но тогда положение воспринималось так: о'кей, мы нашли алгоритм, позволяющий определить истинность или ложность любого высказывания о действительных числах! Можно расходиться по домам! Задача решена!

Беда в том, что если разобраться, сколько шагов требуется этому алгоритму для выяснения истинности высказывания из n символов, то окажется, что это число растет, как громадная лесенка из экспонент: Я читал в биографии[24]24
  A. Burdman Fefferman and S. Fefferman, Alfred Tarski: Life and Logic (Cambridge: Cambridge University Press, 2008).


[Закрыть] Тарского, что когда в 1950-е гг. на сцену вышли реальные компьютеры, первым делом кому-то пришло в голову применить алгоритм Тарского для оценки высказываний о действительных числах. И оказалось, что это безнадежно, мало того, это было бы безнадежно даже для сегодняшних компьютеров! А для компьютеров 1950-х гг. это было безнадежно безнадежно… безнадежно.

Итак, в настоящее время мы говорим о вычислительной сложности. (Или, по крайней мере, это делает большинство из нас.) Идея следующая: вы задаете верхнюю границу некоторого ресурса, который может использовать ваш компьютер. Самые очевидные ресурсы – это (1) время и (2) объем памяти, но можно определить и множество других ресурсов. (На моем сайте Зоопарка cложности[25]25
  http://www.complexityzoo.com


[Закрыть] вы найдете около 500 вариантов.)

Одно из самых первых открытий состоит в том, что если спросить, сколько можно вычислить за 10 миллионов шагов, или с использованием 20 миллиардов бит памяти, то ничего не выяснишь. Ваша теория вычисления окажется игрушкой произвольного выбора параметров в базовой модели. Иными словами, вы будете заниматься вовсе не теоретической информатикой – вы будете заниматься архитектурой, а это, конечно, бесконечно интересная сама по себе тема, которая никогда не даст вам скучать, но это не наша тема.

Так что вместо этого вам придется задавать более неопределенный вопрос: сколько всего можно вычислить за время, которое растет линейно (или квадратично, или логарифмически) с ростом размеров задачи? Такая постановка вопроса позволит вам игнорировать постоянные коэффициенты.

Итак, определим TIME(f(n)) как класс задач, для которых каждый пример размером n решаем за время, которое растет по линейному закону f(n). Здесь под «решаемым» мы понимаем то, что может решить некоторый конкретный тип идеализированного компьютера (скажем, машины Тьюринга), который мы фиксируем в качестве «опорного». Ключевой эмпирический факт, на который опирается вся теория, состоит в том, что не слишком важно, какой именно тип идеализированного компьютера мы выберем, до тех пор пока мы остаемся в некоторых широких рамках (к примеру, мы рассматриваем только последовательные, детерминистские, классические компьютеры, а не квантовые компьютеры или еще что-то подобное).

Аналогично SPACE(f(n)) – это класс задач, решаемых нашей опорной машиной с использованием объема памяти (пространства), растущего по линейному закону f(n).

Что можно сказать о взаимоотношениях между этими классами? Понятно, что для любой функции f(n) TIME(f(n)) содержится в SPACE(f(n)). Почему? Потому что за один шаг по времени машина Тьюринга может получить доступ максимум к одной ячейке памяти.

Что еще? Вы, надо понимать, согласны, что TIME(n²) входит в TIME(n³). Вот вам вопрос: оно заключено строго внутри? Иными словами, можно ли решить за время n³ больше задач, чем за время n²?

Оказывается, можно. Это следствие фундаментального открытия, получившего название теоремы об иерархии (по времени); эту теорему доказали Хартманис и Штернс в середине 1960-х гг., за что были удостоены премии Тьюринга. (Не хочу принизить их вклад в науку, но тогда премия Тьюринга котировалась не особенно высоко! Конечно, чтобы ее добиться, нужно было знать о существовании премии, а знали о ней немногие.)

Посмотрим, как это доказывается. Нужно найти задачу, решаемую за время n³, но не за n². Что это может быть за задача? Это простейшая вещь, какую только можно себе представить: ограниченный во времени аналог проблемы остановки Тьюринга.

Пусть M – машина Тьюринга; остановится ли M не более чем за n^2,5 шагов? (Здесь n^2,5 – всего лишь некоторая функция, лежащая между n² и n³.)

Ясно, что мы можем решить приведенную задачу за n³ шагов, промоделировав M на n^2,5 шагов и посмотрев, остановится она или нет. (Более того, мы можем решить эту задачу за что-то вроде n^2,5 log n шагов. Конечно, при моделировании нам всегда нужен какой-то запас, но его можно сделать чрезвычайно маленьким.)

А теперь предположим, что существует программа P, способная решить эту задачу за n² шагов, и придем к противоречию. Ясно, что, используя P как подпрограмму, мы могли бы получить новую программу P′, которая ведет себя следующим образом. Получив программу M на вход, P′

1. Работает до бесконечности, если M останавливается не более чем через n^2,5, получив на вход собственный текст, или

2. Останавливается через n^2,5 шагов, если M делает больше, чем n^2,5 шагов, получив на вход свой собственный текст.

Кроме того, P′ делает все это не более чем за n^2,5 шагов (точнее, за n² шагов плюс некоторая добавка).

Что мы делаем дальше? Ну конечно, подаем P′ на вход ее собственный текст! И обнаруживаем, что P′ должна делать противоположное тому, что делает сейчас: работать вечно, если останавливается, или останавливаться, если работает вечно. Это дает нам противоречие, из которого следует, что P вообще не может существовать.

Очевидно, выбор между n³ и n² не имеет особого значения. Можно поставить вместо этого выбор между n¹⁷ и n¹⁶, между 3ⁿ и 2ⁿ и т. п. Но тут возникает интересный вопрос: можно ли подставить сюда любые функции f и g, такие, что f растет значительно быстрее g? Удивительно, но ответ – нет! Функция g должна обладать свойством, известным как конструируемость во времени, которое означает (в основном), что существует некоторая программа, которая останавливается за g (n) шагов, получив на вход n. Без этого свойства программа P′ не знала бы, на сколько шагов нужно моделировать M, и доказательство бы не прошло.

Вообще говоря, любая функция, которая может вам встретиться в обычной жизни, будет конструируемой во времени. Но в начале 1970-х гг. специалисты по теории вычислительной сложности придумали несколько необычных, стремительно растущих функций, которые не являются таковыми. И для этих функций вы реально можете получить произвольно большие прорехи в иерархии вычислительной сложности! К примеру, существует функция f, такая, что TIME(f(n)) = TIME(2f⁽ⁿ⁾). Бреееед.

Аналогом теоремы иерархии (по времени) является теорема иерархии (по памяти), которая утверждает, что существует задача, решаемая при наличии n³ бит памяти, но не решаемая при наличии n² бит.

Ну хорошо, следующий вопрос: в информатике нас обычно интересует наиболее быстрый алгоритм решения той или иной задачи, однако очевидно ли, что у каждой задачи есть самый быстрый алгоритм? Или может существовать задача, которая допускает бесконечный ряд алгоритмов, в котором каждый последующий быстрее предыдущего, но медленнее какого-то еще?

В противоположность тому, что вы могли бы подумать, это не просто теоретический кабинетный вопрос – это конкретный, очень практический кабинетный вопрос! В качестве примера рассмотрите задачу перемножения двух матриц n × n. Очевидный алгоритм занимает время O(n³). В 1968 г. Штрассен предложил более сложный алгоритм, занимающий время O(n^2,78). За этим последовала длинная цепь улучшений, кульминацией которой стал алгоритм Копперсмита и Винограда с оценкой O(n^2,376). После этого 23 года ничего не менялось, пока в 2011 г., незадолго до того, как эта книга отправилась в печать, Стозерс[26]26
  A. Stothers, On the complexity of matrix multiplication. Unpublished PhD Thesis, University of Edinburgh (2010). http://www.maths.ed.ac.uk/pg/thesis/stothers.pdf


[Закрыть] и затем Василевская[27]27
  V. Vassilevska Williams, Breaking the Coppersmith – Winograd barrier. In Proceedings of Annual ACM Symposium on Theory of Computing (2012). http://www.cs.berkeley.edu/~virgi/matrixmult.pdf


[Закрыть] объявили об улучшениях, дающих алгоритм с оценкой O(n^2,373). Но конец ли это? Может быть, существует алгоритм перемножения матриц за время порядка n²? Или более странная возможность: может ли быть, что для любого ε > 0 существует алгоритм перемножения матриц n × n за время O(n^2+ε), но по мере приближения ε к нулю эти алгоритмы становятся все более и более сложными, и так до бесконечности?

Понимаете, кое-что в материале о палеосложности по-настоящему нетривиально! (Может, тираннозавр рекс и был динозавром, но зубы у него были весьма острые!) В данном случае имеется результат 1967 г., известный как теорема ускорения Блума, который утверждает, что задачи, для которых нет самого быстрого алгоритма, действительно существуют. И не только это: существует задача P, такая, что для любой функции f, если для P имеется алгоритм на O(f(n)), для нее имеется также алгоритм на O(log f(n))!

Посмотрим, как это происходит. Пусть t(n) – оценка вычислительной сложности. Наша цель определить функцию f на множестве целых чисел со значениями в {0, 1}, такую, что если f может быть вычислена за O(t(n)) шагов, то она может быть вычислена также за O(t(n – i)) шагов для любого положительного целого i. Тогда, считая, что t растет достаточно быстро, получаем сколь угодно сильное ускорение: к примеру, если мы зададим t(n):= 2^t(n–1), то с определённостью t(n – 1) = O(log t(n)).

Пусть M₁, M₂,… будет упорядоченным списком машин Тьюринга. Далее, пусть S_i = {M₁, …, M_i} – множество, состоящее из первых i машин. Вот что мы делаем: получая на вход целое n, мы проходим по всем i от 1 до n. На i-й итерации мы моделируем все машины в Si, не «вычеркнутые» на итерациях от 1-й до (i – 1)-й. Если ни одна из этих машин не останавливается не более чем за t(n – i) шагов, то задаем f(i) = 0. В противном случае пусть M_j будет первой машиной, которая остановится не более чем за t(n – i) шагов. Затем определяем f(i) как 1, если M_j выдает 0, и как 0, если Mj выдает 1. (Иными словами, мы заставляем M_j ошибиться при вычислении f(i).) Мы также «вычеркиваем» M_j в том смысле, что M_j не нужно будет моделировать в дальнейших итерациях. Так определяется функция f.

Конечно, f(n) можно вычислить за O(n²t(n)) шагов, просто смоделировав всю описанную выше итеративную процедуру. Ключевое наблюдение таково: для любого целого i, если мы жестко пропишем результат итераций с 1-й по i-ю в наш алгоритм моделирования (то есть сообщим алгоритму, какие M_j вычеркиваются в этих итерациях), мы можем пропустить итерации 1… i и перейти сразу к итерации i + 1. Более того, считая, что мы начинаем с итерации i + 1, мы можем вычислить f(n) всего за O(n²t(n – i) шагов вместо O(n²t(n)) шагов. Так что чем больше информации мы вычислим предварительно, тем быстрее алгоритм будет работать при достаточно больших входных n.

Чтобы превратить эту идею в доказательство, главное, что нужно сделать, – это показать, что моделирование итеративной процедуры – практически единственный способ вычислить f, или, более точно, что любой алгоритм вычисления f требует по крайней мере t (n – i) шагов для некоторых i. Это, в свою очередь, подразумевает, что для вычисления f не существует более быстрых алгоритмов.