М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 61
Текст из файла (страница 61)
Аналогичный вывод об универсальности верен и для квантовых вычислений, если назвать набор элементов универсальнь~м длл квангаовых вьгчислений в том случае, когда любая унитарная операция может быть сколь угодно точно аппроксимирована квантовой схемой, содержащей только элементы из этого набора. Опишем три универсальные конструкции для квантовых вычислений. Эти конструкции построены одна на другой; в конечном счете получится, что любая унитарная операция может быть с произвольной точностью аппроксимирована с использованием следующих элементов: Адамара, сдвига фазы, скот и т/8. (Вы можете спросить, зачем включатЬ в этот список сдвиг фазы, если его можно сконструировать из двух элементов к/8; дело в том, что сдвиг фазы естественно возникает в устойчивых к ошибкам конструкциях, описанных в гл. 10.) Наша первая конструкция покажет, что любой унитарный оператор можно пгочно представить в виде композиции унитарных операторов, каждый из которых нетривиально действует только на подпространстве, порожденном двумя состояниями из вычислительного базиса.
Вторая конструкция, объединяющая первую с результатами предыдущего подраздела, дает точное представление любого унитарного оператора в виде композиции однокубитовых операторов и элементов скот. Наконец, третья конструкция показывает, что однокубитовый оператор можно с произвольной точностью аппроксимировать композицией элементов Адамара, сдвига фазы и к/8; отсюда с учетом второй конструкпди следует, что любой унитарный оператор можно с произвольной точностью аппроксимировать композицией элементов Адамара, сдвига фазы, скот и к/8.
Наши конструкции не позволяют оценить эффективность (полиномиальное или экспоненциальное количество элементов требуется для реализации данной унитарной операции?). В подрезд. 4.5.4 будет показано, что существуют унитарные преобразования, для аппроксимации которых требуется экспоненциально много элементов. Разумеется, цель теории квантовых вычислений— найти интересные семейства унитарных операторов, которые лгоагснв выполнить эффективно. Упражнение 4. 36.
Постройте квантовую схему, которая складьгвает два двух- битовых числа х и у по модулю 4. Иными словами, схема должна действовать по правилу )х, у) — + (х, х + у шог1 4) . 16 ква ма и в н сл 242 Глава 4. Квантовые схемы 4.5.1 Универсальность двухуровневых унитарных операторов Рассмотрим унитарную матрицу У, действуюшую в 4-мерном гильбертовом пространстве. В этом подразделе мы объясним, как можно разложить ее на произведение деухуровиевмх унигааримх матриц, т. е. унитарных матриц, нетривиально действующих не более чем на двух базисных векторах. Основную идею, на которой основано это разложение, можно уяснить на примере 3 х 3-матриц; итак предположим, что У имеет вид У= с е Й (4.41) Мы хотим найти такие двухуровневые унитарные матрицы Уь Уь Уз, что УзУзУгУ = 1 (4.42) Из этого равенства следует, что У = У~ Уэ Уз. 1 (4.43) (4.44) а если Ь ф О, то О ~~ р+~ь!* О ь/~~Р+Щ' О 1 (4.45) (а(~+ )ьр О Заметим, что в обоих случаях У~ является двухуровневой унитарной матрицей, и что в результате ее умножения на У получим а' а' д' О е' Ь' сФ ~/ 'Р (4.46) Существенным моментом здесь служит то, что средний.
элемент в левом столб- це равен нулю. Остальные элементы этой матршця обозначим буквами со штри- хами; их точные выражения для них нам не важны. Матрицы Уь Уэ и Уз, являются двухуровневыми унитарными. Нетрудно заметить, что таковы же и их обратные матрицы Ую Уэ и Уэ. Таким образом, если удастся доказать равенство (4.42), из этого будет следовать существование разложения матрицы У в произведение двухуровневых унитарных матриц. Для построения Уг воспользуемся следующей процедурой. Если б = О, то положим 4.5. Уннверсэльвые квантовые элементы 243 У,= О 10 (4.47) а если с' ф О, то (4.48) В каждом из этих случаев, если перемножить матрицы, получим (в а 0 е" Ь" 0 /в,у" У,У,У= (4.49) Так как матрицы У, У~ и Уз унитарны, то и матрица УО~Уэ унитарна, и тогда дв = йэ = О, поскольку норма первой строки должна быть равна единице. Положим, наконец, о о ~ 0 е"* 0 5"* (4.50) Легко проверить, что УэУэУ~У = Х, так что У = У~Уэ1Уэ1, что и дает разложение У на произведеяие двухуровневых унитарных матриц.
Рассмотрим более общий случай. Предположим, что У действует на Н- мерном пространстве. Тогда, действуя так же, как в 3 х 3-мерном случае, можно найти такие двухуровневые матрицы Ум..., Уэ и что произведение Уэ ~У4 э... У~У имеет единицу в верхнем левом углу и нули в остальных местах первой строки и первого столбца. Повторим эту процедуру для унитарной (4 — 1) х (д — 1)-матрицы, полученной вычеркиванием из матрицы Уэ ~Уа э... У~У первой строки и первого столбца, и т. д; в конце концов мы придем к разложению (4.51) где Ъ; — двухуровневые унитарные матрицы и й < (Н вЂ” 1) + (Ы вЂ” 2) +... + 1 = Н(Н вЂ” 1)/2. Упражнение 4.37. Разложите матрипу 1 1 1 — 1 — 1 1 — 1 †— 1 г (4.52) Теперь применим аналогичную процедуру, чтобы получить такую матрипу Ую что у произведения УзУ~У нуль стоит е левом нижнем углу.
Именно, если с' = О, положим 244 Глава 4. Квантовые схемы иа произведение двухуровневых унитарных матриц. (Это частный случай квантового преобразования Фурье; более подробио ои будет рассмотрен в следующей главе.) Из доказанного нами результата сле,зует, что всякая унитарная матрица, действующая иа и-кубитовой системе, может быть разложена в произведение ие более чем 2" 1(2" — 1) двухуровневых унитарных матриц.
Для коикретиых унитарных матриц можно иногда найти гораздо более эффективное разложеиие, ио, как вы сейчас докажете, существуют матрицы, которые нельзя разложить иа произведение менее чем д — 1 двухуровневых унитарных матриц. Упражнение 4.38. Докажите, что существует унитарная 4 х 4-матрица У, которую иельзя разложить иа произведение менее чем (и' — 1) двухуровиевых унитарных матриц. 1 0 1 0 0 1 1 0 1 О 1 1 1 0 0 0 1 1 1 1 0 0 1 1 (4.53) Пусть дь...,д — элемеиты кода Грея, соединяющего з и $, причем д1 = з и д,„= й Отметим, что всегда можно найти код Грея, для которого т < п+ 1, поскольку з и 1 могут отличаться ие более чем в и местах.
4.5.2 Универсальность набора из однокубитовых элементов и СХОТ Выше было показано, что любая унитарная матрица в 4-меряем гильбертовом пространстве может быть разложена иа произведение двухуровневых уиитаряых матриц. Теперь покажем, что одиокубитовых элементов вместе с элемеитом скот достаточно, чтобы реализовать произвольную двухуровневую операцию иа пространстве состояний и кубитов.
Объединяя эти два результата, можно видеть, что с помощью одяокубитовых и скот-элемеятов можно реализовать произвольную унитарную операцию иа п кубитах, так что набор из двухкубитовых и скот-элемеитов универсален для квантовых вычислений. Пусть У вЂ” двухуровневая унитарная матрица, действующая яа и-кубитовом квантовом компьютере. Предположим, У действуег нетривиально только иа подпростраистве, порождеивом состояниями (из вычислительного базиса) ~з) и ~г), где з = з1... з„и 1 = 11... Ц, — двоичные разложения для з и 1. Пусть У вЂ” нетривиальная унитарная 2 х 2-подматрица матрицы У; матрицу О можно рассматривать как унитарную матрицу, действующую иа одном кубите.
Наша ближайшая цель — реализовать У с помощью схемы, состоящей из одиокубитовых и скот-элемеятов. Для этого воспользуемся кодами Грея. Предположим, даны два разных двоичных числа з и й Тогда ход Грея, соединяющий з и $, — это последовательность двоичных чисел, начинающаяся з и закаячивающаяся 1, которая обладает тем свойством, что два соседних числа в этой последовательности отличаются ровно в одной позиции. Если, например, з = 101001 и 1 = 110011, то код Грея выглядит как 4.5. Универсальные квантовые элементы 245 (4 54) (4.55) (4.56) Ь -~) -' !д -г), (4.57) а все остальные состояния из вычислительного базиса остаются неизменными.
Предположим теперь, что д„, ~ и д отличаются в у-ом бите. Применим управляемое У, для которого управляемым будет у-й кубит, при условии, что значения всех остальных кубитов — те же, что у остальных битов в д„, ~ и д„,. Наконец, проведем обмен в обратном порядке: обменяем ~д ~) с ~д з), затем ~д -г) с )д -з) и т.д., пока не обменяются )дз) и )д~). Данную процедуру можно проиллюстрировать на простом примере. Предположим, необходимо выполнить преобразование, имеющее вид а О О О О О О с О 1 О О О О О О О О 1 О О О О О О О О 1 О О О О О О О О 1 О О О О О О О О 1 О О О О О О О О 1 О Ь О О О О О О И (4.58) Здесь а, Ь, с и 4 — произвольные комплексные числа, обладающие тем свой ~а с1 ством, что У ьз ~ ~ — унитарная матрица.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
