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

с открытым ключом) не полагаясь ни на какое предположение о вычислительной нераскрываемости, — на самом деле единственное, на что им придется положиться, это на справедливость квантовой механики и на доступность классического канала связи с аутентификацией пользователя. Возможность такого рода криптографии предсказал Стивен Визнер[61] в 1969 г. в замечательной статье, обогнавшей время на десятилетия — настолько, что на протяжении 15 лет Визнеру не удавалось ее опубликовать. (Не так давно во время визита в Иерусалим у меня была возможность встретиться с Визнером. В настоящее время этот необычайно интересный человек по собственному выбору работает на стройке простым рабочим.) Первое явное предложение по QKD сделали в 1984 г. Беннетт и Брассар[62], поэтому его весьма изобретательно назвали BB84. Я не стану представлять здесь этот протокол в подробностях: они хоть и не слишком сложны, но не имеют для нас значения; во всяком случае, хороших описаний BB84 полно и в учебниках, и в сети.

Вместо этого позвольте мне просто изложить концептуальный вопрос о том, как квантовая механика в принципе могла бы обеспечить согласование секретного ключа без личной встречи Алисы и Боба и без всяких вычислительных предположений — то, что исключено в классическом мире в силу аргументов Шеннона (см. главу 8). Основная идея в том, что Алиса и Боб посылают друг другу кубиты, подготовленные случайным образом в двух или более неортогональных базисах; к примеру, пусть это будут четыре «состояния BB84»: |0〉, |1〉,

Затем они измеряют некоторые из кубитов, полученных ими в одном из двух случайных базисов ({|0〉, |1〉} или и посылают друг другу результаты по надежному классическому каналу, чтобы проверить, была ли передача успешной. Если нет, они могут попробовать еще раз. Если да, они могут использовать другие исходы измерений — те, которые они не передавали по открытому каналу, — для формирования общего секретного ключа. Ага, но откуда им знать, что третья сторона, известная как Ева, не отслеживала втайне эти кубиты? Ответ дает теорема о запрете клонирования! По существу, утверждается, что если бы Ева узнала что-то существенное о тех кубитах, то она не смогла бы при этом запихнуть кубиты обратно в канал, так чтобы они прошли проверку у Алисы и Боба с некоторой отличной от нуля вероятностью. Поскольку Еве неизвестен базис, в котором следует измерять каждый кубит, Алиса и Боб без труда заметили бы, что Ева мониторит канал. Единственное, что Ева смогла бы сделать, — это полностью перехватить канал и притвориться Алисой или Бобом, реализуя так называемую атаку посредника (или посредницы). Но для этого потребовалось бы скомпрометировать не только квантовый канал, но и классический, причем, как мы считаем, подтвержденный и надежный.

Кстати говоря, в статье Визнера было представлено еще одно поразительное приложение теоремы о запрете клонирования, приложение, очень интересующее меня последние несколько лет: квантовые деньги. Идея проста: если квантовые состояния действительно не поддаются точному копированию, то почему бы не воспользоваться этим свойством для создания денег, которые физические невозможно подделать? Однако, как только мы начинаем размышлять об этом, возникают проблемы: деньги полезны только в том случае, когда кто-то может проверить их и удостоверить их подлинность. Поэтому вопрос стоит так: можно ли получить квантовые состояния |ψ〉, которые законопослушные пользователи могли бы измерить, чтобы убедиться в их аутентичности, но которые фальшивомонетчики не могли бы измерить, чтобы скопировать? Визнер предложил схему, позволяющую этого добиться, — что интересно, ее надежность была строго доказана лишь недавно[63]. В его схеме задействованы ровно четыре состояния (|0〉, |1〉,

 — те самые, которые позже приобрели известность как состояния BB84.

Однако главным недостатком схемы Визнера было то, что проверить купюру на подлинность мог только банк, ее выпустивший, поскольку только банк знал, в каких базисах ({|0〉, |1〉,} или

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

И третий аспект квантовой механики, прежде чем мы закончим главу, — это квантовая телепортация. Название, разумеется, всего лишь приманка для публики, всегда готовой слушать падких на сенсации журналистов и жаждущей верить, что квантовая механика сделает возможным мир сериала Star Trek. На самом деле квантовая механика решает задачу, которой просто не было бы, если бы не сама квантовая механика! В классическом мире вы всегда можете «телепортировать» информацию, передав ее, к примеру, по Интернету. (В пять лет, когда я с интересом наблюдал за работой факсового аппарата в папином кабинете, для меня стало откровением, что бумага при этом не переносится и не материализуется в аппарате, а просто превращается в информацию и восстанавливается на приемном конце.) Проблема квантовой телепортации в следующем: а можно ли передать кубиты по классическому каналу? На первый наивный взгляд это представляется совершенно невозможным. Лучшее, что вы сможете сделать при использовании классического канала, — это передать результаты измерения состояния |ψ〉 в некотором базисе, но если не окажется, что этот базис включает |ψ〉, то информации на втором конце будет откровенно недостаточно, чтобы восстановить по ней |ψ〉. Поэтому в 1993 г., когда Беннетт и др.[64] открыли, что если у Алисы и Боба есть общая ЭПР-пара

то Алиса может передать Бобу произвольный кубит посредством протокола, в котором она посылает Бобу два