Квантовые вычисления со времен Демокрита - Скотт Ааронсон

реальности могут быть вполне различимыми. В самом деле, в 1998 г. Абрамс и Ллойд[59] воспользовались именно этим наблюдением, чтобы показать, что если бы квантовая механика была нелинейна, то можно было бы построить компьютер для решения NP-полных задач за полиномиальное время. Конечно, мы не знаем, являются ли NP-полные задачи эффективно решаемыми в физическом мире. Но в исследовании[60], написанном мной несколько лет назад, я объяснил, почему способность решать NP-полные задачи дала бы нам «божественные» возможности, — есть мнение, что даже более «божественные», чем способность передавать сигналы на сверхсветовых скоростях или обратить вспять второй закон термодинамики. Основная идея здесь в том, что когда мы говорим об NP-полных задачах, то речь идет не просто о составлении расписания авиарейсов (или, может быть, о взломе криптосистемы RSA). Речь идет об автоматизации озарения: доказательства гипотезы Римана, моделирования фондового рынка, отыскания всех существующих в мире закономерностей или логических цепочек.

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

Упражнение 7 для неленивого читателя. Докажите, что если бы квантовая механика была нелинейна, то мы не только могли бы решать NP-полные задачи за полиномиальное время, но и использовать ЭПР-пары для передачи информации со сверхсветовой скоростью.

Позвольте мне завершить эту главу упоминанием трех основных аспектов квантовой механики, которые фигурируют в данной книге.

Первый из них — это теорема о запрете клонирования. Это просто утверждение о том, что в рамках квантовой механики не существует процедуры, которая брала бы в качестве входа неизвестное квантовое состояние |ψ〉 и выдавала в качестве выхода две отдельные копии |ψ〉, то есть тензорное произведение |ψ〉 ⊗ |ψ〉. Доказательство этого настолько тривиально, что можно спорить, достойно ли вообще это утверждение названия «теорема», но важность его несомненна. Вот это доказательство: примем без потери общности, что |ψ〉 — это всего один кубит, |ψ〉 = α|0〉 + β|1〉. Тогда «карта клонирования», которая записывает копию |ψ〉 в другой кубит, инициализированный, скажем, в |0〉, должна будет проделать следующее:

(α|0〉 + β|1〉)|0〉 → (α|0〉 + β|1〉) (α|0〉 + β|1〉) = α²|0〉|0〉 + αβ|0〉|1〉 + αβ|1〉|0〉 + β²|1〉|1〉.

Обратите внимание на то, что α², αβ и β² — квадратичные функции от α и β. Но унитарные преобразования могут давать только линейные комбинации амплитуд, и поэтому не в состоянии породить эволюцию указанного выше типа. А это, собственно, и есть теорема о запрете клонирования! Мы видим, что в отличие от классической информации, которая может копироваться как угодно по всей Вселенной, квантовая информация обладает некоторой «приватностью», мало того, в некоторых отношениях она меньше похожа на классическую информацию, нежели на золото, нефть или другие «неделимые» ресурсы.

Уместно сделать несколько замечаний касательно теоремы о запрете клонирования.

• Эта теорема — не просто артефакт не по-физически настойчивого желания иметь идеальное копирование. При желании можно было бы убедиться, что линейность квантовой механики запрещает даже изготовление «довольно хорошей» копии кубита, взяв подходящее определения понятия «довольно хороший».

• Конечно, мы можем преобразовать состояние (α|0〉 + β|1〉)|0〉 в α|0〉|0〉 + β|1〉|1〉, пропустив первый кубит через вентиль управляемой инверсии C-NOT («управляемое не»). Но это не даст нам двух экземпляров первоначального состояния α|0〉 + β|1〉; вместо этого мы получим запутанное состояние, где каждый отдельный кубит находится в смешанном состоянии

В самом деле, единственный случай, который можно рассматривать как «копирование», — это α = 0 или β = 0; однако в этом случае речь идет о классической, а не квантовой информации.

• Если теорема о запрете клонирования напоминает вам знаменитый принцип неопределенности Гейзенберга — ну что же, так и должно быть! Принцип неопределенности утверждает, что существуют пары свойств — самая известная из них — это положение частицы в пространстве и ее импульс, — в которых невозможно оба свойства измерить с произвольной точностью, между тем и другим должен быть количественный компромисс. Чтобы изложить принцип неопределенности в том виде, в каком его знает большинство физиков, нам потребовалось бы больше физики, чем помещается в этой книге: мне пришлось бы объяснять взаимоотношения между положением (координатой) и импульсом и даже вводить постоянную Планка ħ (хотя бы для того, чтобы заявить, что в моих единицах ħ равна 1!). Но даже без этого позвольте мне показать начерно, как из теоремы о запрете клонирования следует информационно-теоретический вариант принципа неопределенности и наоборот. С одной стороны, если бы можно было измерять все свойства квантового состояния с неограниченной точностью, то можно было бы изготавливать и произвольно точные копии (клонировать). С другой стороны, если бы можно было копировать состояние |ψ〉 произвольное число раз, то можно было бы и узнать все его свойства с неограниченной точностью, к примеру положение мерить у одних копий, а импульс — у других.

• В определенном смысле теорема о запрете клонировании не имеет почти никакого отношения к квантовой механике. В точности аналогичную теорему можно доказать для классических распределений вероятности. Если у вас есть монетка, которая падает орлом кверху с какой-то неизвестной вероятностью p, то не существует способа превратить ее в две монетки, которые бы падали орлом кверху с вероятностью p независимо друг от друга. Конечно, вы можете внимательно осмотреть свою монетку, но информация о p, которую вы сможете получить таким способом, слишком ограничена для копирования. Из нового в квантовой механике только то, что принцип запрета клонирования приложим не только к смешанным, но и к чистым состояниям — таким, что если бы вы знали правильный базис, в котором измерять, то могли бы получить информацию о состоянии с абсолютной точностью. Но если правильный базис неизвестен, то вы не можете ни получить полную информацию о состояниях, ни скопировать их.

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