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

Но хорошо, человеческий мозг – это водянистая, рыхлая, неаккуратная штука, и мы, возможно, не смогли бы поддерживать его в состоянии когерентной суперпозиции на протяжении 500 миллионов лет. Чем можно заменить этот эксперимент? Ну, мы могли бы поместить компьютер в состояние суперпозиции. Чем сложнее компьютер – чем сильнее он напоминает мозг и нас самих, тем дальше мы сможем отодвинуть ту самую «линию» между квантовым и классическим. Сами видите, от этого до идеи квантовых вычислений остался всего один крохотный шажок.

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

Ну, на первый взгляд все это кажется каким-то скучным. Но, когда привыкаешь к подобной работе, мне кажется, обнаруживаешь, что это… все равно скучно!

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

2. Множества

Здесь мы будем говорить о множествах. Что будут содержать эти множества? Другие множества! Как куча картонных коробок, открыв которые, обнаруживаешь внутри только новые картонные коробки, и так далее, до самого дна.

Вы можете спросить: «Какое отношение все это имеет к книге о квантовых вычислениях?»

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

Мне, вероятно, следует без обиняков сказать вам, что я собираюсь втиснуть весь курс математики в эту одну главу. С одной стороны, это означает, что я не рассчитываю всерьез, что вы все поймете. С другой стороны, в той мере, в какой поймете, – замечательно! Вы получаете целый курс математики в одной главе! Добро пожаловать.

Итак, начнем с пустого множества и посмотрим, как далеко нам удастся пройти.

Пустое множество

Вопросы есть?

На самом деле, прежде чем говорить о множествах, нам необходимо обзавестись языком для разговора о множествах. Язык, который придумали для этого Фреге, Рассел и другие, называется логикой первого порядка. Он включает в себя булевы функции (и, или, не), знак равенства, скобки, переменные, предикаты, кванторы («существует» и «для любого»[10]10
  У автора – «для всех» (for all). – Прим. пер.


[Закрыть]) – и, пожалуй, все. Говорят, что физики испытывают со всем этим сложности… Эй, потише, я просто пошутил. Если вы прежде не встречались с таким способом мышления, значит, не встречались, ничего страшного в этом нет. Но давайте все же пойдем навстречу физикам и пробежимся по основным правилам логики.

Правила логики первого порядка

Все правила здесь говорят о том, как составлять предложения, чтобы они были корректны – что, говоря по-простому, означает «тавтологически истинны» (верны для всех возможных подстановок переменных)[11]11
  Упрощая, автор использует далее как синонимы слова valid, которое описывает корректность (выводимость) логической формулы, и true, характеризующее истинность конкретного высказывания. – Прим. пер.


[Закрыть], но что мы пока можем представить просто как комбинаторное свойство определенных символьных строк. Я буду печатать логические предложения другим шрифтом, чтобы их было легко отличить от окружающего текста.

• Пропозициональные тавтологии: A или не A, не (A и не A) и т. п. – истинны.

• Modus ponens (правило отделения): если A истинно и из A следует B истинно, то B истинно.

• Правила равенства: высказывания x = x; из x = y следует y = x; если x = y и y = z, то x = z; и из x = y следует f (x) = f (y) – истинны.

• Замена переменных: при изменении имен переменных высказывание остается истинным.

• Исключение квантора: если для всех x A (x) истинно, то A (y) истинно для любого y.

• Добавление квантора: если истинно A (y), где y – переменная без ограничений, то для всех x, A (x) истинно.

• Правило квантификации: если не (для любого x, A (x)) истинно, то существует такой x, что не (A (x)) истинно.

Приведем в качестве примера аксиомы Пеано для неотрицательных целых чисел, записанные в терминах логики первого порядка. В них S(x) – это функция следования, интуитивно S(x) = x + 1, и я предполагаю, что функции определены заранее.

Аксиомы Пеано для неотрицательных целых чисел

• Нуль существует: существует такое z, что для любого x, S(x) не равно z. (Это z принимается за 0.)

• Каждое целое число имеет не более одного предшественника: для любых x, y если S(x) = S(y), то x = y.

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

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

Так вот, именно поэтому я и не считаю, что аксиомы и формальную логику можно использовать для подведения под арифметику более надежного фундамента. Если вы почему-то не согласны с тем, что 1 + 1 = 2, то сколько ни изучай математическую логику, понятнее это не станет! Тем не менее все эти штучки безумно интересны не менее чем по трем причинам.

1. Ситуация изменится, как только мы начнем говорить не о целых числах, а о разных размерах бесконечности. Там формулирование аксиом и разбор следствий из них – это практически все наши инструменты!

2. Как только мы все формализовали, можно запрограммировать компьютер и заставить его думать за нас:

предположение 1: для любого x если A (x) истинно, то B (x) истинно;

предположение 2: существует x такой, что A (x) истинно;

вывод: существует x такой, что B (x) истинно.

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

3. Помимо того что доказательства для нас будет искать компьютер, мы сможем работать с этими доказательствами как с математическими объектами, что откроет путь к мета-математике.

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

Аксиомы теории множеств

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

• Пустое множество: существует пустое множество, то есть множество x, для которого не существует такого y, что y ∈ x.

• Аксиома объемности: если в два множества входят одни и те же члены, то эти множества равны. То есть для любых x и y если (z ∈ x тогда и только тогда, когда z ∈ y для любого z), то x = y.

• Аксиома пары: для любых множеств x и y существует множество z = {x, y}, то есть множество z, такое, что для любого w w ∈ z тогда и только тогда, когда (w = x или w = y).

• Аксиома суммы: для любых множеств x существует множество, равное объединению всех множеств, содержащихся в x.

• Аксиома бесконечности: существует множество x, содержащее пустое множество и содержащее также {y} для любого y ∈ x. (Почему в этом x должно содержаться бесконечное число элементов?)

• Аксиома степени (множество всех подмножеств): для любого множества x существует множество, состоящее из всех подмножеств x.

• Аксиома замены (на самом деле бесконечное число аксиом, по одной для каждой функции A, устанавливающей соответствие одних множеств другим): для любого множества x существует множество z = {A(y) | y ∈ x}, которое образуется в результате применения A ко всем элементам x. (Технически следовало бы определить также, что подразумевается под «функцией, устанавливающей соответствие одних множеств другим»; сделать это можно, но я не буду здесь этим заниматься.)

• Фундирование (аксиома регулярности): в любом непустом множестве x имеется элемент y, такой, что для любого z либо z ∉ x, либо z ∉ y. (Это техническая аксиома, смысл которой в том, чтобы исключить такие множества, как {{{{…}}}}.)

Эти аксиомы, известные как аксиомы Цермело – Френкеля, служат фундаментом практически для всей математики. Поэтому я решил, что вам стоит посмотреть на них хотя бы раз в жизни.

Ну хорошо, один из самых базовых вопросов, которые мы можем задать о множестве, звучит так: насколько оно велико? Каков его размер, его мощность? В смысле, сколько в нем элементов? Вы можете сказать, что это просто: достаточно пересчитать элементы. Но что, если их бесконечно много? Скажите, целых чисел больше, чем нечетных целых чисел? Это приводит нас к Георгу Кантору (1845–1918) и первому из нескольких его громадных вкладов в копилку человеческого знания. Он сказал, что два множества равны по мощности тогда и только тогда, когда их элементы можно поставить в строгое соответствие попарно, то есть один к одному. И точка. А если, как бы вы ни пытались распределить элементы по парам, в одном из множеств все равно остаются лишние, значит, то множество, где остаются лишние элементы, большее из двух.

Какой может быть мощность множества, или, иначе, его кардинальное число? Разумеется, существуют множества конечной мощности, по одному на каждое натуральное число. Затем идет первая бесконечная мощность, мощность множества целых чисел, которую Кантор назвал ℵ0 («алеф-нуль»). Множество рациональных чисел обладает той же мощностью ℵ0; иначе этот факт можно выразить, сказав, что рациональные числа являются счетными – в том смысле, что их можно поставить в попарное соответствие с целыми числами. Иными словами, мы можем составить бесконечный список таким образом, что рано или поздно в нем появится каждое рациональное число.

Как доказывается, что множество рациональных чисел счетно? Вы никогда не видели этого доказательства? Ну хорошо. Для начала запишем 0 и добавим все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равна 2. Затем добавляем к списку все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равно 3. И так далее. Ясно, что любое рациональное число рано или поздно появится в этом списке. Следовательно, их бесконечное количество счетно. Что и требовалось доказать.

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

С доказательством этого вы тоже не встречались? Ну хорошо, хорошо. Пусть у вас имеется бесконечное множество A. Мы покажем, как получить другое бесконечное множество B, которое будет больше, чем A. Просто возьмем в качестве множества B множество всех подмножеств A, которое гарантированно существует, согласно аксиоме о степенном множестве. Откуда мы знаем, что B больше, чем A? Ну предположим, что мы смогли каждому элементу a ∈ A поставить во взаимно однозначное соответствие элемент f (a) ∈ B, так что лишних элементов B не осталось. Тогда мы можем определить новое подмножество S ⊆ A, состоящее из всех a, которые не входят в подмножество f (a). Такое S также является элементом B. Но, заметьте, S не может соответствовать никакому a ∈ A, поскольку в противном случае a содержалось бы в f (a) тогда и только тогда, когда оно не содержалось бы в f (a). Получили противоречие. Следовательно, B больше A, и мы получили бесконечность большую, чем та, с которой мы начали.

Это определенно одно из четырех или пяти величайших доказательств во всей математике – и опять же полезно посмотреть на него хотя бы раз в жизни.

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

0, 1, 2, 3, …

Затем, говорим мы, определим нечто, что будет больше любого натурального числа:

ω.

Что идет после ω?

ω + 1, ω + 2, …

Далее, что идет после всего этого?

2ω.

Так, мы ухватили идею:

3ω, 4ω, …

Так, мы ухватили идею:

ω², ω³, …

Так, мы ухватили идею:

ω^ω, _ωω^ω, …

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

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

А теперь кое-что интересное. Все ординальные числа, которые я перечислил, обладают одним особым свойством: они имеют не более счетного количества (то есть не более ℵ₀) предшественников. Что, если рассмотреть множество всех ординальных чисел с не более чем счетным числом предшественников? Ну, у такого множества тоже имеется следующий элемент, назовем его α. Но сколько предшественников у α, тоже ℵ₀? Разумеется, нет, поскольку в противном случае α не был бы следующим элементом по отношению к нашему множеству, а входил бы в это множество! Множественно предшествующих α элементов обладает следующей возможной мощностью, которая называется ℵ₁.

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

Таким образом, начиная с ℵ₀ (мощность множества целых чисел), мы уже видели два разных способа получить «большие бесконечности, чем бесконечность». Один из этих способов выдает мощность множества множеств целых чисел (или, что то же самое, мощность множества действительных чисел), которую мы обозначаем 2^ℵ₀. Другой способ выдает ℵ₁. Можно ли сказать, что 2ℵ₀ равно ℵ₁? Или скажем иначе: существует ли бесконечность промежуточного размера между бесконечностью целых чисел и бесконечностью действительных чисел?

Этот вопрос стоял первым в списке задач Давида Гильберта, предложенных им в 1900 г. Более полувека он оставался одной из великих нерешенных математических задач, пока не получил «решения» (оказавшегося несколько обескураживающим, как вы увидите).

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

Кроме континуум-гипотезы, существует еще одно утверждение касательно бесконечных множеств, которое никто не мог доказать или опровергнуть, исходя из аксиом Цермело – Френкеля. Это утверждение – печально известная аксиома выбора, в которой говорится, что если у вас имеется (возможно, бесконечное) множество множеств, то можно сформировать новое множество, взяв по одному элементу из каждого множества. Звучит разумно, не правда ли? Вот только если вы принимаете это утверждение, то вам придется признать также, что существует способ разрезать шар на конечное число кусочков, а затем собрать из этих же кусочков новый шар в тысячу раз большего размера. (Это «Парадокс Банаха – Тарского». Следует признать, что отрезать такие «части» ножом довольно проблематично…)

Но почему аксиома выбора приводит к таким драматическим последствиям? В основном потому, что утверждает, что некоторые множества существуют, но не дает никакого правила по формированию этих множеств. Как сказал по этому поводу Бертран Рассел, «чтобы взять по одному носку от каждой из бесконечного числа пар носков, требуется аксиома выбора, а для ботинок такой аксиомы не требуется». (Какая разница?)

Оказывается, аксиома выбора эквивалентна утверждению о том, что любое множество может быть вполне упорядоченным: иными словами, элементы любого множество можно попарно поставить в соответствие порядковым числам 0, 1, 2, …, ω, ω + 1, …, 2ω, 3ω, … вплоть до некоторого порядкового числа. Если подумать, к примеру, о множестве действительных чисел, это представляется далеко не очевидным.

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

Хотите убедиться в обратном? Почему аксиома выбора подразумевает, что любое множество можно полностью упорядочить? Да?

Хорошо! У нас имеется множество A, которое мы хотим полностью упорядочить. К каждому собственному[12]12
  Собственным подмножеством называется подмножество, не совпадающее с самим множеством. – Прим. пер.


[Закрыть] подмножеству B ⊂ A мы применим аксиому выбора, чтобы выбрать элемент f(B) ∈ A – B (где A – B означает множество всех элементов A, которые не являются также элементами B). Теперь мы можем начать упорядочение A так: пусть s₀ = f({}), далее пусть s₁ = f({s₀}), s2 = f({s₁}) и т. п.

Может ли этот процесс продолжаться до бесконечности? Нет, не может. Потому что если бы он продолжался до бесконечности, то посредством так называемой «трансфинитной индукции» мы могли бы запихнуть в A произвольно большие бесконечные кардинальные числа. А множество A хотя и бесконечно, но имеет не более чем фиксированный бесконечный размер! Так что процесс этот должен где-то остановиться. Но где? На некотором собственном подмножестве B множества A? Нет, это тоже невозможно, поскольку если бы это было так, то мы просто продолжили бы процесс добавлением f(B). Так что единственное место, где он может остановиться, это само A. Следовательно, A может быть полностью упорядочено.

Ранее я упоминал некие математические сложности, изначально присущие континууму, и есть у меня одна головоломка, некоторым образом связанная с ними.

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

На самом деле сумма длин таких интервалов может быть не просто конечной, она может быть сколь угодно близкой к нулю! Просто пронумеруем рациональные числа: r₀, r₁, r₂, и т. п. Затем для каждого i окружим каждое из чисел r_i интервалом протяженностью ε/2ⁱ.

А вот задачка посложнее: мы хотим иметь подмножество S точек (x, y) в единичном квадрате [0, 1]², такое, что для любого действительного числа x ∈ [0, 1] существует лишь счетное количество значений y из [0, 1], таких, что (x, y) попадает в S. Можно ли выбрать S так, что для любого (x, y) ∈ [0, 1]², или (x, y) ∈ S, или (y, x) ∈ S?

Я дам вам два ответа: что такое невозможно и что такое все же возможно.

Начнем с того, почему такое невозможно. Для этого я предположу, что континуум-гипотеза ошибочна. Далее, существует некоторое собственное подмножество A ⊂ [0, 1] мощностью ℵ₁. Пусть B – множество всех y, которые фигурируют в точках (x, y) ∈ S на всех x ∈ A. Поскольку для любого x существует счетное количество таких y, мощность множества B также равна ℵ₁. Поэтому, раз мы предположили, что ℵ₁ меньше чем, 2^ℵ₀ должно существовать некоторое y₀ ∈ [0, 1], не входящее в B. Отметим, что существует ℵ₁ действительных чисел x ∈ A, но ни одно из них не удовлетворяет условию (x, y₀) ∈ S, и лишь ℵ₀ < ℵ₁ из них может удовлетворять условию (y₀, x) ∈ S, так что существует некоторое x₀, для которого (x₀, y₀) и (y₀, x₀) не входят в S.

А теперь посмотрим, почему это возможно. Для этого я хочу предположить, что и аксиома выбора, и континуум-гипотеза верны. Согласно континуум-гипотезе, в отрезке [0, 1] имеется только ℵ₁ действительных чисел. Тогда, по аксиоме выбора, мы можем вполне упорядочить эти действительные числа и сделать это таким способом, чтобы каждое число имело не более ℵ₀ предшественников. Далее, пусть (x, y) входит в S тогда и только тогда, когда y ≤ x, где ≤ означает сравнение по отношению к полной упорядоченности (а не к обычному порядку действительных чисел). Тогда для любого (x, y) ясно, что либо (x, y) ∈ S, либо (y, x) ∈ S.

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