Классические и квантовые вычисления

Тема 14.6 Симплектические (стабилизирующие) коды [26]

Это аналог классических линейных кодов. Квантовые симплектические коды устроены так же, только вместо контрольных сумм будут использоваться -операторы ( в предыдущих обозначениях).

Зададим, например, таким способом код Шора. Для него , . Кодовое подпространство порождено двумя векторами, см. (14.11).

Каким условиям удовлетворяют базисные векторы ?

Для любых выполнено , т.е. каждая строка состоит из повторений одного бита.

Для любого выполнено . Что означает это условие? Оператор переводит

(остальные строки не меняются). Эти два вектора должны входить в с одинаковыми коэффициентами.

Утверждение 14.4. Если удовлетворяет условиям 1 и 2, то .

Прежде чем перейти к изучению более общих симплектических кодов, рассмотрим подробнее свойства -операторов.

Как уже говорилось, -операторы удобно индексировать элементами группы . Будем обозначать мультииндекс -оператора через .

-операторы образуют базис в , более того, есть естественная -градуировка:

Для -операторов выполнены следующие соотношения

где

Рассмотрим унитарные преобразования -- действия унитарных операторов . Такое действие не меняется при домножении на число, равное по модулю единице, поэтому группа унитарных преобразований имеет вид . Отметим, что унитарные преобразования -- это в точности автоморфизмы -алгебры .

Нас интересуют такие преобразования, для которых ( -- некоторая функция). Оператор эрмитов, поэтому , то есть мы можем написать



(14.14)

Группа таких преобразований называется расширенной симплектической группой и обозначается . Операторы из этой группы будем называть симплектическими. Приведем примеры.

-операторы. . В данном случае .

Оператор . Непосредственно проверяется, что . Таким образом, преобразование .

Можно показать, что . Если учитывать фазовые множители, то получилась бы группа Клиффорда из элементов.

Основные свойства введенного отображения таковы:

линейно на .

сохраняет форму , т.е. .

Отображения с такими свойствами, как известно, называются симплектическими; они образуют симплектическую группу . Таким образом, определен гомоморфизм .

Теорема 14.3. , (ядро состоит из -операторов). Таким образом, .

Для понимания доказательства желательно знать что-нибудь про расширения и когомологии групп [15]. Читателю, незнакомому с этими понятиями, будет предложен "обходной путь" (см. ниже).

Доказательство. Преобразование (14.14) должно быть автоморфизмом -алгебры . Это имеет место тогда и только тогда, когда сохраняются правила умножения операторов . Это означает, что функция обладает указанными свойствами, а удовлетворяет уравнению

(14.15)

где .

В случае, когда -- тождественное отображение, правая часть уравнения (14.15) равна нулю. Решениями являются все линейные функции. Это доказывает, что .

Утверждение равносильно тому, что уравнение (14.15) имеет решение при любом из . Чтобы доказать это, заметим, что функция обладает следующими свойствами:

(14.16)

(14.17)

(14.18)

Формула (14.16) -- это уравнение коцикла. Оно означает, что функция задает структуру группы на декартовом произведении множеств согласно правилу . Полученная группа (обозначим ее ) является расширением посредством , т.е. определен гомоморфизм , с ядром .

Уравнение (14.17) означает, что группа абелева. Наконец, уравнение (14.18) означает, что все элементы группы имеют порядок (или ). Следовательно, . Отсюда вытекает, что расширение тривиально: существует гомоморфизм , такой что . Записывая этот гомоморфизм в виде , получаем решение уравнения (14.15).

Существует другой, несколько кустарный способ доказать, что . Рассмотрим следующие симплектические преобразования: , и . (Напомним, что ). Их образы при гомоморфизме порождают всю группу . (Намек на доказательство: любую пару векторов , такую что , можно перевести этими преобразованиями в , и .) На самом деле, таким способом можно получить и другой интересный результат. Указанные элементы группы порождают все матрицы Паули, т.е. ядро гомоморфизма . Следовательно, верно такое утверждение.

Утверждение 14.5. Группа порождается элементами

Для примера посмотрим на действие оператора . По определению имеем . Действие на образующие алгебры :

Приведенные равенства можно без труда проверить прямым вычислением. Однако полезно привести объяснение на "пальцах". Оператор можно понимать как измерение значения соответствующего q-бита. Первые два равенства просто показывают, как меняются эти значения при замене базиса, задаваемой . Третье равенство показывает, что изменение значения второго q-бита коммутирует с заменой базиса . Четвертое -- что изменение значения первого q-бита при неизменном втором бите в повернутом базисе означает одновременное изменение значений обоих q-битов в исходном базисе.

Дадим теперь определение симплектического кода. В пространстве мы выделим подпространство условиями ( будем называть проверочными операторами ). Проверочные операторы будут иметь вид

(14.19)

Без ограничения общности можно считать, что линейно независимы. Потребуем еще, чтобы все операторы коммутировали. Поскольку , условие коммутирования означает, что .

Определение 14.9. Симплектический квантовый код задается условиями (14.19), где все коммутируют.

Итак, симплектическому квантовому коду соответствует изотропное подпространство ; изотропность означает, что для любых выполнено . Поэтому размерность симплектического кода легко вычисляется.

Теорема 14.4. .

Лемма 14.6. Любой симплектический код приводится преобразованиями из к стандартному виду, когда проверочными операторами являются , где .

Доказательство. Подпространство можно перевести отображением из в подпространство , состоящее из векторов вида , где -- произвольные. Согласно теореме 14.3, этому отображению соответствует некоторое унитарное преобразование . Оно переводит кодовое подпространство в подпространство, заданное проверочными операторами ( ). Применяя дополнительное преобразование вида , все знаки можно сделать плюсами.

Теперь посмотрим, какие ошибки способен обнаруживать симплектический код. Напомним, что код обнаруживает ошибки из , если

(14.20)

По соображениям линейности достаточно рассматривать лишь , .

Пусть , т.е. для всех , где . Обозначим , где . Как мы сейчас увидим, вектор является собственным для всех проверочных операторов , поэтому он либо принадлежит кодовому подпространству , либо ему ортогонален. Подействуем проверочным оператором на :

Условие равносильно условию для всех . Такие образуют линейное подпространство, которое мы обозначим , т.е.

.

Возможны следующие три случая:

. При этом , поэтому . Такую ошибку код обнаружит.

. Такая ошибка фактически неотличима от тождественного оператора, так как она не меняет кодового вектора (с точностью до фазового множителя). Пусть , тогда , где . В этом случае -- условие (14.20) выполнено.

. В этом случае (проверьте!) не имеет вида . Такую ошибку код не обнаруживает.

Этими рассуждениями доказана следующая теорема.

Теорема 14.5. Кодовое расстояние для симплектического кода

Заметим отличие от классических линейных кодов. Там кодовое расстояние определяется как наименьшая норма вектора из подпространства с выкинутым нулем. А у симплектических кодов нуль раздувается до подпространства.

Задача 14.4. Постройте симплектический квантовый код типа , исправляющий одну ошибку.

Задача 14.5. Докажите, что не существует квантового кода типа , исправляющего одну ошибку.

Тема 14.7 Торические коды

Приведем важный пример симплектического кода. Он строится так. Пусть есть квадратная решетка размера на торе. Сопоставим каждому ее ребру по q-биту. Таким образом, всего имеется q-битов. Проверочные операторы будут двух типов.



Рис. 14.1.

Тип I задается вершинами. Выберем некоторую вершину и сопоставим ей проверочный оператор

Тип II задается гранями. Выберем некоторую грань и сопоставим ей проверочный оператор

Операторы и коммутируют, поскольку граница и звезда всегда пересекаются по четному числу ребер. (Перестановочность операторов одного типа очевидна.)

Хотя мы указали проверочных операторов (по одному на грань и на вершину), между ними есть соотношения. Произведение всех -операторов, как и произведение всех -операторов, равны тождественному. Можно показать, что других соотношений нет. Поэтому , а . Поэтому торический код позволяет закодировать два q-бита. Посмотрим, чему равно кодовое расстояние для торического кода.

Для торического кода имеются естественные разложения

на подпространства, соответствующие проверочным операторам, состоящим только из , либо только из . Такие коды называются CSS кодами (по фамилиям авторов, впервые рассмотревших этот класс кодов [25, 44]). В случае торического кода элементы подпространств , имеют вид ; им можно сопоставить 1-цепи, т.е. формальные линейные комбинации ребер с коэффициентами . Элементам подпространств сопоставляются 1-коцепи. Рассмотрим вектор , отвечающий грани с номером . Ему будет сопоставлена 1-цепь, являющаяся границей этой грани. Легко видеть, что пространство состоит из всех 1-границ. Аналогично, векторам будут сопоставляться 1-кограницы, порождающие все пространство 1-кограниц.

Возьмем произвольный элемент , . Условия коммутирования запишутся следующим образом:

Чтобы выполнялось , нужно, чтобы в любой звезде было четное число ребер с ненулевыми весами из . Другими словами, -- это 1-цикл (с коэффициентами в ). Аналогично, должен быть 1-коциклом.

Итак, пространства , состоят из 1-циклов и 1-коциклов, а пространства , состоят из 1-границ и 1-кограниц. Следовательно, кодовое расстояние есть минимальная мощность (количество ненулевых коэффициентов) по циклам, не являющимся границами, и коциклам, не являющимся кограницами. Легко видеть, что этот минимум равен (нужны либо цикл, либо разрез, не гомологичные 0). Это означает, что торический код исправляет ошибок.

Будем обозначать коды описанного вида через .

Замечание. Торические коды являются очень важным примером, обладающим рядом замечательных свойств. В частности, это коды с локальными проверками. Последовательность кодов называется кодами с локальными проверками, если выполнены следующие условия:

каждый проверочный оператор действует на ограниченное константой число q-битов;

каждый q-бит входит в ограниченное константой число проверочных операторов;

кодовое расстояние неограниченно возрастает.

Такие коды представляют интерес для задачи построения вычислительных схем, устойчивых к ошибкам. При исправлении ошибок могут происходить новые ошибки. Но для кодов с локальными проверками схемы исправления ошибок имеют фиксированную глубину, поэтому одна ошибка при работе такой схемы портит ограниченное число q-битов.

Процедура исправления ошибок.

Определение 14.6 и теорема 14.2 указывают только на принципиальную возможность восстановить исходное состояние системы после действия ошибки. На примере симплектических кодов покажем, как реализовать процедуру исправления ошибки.

Рассмотрим частный случай, к которому все сводится. Пусть имеются две ошибки, заданные операторами , . Тогда ( ). Назовем синдромом ошибки вектор (для -- аналогично).

Возьмем вектор . Обозначим . Проверочные операторы действуют на так: . Поэтому, измеряя собственные числа на состоянии , можно измерить синдром.

Рис. 14.2.

Если кодовое расстояние равно , то выполнено

Условие означает эквивалентность ошибок и , т.е. для любого вектора из кодового подпространства. Условие равносильно тому, что синдромы ошибок и не совпадают. Итак, либо ошибки эквивалентны, либо их можно различить по синдрому. Следовательно, по синдрому можно определить ошибку с точностью до эквивалентности, т.е. по модулю подпространства .

Теперь ясно, как нужно исправлять ошибку. После того как определен синдром, применим оператор, обратный к оператору восстановленной по синдрому ошибки. Получим состояние, отличающееся от исходного лишь на фазовый множитель. Вся процедура изображена на рис. 14.2.

Выше рассмотрен случай ошибки типа . На самом деле ошибка состоит в действии преобразования матриц плотности вида

В качестве упражнения читателю предлагается проверить, как работает приведенная выше схема в случае такого общего преобразования матриц плотности.

Задача 14.6. Постройте полиномиальный алгоритм определения ошибки по синдрому для торического кода.

Тема 14.8 Анионы (иллюстративный пример на основе торического кода)

На примере торического кода можно дать более точное представление об анионных системах, о которых говорилось во введении.

Итак, вновь рассмотрим квадратную сетку на торе (а можно и на плоскости -- сейчас нас будет интересовать только ее центральная часть). Как и раньше, для каждой вершины и каждой грани рассмотрим проверочные операторы

Состояние кодового подпространства задается условиями , . Их можно переписать другим способом. Рассмотрим следующий гамильтониан -- эрмитов оператор

Этот оператор неотрицательный, причем его нулевое подпространство в точности совпадает с кодовым подпространством торического кода. Таким образом, векторы из кодового подпространства являются собственными и обладают наименьшей энергией (т.е. собственным числом гамильтониана). Такие векторы называются основными состояниями, а векторы из ортогонального дополнения -- возбужденными состояниями.

Рассмотрим возбужденные состояния с наименьшей ненулевой энергией, когда нарушено ровно два условия (например, вершинных). (Число нарушенных условий каждого типа четное, поскольку .) Тогда для двух вершин, в которых кодовые условия нарушаются, выполнено

Как можно получить состояние из кодового состояния ? Соединим и решеточным путем и подействуем на оператором . Этот оператор коммутирует с проверочными вершинными операторами для всех промежуточных вершин пути , а в концах -- антикоммутирует: . Положим и покажем, что удовлетворяет требуемым свойствам. Для вершины (аналогично и для ) имеем



( , так как состояние -- кодовое).

Любое состояние системы можно построить из элементарных возбуждений двух типов, одни из которых "живут" на вершинах, другие -- на гранях. Элементарное возбуждение -- это просто нарушенное кодовое условие, но теперь мы думаем о нем как о частице. Частицы-возбуждения можно двигать, создавать и уничтожать. Пара возбуждений первого типа получается из основного (кодового) состояния действием оператора , приведенного выше; пара возбуждений второго типа -- действием оператора , где -- путь, соединяющий две грани, как показано на рис. 14.3a). Как и раньше проверяется, что .

Рис. 14.3.

Что случится, если двигать возбуждение одного типа (крестик) вокруг возбуждения второго типа (кружочка)? (См. рис. 14.3б).) Движение возбуждения описывается оператором , зависящим от контура обхода (здесь пробегает все грани внутри ). Очевидно, что для всех . В результате мы получим

То есть вектор состояния домножился на . Это и означает, что рассматриваемые возбуждения являются (абелевыми) анионами.

На торе можно двигать частицы по двум различным циклам, образующим базис в группе гомологий. Например, можно создать из основного состояния пару возбуждений одного типа, обнести одно из возбуждений по циклу и проаннигилировать со вторым возбуждением. Этот процесс описывается некоторым оператором, действующим на кодовом подпространстве, -- произведением вдоль пути на решетке, либо вдоль пути на двойственной решетке. Поскольку существует два типа возбуждений, мы имеем 4 таких оператора: и соответствуют одному базисному циклу, а и -- другому. Эти операторы действуют на два закодированных q-бита как ( ), потому что они обладают такими же коммутационными соотношениями: (остальные пары коммутируют).



Список литературы

1. Ахо. А., Хопкрофт,Дж., Ульман,Дж Построение и анализ вычислительных алгоритмов М.: Мир, 1979

2. Виноградов.И.М Основы теории чисел Изд.8-е, испр. М.: Наука, 1972

3. Гэри.М., Джонсон.Д Вычислительные машины и труднорешаемые задачи М.: Мир, 1982

4. Китаев.А.Ю. Квантовые вычисления: алгоритмы и исправление ошибок УМН, номер6, 1997

5. Клини.С. Математическая логика М.: Мир, 1973

6. Клини.С Введение в метаматематику М.: ИЛ, 1957

7. Кнут.Д Искусство программирования на ЭВМ. В 3т М.: Мир, 1977

8. Кострикин А.И., Манин Ю.И Линейная алгебра и геометрия М.: Наука, 1986

9. Мак-Вильямс Ф.,Дж., Слоэн Н.,Дж. А. Теория кодов, исправляющих ошибки М.: Связь, 1979

10. Мальцев А. И Алгоритмы и рекурсивные функции М.: Наука, 1965

11. Пападимитриу Х., Стаглиц К Комбинаторная оптимизация. Алгоритмы и сложность М.: Мир, 1985

12. Прасолов В.В Задачи и теоремы линейной алгебры М.: Наука. Физматлит, 1996

13. Роджерс Х Теория рекурсивных функций и эффективная вычислимость М.: Мир, 1972

14. Схрейвер А Теория линейного и целочисленного программирования. В 2т М.: Мир, 1991

15. Шафаревич И.Р Основные понятия алгебры // Алгебра-1. Итоги науки и техники М.: ВИНИТИ, 1986

16. Шенфилд Дж.Р Математическая логика М.: Наука, 1975

17. Шенфилд Дж.Р Степени неразрешимости М.: Наука, 1977

Размещено на Allbest.ru