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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве меры сложности была также предложена алгоритмическая информация – кстати, Хайтин сначала назвал ее «алгоритмической сложностью». Но строки битов строки с высоким содержанием алгоритмической информации не выглядят сложными, они выглядят случайными; и действительно, алгоритмическую информацию также называют алгоритмической случайностью. Кроме того, строки битов с высоким содержанием алгоритмической информации легко создать: достаточно всего 100 раз подбросить монетку. Получившаяся строка битов, вероятно, будет иметь близкое к максимально возможному содержание алгоритмической информации. Мы с Хайнцем считали, что сложные вещи должны быть замысловатыми, структурированными и трудновоспроизводимыми. Для описания вещей с высоким содержанием алгоритмической информации может требоваться много битов, но почти все строки битов с высоким содержанием алгоритмической информации неструктурированны, и их легко создать.

Я продолжал читать, находя все больше определений сложности, но все они были вариациями на тему необходимых усилий или количества информации. Несколько лет спустя я сделал доклад об этих различных мерах сложности на конференции в Институте Санта-Фе, основанном в середине 1980-х Джорджем Коуэном, Мюрреем Гелл-Манном и группой старших научных сотрудников из соседнего Лос-Аламоса, которых интересовало изучение правил, дающих начало сложным системам и лежащих в их основе. Этот доклад назывался «Тридцать одна мера сложности» (Thirty-one Measures of Complexity), причем «тридцать один» было хорошо известным намеком на количество сортов мороженого Baskin-Robbins. Хотя я не опубликовал доклад под этим названием, молва о нем распространилась в Интернете, и в течение многих лет доклад о 31 способе измерения сложности был моей самой часто запрашиваемой работой, несмотря на то что ее просто не существовало. (Несколько лет назад я, наконец, опубликовал этот список в виде статьи{15}, просто для того, чтобы больше не отвечать на электронные письма, в которых меня просили выслать эту несуществующую статью.) Кстати говоря, за время от прочтения доклада до публикации статьи количество способов измерения сложности выросло с тридцати одного до сорока двух. (Длина нового списка побудила писателя Джона Хоргана в книге «Конец науки» (The End of Science) утверждать, что наука о сложных системах оказалась несостоятельной, так как исследователи не смогли договориться даже о том, что такое сложность, уже не говоря о каких-либо серьезных исследованиях в этой области.)