М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 7
Текст из файла (страница 7)
Одного примера из атой области должно хватить, чтобы убедить вас в значимости такой общей теории. Предположим, что мы пытаемся передавать информацию от Алисы к Бобу по квантовому каналу с шумом. Если этот канал имеет нулевую пропускную способность для квантовой информации, то по нему нельзя надежно передавать никакую информацию. Теперь допустим, что мы рассматриваем две копии канала, работающие синхронно.
С интуитивной точки зрения очевидно (и это можно строго доказать), что для квантовой информации такой канал также имеет нулевую пропускную способность. Но если мы изменим направление одного из каналов на обратное, как показано на рис. 1.1, то оказываетсл, что иногда можно получить ненулевую пропускную способность для передачи информации от Алисы к Бобу! Противоречащие интуиции свойства наподобие только что описанного иллюстрируют странную природу квантовой информации.
Лучшее понимание возможностей передачи информации по сетям квантовых каналов представляет собой большую проблему в области квантовых вычислений и квантовой информации. Я 3 Рис. 1.1. Если в классичесном случае мы имеем два канала с сильным шумом и нулевой пропускной способностью. работающих параллельно, то объединенный канал также имеет нулевую пропускную способность. Неудивительно, что если изменить направление одного из каналов на обратное, то мы по-прежнему будем иметь нулевую пропускную способность. В квантовомеханическом случае обращение одного из наналов с нулевой пропускной способностью может позволить нам передавать информацию! 30 Глава 1. Введение и общий обзор Давайте сменим тему, обратившись к старому как мир искусству нриншографии.
Говоря в самых общих чертах, криптография решает проблему осуществления связи или вмчиегений е участием двух и более сторон, которые не могущ доверять друг другу. Самая известная криптографическая проблема— это передача секретных сообщений. Предположим, что две стороны желают засекретить связь. Например, вы хотите передать продавцу номер своей кредитной карты в обмен на товары, причем так, чтобы этот номер не могла перехватить третья сторона. Это делается при помощи криптографического протоюма. Далее в книге мы подробно опишем работу криптографических протоколов, а пока достаточно провести несколько простых разграничений.
Наиболее важно понимать различие между нрипшосисгагмами с сенрегпнььн нзючс,н (рггиаге веу) и криптосистемами с сгаармтььн ключом (риЫгс 'веу). Работа криптосистемы с секретным ключом основана на том, что две стороны, Алиса и Боб, используют для связи секретанмй ключ, известный только им. Точный формат ключа сейчас не имеет значения; представьте себе строку нулей и единиц. Главное в том, что этот ключ используется Алисой для шифрования информации, которую она хочет послать Бобу.
Зашифрованную информацию Алиса посылает Бобу, который теперь должен восстановить исходную информацию. Как именно Алиса зашифрует сообщение — зависигп от секретного ключа, поэтому для восстановления исходного сообщения Боб должен знать этот ключ, чтобы обратить примененное Алисой преобразование.
К сожалению, криптосистемы с секретным ключом имеют недостатки во многих отношениях. Наиболее фундаментальный вопрос — как распределять ключи? Проблема распределения ключей по своей сложности во многом аналогична исходной проблеме секретной связи — третья сторона может перехватить ключ, а затем использовать его для расшифровки передаваемых сообщений. Одним из самых первых открытий в области квантовых вычислений и квантовой информации стал тот факт, что квантовая механика позволяет исключить нарушение конфиденциальности при распределении ключей. Соответствующая процедура известна как квантповол нри©тпографил или явантповое распределение нзючсй.
Основная идея заключается в том, чтобы использовать квантовомеханический принцип, согласно которому наблюдение в общем случае возмущает наблюдаемую систему. Если злоумышленник попытается вести подслушивание во время передачи ключа между Алисой и Бобоы, то его присутствие будет проявляется в виде возмущения канала связи, используемого Алисой и Бобом для согласования ключа. В таком случае Алиса и Боб могут отбросить биты ключа, принятые во время подслушивания, и начать все заново. Принципы квантовой криптографии были впервые предложены Стивеном Уиснером в конце 60-х гг., но, к сожалению, его работу не приняли к печати! В 1984 г. Чарльз Беннет и Джилльз Брассар, опираясь на более раннюю работу Унснера, предложили квантовомеханический протокол распределения ключей, исключающий любую возможность их компрометации. С тех пор было предложено множество квантовых криптографических протоколов и разработано не меньшее количество их экспериментальных прототипов.
На момент написания 1.1. Глобальные перспективы 31 книги эти прототипы почти достигли такого состояния, когда они могут быть полезны в реальных приложениях ограниченного масштаба. Вторым важным типом криптосистем являются криптосистемы с открытым ключам. Эти криптосистемы не опираются на предварительную передачу секретного ключа между Алисой и Бобом. Вместо этого Боб просто публикует свой «открытый ключ», делал его доступным всем желающим. Алиса может воспользоваться этим открытым ключом для шифрования сообщения, посылаемого Бобу. Интересно, что при этом третья сторона не может использовать открытый ключ Боба для расшифровки сообщения! Точнее говоря, шифрующее преобразование выбирается настолько хитроумным и нетривиальным способом, что его исключительно трудно (хотя в принципе возможно) обратить, зная только открытый ключ.
Чтобы обращение было простым для Боба, у него есть сенретнь«6 ключ, соответствующий открытому ключу. Вместе эти ключи позволяют с легкостью выполнять расшифровку. Секретный ключ известен только Бобу, и это дает ему определенную степень уверенности, что никто другой не сможет прочитать сообщение Алисы.
Действительно, вряд ли у кого-то окажется достаточно вычислительных ресурсов, чтобы обратить шифр только по открытому ключу. Таким образом, криптосистемы с открытым ключом решают проблему распределения ключей, делая ненужной передачу секретного ключа перед установлением связи. Удивительно, что криптография с открытым ключом, которая произвела революцию в области криптографии, не получала широкого распространения до середины 70-х гг., когда она была независимо предложена Уитфилдом Диффи и Мартином Хеллманом, а также Ральфом Меркле. Немного позже Рональд Райвест, Ади Шамир и Леонард Эдельман разработали криптосистему ВЯА, которая на момент написания книги является наиболее распространенной криптосистемой рассматриваемого типа, превосходно сочетающей в себе безопасность и практичность.
В 1997 г. выяснилось, что все это — криптография с открытым ключом, криптосистемы Диффи-Хеллмана и ВЯА — на свмом деле было изобретено в конце 60-х и начале 70-х гг. исследователями из Британского разведывательного управления ССН1г. Безопасность криптосистем с открытым ключом основана на том факте, что обращение стадии шифрования только при наличии открытого ключа в общем случае должно быть затруднительным. Например, оказывается, что задача обращения стадии шифрования ВЯА тесно связана с задачей факторизации. Предположение о безопасности ВЯА во многом обусловлено верой в то, что задачу факторизации трудно решить на классическом компьютере. Однако быстрый алгоритм факторизации на квантовом компьютере, разработанный Шорам, мог бы использоваться для взлома ВЯА! Другие криптосистемы с открытым ключом также могли бы быть взломаны, если бы был известен быстрый классический алгоритм решания задачи о вычислении дискретного логарифма, подобный шоровскому квантовому алгоритму вычисления дискретного логарифма.
Именно это практическое применение квантовых компьютеров— взлом криптографических кодов — в значительной степени стимулировало интерес к квантовым вычислениям и квантовой информации. 32 Глава 1. Введение и общий обзор Вьппе мы рассматривали исторические корни квантовых вычислений и кваытовой информации. Конечно, с ростом и развитием этой области из нее выделились самостоятельные подобласти исследований. Возможно, наиболее поразительным из них является изучение кзаншозой заиутианносгаи. Запутанность — это уникальный квавтовомеханический ресурс, который играет ключевую роль во многих наиболее интересных применениях квантовых вычислений и квантовой информации; это своего рода железо в бронзовом веке классического мира. Запутанность считается фундаментальным ресурсом Природы, сравнимым по важности с энергией, информацией, энтропией или любым другим фундаментальным ресурсом.
В последние годы предпринимаются огромные усилия, направленные на лучшее понимаыие ее свойств, Хотя законченной теории запутанности пока ыет, к настоящему времени удалось достичь некоторого прогресса в понимании этого странного понятия квантовой механики. Многие исследователи надеются, что дальнейшее изучение свойств запутанности даст сведения, которые будут способствовать разработке ее новых применений в области квантовых вычислений и квантовой информации.
1.1.2 Направления будущих исследований Мы немного познакомились с историей и современным состоянием квантовых вычислений и квантовой информации. Что ждет нас в будущем? Что могут предложить квантовые вычисления и квантовая информация науке, технике и всему человечеству? Что нового дает эта область по сравнению с ее родительскими дисциплинами — информатикой, теорией информации и физикой? Каковы основные нерешенные проблемы? Перед тем, как переходить к более подробному описанию вычислений и квантовой информации, мы сделаем несколько очень коротких замечаний по этим глобальным вопросам.
Квантовые вычисления и квантовая информация научили нас думать о вычислениях физически, и мы обнаружили, что этот подход открывает много ыовых возможностей в области связи и обработки информации. Специалисты по информатике и теории информации получили новую плодотяорную парадигму для исследований. Более того, фактически мы поняли, что любая физическая газаров, а не только квантовая механика, может служить базисом для теории обработки информации и теории связи. В результате этих исследований однажды могут быть созданы устройства обработки иыформации, намного превосходящйе по своим возможностям совремеыные вычислительные и коммуникационные системы, что будет иметь свои положительыые и отрицательные последствия для всего общества. Конечно, квантовые вычисления и квантовая информация ставят перед физиками массу задач, но при этом не совсем понятно, что зта область предлагает физике в долгосрочной перспективе.