Программируя Вселенную. Квантовый компьютер и будущее науки - Сет Ллойд

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

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

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

Что нужно делать, чтобы это объяснение было проверяемым?[41] Чтобы вычислительное объяснение сложности работало, нужны два ингредиента: компьютер и обезьяны. Компьютер существует благодаря законам квантовой механики. Но где обезьяны? Какой физический механизм вводит информацию в нашу Вселенную, программируя ее с помощью строки случайных битов? Здесь нам тоже не нужно искать что-либо, кроме законов квантовой механики, которые постоянно вбрасывают новую информацию во Вселенную в виде квантовых флуктуаций. В ранней Вселенной, например, галактики формировались вокруг «зародышей» – мест, где плотность материи была чуточку выше, чем в других местах. Эти «зародыши» галактик возникли в результате квантовых флуктуаций: средняя плотность материи повсюду была одинаковой, но квантовая механика добавила случайные флуктуации, благодаря которым и начали формироваться галактики.

Квантовые флуктуации вездесущи и имеют тенденцию возникать в тех точках, где Вселенная наиболее чувствительна. Например, возьмем биологию. Мы получаем свою ДНК от отца и матери, но наша индивидуальная последовательность ДНК возникает в процессе рекомбинации, после того как сперма входит в яйцеклетку и вносит в нее свой генетический материал[42]. То, какие гены матери объединятся с какими генами отца, существенным образом зависит от химических и тепловых флуктуаций во время процесса рекомбинации, а эти химические и тепловые флуктуации имеют в своей основе квантовую механику. Квантовые события – и ничто иное – запрограммировали вашу ДНК так, что она отличается от ДНК ваших братьев и сестер. Вы и я, а также различия между нами произошли из квантовых событий. И так же из квантовых «зародышей» возникла сама Вселенная. Квантовые флуктуации – это и есть обезьяны, программирующие Вселенную.

Случайность возникает в вычислительной Вселенной из-за того, что начальное состояние Вселенной – это суперпозиция различных состояний программы, каждое из которых отправляет Вселенную по тому или иному пути вычислений, причем некоторые из этих путей приводят к сложному и интересному поведению. Квантово-вычислительная Вселенная следует всеми этими путями одновременно, квантово-параллельно, и эти пути соответствуют декогерентным историям, описанным выше. Так как истории вычислений декогерентны, мы можем обсуждать их за обедом; лишь одна (или другая) из этих историй произошла на самом деле. Одна из этих декогерентных историй соответствует Вселенной, которую мы видим вокруг.

Что такое сложность?

Вычислительная Вселенная спонтанно дает начало всем возможным формам вычисляемого поведения; все действия, которые можно запрограммировать, она программирует. Отчасти это поведение упорядоченное, отчасти случайное; иногда оно простое, иногда сложное. Но что такое сложность?

Я писал диссертацию по физике в Университете Рокфеллера, и однажды меня чуть не отчислили. Я поступил в Университет Рокфеллера потому, что он славится тем, что здесь поддерживают независимые исследования. Я сдал квалификационные экзамены и начал работу, связанную с ролью информации в квантово-механических системах и с тем, какое отношение квантовая обработка информации может иметь к фундаментальным процессам в физике, в том числе к квантовой гравитации. Иначе говоря, я занимался тем же самым, чем занимаюсь и сейчас, почти двадцать лет спустя. Научного руководителя у меня не было. И вот однажды (дело было в 1986 г.) в мой кабинет зашли два профессора и Хайнц Пэджелс, исполнительный директор Нью-Йоркской академии наук. «Ллойд, – сказали они, – вам следует прекратить работать над этой бредятиной и заняться темой, которую мы могли бы понять. В противном случае вам придется оставить Университет Рокфеллера».

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

Но над теорией струн тогда работало много людей, а квантовой информацией в то время почти никто не занимался. Позже я познакомился с теми, кто это делал, и стал с ними сотрудничать, но тогда я даже не знал их имен. Немедленным результатом визита было то, что я сдался и согласился посвятить следующие несколько месяцев решению двух традиционных проблем квантовой теории поля. Но самым лучшим следствием угрозы вылететь из аспирантуры было то, что я стал сотрудничать с Хайнцем Пэджелсом. Хайнц был большой оригинал. Он носил двубортные костюмы в тонкую полоску и дорогую лакированную обувь. С зачесанными назад седыми волосами и в ботинках а-ля мафиози он напоминал Джона Готти, только более стройного. В физике он тоже был большим оригиналом… и вот он решил поруководить мною.

Через четыре месяца я разделался с обеими проблемами, которыми мне поручили заниматься «для порядка». Через восемь месяцев я убедил Хайнца, что рассмотреть испарение черных дыр с точки зрения квантовой обработки информации – не такая уж плохая идея. Через год он уже брал меня с собой в Ист-Виллидж, где мы встречались с его еще более эксцентричными друзьями – большинство из них были актерами. Он также представил меня своей жене, Элейн, автору «Гностических Евангелий» (Gnostic Gospels), книги, полностью изменившей мои взгляды на социальную природу религии. Возможно, мне все еще светило ремесло таксиста, как и очень многим другим безработным физикам со степенью, но теперь мне было хотя бы не скучно.

Поворотный пункт наших интеллектуальных отношений наступил в тот день, когда Хайнц зашел в мой кабинет и сказал:

– Ладно, Сет, но как мы будем измерять сложность?

– Так мы не можем этого сделать! – ответил я. – Вещи становятся сложными как раз тогда, когда числом это измерить невозможно.

– Ерунда, – сказал Хайнц, – давай попробуем.

Спросить, как измерить сложность, – все равно что спросить, как измерить физику. Законы физики предлагают множество измеримых величин – энергия, расстояние, температура, давление, электрический заряд, но сама «физика» измеримой величиной не является. Точно так же, выявляя законы сложности, мы должны ожидать увидеть множество измеримых величин, составляющих сложную систему.

Я несколько месяцев читал о разных методах определения сложности. Первой концепцией, на которую я обратил внимание, была вычислительная сложность. Вычислительная сложность равна числу элементарных логических операций, которые нужно выполнить в ходе вычисления. (Связанная с ней концепция, пространственная вычислительная сложность, равна числу битов, используемых в ходе вычисления.) Вычислительная сложность – не столько мера сложности, сколько мера усилий, или ресурсов, необходимых для выполнения данной задачи. Есть множество вычислений, занимающих много времени и расходующих много места, но они не производят ничего сложного. Как мы увидим, вычислительная сложность – важный ингредиент хорошего определения сложности, но сама по себе она не является хорошим определением.