М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 178
Текст из файла (страница 178)
Покажите, что существуют два одномерных неприводимых представления группы Яэ, одно из которых — тривиальное, а второе имеет вид 1, 1, 1, — 1, — 1, — 1 (порядок чисел соответствует приведенному выше порядку элементов группы Яз). Покажите также, что существует двумерное неприводимое представление, состоящее из матриц где величины р, д и бр» имеют тот же смысл, что и в теореме, а 1л» вЂ” значение, которое принимает характер р-го неприводимого представления на»тм клас- се сопряженных элементов группы С; т; — мощность ого класса сопряженных элементов. 746 Приложение 2.
Теория групп — ~Гз ~/3 — 1 ' 2 О 1 2 -1 О~ Ь[ (П2.5) Проверьте, что указанные выше двумерное и нетривиальное одномерное пред- ставления ортогональны. = — Я г*Ю'Хь 1 !С),, * (П2.6) 'Упражнение П2.19. Покажите (с использованием теоремы П2.6), что регулярное представление содержит по Нр экземпляров каждого неприводимого представления рг.
Другими словами, если Я обозначает регулярное представление, а через С вЂ” множество всех неэквивалентных неприводимых представлений, то Х," = ~4Х,'. ред (П2.7) П2.2.3 Регулярное представление Число 1 является допустимым одномерным матричным представлением для любой группы,— оно тривиальное.
Представление относят к точиъьи, если группа матриц представления изоморфиа исходной группе. Регулярным называют точное представление, построенное по еле,сующим правилам. Пусть д = ~дпдю...,дщ)~ — вектор-столбец элементов из группы С. Умножение всех элементов из д на элемент д е С приводит к перестановке этих элементов, которая может быть представлена матрицей размера (С) х )С), умножаемой на вектор д по обычным правилам умножения матрицы на вектор-столбец. Получаемые ~С~ таких матриц, соответствующие различным перестановкам, образуют точное представление группы С (с операцией умножения матриц).
Упражнение П2.17. Докажите, что регулярное представление действительно является точным. Упражнение П2 18. Покажите, что характер регулярного представления равен нулю, за исключением представления единичного элемента, для которого х(1) =)С). Разложения произвольных представлений в прямые суммы неприводимых представлений удовлетворяют следующей теореме.
Теорема П2.5. Если р — произвольное представление группы С с характером Х, а рэ — неэквивалентные неприводимые представления С с характерами Х", то р = Юрсррэ, где знак «Ю» обозначает прямую сумму, а ср — числа, определяемые формулой П2.2. Представления 747 "ргпражнение П2.20.
Характер регулярного представления равен нулю, кро- ме того класса сопряженных элементов г, который содержит единичный эле- мент е группы С. Покажите, что ~ и ХР(д) =1999' реС (П2.8) упражнение П2.21. Докажите справедливость равенства ,'С с а~~ = ~С~. П2.2.4 Преобразования Фурье Пусть С вЂ” конечная группа порядка Ж, у — функция, отображающая элементы груйпы во множество комплексных чисел. Для неприводимого представления р группы С (размерность которого равна Нр) определим преобразование Фурье 1 функции 7 следующим образом". 1(д) = — ~( ф ~ У(д)а(д). (П2.9) 1(д) —,>, ЯМЯд)р(д )) 1 РЕС (П2.10) Поскольку 2 Рр = М, обе функции 1 и 7' могут быть представлены в виде и-мерных векторов над комплексным пространством.
Коэффициенты в двух предыдущих уравнениях были выбраны таким обрезом, что если С состоит из унитарных представлений, то преобразования Фурье являются унитарными. Приведенные выше определения легко понять, если подставить выражение (П2.9) в (П2.10): )'(д) = — ~ ~~ Ирод ) сг(р(д )р(д )) = 1 реС9 ЕС вЂ” Ир7'(д') Сг(р(д'д 1)) = 1 рес 9'ЕС 1 = у ~„У(д') ~4х'(д'д ') 9 ЕС РЕС (П2.11) (П2.12) (П2.13) Обратите внимание, что р — матричное представление, 1(р) отображает матрицы в матрицы. Пусть С вЂ” полный набор неэквивалентных неприводимых представлений группы С. Определим обратное преобразование Фурье от у следуюшдм равенством: 748 Приложение 2. теория групп С использованием уравнения (П2.8) можно упростить (П2.13) до следующего вида: ~(д) ~~~ ~(д )бд д (П2.14) д'ео что и требовалось.
'Упражнение П2.22. Подставьте выражение (П2.10) в (П2.9) и убедитесь, что действительно получается функция у'(р). 'Упражнение П2.23. Рассмотрим представления абелевой группы С остатков от деления на 57, в которой групповой операцией является сложение по модулю )у'. По определению, рь(д) = ехр[ — 2х1дй/57) для Ь-го представления д, д е [О, г7 — 1). Это представление является одномерным, поэтому 4р — — 1. Покажите, что уравнения (П2.9), (П2.10) в данном случае выглядят следующим образом: и-1 лч1 ~(Ь) = — ~, У(д)е ~ 'д"~", ~Я = — 2 Яд)е~~ д"~~. (П2,15) Упражнение П2.24. Постройте (с использованием результатов упражнения П2.16) преобразование Фурье на группе оз и запишите его в виде унитарных матриц размера 6 х 6.
История и дополнительная литература По теории групп написано много выдающихся книг, и почти все учебники по алгебре содержат раздел, посвященный этой области математики.' Б данном приложении в значительной мере использованы обозначения из книги Ломонта [260]. Стандартным введением в теорию групп для физиков является учебник Хаммермеша [176]. Преобразования Фурье на произвольных группах не являются широко распространенными. Имеется хорошая статья Диакониса и Рокмора об эффективном выполнении преобразований Фурье на группах [129); многие их результаты обсуждаются в книге Фэсслера и Стифела [154].
Быстрое преобразование Фурье на группах независимо открыли Бет [50] и Клаузен [90). 1 На русском языке см, например, Вииберг 3 В. Алгебра М: Фрактал, 1999 — Прим ред Приложение 3 ТЕОРЕМА СОЛОВЕЯ вЂ” КИТАЕВА В гл. 4 было показано, что произвольная унитарная операция У может быть реализована на квантовом компьютере с использованием схемы, состоящей из однокубитовых элементов и элементов скот. Такое утверждение об рниеерсальносши очень важно, поскольку гарантирует эквивалентность различных моделей квантовых вычислений.
Например, это позволяет программисту создавать квантовые схемы с элементами, имеющими четыре входных и выходных кубита, будучи уверенным, что такие схемы могут быть смоделированы с помощью фиксированного числа однокубитовых элементов и элементов скот. Недостатком универсальности набора из элементов скот и произвольных унитарных элементов на одном кубите является то, что операторы на одном кубите образуют континуум, в то время как описанные в гл. 10 устойчивые к ошибкам методы квантовых вычислений работают только для конечноео набора элементов.
Однако в гл. 4 мы видели, что любой элемент на одном кубите может быть аппроксимирован с произвольной точностью с использованием конечного набора таких элементов, как скот, элемент Адамара Н, фазовый элемент Я и (я/8)-элемент. Мы также привели эвристическое доказательство того, что для приближенной реализации выбранного элемента на одном кубите с точностью е требуется лишь 9(1/е) элементов, выбранных из конечного множества. Далее, в гл. 10 было показано, что скот, элемент Адамара, фазовый элемент и (я/8)-элемент могут быть реализованы устойчивыми к ошибкам.
В данном приложении будет показано, что можно достигнуть более быстрой сходимости, чем 9(1/е). Теорема Соловел-Китоаееа показывает, что для любого элемента У на одном кубите и е > 0 можно приблизить У с точностью е с использованием 9(1о8'(1/е)) элементов из фиксированного конечного набора, где с- малая константа, примерно равная двойке.
Наилучшее возможное значение величины с к моменту написания книги неизвестно, поэтому мы приведем доказательство теоремы Соловея-Китаева с величиной с, примерно равной 4, а в задачах, предлагаемых в конце приложения, дадим набросок метода, с помощью которого можно приблизить число с к двойке. Мы также докажем, что с не может быть меньше единицы; определение наилучшего возможного значения с (лежащего, таким образом, между единицей и двойкой) остается нерв|пенной задачей. Чтобы оценить важность теоремы Соловея-Китаева, представьте себе, что программист создает алгоритм для квантового компьютера, использующий /(а) элементов.
предположим, что в построенном алгоритме помимо енот, элементов Адамара, фазовых элементов и (я/8)-элементов применяется множество других элементов. Какое количество элементов потребуется, чтобы реализовать алгоритм устойчивым к ошибкам обрезом? Если допустимая ошибка всего алгоритма равна е, то каждый отдельный элемент должен быть ап- 750 Приложение 3. Теорема Соловея-Китаева проксимнрован с точностью е//(и). Согласно эвристическому доказательству в гл. 4, для реализации устойчивого к ошибкам варианта элемента, используемого в алгоритме, потребуется Н(/(и)/е) элементов. Таким образом, всего для алгоритма потребуется 6(/~(п)/е) элементов, т.
е. число элементов для алгоритма растет с полиномиальной скоростью. С учетом теоремы Соловея-Китаева каждый элемент может быть смоделирован с помощью 0(1оя'(/(и)/е) элементов из устойчивого к ошибкам набора, а полное количество элементов для устойчивого к ошибкам алгоритма должно иметь порядок ОЩп) 1ов'(У(п)/е)), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
