М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 59
Текст из файла (страница 59)
Таким образом, в этом базисе управляющий и управляемый кубиты поменялись ролями! Рис. 4.5. Управляемый сдвиг фазы и эквивалентная ему схема на двух кубитах Наша ближайшая цель — понять, как можно реализовать операцию «управляемое У» для произвольного У, действующего на одном кубите, с помощью операций на одном кубите и элемента скот. Наш план, основанный на разложении У = е«" АХВХС (см. следствие 4.2) состоит из двух частей. 232 Глава 4. Квантовые схемы Вначале применим к управляемому кубиту сдвиг фазы ехр(э«э), но не просто так, а в зависимости от состояния управляющего кубита. То есть, если управляющий кубит )О), то управляемый кубит не меняется, если же он равен )1), то к управляемому кубиту применяется сдвиг фазы на ст.
Схема, реализующая такую операцию с использованием элемента, действующего на одном кубите, изображена в правой части рис. 4.5. Чтобы убедиться в том, что данная схема действует именно так, как показано, заметим, что в вычислительном базисе это действие записывается следующим образом: )00) — )00), )01) -+ )01), )10) — е' )10), )11) — » е' )11), 14.28) и это согласуется с нашим описанием. Рис.
4.6. Схема, реаливующаи операцию «управляемое У», где У вЂ” операция на одном нубите а, А, В и С удовлетворяют соотношениям У = ехр1эих)АХВХС, АВС = 1 Далее мы утверждаем, что схема, изображенная на рис. 4.6, реализует операцию «управляемое У». Чтобы понять, почему это так, вспомним, что, согласно следствию 4.2, оператор У можно записать в виде У = е"*АХВХС, где А, В и С вЂ” такие операции на одном кубите, что АВС = 1.
Предположим, управляющий кубит установлен в единицу. Тогда операция е' АХВХС = У применяется ко второму кубиту. Если же управляющий кубит установлен в ноль, то ко второму кубиту применяется операция АВС = 1, т. е. он не меняется. Значит, эта схема действительно реализует операцию «управляемое У». п=4 к 3 Рис. 4.7. Иэображение операции С" (У), где У вЂ” унитарный оператор на Ь хубитах, п = 4, Ь = 3. Теперь, когда мы знаем, как схемы выполняют условные операции, завися- щие от состояния одного кубита, подумаем, как можно реализовать условные 4.3. Условные операции 233 операторы, зависящие от нескольких кубвтов. Выше приводится пример такого оператора — это элемент Тоффоли, который меняет состояние третьего (управляемого) кубита при условии, что оба управляющих кубита установлены в единицу. Более общая ситуация: (и+ к) кубит, и У вЂ” унитарный оператор, действующий на )с кубит. Определим операцию С" (У) по формуле Сп(У))хъхз...хп))ф) = )х~хэ...хп)У*'*з *"ф), (4.29) где хэхз...
х„в верхнем индексе У есть произведение битов хэ, хз,..., х„. Это означает, что оператор У применяется к )с последним кубитам, если и первых кубитов установлены в единипу; в противном случае ничего не происходит. Такие условные операторы настолько важны, что полезно ввести для них специальное обозначение, рис. 4.7. В дальнейшем для простоты примем к = 1; случай ббльших й может быть разобран аналогичным способом, но при к > 2 возникает дополнительная трудность, состоящая в том, что мы (пока) не умеем выполнять произвольные операции на й кубитах. Пусть У вЂ” унитарнцй оператор, действующий на одном кубите, и тт — такой унитарный оператор, что у'2 = У. Тогда операция Сз(У) может быть реализована с помощью схемы, изображенной на рис.
4.8. Рис. 4.8. Схема, реализующая элемент Сз(У). Р— произвольный унитарный оператор, удовлвтаоряющий условию рз = У Если р вз (1 — з)(7+ зХ)/2, то получится элемент Тоффоли Упражнение 4.21, Проверьте, что схема на рис. 4.8 выполняет операцию Сз(У). Упражнение 4.22. Докажите, что Сз(У) для любого однокубитового оператора У может быть представлено схемой, состоящей из < 8 однокубитовых элементов и 6 элементов СКОТ. Упражнение 4.23. Постройте схемы, реализующие С'(У) для У = В (8) и У = Вв(8), с помощью элемента скот и операций на одном кубите. Можно ли сократить число последних с трех до двух? Знакомый нам элемент Тоффоли является особенно важным частным случаем операции С2(У), а именно операцией С (Х). Если определить т' по формуле тт эз (1 — з)(1+ гХ)/2 и заметить, что 1тз = Х, то окажется, что на рис.
4.8 изображена реализация элемента Тоффоли с помощью одно- и двухкубитовых операций. С классической точки зрения это — удивительный результат: вспомните, что в задаче 3.5 мы убедились, что классических одно- и двухбитовых обратимых элементов недостаточно для того, чтобы реализовать элемент 234 Глава 4. Квантовые схемы Тоффоли и тем самым универсальное вычисление. В квантовом случае мы, напротив, видим, что одно- и двухкубитовых обратимых элементов достаточно, чтобы реализовать элемент Тоффоли, а в дальнейшем мы докажем, что их достаточно и для выполнения универсального вычисления.
Ниже мы покажем, что всякую унитарную операцию можно с любой точностью аппроксимировать композицией таких элементов, как элемент Адамара, сдвиг фазы, скот и т/8. На рис. 4.9 изображена простая схема, реализующая элемент Тоффоли. Рис. 4.9. Реализация элемента Тоффоли с помощью элемента Адамара, сдеига фазы, СМОТ и я/8 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 О 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 (4.30) 1. Реализуйте элемент Фредкина с помощью квантовой схемы, использующей три элемента Тоффоли.
(Указание: подумайте, как поменять местами значения двух булевых переменных с помощью трех сложений по модулю 2.) 2. Покажите, что первый и последний из этих элементов Тоффоли можно заменить на скот. 3. Замените средний элемент Тоффоли на схему, приведенную на рис. 4.8, и получите реализацию элемента Фредкина с использованием только шести двухкубитовых элементов. 4. Можно ли в этой последней конструкции обойтись лишь пятью двухкубитовыми элементами? Упражнение 4.24.
Проверьте, что на рис. 4.9 действительно изображена ре- ализация элемента Тоффоли. 'Упражнение 4.25 (реализация элемента Фредкина). Напомним, что эле- мент Фредкина (управляемый обмен) — это преобразование 4.3. Условные операции 235 Упражнение 4.26. Покажите, что схема отличается от элемента Тоффоли только относительными фазами: она переводит )сп сз, й) в ем<" "'>)сы сз,1 Ю с~сз), где ем<" еьй — относительный фазовый множитель. Такого рода схемы могут быть полезны в экспериментальных физических приложениях: может оказаться, что элемент, отличный от элемента Тоффоли на фазовый множитель, реализовать легче, чем сам элемент Тоффоли. Упражнение 4.27.
Пользуясь только элементами скот и Тоффоли, создайте квантовую схему, реализующую преобразование О 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 (4.31) Ниже (в гл. 7) мы воспользуемся такими «частичными циклическими перестановкамиэ. Как можно реализовать С" (У), где П вЂ” произвольная операция на одном кубите, используя только набор известных нам элементов? Простая схема, дающая ответ на этот вопрос, изображена на рис. 4.10.
Реализация проходит в три этапа с использованием небольшого числа (п — 1) рабочих кубитов, которые в начале и конце работы находятся в состоянии ~0). Пусть управляющие кубиты находятся в состоянии )сы сю..., с„) (мы работаем в вычислительном базисе). Первый этап работы схемы состоит в том, что над управляющими кубитами ем се,..., с„производятся операции «обратимое АХП», что дает в итоге произведение с«сз °... с„. Для этого первый элемент в схеме проводит операцию АМП над с«и сз с использованием элемента Тоффоли, в результате чего состояние первого рабочего кубита переходит в )с~ ° сз). Следующий элемент Тоффоли выполняет оператор над сз и с~ сз, так что состояние второго рабочего кубита переходит в )с~ сз сз).
Продолжая применить таким образом элементы Тоффоли, придем к тому, что последний рабочий кубит окажется в состоянии ~с~ сз...с„). Теперь над управляемым кубитом проводится операция У (в случае, если последний рабочий кубит установлен в единипу, т.е. тогда и только тогда, когда в единипу установлены все кубиты от с«до с„включительно). Наконец, иа третьем этапе работы схемы первый этап повторяется в 236 Глава 4. Квантовые схемы обратном порядке, и все рабочие кубиты возвращаются в состояние !О).
Общий итог состоит в том, что унитарный оператор 1г' применяется к управляемому кубиту тогда и только тогда, когда управляющие кубиты см..., с„установлены в единицу, чего мы и хотели. (с1) Управляющие иубиты )сз) (с4) !сб) (О) Рабочие ~ !О) кубиты !О) !О) Управляемый кубит Рис. 4.10. Схема, реализующая Сп(У), при и = б 'Упражнение 4.28. Пусть У = 'х'з, где У вЂ” унитарный оператор; постройте элемент Сз(У), аналогичный использованному на рис.
4.10, без использования рабочих кубитов. Вы можете пользоваться элементами «управляемое У» и «управляемое у'1». Упражнение 4.29. Постройте схему, использующую только элементы Тоффоли, скот и однокубитовые элементы, общим количеством 0(пз), реализующую элемент С" (Х) (и > 3) и не использующую рабочих кубитов.
'Упражнение 4.30. Пусть У вЂ” унитарная операция на одном кубите. Постройте схему, использующую только элементы Тоффоли, скот и однокубитовые элементы, общим количеством 0(пз), реализующую элемент С" (У) (п > 3) и не использующую рабочих кубитов. Рис. 4.11. Условная операция, в которой НОТ применяется ко второму кубиту в зависимости от того, установлен ли первый кубит в нуль До сих пор в условных операциях, которые мы рассматривали, оператор применялся к управляемому кубиту, если управляющие кубиты были установлены в единицу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
