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

Здесь вы можете возразить, что даже в обычной жизни, без всяких путешествий во времени, всегда есть вероятность того, что ваш компьютер будет разбит метеоритом или из-за какого-то другого непредвиденного происшествия вполне «реальный» процесс вычисления отклонится от своей абстрактной математической модели! Тем не менее мы, как правило, не считаем, что этот очевидный факт как-то отражается на нашей теории сложности или означает, к примеру, что законы природы вообще не поддерживают универсальных вычислений. Так чем же отличается ситуация в случае присутствия на сцене CTC? Тем, что в этом случае мы делаем кое-что новое и экзотическое: просим природу найти нам неподвижную точку заданного физического процесса, но не говорим, какую именно неподвижную точку. В такой ситуации, если вокруг имеются «обманные» неподвижные точки — те, что не соответствуют никаким неподвижным точкам первоначальной схемы C, которую мы моделируем, и не требуют решения каких бы то ни было трудных вычислительных задач, то почему бы Природе не полениться немного и не выбрать одну из таких точек вместо одной из «трудных» неподвижных точек? Если так, то в присутствии CTC «загадочные» отказы компьютеров были бы нормой, а не экзотической аберрацией.

Чтобы решить эту проблему, необходимо было бы показать, что поиск неподвижной точки в реальных уравнениях эволюции Вселенной — заданных Стандартной моделью, квантовой гравитацией, чем-то еще — является PSPACE-полной задачей (и также что можно в принципе задать нужные начальные состояния). Принципиально важно: здесь недостаточно указать, что законы природы универсальны по Тьюрингу, поскольку легко построить игрушечные образцы «законов природы», универсальных по Тьюрингу, для которых неподвижные точки будут легко находиться. (В качестве иллюстрации представьте, что всякая физическая система содержит «контрольный бит» b и что вселенная осуществляет универсальное вычисление при b = 1 или тождественное при b = 0. Такая вселенная была бы так же способна на универсальное вычисление, как и наша, но при этом она всегда могла бы выдавать фиктивные неподвижные точки, установив b = 0.) Мы с Ватрусом показали лишь, что существуют вычислительно эффективные законы, для которых поиск неподвижных точек — это трудная вычислительная задача, но вопрос о том, относятся ли законы нашей настоящей Вселенной к этой категории, остается открытым.

Интересно отметить, что, по мнению Дойча, CTC не должны позволять решение трудных вычислительных задач. Ведь если бы они это позволяли, то нарушали бы тем самым то, что Дойч называет «эволюционным принципом», — это принцип, согласно которому «знание может возникать только в результате эволюционных процессов» (или, если перевести это на язык теоретической информатики, что NP-полные и другие аналогичные задачи не должны «решаться как по волшебству»). Иначе говоря, Дойч сказал бы, что окончательные законы природы, каковы бы они ни были, непременно воспользуются этими фиктивными неподвижными точками, избавив таким образом природу от необходимости решать PSPACE-полную задачу, чтобы гарантировать непротиворечивость вокруг CTC. Лично мне подобные рассуждении кажутся странными. Если бы замкнутые времениподобные траектории существовали, они, очевидно, заставили бы нас пересмотреть чуть ли не все наши представления о пространстве, времени, причинности и многих других вещах. Что, позвольте спросить, дает Дойчу такую уверенность в том, что эволюционный принцип пережил бы такой переворот, при том что многие другие тоже казавшиеся фундаментальными интуитивные знания не пережили бы? Коли на то пошло, почему не подкрепить эволюционный принцип и еще много чего, просто предположив, что замкнутые времениподобные траектории не могут существовать, — такая гипотеза, судя по всему, полностью согласуется со всем, что нам известно?

Как обычно, я закончу загадкой для следующей главы. Предположим, вы можете установить при помощи CTC только один бит за раз. Можно сделать сколь угодно много замкнутых времениподобных траекторий, но через каждую из них можно переслать лишь один бит, а не полиномиальное их количество. (В конце концов, мы не хотим быть экстравагантными!) Можете ли вы решать в этой альтернативной модели NP-полные задачи за полиномиальное время?

21. Космология и вычислительная сложность

Загадка из предыдущей главы: что можно вычислить при помощи «узких» CTC, способных пересылать назад во времени только по одному биту?

Решение. Пусть x — уважающий хронологию бит, а y — CTC-бит. Далее присвоим x: = x ⊕ y и y:= x. Предположим, что Pr[x = 1] = p, а Pr[y = 1] = q. Тогда, исходя из причинной непротиворечивости, p = q. Следовательно, Pr[x ⊕ y = 1] = p(1 — q) + q(1 — p) = 2p(1 — p).

Так что мы можем начать с экспоненциально малого p, а затем последовательно увеличивать его. Таким образом мы можем решать NP-полные задачи за полиномиальное время (и PP тоже, при условии, что у нас имеется квантовый компьютер).

Я начну с космологической модели The New York Times, то есть с того, что можно было до недавнего времени прочитать в популярных статьях. Там говорилось, что все зависит от плотности вещества во Вселенной. Существует параметр Ω, представляющий плотность массы Вселенной, и если он больше единицы, то Вселенная замкнута. Это значит, что плотность вещества во Вселенной достаточно высока, чтобы после Большого взрыва непременно произошло Большое сжатие. Более того, если Ω > 1, то пространство-время обладает сферической геометрией (с положительной кривизной). Если Ω = 1, то геометрия пространства плоская и Большого сжатия не будет. Если Ω < 1, то Вселенная незамкнута и обладает гиперболической геометрией. Считалось, что возможны именно эти три случая.

Сегодня мы знаем, что эта модель ошибочна по крайней мере в двух отношениях. Первое, в чем она неверна, — это, разумеется, тот факт, что в ней не учитывается космологический член. Насколько астрономы могут судить, пространство вокруг нас приблизительно плоское. Иначе говоря, никто пока не зарегистрировал нетривиальной кривизны пространства-времени в масштабах Вселенной. Даже если кривизна есть (а это возможно), она достаточно мала. При этом старая картина Вселенной заставляет считать, что наша Вселенная находится на грани Большого сжатия: измени плотность вещества хотя бы чуть-чуть, и получишь сферическую Вселенную, которая когда-нибудь схлопнется, или же гиперболическую, которая будет расширяться вечно. Но на самом деле состояние Вселенной вовсе не находится рядом с режимом, который гарантировал бы Большое сжатие. Почему нам это не грозит? Ну, следует посмотреть, из чего состоит плотность энергии во Вселенной. Есть материя, которая включает обычное вещество и скрытую массу (темную материю), есть излучение, а есть еще знаменитый космологический член —