Загадка из предыдущей главы: что можно вычислить при помощи «узких» 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, то Вселенная незамкнута и обладает гиперболической геометрией. Считалось, что возможны именно эти три случая.

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

Вдоль черной диагональной линии располагаются точки, соответствующие плоскому пространству. Здесь плотности энергии, связанные с космологической константой и с веществом, в сумме дают единицу. В прежней теории никакой космологической константы не было, но пространство тоже было плоским, так что мы находимся на пересечении двух сплошных черных линий. Вы видите, что вторая сплошная линия постепенно начинает загибаться кверху. Если вы находитесь выше этой линии, то Вселенная расширяется вечно, а если ниже — то она со временем вновь схлопывается. Так что если вы находитесь на пересечении, то эта позиция действительно соответствует границе между расширением и сжатием. Но с учетом того, что 70 % плотности энергии вселенной связано с Λ, мы, как вы видите, находимся где-то около пересечения диагональной линии с внутренним овалом, то есть далеко от тех областей, где Вселенная схлопывается.

Но это только одно из ошибочных положений простой трихотомии «сферический/плоский/гиперболический». Еще одна ошибка связана с тем, что геометрия Вселенной и ее топология — два разных вопроса. Если мы считаем Вселенную плоской, из этого не следует непосредственно, что она бесконечна. При постоянной положительной кривизне она была бы конечна. Представьте себе Землю; узнав, что она обладает постоянной положительной кривизной, вы сделали бы вывод о ее шарообразности. Я имею в виду, что да, она могла бы уйти в бесконечность сразу за пределами вашего поля зрения, но считая, что ее кривизна везде одинакова, математически она должна завернуться либо в шар, либо в другую более сложную конечную фигуру. Однако если пространство плоское, то это ничего не говорит вам о его конечности или бесконечности. Оно может быть устроено похоже на компьютерную игру, в которой если вы уходите за пределы экрана с одной стороны, то тут же появляетесь с другой. Это вполне совместимо с геометрически плоской формой, но соответствовало бы замкнутой топологии. Таким образом, ответ на вопрос о конечности или бесконечности Вселенной состоит в том, что мы, к несчастью, этого не знаем. (Больше об этом вы можете узнать из работы Корниша и Уикса[185].)

Студент: Но при положительной кривизне возможно также что-то, что уходит в бесконечность, как параболоид.

Скотт: Да, но это уже не постоянная кривизна. Постоянная — значит, одинаковая всюду.

Студент: Мне кажется, во всех этих картинах до сих пор отсутствует время. Как мы считаем: что время началось в какой-то фиксированной точке и идет вперед или что время ходит по кругу и возвращается назад в минус бесконечность?

Скотт: Все эти картины сходятся на том, что когда-то был Большой взрыв, так? Все это варианты космологии Большого взрыва.

Студент: Но если время началось в какой-то конечной точке, то время конечно. Но теория относительности говорит нам, что между временем и пространством на самом деле нет никакой разницы, верно?

Скотт: Нет, она этого не говорит. Она утверждает, что время и пространство взаимосвязаны нетривиальным образом, но время имеет иную сигнатуру метрики (metric signature), нежели пространство. Замечу в скобках, что это моя любимая мозоль. Один физик даже спросил меня, как может P отличаться от PSPACE, поскольку «теория относительности говорит нам, что время и пространство — это одно и то же». Ну, суть в том, что время имеет отрицательную сигнатуру. Это связано с тем фактом, что в пространстве вы можете двигаться и вперед, и назад, а во времени — только вперед. В предыдущей главе мы говорили о замкнутых времениподобных траекториях CTC. Там смысл в том, что CTC позволяют вам двигаться назад во времени, и вследствие этого время и пространство как вычислительные ресурсы действительно становятся эквивалентными. Но до тех пор, пока движение во времени остается односторонним, время — не то же самое, что пространство.

Студент: А можем ли мы зайти в пространстве достаточно далеко, чтобы замкнуть петлю?

Скотт: Если бы ваша рука была достаточно длинной, могли бы вы вытянуть ее вперед и ударить себя в затылок? Как я уже говорил, ответ в том, что мы этого не знаем.

Студент: В том, что касается распределения массы, мне кажется, мы считаем его конечным из-за Большого взрыва.

Скотт: Это результат неверных представлений о Большом взрыве. Большой взрыв происходит не в одной точке пространства; Большой взрыв — это событие, при котором рождается пространство-время. Стандартная аналогия состоит в том, что галактики — это небольшие пятнышки на воздушном шарике, и при надувании шарика дело не в том, что точки разбегаются, дело в том, что шарик становится больше. Если пространство-время незамкнуто, то вполне может оказаться, что в момент Большого взрыва у вас вместо кучки спрессованного вещества на самом деле было бесконечное количество вещества. Со временем бесконечная Вселенная растягивается, но в любой момент времени она все равно продолжается бесконечно. Если посмотреть на наш локальный горизонт, то увидишь, как все объекты разбегаются прочь друг от друга, но это только потому, что мы не можем проникнуть за горизонт и увидеть, что происходит там. Так что Большой взрыв — это не какой-то взрыв, имевший место в определенное время в определенной точке пространства; это просто начало целого многообразия.

Студент: Но разве не должна при этом масса/энергия распространяться быстрее скорости света?

Скотт: Еще один хороший вопрос; я рад, что могу объяснить хоть что-то! В неподвижной системе отсчета вы можете иметь две точки, которые, как кажется, удаляются друг от друга быстрее скорости света, но причина этого явления в том, что пространство в промежутке между ними расширяется. Эмпирическим фактом действительно является то, что далекие галактики уносятся прочь друг от друга быстрее света. Скорость света ограничивает скорость, с которой муравей может двигаться по поверхности раздувающегося шарика, а вовсе не скорость расширения самого шарика.

Студент: Значит, можно наблюдать, как объект уносится от тебя прочь быстрее скорости света?

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

Студент: Могут ли две галактики двигаться навстречу друг другу быстрее скорости света?

Скотт: При схлопывании могут.

Студент: Как мы обходим все те же старые парадоксы, которые возникают, когда мы разрешаем объектам двигаться быстрее света?

Скотт: Иными словами, почему расширение или сжатие со скоростями, превышающими скорость света, не порождает проблем причинности? Понимаете, именно в этом месте я начинаю уважать людей, которые по-настоящему понимают общую теорию относительности. Но позвольте и мне предложить объяснение: существуют, безусловно, возможные геометрии пространства-времени, к примеру те, в которых имеются кротовые дыры, или вращающаяся вселенная Гёделя, в которых имеются проблемы с причинностью. Но как насчет реальной геометрии, в которой мы живем? Здесь объекты просто удаляются друг от друга, и это невозможно использовать для пересылки сигналов со сверхсветовой скоростью. Что вы можете получить в нашей геометрии, так это объекты, которые расположены так далеко друг от друга, что, наивно говоря, они «никогда не должны были вступать в причинный контакт»; тем не менее они выглядят так, как если бы вступали. Так что гипотеза такова: в самом начале Вселенной был период стремительной инфляции, в ходе которого объекты могли прийти в равновесие между собой, и только после этого они были причинно разделены инфляцией.

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

Можно описать это в терминах масштабного фактора Вселенной. Измерим время t с начала Вселенной в покоящейся системе отсчета, связанной с реликтовым космическим излучением (обычный прием). Насколько «велика» Вселенная в зависимости от времени? Или, формулируя более строго, как изменялось расстояние a(t) между двумя заданными точками как функция времени? Согласно инфляционной гипотезе, в самом начале — при Большом взрыве — в течение нескольких планковских времен происходит тот самый громадный экспоненциальный рост. После этого идет некоторое расширение, но есть уже и гравитация, которая пытается стянуть Вселенную обратно. Получается, что в этот период масштабный фактор увеличивается как t2/3. Через десять миллиардов лет после Большого взрыва, когда на Земле только начинает формироваться жизнь, космологическая константа начинает брать верх над гравитацией. После этого идет просто экспоненциальное расширение, как в самом начале, но не так быстро.

Интересный вопрос: почему все мы живем в период, когда космологическая константа дает 70 %, а вещество — 30 % плотности энергии? Почему бы одному из компонент не давать почти весь вклад, а второму не быть пренебрежимо малым? Почему существование человека укладывается в небольшое окошко, где оба компонента имеют один порядок величины? Конечно, можно воспользоваться антропным принципом: если бы мы жили в более позднюю эпоху, то здесь нас, может, было бы двое или трое, а остальные находились бы за космологическим горизонтом. Вселенная была бы куда менее наполненным местом.

Физики описали бы космологическую константу так, но я описал бы ее как просто величину, обратную числу битов, которые могут быть когда-либо использованы в вычислениях! Более точно:

В планковских единицах космологическая константа приблизительно равна 10^–121, поэтому 10¹²² — приблизительно максимальное число битов, которые могут быть когда-либо использованы в вычислениях в физическом мире. (Позже мы еще поговорим о том, что конкретно имеется в виду под максимальным числом битов, которые могут быть задействованы в вычислениях.) На чем основана такая интерпретация космологической константы?

Студент: А каково определение космологической константы?

Скотт: Это энергия вакуума. Это с точки зрения физики. Люди не определяют явления и вещи, они их наблюдают. Они не знают, что такое на самом деле энергия вакуума, они просто знают, что она существует. Это энергия пустого пространства, происхождение которой может очень разным.

Студент: Усредненная?

Скотт: Ну да, но она, судя по всему, очень близка к постоянной всюду, где человек в состоянии ее измерить, и во времени тоже. Никто пока не обнаружил никаких отклонений от допущения о том, что она везде одинакова. Можно, к примеру, представить ее так: в вакууме всегда существуют пресловутые пары частица/античастица, они постоянно образуются и тут же аннигилируют друг с другом. Пустое пространство — чрезвычайно сложная штука! Поэтому неудивительно, наверное, что оно должно обладать ненулевой энергией. На самом деле в квантовой теории поля трудно объяснить не почему существует какая-то космологическая константа, а почему по величине она не в 10120 раз больше, чем на самом деле! Наивное рассуждение с позиций квантовой теории поля предсказывает, что вся вселенная должна попросту взорваться в одно мгновение.

Студент: Так что, это ΩΛ?

Скотт: Нет, ΩΛ — это всего лишь доля полной плотности энергии, обусловленной космологической константой. Так что этот параметр зависит также от плотности вещества и, в отличие от самой Λ, может изменяться со временем.

Чтобы понять, какое все это имеет отношение к вычислениям, нам придется отвлечься и поговорить немного о голографическом пределе. Это одна из очень немногих вещей, которые, похоже, мы все же знаем о квантовой гравитации; в этом вопросе специалисты по теории струн и сторонники петлевой квантовой гравитации сходятся. Плюс это некая граница, то есть оценка, а этим языком я владею. Мое рассуждение будет следовать неплохой обзорной работе Буссо[186]. Я включу эту статью в список обязательного чтения, но только для физиков.

Мы уже видели, что существует планковская площадь Ее можно получить, скомпоновав кучу физических констант таким образом, чтобы единицы сократились и осталась длина в квадрате. Сам Планк проделал такую операцию примерно в 1900 г. Ясно, что это очень глубокая штука, потому что для ее получения вы сваливаете в одну кучу постоянные Ньютона и Планка и добавляете к ним скорость света, а получаете величину в единицах площади порядка 10^–69 м².

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

Студент: А этот вывод объясняет, почему нужно делить на 4, а не, скажем, на 3?

Скотт: Специалисты по теории струн считают, что у них есть объяснение этому. Это большой успех, который позволяет им взять верх над остальными квантовомеханическими подходами! У сторонников петлевой квантовой гравитации константы не сходятся, и им приходится подстраивать их вручную при помощи так называемого параметра Иммирци. (Примечание: после 2006 г. из лагеря петлевой квантовой гравитации появились утверждения о том, что эту проблему им удалось решить.)

Грубая интуиция говорит, что если вы пытаетесь построить куб из битов (скажем, жесткий диск) и делаете его все больше и больше, то рано или поздно он коллапсирует в черную дыру. После этого вы можете и дальше вкладывать туда все новые биты, но тогда эта информация просто прилипает к горизонту событий; как — этого никто до конца не понимает. И как бы то ни было, с этого момента содержание информации начинает расти пропорционально площади поверхности.

Чтобы это «вывести», первое, что нам потребуется, — это так называемый предел Бекенштейна. Именно Бекенштейн еще в 1970-е гг. осознал, что черные дыры должны обладать энтропией. Почему? Если энтропии нет и вы роняете что-то в черную дыру, это что-то исчезает, что на первый взгляд нарушает второе начало термодинамики. Более того, черные дыры демонстрируют всевозможные однонаправленные свойства: в черную дыру можно уронить что-то, но невозможно извлечь это что-то обратно; можно смешать две черные дыры и получить третью, большего размера, но невозможно расщепить одну черную дыру на несколько более мелких. Косвенным образом это чрезвычайно сильно напоминает энтропию. Задним числом это очевидно даже мне.

Итак, что такое предел Бекенштейна? Это утверждение о том, что в планковских единицах энтропия S любой заданной области удовлетворяет условию

где k — постоянная Больцмана, E — энергия данной области, а R — ее радиус (опять же в планковских единицах). Почему это так? В сущности, эта формула объединяет π, постоянную Больцмана, постоянную Планка и скорость света, так что она просто обязана быть верна. (Я учусь думать как физик. Шучу!) Если серьезно, то она отталкивается от мысленного эксперимента, в котором мы роняем каплю какого-то вещества в черную дыру и выясняем, насколько должна увеличиться температура этой черной дыры (при этом мы используем физику, в которую здесь вдаваться не будем), а затем используем соотношение между температурой и энтропией, чтобы определить, насколько должна возрасти энтропия черной дыры. После этого мы применяем второе начало термодинамики и говорим, что капля, которую мы туда роняем, должна была иметь энтропию не более той, что получила при этом черная дыра. В противном случае полная энтропия Вселенной снизилась бы, что противоречит Второму началу.

Студент: А разве площадь не пропорциональна квадрату радиуса?

Скотт: Пропорциональна.

Студент: Тогда почему в формуле предела Бекенштейна фигурирует R, а не R²?

Скотт: Мы к этому подходим!

Это факт номер один. Факт номер два — это оценка Шварцшильда, которая гласит, что энергия системы может быть не более чем пропорциональна ее радиусу. В планковских единицах E ≤ R/2. Это опять же потому, что если бы вам пришлось паковать вещество/энергию более плотно, то рано или поздно они коллапсировали бы в черную дыру. Если мы хотим построить жесткий диск, в котором на представление каждого бита тратится фиксированное количество энергии, то мы можем изготовить одномерную ленту Тьюринга, которая будет продолжаться до бесконечности, но если попытаться сделать ее хотя бы двумерной, то, став достаточно большой, она коллапсирует в черную дыру. По этому соотношению, радиус черной дыры пропорционален ее массе (и энергии). Можно сказать, что черная дыра дает максимальный эффект: позволяет впихнуть в заданный радиус максимальное количество энергии. Так что черные дыры максимальны по крайней мере в двух отношениях: они имеют больше всего энергии на единицу радиуса и также больше всего энтропии на единицу радиуса.

Итак, если принять эти два факта, можно объединить их в одно утверждение:

S ≤ 2π ER ≤ π R ² = A /4.

То есть энтропия любой области не превышает площади ее поверхности в планковских единицах, деленной на 4. Что до объяснения, почему мы делим здесь A на 4, то мы, в сущности, сводим задачу к объяснению, почему E ≤ R/2. π уходит, поскольку площадь поверхности сферы составляет 4πR².

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

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

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

Студент: Лента схлопнется в черную дыру?

Скотт: Как я уже сказал, лента может быть одномерной и сколь угодно длинной.

Студент: А что если лента начнет удаляться от вас?

Скотт: Верно! Вот ваши биты перед вами, а потом стоит вам отвернуться всего лишь на пару десятков миллиардов лет — и они из-за расширения Вселенной отдалились от вас и пропали за космологическим горизонтом.

Смысл в том, что недостаточно просто иметь все эти биты доступными где-то во Вселенной. Вы должны иметь возможность контролировать их все и задавать их, а затем вам важно иметь доступ к ним позже, в ходе вычисления. Буссо формализует эту идею при помощи штуки, которую он называет «ромбом причинности», но я бы назвал просто вычислением с входом и выходом. Идея в том, что у вас есть некоторая начальная точка P и конечная точка Q, а затем вы смотрите на пересечение светового конуса, направленного вперед из точки P, и светового конуса, направленного назад из точки Q. Это и есть ромб причинности.

Идея в том, что в любом эксперименте, который мы реально можем провести (в любом вычислении, которое мы реально можем осуществить), у нас обязательно будет некая начальная точка эксперимента и некая конечная точка, где мы получаем свои данные (считываем выходные данные). Нам важно не полное количество энтропии во Вселенной, но лишь полное количество энтропии, которая может содержаться в одном из таких ромбов причинности.

С тех пор Буссо опубликовал еще одну статью[187], в которой утверждает, что если вы находитесь в пространстве де Ситтера — то есть в пространстве с космологической константой — примерно таком же, как пространство, в котором мы, судя по всему, живем, то количество энтропии, которая может содержаться в одном из таких ромбов причинности, не превышает 3π/Λ. Вот почему в нашей Вселенной существует предел, приблизительно равный 10¹²² бит. Смысл в том, что Вселенная расширяется с экспоненциальной скоростью, и поэтому точка, расположенная в настоящий момент на линии нашего горизонта, еще через 15 млрд лет или около того (то есть еще через нынешний возраст Вселенной) окажется от нас на расстоянии в некоторое постоянное число раз больше.

Студент: Где вы помещаете точки P и Q, чтобы получить это число?

Скотт: Их можно поместить где угодно. Вы ищете максимум по всем P и Q. Именно это здесь главное.

Студент: И где же этот максимум возникает?

Скотт: Ну, выбираем P где угодно, затем выбираем Q, скажем, в паре десятков миллиардов лет в ее причинном будущем. Если через 20 млрд лет или около того вы еще не свернете свое вычисление, то данные на другом конце памяти отступят за ваш космологический горизонт. Невозможно на самом деле построить работающий компьютер, радиус которого будет больше 20 млрд световых лет. Это неприятная, но правда.

Студент: Меняется ли Λ со временем?

Скотт: Преобладает мнение, что нет. Могла бы, в принципе, но существуют довольно сильные экспериментальные ограничения в отношении того, на сколько. А вот доля ΩΛ плотности энергии, приходящаяся на Λ, изменяется точно. По мере того как Вселенная становится все более и более разреженной, доля энергии, за которую отвечает Λ, становится все больше и больше, хотя сама Λ остается неизменной.

Студент: Но радиус Вселенной меняется.

Скотт: Да. В нынешнюю эпоху мы видим все больше и больше прошлого, по мере того как свет доходит до нас из все более отдаленных мест. Но как только Λ начнет брать верх над веществом, радиус наблюдаемой Вселенной стабилизируется в состоянии примерно 10 млрд световых лет или около того.

Студент: Почему именно 10 млрд световых лет?

Скотт: Потому что с вашей точки зрения объекты, находящиеся на этом расстоянии, будут удаляться от вас со скоростью света, если нет уравновешивающего влияния гравитации.

Студент: Так это просто совпадение, что нынешний размер наблюдаемой Вселенной составляет примерно такую величину?

Скотт: Либо совпадение, либо нечто более глубокое, чего мы пока до конца не понимаем!

Все это прекрасно, но я обещал, что мы еще поговорим о вычислительной сложности. Итак, если голографический предел в сочетании с космологической константой накладывает конечный верхнюю границу на число битов в любом возможном вычислении, то можно было бы сказать, что мы можем решать только задачи, решаемые за постоянное время! При этом есть ощущение, что в каком-то смысле это сводит на нет всю теорию вычислительной сложности. К счастью, из этого тупика есть элегантный выход: мы говорим, что теперь нас интересует асимптотика не только по n (размеру входной строки), но и по 1/Λ. Забудьте на время, что Λ имеет известное (крохотное) значение, и представьте ее себе как переменный параметр — и теория сложности вернется!

Принимая этот момент во внимание, позвольте мне заявить следующее: предположим, что вселенная (1 + 1) — мерна, то есть имеет одно пространственное и одно временное измерение, и характеризуется космологической константой Λ. Тогда класс задач, которые мы в состоянии решить, входит в DSPACE (1/Λ): это класс задач, которые способна решить детерминистская машина Тьюринга с использованием ~1/Λ клеток ленты. Более того, он равен DSPACE (1/Λ), в зависимости от того, какие допущения вы готовы сделать о физике процесса. И уж во всяком случае он включает DSPACE (1/√Λ).

Во-первых и в-главных: почему мы не можем сделать больше чем DSPACE (1/Λ)?

Ну, если подходить к вопросу формально, позвольте мне определить модель вычисления, которое я назову машиной Тьюринга для космологической константы. В этой модели у нас есть бесконечная лента для машины Тьюринга, но теперь на каждом шагу по времени, между каждыми двумя клетками, существует независимая вероятность Λ того, что сформируется новая клетка с символом «*» в ней. На первый взгляд это кажется разумной моделью того, как Λ будет влиять на вычисление. Далее, если считывающая головка машины находится на некоторой клетке, то клетки на расстоянии 1/Λ от нее будут выглядеть удаляющимися от головки со скоростью в среднем одна клетка за шаг. Таким образом, вы не можете рассчитывать добраться до этих клеток хоть когда-нибудь. Всякий раз, когда вы будете делать шаг в их направлении, где-то в промежутке, вероятно, будет возникать новая клетка. (В этой модели скорость света можно считать равной одной клетке за шаг по времени.) То есть класс задач, которые вы будете в состоянии решить, обязательно войдет в DSPACE (1/Λ), поскольку вы всегда можете просто записать содержимое клеток в пределах расстояния 1/Λ от текущего положения головки и не обращать внимания на все остальные клетки ленты.

Но можем ли мы в реальности получить DSPACE (1/Λ)? Можно придумать очень простой алгоритм, позволяющий это сделать. А именно: представьте себе свои 1/Λ битов как стадо животных, которые постоянно норовят разойтись в разные стороны. Вам приходится непрерывно сдерживать их при помощи лассо, подобно этакому космологическому ковбою. Иными словами, ваша считывающая головка будет просто шагать вперед и назад по очереди, сжимая биты, которые постоянно норовят расползтись, и одновременно выполняя вычисления с ними. Далее, вопрос в том, сможете ли вы на самом деле удержать биты при помощи лассо за время О (1/Λ)? Я не писал для этого доказательства, но я не думаю, что это можно сделать за время меньшее чем ~1/Λ² при помощи стандартной считывающей головки машины Тьюринга (не обладающей, к примеру, способностью уничтожать клетки ленты). С другой стороны, вы определенно можете удержать ~1/√Λ битов за время О(1/Λ). Следовательно, вы можете вычислить DSPACE (1/√Λ). Я предполагаю, что это строгая оценка.

Второй интересный момент — то, что в пространстве двух и более измерений вы не получите той же самой картины. В двух измерениях радиус тоже удваивается за время, примерно равное 1/Λ, но даже для того, чтобы посетить все биты, которые нужно удерживать, здесь требуется время порядка 1/Λ². Так что мы можем спросить, существует ли что-то, что мы можем сделать за время 1/Λ на двумерной квадратной решетке, чего мы не можем сделать за время 1/Λ на одномерной ленте. Вы здесь имеете 1/Λ² пространство, и интуитивно кажется, что невозможно за время 1/Λ использовать больше чем 1/Λ клеток решетки; непонятно, однако, действительно ли это так. Разумеется, если хочется повеселиться, вы можете задать все те же вопросы для квантовой машины Тьюринга.

Еще о чем можно спросить, это о сложности запросов (query complexity) в этой модели. К примеру, допустим, что вы потеряли ключи и они могут при этом оказаться в любой точке вселенной. Если они находятся где-то в пределах вашего космологического горизонта, а ваше пространство одномерно, то вы в принципе можете их найти. Вы можете пройти все пространство в пределах своего горизонта за время O(1/Λ). Но уже при двух измерениях число локаций, которые вы в состоянии проверить прежде, чем большая часть наблюдаемой вселенной отступит за горизонт, сходно лишь с корнем квадратным от числа всех возможных локаций. Вы можете выбрать какое-то отдаленное место, переместиться туда, — и к моменту вашего возвращения область удвоится в размерах.

В квантовом случае есть выход: воспользоваться алгоритмом Гровера! Напомню: алгоритм Гровера позволяет нам провести поиск в базе данных, содержащей N записей, всего за √N шагов. На первый взгляд этого достаточно, чтобы просмотреть двумерную базу данных размером порядка наблюдаемой вселенной. Но есть одна проблема. Представьте, как на самом деле работает алгоритм Гровера. Шаги-запросы в нем чередуются с шагами увеличения амплитуд. Для этого нужно собрать все эти амплитуды в одном месте, так чтобы над ними можно было осуществить предложенную Гровером операцию отражения. Если представить себе квантового робота, который ищет что-то в двумерной базе данных размером √N × √N, то ему потребуется всего лишь √N итераций алгоритма Гровера, поскольку всего в базе содержится N записей, но каждая итерация займет √N времени, поскольку роботу придется собирать результаты всех запросов. Это проблема, поскольку мы при этом не получаем, кажется, никаких преимуществ по сравнению с классическим случаем. Следовательно, предложенное решение по поиску в базе данных размером со вселенную, судя по всему, работать не будет. Хотя при трех измерениях оно, кажется, все же даст нам некоторое преимущество. Если представить себе трехмерный жесткий диск, то длина стороны здесь будет равна N^1/3, так что нам потребуется √N итераций по Гроверу, каждая из которых займет время N^1/3; в итоге суммарное время составит N^5/6. Это, по крайней мере, чуть лучше, чем N. По мере увеличения числа измерений полное время будет постепенно приближаться к √N. К примеру, если бы пространство имело 10 полноценных измерений, мы имели бы суммарное время операции, равное N^12/22.

В работе, написанной мною в соавторстве с Андрисом Амбайнисом[188] много лет назад, мы показали, что можно воспользоваться рекурсивным вариантом алгоритма Гровера для поиска в двумерной решетке с затратами времени порядка √N log^3/2 N. Для трех и более измерений порядок времени составит просто √N. Я могу высказать кое-какие самые базовые догадки о том, как работает наш алгоритм. При этом используется стратегия «разделяй и властвуй», то есть вы делите свою решетку на кучку меньших решеток. После этого вы можете и дальше делить эти меньшие решетки на еще более мелкие подрешетки и применять к каждой подрешетке местный процесс алгоритма Гровера.

В качестве первого шага можно сказать даже, что вы просматриваете каждую строку отдельно. Просмотр каждой строки занимает всего √N времени, а затем вы можете вернуться назад и собрать все результаты воедино. После этого можно провести поиск Гровера по √N строк, каждый проход займет время N^1/4; полное время при этом получится равным N^3/4.

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