М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 12
Текст из файла (страница 12)
Если Алиса вьпюлняет измерение и получает результат [00), то система Боба будет в состоянии имеющихся у нее кубита в базисе Велла, получая один из четырех возможных классических результатов — 00, 01, 10 и 11. Она посылает эту информацию Бобу. В зависимости от классического сообщения Алисы Воб выполняет одну из четырех операций над своей половиной ЭПР-пары. Кэк ни удивительно, это позволяет ему Восстановить исходное состояние ]эр)! 1.3. Квантовые вычисления 51 [ф. Таким образом, из приведенного выше выражения мы можем определить состояние кубнта Боба после измерения, выполненного Алисой: 00 -+ [э'з(00)) щ [а[0) + р[1)] 01 - фз(01)) ж [а[1) + 0[0)] 1о [~з(10)) = [а[о)-1311)] 11 - 14з(11)) ш [а[1)-)?10)]. (1.33) (1.34) (1.35) (1.36) В зависимости от исхода измерения Алисы кубит Боба окажется в одном из этих четырех возможных состояний.
Конечно, чтобы зыать, в каком состоянии находится кубит, Боб должен получить результат измерения Алисы. Далее мы покажем, что именно это обстоятельство не позволяет использовать телепортацию для передачи информации со скоростью, превышающей скорость света. Как только Боб узнает исход измерения, он может эподправитьэ состояыие своего кубита и восстановить [ф), применив подходящий квантовый элемент. Например, когда измерение дает 00, Бобу не нужно ничего делать.
Если измерение дает 01, то Боб может скорректировать свое состояние, применив элемент Х. Если измерение дает 10, то Боб может скорректировать свое состояние, применив элемент Я. Если измерение дает 11, то Воб может скорректировать свое состояние, применив сначала элемент Х, а затем элемент 2. В общем случае Бобу нужно применить к этому кубиту преобрэзоваыие Я~'Х~' (обратите внимание, что на схемах время идет слева ыаправо, тогда как в матричыых произведениях сомножители перемножаются справа налево); при этом он восстановит состояние [э'). Телепортация имеет много интересных свойств; позже мы вернемся к некоторьгм из них, а сейчас ограничимся двумя комментариями. Во-первых, не позволяет ли телепортацвя передавать квантовые состояния со скоростью, быстрее скорости света? Это было бы весьма странно, поскольку из теории относительности следует, что передача информации быстрее света могла бы использоваться для отправки информации в прошлое.
К счастью, квантовая телепортация не дает возможности устанавливать сверхсветовую связь, поскольку для завершения телепортации Алисе необходимо передать результат своего измерения Бобу по классическому каналу связи. В подрэзд. 2.4.3 мы покажем, что без этой классической связи телепортацня не переносит вообще никаяоа информации. Классический канал ограничен скоростью света, и, следовательно, квантовая телепортэция не может осуществляться быстрее скорости света, что и разрешает кажущийся парадокс. Второй парадокс телепортации состоит в том, что она, казалось бы, создает копию телепортируемого квантового состояния, тем самым нарушая теорему о невозможности копнроваыия, обсуждавшуюся в подрэзд.
1.3.5. Но это нарушение кажущееся, так как по завершении процесса телепортацни только управляемый кубит остается в состоянии [э'), а исходный кубит данных оказывается в ~дном из состояний вычислительного базиса, 10) или 11), в зависимости от результата измерения первого кубита.
52 Глава 1. Введение и общий обзор Чему нас может научить квантовая телепортация? Довольно многому! Она представляет собой гораздо больше, чем просто ловкий трюк, который можно проделывать с квантовыми соетояниями. Квантовая телепоргация подчеркивает взаимозаменяемость раэличныз ресурсов в квантовой механике, показывая, что одна разделяемая ЭПР-пара вместе с двумя классическими битами связи является ресурсом, как минимум эквивалентным одному кубиту связи. Квантовые вычисления и квантовая информация выявили массу методов обмена ресурсами, многие из которых построены на квантовой телепортации. В частности, в гл.
10 мы объясним, как можно использовать телепортацию для построения квантовых элементов, устойчивых к воздействию шума, а в гл. 12 покажем, что телепортация тесно связана со свойствами кодов, исправляющих квантовые ошибки. Справедливости ради следует сказать, что несмотря на эти связи с другими дисциплинами, мы только начинаем понимать, почему в квантовой механике возможна квантовая телепортация; в последующих главах мы попытаемся разъяснить некоторые соображения, делающие возможным такое понимание. 1.4 Квантовые алгоритмы Вычисления какого класса можно выполнять при помощи квантовых схем? Как этот класс соотносится с вычислениями, которые можно выполнять с использованием классических логических схем? Можно ли найти задачу, которую квантовый компьютер способен решать лучше, чем классический? В этом разделе мы исследуем перечисленные вопросы, объясняя, как выполняются классические вычисления на квантовых компьютерах, приводя некоторые примеры задач, для которых квантовые компьютеры имеют преимущества перед классическими, и характеризуя известные квантовые алгоритмы.
1.4.1 Классические вычисления на квантовом компьютере Момаю ли смоделировать классическую логическую схему при помощи квантовой а~емы? Неудивительно, что ответ на этот вопрос оказывается положительным. Очень неожиданно было бы, окажись это не так, поскольку физики уверены, что все аспекты окружающего мира, включая классические логические схемы, могут быть в конечном счете объяснены квантовой механикой. Как отмечалось ранее, причина, по которой квантовые схемы не могут использоваться для непосредственного моделирования классических схем, состоит в том, что унитарные квантовые логические элементы по своей природе обрагнимм, тогда как многие классические логические элементы, такие как г1АНП, принципиально необратимы.
Любую классическую схему можно заменить эквивалентной схемой, содер жащей только обрагннл4ые элементы, используя обратимый элемент, известный как элемента Таффоли. Элемент Тоффоли имеет три входных и три выходных бита, как иллюстрируется на рис. 1.14. Два бита являются рнраеляющалю, и действие элемента их не меняет.
Третий бит является рпраеллемььн; он ин- 1.4. Квантовые алгоритмы 53 вертируется, когда оба управляющих бита установлены в 1, и не меняется в противном случае. Заметьте, что двукратное применение элемента Тоффоли к набору битов дает (а, Ь,с) -+ (а, Ь,сгваЬ) -+ (а,Ь,с), и, следовательно, элемент Тоффоли обратим, поскольку имеет обратный элемент — самого себя. су аЬ Рис. 1.14. Таблица значений для элемента Тоффоли и его условное обозначение Элемент Тоффоли может применяться для моделирования элементов 1ч АХП (рис. 1.15), а также для выполнения операции РАХОВ (рис.
1.16). Используя эти две операции, можно моделировать все остальные элементы классической схемы, и, следовательно, произвольная классическая схема может быть смоделирована эквивалентной обратимой схемой. (аЬ) Рис. 1.1б. Классическая схема, реализующая элемент НАМ0 при помощи элемента Тоффоли Деа еергних бита представлмот входы элемента МАМ0, а третий бит устанавливается в состояние 1, иногда наэываемсм вспомогательным состоянием (апнйа агате). Выходом элемента мАм0 является зретий бит. Элемент Тоффоли был описан как классйческий элемент, но его можно реализовать и как квантовый элемент.
По определению, квантовая реализация элемента Тоффоли просто меняет состояния вычислительного базиса таким же образом, как и классический элемент Тоффоли. Например, квантовый элемент Тоффоли, действующий на состояние ~110), инвертирует третий кубит, поскольку первые два установлены в 1, что дает в результате ~111).
Это преобразование нетрудно (хотя и утомительно) записать в виде матрицы У размера 54 Глава 1. Введение и общий обзор 8 х 8 и явно проверить, что онв унитарна, а, следовательно, элемент Тоффоли является допустимым квантовым элементом. Квантовый элемент Тоффолн, как и его классический вариант, можно использовать для моделирования необратимых классических логических элементов. Это озыачэет, что квантовые компьютеры способны выполнять любые вычисления, которые возможны на классическом (детерминированном) компьютере. 1 1 0 а Рис. 1.16. Реализация ЕАНООТ при помощи алемента Тоффоли Второй бит — вход элемента РАМООТ, два других бита вспомогательные. Выход влемента РАМООТ вЂ” второй и третий биты. А если классический компьютер — вероятностный, т.
е. способен генерировать случайные биты для использования в вычислениях? Неудивительно, что квантовый компьютер может с легкостью моделировать и этот случай. Окэзывзется, по для такого моделирования достаточно производить случайные подбрасывания моыеты, что может быть сделано путем приготовления кубита в состоянии )О), применения к нему элемента Адамара для получения ()О)+ ~1))/т/2 и последующего измереыия состояния. Результатом будет ~0) или ~1) с вероятностью 50/50.