9. Квантовые компьютеры

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

Квантовые вычисления — это нечто большее, чем просто более быстрая и миниатюрная технология реализации машины Тьюринга. Квантовый компьютер — это машина, которая использует уникальные квантово-механические эффекты, в особенности интерференцию, для выполнения совершенно новых видов вычислений, которые даже в принципе было бы невозможны выполнить ни на одной машине Тьюринга, а, следовательно, и ни на каком классическом компьютере. Таким образом, квантовые вычисления — это не что иное, как принципиально новый способ покорения природы.

Позвольте мне конкретизировать это заявление. Самыми первыми изобретениями для покорения природы были инструменты, приводимые в действие силой человеческих мускулов. Они радикально изменили условия жизни наших предков, но страдали от ограничения, которое заключалось в том, что они требовали постоянного внимания и усилий человека во время их использования. Дальнейшее развитие технологии позволило преодолеть это ограничение: люди сумели приручить некоторых животных и растения, обратив биологические адаптации этих организмов на пользу человеку. Урожай рос, а сторожевые собаки охраняли дом, пока их владельцы спали. Ещё один новый вид технологии появился, когда люди начали не просто использовать существующие адаптации (и существующие небиологические явления, например, огонь), а создали совершенно новые для мира адаптации в виде керамики, кирпичей, колёс, металлических изделий и машин. Чтобы сделать это, они должны были поразмыслить над законами природы, управляющими Вселенной, и понять их, включая, как я уже объяснил, не только её поверхностные аспекты, но и лежащую в основе структуру реальности. Последовали тысячи лет развития технологий этого типа, позволивших овладеть некоторыми материалами, а также физическими силами и энергиями. В XX веке, когда изобретение компьютеров позволило осуществить сложную обработку информации вне человеческого мозга, к этому списку добавилась информация. Квантовые вычисления, которые сейчас находятся в зачаточном состоянии, — качественно новый этап этого движения. Это будет первая технология, которая позволит выполнять полезные задачи при участии параллельных вселенных. Квантовый компьютер сможет распределить составляющие сложной задачи между множеством параллельных вселенных, а затем предоставить им всем результаты.

Я уже говорил о важности универсальности вычислений — о том, что один физически возможный компьютер может, при наличии достаточного времени и памяти, выполнить любое вычисление, доступное любому другому физически возможному компьютеру. Законы физики, как мы их сейчас понимаем, признают универсальность вычислений. Но для того, чтобы универсальность была полезной или важной в общей схеме вещей, сказанного мною недостаточно. Приведённое определение просто означает, что в конечном итоге универсальный компьютер сможет сделать то, что может сделать любой другой компьютер. Другими словами, он универсален при наличии достаточного времени. А что делать, если времени недостаточно? Представьте себе универсальный компьютер, который мог бы выполнить только одно вычислительное действие за всю жизнь Вселенной. Его универсальность по-прежнему оставалась бы глубоким свойством реальности? Вероятно, нет. Обобщая, можно раскритиковать такое узкое понятие универсальности, поскольку оно признаёт задачу входящей в репертуар компьютера без учёта физических ресурсов, которые придётся израсходовать компьютеру на выполнение этой задачи. Так, например, мы рассматривали пользователя виртуальной реальности, готового к остановке мозга на миллиарды лет, пока компьютер вычисляет, какую анимацию показывать дальше. Такое отношение вполне уместно при обсуждении пределов виртуальной реальности. Но когда мы говорим о её полезности, или, что даже более важно, фундаментальной роли, которую она играет в структуре реальности, нам следует быть более разборчивыми. Эволюция никогда бы не произошла, если бы задача воспроизведения определённых свойств самых первых, простейших сред обитания не была легкорешаемой (т. е. вычислимой в течение разумного периода времени) при использовании в качестве компьютеров легкодоступных молекул. Точно так же никогда не началось бы развитие науки и техники, если бы для изобретения каменного инструмента понадобились тысячи лет размышлений. Более того, то, что было истиной в самом начале, остаётся абсолютным условием прогресса на каждом этапе. Универсальность вычислений была бы бесполезна для генов независимо от количества содержащегося в них знания, если бы воссоздание организма не было легкорешаемой задачей — скажем, если бы один репродуктивный цикл занимал миллиарды лет.

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

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

Насколько эффективно можно воспроизвести те или иные аспекты реальности? Другими словами, какие вычисления можно практически выполнить за данное время и при данных возможностях? Это основной вопрос теории вычислительной сложности, которая, как я уже сказал, занимается изучением ресурсов, необходимых для решения вычислительных задач. Теория сложности ещё не объединена в достаточной степени с физикой, чтобы дать многие ответы в количественном виде. Однако она достигла немалого успеха в важном деле грубого различия вычислительных задач на легко- и труднорешаемые. Общий подход лучше всего проиллюстрировать на примере. Рассмотрим задачу умножения двух достаточно больших чисел, скажем, 4 220 851 и 2 594 209. Многие из нас помнят тот метод умножения, которому мы научились в детстве. Он включает умножение каждой цифры одного числа поочерёдно на каждую цифру другого, сдвиг промежуточных результатов и их сложение. Этот стандартный алгоритм позволяет получить окончательный ответ, в данном случае — 10 949 769 651 859. Вероятно, многие не захотят признать, что эта утомительная процедура делает умножение «лёгкой» задачей хоть в каком-то обыденном смысле этого слова. (В действительности существуют более эффективные методы умножения больших чисел, но этот весьма нагляден.) Однако с точки зрения теории сложности, которая имеет дело с трудными задачами, решаемыми компьютерами, не подверженными скуке и почти никогда не ошибающимися, этот метод определённо попадает в категорию «лёгких».

В соответствии со стандартным определением для «лёгкости» решения задачи важно не фактическое время, затрачиваемое на умножение конкретной пары чисел, а тот факт, что при применении того же самого метода даже к большим числам время увеличивается не слишком резко. Возможно, это покажется неожиданным, но такой очень косвенный метод определения «лёгкости» очень хорошо работает на практике для многих (хотя и не всех) важных классов вычислительных задач. В случае умножения, например, нетрудно убедиться, что стандартный метод можно использовать и для умножения чисел, скажем, в десять раз больших, приложив совсем незначительные дополнительные усилия. Ради иллюстрации предположим, что каждое элементарное умножение одной цифры на другую занимает у некоторого компьютера одну микросекунду (включая время, необходимое для сложения, сдвига и других операций, сопровождающих каждое элементарное умножение). При умножении семизначных чисел 4 220 851 и 2 594 209 каждую из семи цифр первого числа нужно умножить на каждую из семи цифр второго числа. Таким образом, общее время, необходимое для умножения (если операции выполняются последовательно), составит семью семь, или 49 микросекунд. Если на вход поданы числа примерно в десять раз бо?льшие, то есть содержащие по восемь цифр, на их умножения потребуется 64 микросекунды: увеличение составляет всего 31 %.

Ясно, что числа из огромного диапазона — безусловно содержащего любые числа, которые когда-либо были измерены как количественные значения физических переменных, — можно перемножить за крошечную долю секунды. Таким образом, умножение действительно является легкорешаемой задачей для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). За пределами физики, конечно, могут появиться практические причины для умножения куда больших чисел. Например, для криптографии огромный интерес представляют произведения простых чисел, состоящих примерно из 125 цифр. Наша гипотетическая машина могла бы перемножить два таких простых числа, получив произведение, состоящее из 250 цифр, примерно за 0,01 секунды. За одну секунду она могла бы перемножить два тысячезначных числа, и современные компьютеры легко могут улучшить это достижение. Лишь немногие исследователи эзотерических областей чистой математики интересуются перемножением столь непостижимо больших чисел, однако мы видим, что даже у них нет причины считать умножение неразрешимой задачей.

Напротив, разложение на множители — по сути, процесс, обратный умножению, — кажется гораздо сложнее. Вначале вводится одно число, скажем, 10 949 769 651 859. Задача заключается в том, чтобы найти два его множителя — меньших числа, произведение которых равно 10 949 769 651 859. Поскольку мы только что перемножили эти числа, мы знаем, что в данном случае ответ будет 4 220 851 и 2 594 209 (и поскольку оба эти числа простые, это единственный подходящий ответ). Но не располагая заранее такой подсказкой, как бы мы нашли эти множители? Если в поисках простого метода вы обратитесь к детским воспоминаниям, то это будет бесполезно, поскольку такого метода не существует.

Самый очевидный метод разложения на множители — делить вводимое число на все возможные множители, начиная с 2 и продолжая каждым нечётным числом, до тех пор, пока введённое число не разделится без остатка. По крайней мере, один из множителей (с учётом того, что введённое число не является простым) не может быть больше квадратного корня введённого числа, и это позволяет оценить, сколько времени может потребовать данный метод. В рассматриваемом случае наш компьютер найдёт меньший из двух множителей, 2 594 209, примерно за секунду с небольшим. Однако если исходное число будет в десять раз больше, а его квадратный корень примерно в три раза больше, то разложение его на множители по этому методу займёт в три раза больше времени. Другими словами, увеличение вводимого числа на один разряд уже утроит время обработки. Увеличение его ещё на один разряд снова утроит это время и т. д. Таким образом, время обработки будет увеличиваться в геометрической прогрессии, т. е. экспоненциально, с увеличением количества разрядов в раскладываемом на множители числе. Разложение на множители числа с 25-значными множителями по этому методу заняло бы все компьютеры на Земле на несколько веков.

Этот метод можно усовершенствовать, однако всем современным методам разложения числа на множители присуще это свойство экспоненциального роста. Самое большое число, которое было «в гневе» (а это было действительно так) разложено на множители, — число, сомножители которого тайно выбрали одни математики, чтобы бросить вызов другим математикам, — имело 129 цифр[38]. Разложение на множители выполнили с помощью сети Интернет глобальными совместными усилиями, в которых были задействованы тысячи компьютеров. Знаменитый специалист по алгоритмам Дональд Кнут[39] оценил, что разложение на множители 250-значного числа при использовании самых эффективных из известных методов, с помощью сети, состоящей из миллиона компьютеров, заняло бы более миллиона лет. Такие вещи трудно оценить, но даже если Кнут был чрезмерно пессимистичен, то нужно взять числа всего на несколько разрядов большие, и задача во много раз усложнится. Именно это мы имеем в виду, когда говорим, что разложение на множители больших чисел — труднорешаемая задача. Всё это очень сильно отличается от умножения, где, как мы видели, операцию с парой 250-значных чисел можно выполнить на домашнем компьютере. Никто не может даже представить себе, как можно разложить на множители числа, состоящие из тысячи или миллиона цифр.

По крайней мере, никто не мог этого представить до недавнего времени.

В 1982 году физик Ричард Фейнман[40] занимался компьютерным моделированием квантово-механических объектов. Его отправной точкой был факт, известный уже в течение некоторого времени, важность которого, однако, ещё не была оценена, а именно, что задача предсказания поведения квантово-механических систем (или, как мы можем это переформулировать — воспроизведения квантово-механических сред в виртуальной реальности) в общем случае является труднорешаемой. Одна из причин, по которой важность этого недооценивали, состояла в том, что никто и не ожидал особенно лёгкого предсказания интересных физических явлений с помощью компьютера. Возьмите, например, прогноз погоды или землетрясения. Несмотря на то что нужные уравнения известны, все знают, как трудно применять их в реальных ситуациях. В последнее время к этому привлекли широкое внимание в популярных книгах и статьях о хаосе и «эффекте бабочки». Но не эти эффекты ответственны за трудности, с которыми столкнулся Фейнман, по той простой причине, что они имеют место только в классической физике — то есть не в реальности, поскольку реальность квантово-механическая. Тем не менее я хочу сделать несколько замечаний относительно «хаотических» движений в классике, только чтобы подчеркнуть глубоко различный характер классической и квантовой непредсказуемости.

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

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

Законы квантовой механики требуют, чтобы объект, который первоначально находится в определённом положении (во всех вселенных), «растекался» по мультиверсу. Например, фотон и его партнёры из других вселенных отправляются из одной и той же точки светящейся нити накала, но затем движутся в триллионах различных направлений. Когда мы позднее проводим измерение того, что произошло, мы тоже становимся отличными друг от друга, так как каждая наша копия видит то, что произошло в её конкретной вселенной. Если рассматриваемым объектом является атмосфера Земли, то ураган может произойти, скажем, в 30 % вселенных и не произойти в остальных 70 %. Субъективно мы воспринимаем это как единственный непредсказуемый или «случайный» результат, хотя, если принять во внимание существование мультиверса, все результаты действительно имели место. Эта множественность параллельных вселенных и есть настоящая причина непредсказуемости погоды. Наша неспособность точно измерить начальные состояния тут абсолютно ни при чём. Даже знай мы начальные состояния точно, множественность, а, следовательно, и непредсказуемость движения, всё равно имела бы место. С другой стороны, в отличие от классического случая, поведение воображаемого мультиверса с немного отличными начальными состояниями не слишком отличалось бы от поведения реального мультиверса: он мог пострадать от урагана в 30,000001 % своих вселенных и не пострадать в оставшихся 69,999999 %.

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

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

Квантовую теорию часто представляют как дающую только вероятностные предсказания. Например, в эксперименте с интерференцией на светонепроницаемой перегородке со щелями, описанном в главе 2, можно обнаружить, что фотон попал в любое место на «светлом» участке картины теней. Однако важно понимать, что для множества других экспериментов квантовая теория предсказывает единственный определённый результат. Другими словами, она предсказывает, что во всех вселенных исход будет одним и тем же, даже если на промежуточных стадиях эксперимента эти вселенные отличались друг от друга, и она предсказывает, каким будет этот результат. В таких случаях мы наблюдаем явление неслучайной интерференции. Такие явления может продемонстрировать интерферометр. Это оптический инструмент, состоящий главным образом из зеркал, как обычных (рис. 9.1), так и полупрозрачных (какие используются в фокусах иллюзионистов и в полицейских участках, рис. 9.2). Если фотон падает на полупрозрачное зеркало, то в половине вселенных он отскакивает от него точно так же, как отскочил бы от обычного зеркала. Однако в другой половине вселенных он проходит сквозь это зеркало, словно его нет.

Один фотон входит в интерферометр сверху слева, как показано на рис. 9.3. Во всех вселенных, где проводят эксперимент, фотон и его партнёры движутся к интерферометру по одной и той же траектории. Следовательно, эти вселенные идентичны. Но как только фотон попадает на полупрозрачное зеркало, первоначально идентичные вселенные становятся различными. В половине из них фотон проходит через зеркало и движется вправо вдоль верхней стороны интерферометра. В остальных вселенных фотон отражается от зеркала и идёт вниз вдоль левой стороны интерферометра. Затем эти варианты фотона в разных группах вселенных попадают в обычные зеркала справа сверху и слева снизу соответственно и отражаются от них. Таким образом, в конце они одновременно попадают на полупрозрачное зеркало справа снизу и интерферируют друг с другом. Не забывайте, что мы запускали в аппарат только один фотон, и в каждой вселенной по-прежнему находится только один фотон. Во всех вселенных этот фотон теперь попал в правое нижнее зеркало. В половине вселенных он подошёл к этому зеркалу слева, в другой половине — сверху. Между разновидностями фотона из этих двух групп вселенных произошла сильная интерференция. Суммарный эффект зависит от точной геометрии ситуации, но на рис. 9.3 изображён тот случай, когда во всех вселенных фотон в конце движется вправо сквозь зеркало, и ни в одной вселенной он не проходит и не отражается вниз. Таким образом, в конце эксперимента все вселенные так же идентичны, как и в начале. Они отличались и интерферировали друг с другом лишь краткую долю секунды в промежуточном состоянии.

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

Поскольку в этом опыте присутствуют только два различных вида вселенных, вычисление того, что произойдёт, займёт всего в два раза больше времени, чем в случае, если бы частица подчинялась классическим законам — скажем, если бы мы вычисляли траекторию движения бильярдного шара. Вряд ли коэффициент два превратит такую вычислительную задачу в труднорешаемую. Однако мы уже видели, что довольно легко достичь и гораздо более высокой степени многообразия. В экспериментах с тенями один фотон проходит через перегородку с несколькими маленькими отверстиями и попадает на экран. Предположим, что в перегородке тысяча отверстий. На экране есть места, куда может попасть фотон (и попадает в некоторых вселенных), и места, куда он попасть не может. Чтобы вычислить, может ли конкретная точка экрана принять фотон или нет, мы должны вычислить эффекты взаимной интерференции вариантов фотона из тысячи параллельных вселенных. В частности, мы должны вычислить тысячу траекторий движения фотона от перегородки до данной точки экрана, затем вычислить влияния этих фотонов друг на друга так, чтобы определить, не помешают ли все они друг другу достигнуть этой точки. Таким образом, мы должны выполнить примерно в тысячу раз больше вычислений, чем нам пришлось бы, если бы мы определяли, попадёт ли в конкретную точку классическая частица.

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

Именно этим — труднорешаемостью — и занимался Фейнман. Мы видим, что она не имеет ничего общего с непредсказуемостью: напротив, наиболее ясно она проявляется в квантовых явлениях с высокой степенью предсказуемости. Так происходит потому, что в таких явлениях один и тот же определённый результат имеет место во всех вселенных, однако этот результат — итог интерференции между огромным количеством вселенных, которые в процессе эксперимента отличались друг от друга. Всё это в принципе предсказуемо на основе квантовой теории и не слишком чувствительно к начальным условиям. Предсказать, что в таких экспериментах результат всегда будет одним и тем же, становится трудно потому, что для этого необходимо выполнить чрезмерно большой объём вычислений.

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

Может показаться естественным вывод о том, что реальность всё-таки не показывает подлинной вычислительной универсальности, поскольку явление интерференции невозможно воспроизвести с разумными затратами. Однако Фейнман сделал противоположный вывод и был совершенно прав! Вместо того чтобы считать труднорешаемость задачи воспроизведения квантовых явлений препятствием, Фейнман счёл её благоприятной возможностью. Если для того, чтобы узнать исход эксперимента с интерференцией, необходимо выполнить так много вычислений, то сам факт проведения такого эксперимента и измерения его результатов равносилен выполнению сложного вычисления. Таким образом, рассуждал Фейнман, наверное, эффективно воспроизводить квантовые среды всё-таки возможно, если позволить компьютеру проводить эксперименты над реальным квантово-механическим объектом. Компьютер выбрал бы, какие измерения сделать на вспомогательной составляющей квантового оборудования во время проведения эксперимента, и включил бы результаты этих измерений в свои вычисления.

Эта вспомогательная квантовая аппаратура, в сущности, тоже была бы компьютером! Например, в качестве такого устройства мог бы работать интерферометр, и, как любой другой физический объект, его можно было бы считать компьютером. Сегодня мы назвали бы его специализированным квантовым компьютером. Мы «программируем» его, устанавливая зеркала так, чтобы создать определённую геометрию, и затем направляем один фотон на первое зеркало. В эксперименте с неслучайной интерференцией фотон всегда выйдет в одном конкретном направлении, определяемом установкой зеркал, и мы можем интерпретировать это направление как выдачу результата вычислений. В более сложном эксперименте с несколькими взаимодействующими частицами такое вычисление запросто могло бы, как я уже объяснил, стать «труднорешаемым». Но поскольку мы можем получить результаты, просто проведя этот эксперимент, значит, его всё-таки нельзя назвать действительно трудным. Нам теперь следует быть осторожнее в вопросах терминологии. Очевидно, что существуют вычислительные задачи, «труднорешаемые», если пытаться справиться с ними на любом существующем компьютере, но переходящие в разряд легкорешаемых, если в качестве специализированных компьютеров мы могли бы использовать квантово-механические объекты. (Обратите внимание, что возможность использования квантовых явлений для выполнения вычислений подобным образом обусловлена тем, что эти явления не подвержены хаосу. Если бы результат вычислений был функцией, чрезмерно чувствительной к начальному состоянию, «запрограммировать» такое устройство, установив его в подходящее начальное состояние, было бы невыполнимой задачей.)

Такое использование вспомогательного квантового устройства можно было бы посчитать жульничеством, так как очевидно, что любую среду гораздо проще создать, имея доступ к её запасной копии для проведения измерений во время воспроизведения! Однако Фейнман предположил, что нет необходимости в использовании точной копии воспроизводимой среды: можно найти вспомогательное устройство, конструкция которого гораздо проще, но интерференционные свойства тем не менее будут аналогичны свойствам воспроизводимой среды. Оставшуюся часть работы способен осуществить обычный компьютер, опираясь на аналогию между вспомогательным устройством и воспроизводимой средой. Фейнман ожидал, что эта задача будет легкорешаемой. Более того, он предполагал — как оказалось, правильно, — что все квантово-механические свойства любой воспроизводимой среды можно смоделировать с помощью вспомогательных устройств конкретного вида, который он указал (а именно, совокупности вращающихся атомов, каждый из которых взаимодействует со своими соседями). Он назвал весь класс таких устройств универсальным квантовым симулятором.

Однако этот симулятор не является отдельной машиной, что необходимо для признания его универсальным компьютером. Взаимодействия, которым должны были бы подвергнуться атомы симулятора, нельзя было задать раз и навсегда, как в универсальном компьютере, их нужно было переустраивать для каждой воспроизводимой среды. Однако суть универсальности состоит в том, что должна быть возможность запрограммировать отдельную машину, точно определённую раз и навсегда, для выполнения любого возможного вычисления или воспроизведения любой возможной среды. В 1985 году я доказал, что в рамках квантовой физики существует универсальный квантовый компьютер. Это доказательство было абсолютно прямым. Всё, что мне пришлось сделать, — это сымитировать построения Тьюринга, но воспользоваться квантовой теорией для определения лежащей в их основе физики, а не классической механикой, которую неявно предполагал Тьюринг. Универсальный квантовый компьютер может выполнить любое вычисление, которое может выполнить любой другой квантовый компьютер (или любой компьютер Тьюринга), а также воспроизвести любую конечную физически возможную среду в виртуальной реальности. Более того, с тех пор было показано, что время и остальные ресурсы, которые ему понадобятся для осуществления всего этого, не будут увеличиваться экспоненциально с ростом размеров или детальности воспроизводимой среды, так что соответствующие задачи будут легкорешаемыми по критериям теории сложности.

Классическая теория вычислений, которая в течение полувека оставалась неоспоримым фундаментом обработки данных, сейчас устарела, но, как и остальная классическая физика, может использоваться в качестве приближённой схемы. Современной теорией вычислений является квантовая теория вычислений. Я сказал, что Тьюринг в своих построениях неявно использовал «классическую механику». Но, оглядываясь назад с уровня современных воззрений, мы видим, что даже классическая теория вычислений не полностью соответствовала классической физике и содержала существенные признаки квантовой теории. Это вовсе не совпадение, что слово бит, означающее наименьшее возможное количество информации, которым способен управлять компьютер, в сущности, означает то же самое, что и квант, — дискретную порцию. Дискретные переменные (переменные, которые не могут принимать значения из непрерывного диапазона) чужды классической физике. Например, если переменная имеет только два возможных значения, скажем, 0 и 1, как она вообще переходит из 0 в 1? (Я задавал этот вопрос в главе 2.) В классической физике ей пришлось бы совершить прыжок, нарушив непрерывность, что несовместимо с тем, как работают силы и происходят движения в классической механике. В квантовой физике нет необходимости в скачкообразном изменении — несмотря на то, что все измеримые величины дискретны. Вот как это устроено.

Для начала давайте представим несколько параллельных вселенных, сложенных подобно колоде карт, причём вся колода в целом представляет собой мультиверс. (Такая модель, в которой вселенные располагаются последовательно, сильно преуменьшает сложность мультиверса, но она вполне достаточна, чтобы проиллюстрировать мою мысль.) Теперь давайте изменим эту модель, приняв во внимание тот факт, что мультиверс — это не дискретный набор вселенных, а континуум, и то, что не все вселенные различны. В действительности для каждой вселенной, которая там присутствует, также существует континуум идентичных вселенных, составляющий некую небольшую, но отличную от нуля долю мультиверса. В нашей модели эту долю можно представить через толщину карты, причём каждая карта теперь представляет все вселенные данного типа. Однако, в отличие от толщины карты, доля каждого типа вселенных изменяется со временем в соответствии с квантово-механическими законами движения. Следовательно, доля вселенных, обладающих данным свойством, тоже изменяется, причём это изменение происходит непрерывно. В случае с дискретной переменной, которая переходит из 0 в 1, допустим, что до начала изменения эта переменная во всех вселенных имеет значение 0, а после изменения она принимает значение 1 тоже во всех вселенных. В процессе изменения доля вселенных, в которых значение равно 0, постепенно уменьшается от 100 % до нуля, а доля вселенных, где это значение равно 1, соответственно растёт от нуля до 100 %. На рис. 9.4 показано, как выглядит подобное изменение с точки зрения мультиверса.

Из рис. 9.4 может показаться, что, хотя переход от 0 к 1 является объективно непрерывным с точки зрения мультиверса, он остаётся субъективно скачкообразным для любой отдельной вселенной — представленной, скажем, горизонтальной линией в середине рис. 9.4. Однако это всего лишь ограничение способа представления, а не реальная характеристика того, что происходит на самом деле. Хотя диаграмма выглядит так, словно в каждое мгновение существует конкретная вселенная, которая «только что изменилась» из 0 в 1, потому что она только что «пересекла границу», на самом деле это не так. Так быть не может, потому что такая вселенная строго идентична любой другой вселенной, в которой бит в данный момент имеет значение 1. Поэтому если бы жители одной из них испытывали скачкообразное изменение, то жители всех других испытывали бы то же самое. Значит, ни одна из них такого испытывать не может. Обратите также внимание, что, как я объясню в главе 11, идея о чём-то, движущемся по такой диаграмме, как на рис. 9.4, где уже представлено время, просто ошибочна. В каждое мгновение бит имеет значение 1 в определённой доле вселенных и 0 — в другой. Все эти вселенные во все эти времена уже показаны на рис. 9.4. Они никуда не движутся!

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

Создание универсального квантового компьютера выходит далеко за рамки современной технологии. Как я уже сказал, чтобы обнаружить явление интерференции, нужно вызвать соответствующее взаимодействие всех переменных, которые различались во вселенных, вносящих вклад в интерференцию. Чем больше взаимодействующих частиц участвует, тем сложнее организовать взаимодействие, которое продемонстрировало бы интерференцию, то есть результат вычисления. Среди множества технических сложностей работы на уровне одного атома или электрона одна из важнейших состоит в ограждении среды от воздействия различных интерферирующих субвычислений. Дело в том, что если группа атомов участвует в явлении интерференции и эти атомы по-разному воздействуют на другие атомы окружающей среды, то интерференцию уже невозможно обнаружить по измерениям только исходной группы, и эта группа уже не выполняет какого бы то ни было полезного квантового вычисления. Это называется декогеренцией. Следует добавить, что эту проблему часто представляют в ложном свете: нам говорят, что квантовая интерференция — очень чувствительный процесс, и его следует ограждать от любых внешних воздействий. Но это не так. Внешние воздействия способны вызвать небольшие погрешности, но именно воздействие квантового вычисления на внешний мир вызывает декогеренцию.

Таким образом, ставка делается на создание субмикроскопических систем, в которых несущие информацию переменные взаимодействуют друг с другом, но как можно меньше влияют на свою среду. Ещё одно новое упрощение, уникальное для квантовой теории вычисления, частично компенсирует сложности, вызываемые декогеренцией. Оказывается, что, в отличие от классического вычисления, где необходимо конструировать особые классические логические элементы, такие как И, ИЛИ и НЕ, в квантовом случае конкретная форма взаимодействий вряд ли имеет значение. В сущности, почти любую систему взаимодействующих битов атомного масштаба, если она не декогерирует, можно приспособить для выполнения полезных квантовых вычислений.

Известны интерференционные явления, включающие огромное число частиц, например, сверхпроводимость или сверхтекучесть, но кажется, что ни одно из них невозможно использовать для выполнения каких-либо интересных вычислений. Во время написания этой книги в лаборатории можно было легко выполнить только однобитовые квантовые вычисления. Однако экспериментаторы уверены, что в течение нескольких последующих лет будут созданы двух- и более битовые квантовые логические элементы (квантовые эквиваленты классических логических элементов). Это основные составляющие квантовых компьютеров. Некоторые физики, особенно Рольф Ландауэр[41] из IBM Research, настроены пессимистично относительно перспектив дальнейшего продвижения после этого. Они полагают, что декогеренция никогда не будет сведена до того уровня, при котором можно выполнить более нескольких последовательных шагов квантового вычисления. Большинство исследователей в этой области настроены гораздо оптимистичнее (хотя, возможно, это связано с тем, что над квантовыми вычислениями решаются работать только очень большие оптимисты!). Уже были построены некоторые специализированные квантовые компьютеры (речь о них пойдёт дальше), и лично я думаю, что появление более сложных квантовых компьютеров — скорее дело нескольких лет, чем десятилетий. Что касается универсального квантового компьютера, то я считаю, что его создание — это тоже лишь дело времени, хотя мне не хотелось бы предсказывать, сколько времени это займёт: десятилетия или века.

Тот факт, что репертуар универсального квантового компьютера содержит среды, воспроизведение которых является труднорешаемым в классическом смысле, говорит о том, что новые классы чисто математических вычислений тоже должны стать легкорешаемыми на этом компьютере, потому что законы физики, как сказал Галилей, выражаются на языке математики, а воспроизведение среды эквивалентно вычислению определённых математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантовых вычислений, тогда как для всех известных классических методов они являются труднорешаемыми. Наиболее впечатляющей из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, работавший в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока американское издание этой книги готовилось к печати, были открыты другие впечатляющие квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска в длинных списках.)

Алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромной аппаратурой, чем та, которая понадобилась бы для универсального квантового компьютера. А потому вероятно, что квантовое устройство для разложения на множители будет построено задолго до того, как станет технологически осуществимым весь спектр квантовых вычислений. Эта перспектива имеет грандиозное значение для криптографии (науки о секретной передаче информации и установлении её подлинности). Реальные сети связи могут быть глобальными и иметь огромные, постоянно изменяющиеся наборы участников с непредсказуемыми схемами связи. Непрактично требовать, чтобы каждая пара участников заранее физически обменивалась секретными шифровальными ключами, которые позволили бы им позднее общаться, не боясь, что их подслушают. Криптография с открытым ключом — это любой метод отправки секретной информации, при котором ни отправитель, ни получатель не обменивались до этого никакой секретной информацией. Самый надёжный из известных методов криптографии с открытым ключом основан на труднорешаемости задачи разложения на множители больших чисел. Этот метод известен как криптосистема RSA, которая получила своё название по первым буквам фамилий Рональда Ривеста, Ади Шамира и Леонарда Адельмана, впервые предложивших её в 1978 году. Она полагается на математическую процедуру, посредством которой можно закодировать сообщение, используя в качестве ключа огромное (скажем, 250-значное) число. Получатель может свободно обнародовать этот ключ для использования всеми отправителями, потому что любое сообщение, зашифрованное с его помощью, можно расшифровать, только зная сомножители этого числа. Таким образом, я могу выбрать два 125-значных простых числа и хранить их в секрете, но перемножить их и сообщить всем их 250-значное произведение. Кто угодно может послать мне сообщение, используя это число как ключ, но только я смогу прочитать эти сообщения, потому что только мне известны секретные множители.

Как я уже сказал, не существует практической возможности разложения на множители 250-значного числа с использованием классических средств. Но квантовое устройство разложения на множители, работающее по алгоритму Шора, могло бы это сделать, выполнив всего несколько тысяч арифметических операций, что, возможно, было бы минутным делом. Таким образом, любой человек, имеющий доступ к такой машине, смог бы легко прочитать любое перехваченное сообщение, зашифрованное с помощью криптосистемы RSA.

Криптографам не помогло бы использование более длинных чисел в качестве ключей, потому что ресурсы, необходимые для работы алгоритма Шора, очень медленно увеличиваются с ростом раскладываемого на множители числа. В квантовой теории вычислений разложение на множители — очень легкорешаемая задача. Считается, что при данном уровне декогеренции всё же снова появится некий практический предел размера числа, которое можно разложить на множители, но неизвестен нижний предел технологически достижимой скорости декогеренции. Поэтому мы должны сделать вывод, что однажды в будущем, во время, которое сейчас невозможно предсказать, криптосистема RSA с любой заданной длиной ключа может стать ненадёжной. В определённом смысле это делает её ненадёжной даже сегодня. Ведь люди или организации, которые сейчас перехватывают сообщения, закодированные в системе RSA, дождутся того времени, когда смогут купить квантовое устройство разложения на множители с достаточно низкой декогеренцией, и сумеют расшифровать эти сообщения. Возможно, это произойдёт только через века, возможно, всего через несколько десятилетий, а может, и ещё раньше — кто знает? Но вероятность того, что это случится ещё не скоро, — это всё, что теперь осталось от бывшей абсолютной надёжности системы RSA.

Когда квантовое устройство разложения на множители раскладывает 250-значное число, количество интерферирующих вселенных будет порядка 10⁵⁰⁰, т. е. десять в степени 500. Это ошеломляюще огромное число — причина того, почему алгоритм Шора делает разложение на множители легкорешаемой задачей. Я сказал, что этот алгоритм требует выполнения всего нескольких тысяч арифметических операций. Безусловно, я имел в виду несколько тысяч операций в каждой вселенной, которая вносит вклад в ответ. Все эти вычисления выполняются параллельно в различных вселенных и делятся своими результатами через интерференцию.

Возможно, вам интересно, как мы сможем убедить своих партнёров из 10⁵⁰⁰ или около того вселенных начать работать над нашей задачей разложения на множители. Разве у них нет своих собственных задач, чтобы задействовать компьютеры? Нет — и нам не нужно их убеждать. Алгоритм Шора изначально действует только в наборе вселенных, идентичных друг другу, и вызывает в них отличия только в пределах устройства разложения на множители. Поэтому мы, указавшие число, которое нужно разложить на множители, и ждущие ответа, идентичны во всех интерферирующих вселенных. Несомненно, существует много других вселенных, в которых мы задали другие числа или вообще не построили устройства разложения на множители. Но эти вселенные отличаются от нашей слишком большим количеством переменных — или, точнее, переменными, которые не настроены для правильного взаимодействия посредством запрограммированного алгоритма Шора, — и потому они не интерферируют с нашей Вселенной.

Рассуждения, приведённые в главе 2, будучи применены к любому явлению интерференции, разрушают классическую идею о единственности Вселенной. Логически возможность сложных квантовых вычислений ничего не добавляет к вопросу, на который уже нельзя ответить иначе. Но эта возможность оказывает дополнительное психологическое влияние. Алгоритм Шора очень сильно повышает убедительность этих рассуждений. Для тех, кто всё ещё склонен считать, что существует лишь одна Вселенная, я предлагаю следующий вызов: объясните, как работает алгоритм Шора. Я имею в виду не предсказание, каковы будут результаты его работы, поскольку для этого достаточно решить несколько непротиворечивых уравнений. Я прошу вас дать объяснение. Когда алгоритм Шора разлагает на множители число, задействовав примерно в 10⁵⁰⁰ больше вычислительных ресурсов, чем те, что можно увидеть воочию, — где же это число раскладывается на множители?

Во всей видимой Вселенной существует всего около 10⁸⁰ атомов — число ничтожно малое по сравнению с 10⁵⁰⁰. Таким образом, если бы видимая Вселенная была пространством физической реальности, физическая реальность даже отдалённо не содержала бы ресурсов, достаточных для разложения на множители такого большого числа. Кто же тогда разложил его на множители? Как и где выполнялись вычисления?

Я говорил о традиционных типах математических задач, которые квантовые компьютеры смогли бы выполнить быстрее существующих машин. Но для квантовых компьютеров открыт и дополнительный класс новых задач, которые ни один классический компьютер не способен решить вообще. По странному совпадению, одна из первых найденных задач такого типа также была связана с криптографией с открытым ключом. На этот раз она состояла не во «взломе» существующей системы, а в реализации новой абсолютно надёжной системы квантовой криптографии. В 1989 году в компании IBM Research в Йорктаун-Хайтс, штат Нью-Йорк, в кабинете теоретика Чарльза Беннетта был построен первый рабочий квантовый компьютер. Это был специализированный квантовый компьютер, состоящий из двух квантовых криптографических устройств, спроектированных Беннеттом и Жиллем Брассаром из Университета Монреаля. Этот компьютер стал первой машиной, выполнившей нетривиальные вычисления, которые не смогла бы выполнить ни одна машина Тьюринга.

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

Поскольку квантовая криптография зависит от манипулирования отдельными фотонами, она подвержена существенным ограничениям. Каждый последовательно получаемый фотон, переносящий один бит сообщения, должен быть каким-то образом передан невредимым от отправителя к получателю. Но любой метод передачи связан с потерями, и если они слишком большие, послание никогда не дойдёт до своего адресата. Установка ретрансляционных станций (стандартная мера для устранения этой проблемы в существующих системах связи) подвергла бы риску секретность, потому что подслушивающий мог бы наблюдать за тем, что происходит внутри ретрансляционной станции, не будучи обнаруженным. Лучшие из существующих квантово-криптографических систем используют оптико-волоконные кабели и имеют дальность около десяти километров. Этого было бы достаточно, чтобы обеспечить, скажем, экономический центр города абсолютно надёжной внутренней связью. Возможно, недалеки и коммерческие системы, но чтобы решить проблему криптографии с открытым ключом в общем случае (скажем, для глобальной связи), необходимы дальнейшие шаги в квантовой криптографии[42]. Экспериментальные и теоретические исследования в области квантовых вычислений набирают темп во всём мире. Предлагают всё более перспективные новые технологии реализации квантовых компьютеров и постоянно открывают и анализируют новые типы квантовых вычислений с различными преимуществами перед классическими вычислениями. Я считаю эти разработки совершенно захватывающими и думаю, что некоторые из них принесут технологические плоды. Но для этой книги данный вопрос стал бы отклонением от темы. С фундаментальной точки зрения не имеет значения, насколько полезными окажутся квантовые вычисления, как не имеет значения и то, построим ли мы первый универсальный квантовый компьютер на следующей неделе, через века или не построим его никогда. В любом случае квантовая теория вычислений должна стать неотъемлемой частью мировоззрения всякого, кто ищет фундаментального понимания реальности. То, что квантовые компьютеры говорят нам о связи между законами физики, универсальностью и, казалось бы, не связанными нитями объяснения в структуре реальности, мы можем обнаружить — и уже обнаруживаем, — изучая их теоретически.