М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 62
Текст из файла (страница 62)
Заметим, что У действует Основная идея построения квантовой схемы, реализующей У, состоит в том, чтобы с помощью последовательности элементов провести преобразования ~д~) -+ ~дз) — ... « ~д ~), затем провести операцию «управляемое У», у которой управляемый кубит соответствует тому единственному биту, в котором различаются д«« ~ и д»», и затем выполнить операции первого шага в обратном порядке ~д»» ~) -+ ~д,„-э) — ... -+ ~д~).
Каждый из этих шагов легко выполнить с помощью операций, описанных выше в этой главе, а в результате получится реализация матрицы У. Более подробное описание этой процедуры выглядит так. На первом шаге производится обмен состояний )д~) и ~дз): если д~ и дэ различаются в 1-ом бите, то применяется управляемое нот к г-му кубиту при условии, что все остальные кубиты те же, что и остальные биты в д~ и дз. Затем опять с помощью управляемой операции выполняется обмен ~дэ) и ~дэ) и т. д. — пока не произойдет обмен ~д,„з) и ~д ~).
В результате этих (т — 2) операций имеет место перестановка 246 Глава 4. Квантовые схемы нетривиально только на состояния ~000) и (111). Запишем код Грея, соеди- няющий 000 и 111: А В С 0 0 0 0 0 1 0 1 1 1 1 1 (4.59) Отсюда можно получить требуемую схему (рис. 4.16). Первые два элемента переставляют состояния таким образом, что (000) обменивается с ~011). Затем операция У применяется к первому кубиту состояний ~011) и ~111) при условии, что второй и третий кубиты находятся в состоянии ~11). Наконец, мы снова переставляем состояния, в результате чего )011) снова меняется с (000).
Рис. 4.18. Схема, реализующал двухуровневую унитарную операцию, заданную матрицеа (4.58) В общем случае можно сформулировать, что для реализации двухуровнего унитарного оператора требуется не более 2(п — 1) условных операций (чтобы обменять )д1) с ~д 1), а затем произвести обратный обмен). Каждую из этих операций можно выполнить с помощью 0(п) однокубитовых и снотэлементов; для управляемого У также необходимо 0(п) элементов. Таким образом, У реализуется с помощью 0(пз) однокубитовых и скот-элементов. В предыдущем разделе мы видели, что произвольная унитарная матрица на 2"-мерном пространстве состояний п кубитов может быть записана как произведение 0(2эв) = 0(4") двухуровневых унитарных матриц.
Объединяя эти результаты, получим, что любая унитарная операция на и кубитах может быть осуществлена с помощью схемы, содержащей 0(пз4") однокубитовых и снотзлементов. Ясно, что эта процедура дает не самые эффективные квантовые схемы! Тем не менее в подразд. 4.5.4 будет показано, что данная конструкция близка к оптимальной в том смысле, что существуют унитарные операции, для реализации которых необходимо экспоненциальное количество элементов. Значит, для нахождения быстрых квантовых алгоритмов требуется подход, отличный от примененного в доказательстве универсальности. 4.5.
Универсальные квантовые элементы 247 'Упражнение 4.39. Найдите квантовую схему из однокубитовых и снот- элементов, ревлизующую преобразование 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 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 4 (4.60) ~ а с ) где У = ~ „~ — произвольная унитарная 2 х 2-матрица. 4.5.3 Конечный набор универсальных операций В предыдущем подразделе было показано, что снст и однокубитовые унитарные операторы образуют универсальное семейство для квантовых вычислений.
К сожалению, неизвестен прямой метод, позволяющий реализовать все эти элементы устойчивым к ошибкам образом. Однако, в этом подразделе мы найдем конечный набор элементов, с помощью которого можно проводить универсальные квантовые вычисления, а в гл. 10 будет показано, как использовать квантовые коды, исправляющие ошибки, для устойчивой к ошибкам реализации этих элементов. Аппроксимация унитарных операторов Ясно, что с помощью конечного набора элементов невозможно точно реализовать произвольный унитарный оператор, поскольку множество унитарных операторов имеет мощность континуум. Тем не менее оказывается, что с помощью конечного множества можно аппроксимировать любую унитарную операцию.
Чтобы знать, как это получается, необходимо понять, что такое аппроксимация унитарного оператора вообще. Пусть У и $' — два унитарных оператора на одном и том же пространстве состояний, причем У вЂ” тот оператор, который мы хотим приближенно реализовать, а г' — его приближенная реализация. Определим оиьибху по формуле Е(У, г') ы шах ИУ вЂ” Ъ'))4Ц, !Ф> (4.61) где максимум берегся по всем нормализованным квантовым состояниям ~ф) в пространстве состояний. Во вставке 4.1 будет показано, что определенная таким образом ошибка обладает следующим свойством: если Е1У, Ъ') малб, то для любого начального состояния ~ф) всякое измерение состояния Ъ'(~ф)) дает примерно ту же статистику измерений, что и измерение состояния У(ф)).
248 Глава 4. Квантовые схемы Точнее говоря, если М есть РОМ-элемент в произвольном РОМ и если Р1~ (соответственно Рг) — вероятность получения этого результата при примене- нии У (соответственно Ъ') к начальному состоянию !ф), то (4.62) !Ри — Рг! < 2ЕЯУ). Таким образом, если Е(0, У) малб, то результаты измерений имеют близкие ве- роятности, будь то измерение У или У. Во вставке 4.1 также показано, что если применить последовательно элементы Ъ'ы..., У, являющиеся приближениями к элементам Ум ., У„„то ошибки накапливаются не более, чем линейно: Е(0 П -г ° У1 1г ~Уж-т Ъ~) < „) Е(Ц Р)) (463) 1=~ Вставка 4.1.
Аппроксимация квантовых схем Пусть квантовая система первоначально находится в состоянии !ф) и над ней выполняется либо унитарная операция У, либо унитарная операция Ъ'. После этого проводится измерение. Пусть М вЂ” РОЧМ-элемент, отвечающий этому измерению и Ри (соответственно Рг) — вероятность получения соответствующего М результата измерений после выполнения операции У (соответственно У). Тогда имеем !Рь — Рк ! = Я!Гг1МП)Я вЂ” (фЪ'1ЛЛ~!ф! (4 64) Положим !Д) кз (У вЂ” У)!ф).
Простые выкладки с использованием неравен- ства Коши-Шварца показывают, что Неравенство (ЕЪ вЂ” Рт ! < 2ЕЩ У) является количественным выражением того обстоятельства, что при малой ошибке Е(Ц У) разность вероятностей соответствующих результатов измерений также мала. Пусть теперь мы применили последовательность операторов Ры Ур,..., К„, являющихся приближениями к операторам Уп Уз,..., У„соответственно. Тогда оказывается, что ошибка, вызываемая применением этой последовательности «несовершенныхэ операторов, не превосходит суммы ошибок отдельных операторов: пв Е(У~У~ ~...Ум7~$~а ~...Ъ~) <~ Е(Ц,У1).
(4.69) 1=1 !1Ъ вЂ” Р( ! = !(Ф!П'М!Д)!+ (Д!М1г)М < !щи1М!д) + !(д!МЪ !6)! < !(!д)(!+ !!!д)!! < 2ЕЯ У). (4.65) (4.66) (4.67) (4.68) 4.5. Универсальные квантовые элементы 249 Доказательство этого начнем с рассмотрения случая т = 2. Заметим, что для некоторого состояния ~ф) имеем Е(УгУ„Угр;) = ЦУгУг — Ю;)~ФЦ (4.70) = ~ИУгУ1 ЪЪУ1)~ф) + (УгУг Ъър~)~фЦ (4 71) Пользуясь неравенством треугольника )()а) + (Ь) (! < ~()аЦ + ()(Ь) 3, получим Е(УгУм УгЮ < 1!(Уг — Ъя)У1!Ф)!1 + 'гЪг(Уг — \ч)гф) г (4 72) < Е(Ую Уг) + Е(Ум Ъ"г ) (4.73) что и требовалось доказать.
Результат для произвольного т выводится отсюда по индукции. Неравенства (4.62) и (4.63) очень полезны. Действительно, предположим, мы хотим провести вычисления с помощью квантовой схемы, состоящей из т элементов Уп, У . К сожалению, все, что мы можем,— это аппроксимировать элементы Уг с помощью элементов ~'. Для того чтобы вероятности результатов измерений приближенной схемы не более чем на А ) 0 отличались от истинных вероятностей, достаточно, учитывая неравенства (4.62) и (4.63), добиться того, чтобы выполнялось неравенство Е(У, 1') < А/2т, Универсальность набора, состоящего из элементов Адамара, сдвига фазы, СКОТ и я/8 Теперь мы, наконец, можем изучить аппроксимацию произвольных унитарных операторов с помощью конечного набора элементов.
Рассмотрим два разных конечных набора, каждый нз которых является универсальным. Первый из ннх, называемый стандартным универсальным набором, состоит из элементов Адамара, сдвига фазы, скот и я/8. В гл. 10 будут приведены конструкции устойчивых к ошибкам реализаций этих элементов; доказательство универсальности этого набора очень простое. Второй набор состоит из элементов Адамара, сдвига фазы, енот и Тоффоли.
Упомянутые элементы также можно реализовать устойчивым к ошибкам способом, но доказательство универсальности и устойчивая к ошибкам реализация в этом случае более трудные. Начнем доказательство универсальности с того, что установим, что с помощью элемента Адамара и элемента я/8 любую однокубитовую операцию можно аппроксимировать с произвольной точностью. Рассмотрим элементы Т и НТН. Элемент Т является с точностью до не играющего роли общего фазового множителя поворотом сферы Блоха на угол я/4 относительно оси й, а элемент НТН вЂ” поворот той же сферы на я/4 относительно оси х (упр. 4.14). Взяв композицию этих двух операций, получим с точностью до общей фазы соотношения 250 Глава 4.
Квантовые схемы ехр( — г — Ыехр/ — г — Х1 = [соз — 1 — «ьйп — Я] [соз-1 — бюп — Х) (4.74) згг .г гг я 1, гг = соэ — 1 — г ~соз — (Х + Я) + эш — У~ зш —. (4.75) 8 1 8 8 ] 8 Это — поворот блоховской сферы относительно оси, параллельной вектору В = (соз —, згп э, соэ -) (обозначим соответствующий единичный вектор через 6) на угол В, определяемый из соотношения соз(В/2) ы сов~ $. Значит, пользуясь только элементом Адамара и элементом я/8, можно сконструировать Вг,(В).
Более того, можно показать, что отношение этого угла В к 2я иррационально; доказательство последнего факта выходит за рамки нашей книги (см. «Историю и дополнительную литературу» в конце главы). Теперь покажем, что итерациями В„-В)), можно с произвольной точностью аппроксимировать любой поворот вида Ва(а). Пусть нам нужна аппроксимации с точностью б > 0 и Ж вЂ” целое число, большее 2гг/б. Определим Вь исходя из соотношений Вь Е [О; 2я) и Вь = йВ шоб 2я. Из принципа Дирихле вытекает, что на отрезке [1; АГ] найдутся два различных целых числа г' и Й, обладающих тем свойством, что [Вь — В [ < 2х/Агг, так что имеем [Вь 1] < б.
Поскольку г' ф й, и В есть иррациональное кратное 2х, имеем Вь 1 ~ О. Отсюда следует, что члены последовательности Вггь ~, где г варьируется, можно расположить на интервале [О; 2я) таким образом, чтобы соседние числа отличались друг от друга не более чем на б. Отсюда следует, что для всякого е > 0 существует такое и, что Е(Ва(а), Ва(В) ) < (4.76) 'Упражнение 4.40. Покажите, что для любых а и ~9 выполнено неравенство (4.77) Е(Ва(а), В;,(а + гЗ)) = ]1 — ехр(«В/2)], и выведите отсюда (4.76).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
