ПРОГРАММИРОВАНИЕ, 2010, No 2, с. 64-71
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 004.92+004.94
О НЕКОТОРЫХ АЛГОРИТМАХ ВЫЧИСЛЕНИЯ УНИТАРНЫХ МАТРИЦ ДЛЯ КВАНТОВЫХ СХЕМ*
© 2010 г. В. П Гердт**, А. Н. Прокопеня***
** Объединенный институт ядерных исследований 141980 Россия, Дубна ***Брестский государственный технический университет 224017 Беларусь, Брест, ул. Московская, 267 E-mail: gerdt@jinr.ru, prokopenya@brest.by Поступила в редакцию 01.07.2009 г.
В статье обсуждаются алгоритмы вычисления унитарных матриц, определяемых квантовыми схемами. Эти алгоритмы используются в программе QuantumCircuit, предназначенной для моделирования квантовых схем. Предложены варианты практической реализации алгоритмов в виде функций, написанных на языке системы Mathematica.
1. ВВЕДЕНИЕ
В последнее время наблюдается значительное возрастание интереса к квантовой информатике и квантовым вычислениям [1]. В первую очередь это связано с потенциальной возможностью квантового компьютера выполнять некоторые типы вычислений, например, факторизацию целых чисел и вычисление дискретного логарифма [2], сверхплотное кодирование информации
[3], поиск элемента в неструктурированной базе
[4] существенно более эффективно по сравнению с его классическим аналогом. Однако реалистичный квантовый компьютер, способный решать практические задачи, пока еще не создан, и большая часть исследований в этой области носит теоретический характер. В этой связи представляет интерес разработка классических симуля-торов квантового компьютера, которые могут быть использованы для поиска и тестирования новых эффективных квантовых алгоритмов.
В работе [5] представлена программа QuantumCircuit, написанная на языке системы МаШвтаНеа [6], с помощью которой можно
* Исследования, представленные в настоящей рабо-
те, были выполнены при поддержке гранта РФФИ
10-01-00200.
легко конструировать различные квантовые схемы и вычислять соответствующие им унитарные матрицы. Знание такой матрицы позволяет найти конечное состояние квантового регистра памяти по его заданному начальному состоянию и проверить работу алгоритма, определяемого квантовой схемой. Заметим, что в общем случае п-кубитового регистра соответствующая унитарная матрица имеет размерность 2п х 2п, что означает экспоненциальный рост ресурсов, необходимых для ее вычисления. Поэтому для моделирования квантовых схем на классическом компьютере требуются эффективные алгоритмы вычисления унитарных матриц, что делает их разработку весьма актуальной.
В данной работе анализируются алгоритмы вычисления унитарных матриц, используемые в программе QuantumCircuit. Следует отметить, что эта программа является универсальной в том смысле, что она позволяет моделировать квантовые схемы, состоящие из произвольного числа кубитов и базовых логических элементов. В программе вся информация о квантовой схеме закодирована в символьной матрице, элементы которой обозначают логические операции на одном или нескольких кубитах. Схеме, изображенной на рис. 1 (мы следуем обозначениям, приня-
Рис. 1. Квантовая схема на трех кубитах, содержащая четыре элемента Адамара (Н), фазовый элемент (Б) и два элемента Тоффоли (ССМОТ).
тым в [1]), например, соответствует следующая матрица:
C C N
mat =
( H
H 1
1 1
S
C C N
H H 1
(1)
Сопоставляя матрицу (1) со схемой на рис. 1, легко видеть, что символы H, S, 1 обозначают соответственно элемент Адамара, фазовый элемент и тождественное преобразование кубита. Элемент Тоффоли представлен в матрице mat в виде столбца, в котором символы C и N обозначают соответственно управляющий и управляемый кубиты. При этом каждый столбец матрицы mat определяет набор логических элементов, используемых для преобразования кубитов на очередном шаге вычислений, и содержит либо несколько однокубитовых элементов, либо один многокубитовый элемент.
Напомним, что квантовые схемы следует читать слева направо, а для определения состояния кубита обычно используется стандартное дира-ковское обозначение |a) (см. [1]). Состояние каждого кубита характеризуется вектором в двумерном гильбертовом пространстве, а каждому однокубитовому логическому элементу соответствует унитарная матрица размерности 2 х 2. В соответствии с рис. 1, на первом шаге вычислений входное состояние квантового регистра la\), la2), |аз) преобразуется под действием трех однокубитовых логических элементов: H, H и 1. В таком случае унитарная матрица, определяющая преобразование регистра, вычисляется как тензорное произведение трех унитарных 2 х 2 матриц, соответствующих элементам H,
H и 1. На втором шаге вычислений кубиты взаимодействуют друг с другом посредством трех-кубитового элемента Тоффоли, управляемый и управляющие кубиты которого определяются соответствующими символами во втором столбце матрицы (1). Для элемента Тоффоли и других многокубитовых логических элементов матричное представление можно получить, только непосредственно определяя правила преобразования базисных векторов в 2"-мерном гильбертовом пространстве. Таким образом, вычисление унитарной матрицы, соответствующей квантовой схеме на рис. 1, сводится к последовательному вычислению пяти матриц, задаваемых столбцами матрицы mat слева направо, и их последующему перемножению. Далее мы подробно рассмотрим некоторые алгоритмы, позволяющие эффективно вычислять унитарные матрицы, соответствующие произвольным квантовым схемам, и варианты их практической реализации, используя в качестве программного средства систему компьютерной алгебры Mathematica 7.0.
2. УНИТАРНАЯ МАТРИЦА, ОПРЕДЕЛЯЕМАЯ ОДНОКУБИТОВЫМИ ЭЛЕМЕНТАМИ
Кубит представляет собой квантовую систему, состояние которой характеризуется вектором |a) в двумерном гильбертовом пространстве. Два различных состояния кубита, обозначаемые обычно через |0) и |1), образуют ортонормиро-ванный базис этого пространства, так что его
произвольное состояние |а) можно представить в виде суперпозиции
1а) = а|0) + в |1),
вектора |5)з, например, имеет вид
|0) =
|1) =
(2)
шаН = | шагХ =
И)' шаги = ¿(1 -
10); шагз = и0);
(3)
|ах)|а2) • • • ^п) = |а1а2 ...ап) = = |а1) ® |а2) ® ^п) ,
(4)
15) з = |101) = |1)
где а и в - комплексные числа, удовлетворяющие условию нормировки ^^ + ^|2 = 1. Для базисных состояний используется стандартное векторное представление
0 0
1 0
0 1
При этом матричное представление для одно-кубитовых логических элементов в базисе (2) получается обычным образом (см., например, [1]). Далее нам понадобятся матрицы для тождественного преобразования (шаН), элемента Адамара (шагН), элемента Паули Х (шагХ) и фазового элемента (шагБ):
|0)®|1) =
0 0 0 0 0 1
0 0
Поскольку у любого базисного вектора (4) отлична от нуля только одна компонента, имеет смысл определить его в виде разреженного массива, для представления которых в системе МаЬНвтаЫеа имеется функция БратввАггау. Тогда произвольное базисное состояние ^п, регистра, содержащего п кубитов, можно записать в виде
ЪазгзУееЬот[к_, п.] := Брат8вАттау[ к + 1 ^ 1, 2п ];
(5)
Следует отметить, что выражение вида (3) можно рассматривать как определение матриц, записанное на языке системы МаШвтаНеа.
Состояние квантового регистра, содержащего п кубитов, характеризуется вектором в 2п-мер-ном гильбертовом пространстве, базисные векторы которого определяются соотношением
где а^ =0,1 (] = 1,...,п), а знак ® обозначает тензорное произведение векторов. Так как любая комбинация цифр вида (а1а2 ...ап) определяет некоторое п-битовое число к из диапазона 0 < к < 2п, для базисных векторов регистра можно использовать более короткую форму записи ^п,. Используя определение (4) и векторы (2), легко убедиться в том, что базисный вектор |к)п представляет собой столбец, у которого (к + 1)-ая компонента равна единице, а все остальные компоненты равны нулю. В случае п =3 векторное представление для базисного
Первый аргумент функции Брат8вАттау представляет собой правило замены, в котором число к + 1 указывает номер компоненты вектора, принимающей значение 1, а второй определяет размерность вектора.
Использование функции Брат8вАттау, которая сохраняет информацию только об отличных от нуля элементах массива, позволяет существенно экономить память и моделировать квантовые схемы, содержащие большее число кубитов. Заметим, однако, что сложение разреженной и обычной матриц или их перемножение приводит к преобразованию результата к обычной матрице. По этой причине матрицы (3) также целесообразно определять как разреженные массивы, хотя все элементы матрицы шагН, например, отличны от нуля. При этом возможны различные варианты использования функции Брат8еАттау, что видно из следующих примеров:
ша81 = Брат8вАттау [ {{1,1} ^ 1, {2, 2} ^ 1}, {2, 2} ];
ша8 Н = Брат8вАттау[ {{1/лД 1/л/2}, {1/^2, -1/^2}} ] ;
gates = {H, H, 1};
matU 1 = gateChoose[ gates[[1]] ]; Do[ matU 1 = ArrayFlatten[ Outer[ Times, matU 1,gateChoose[ gates[[j]] ] ] ],
{j, 2, Length[ gates ] } ]
Рис. 2. Набор команд для генерирования унитарной матрицы, определяемой первым столбцом матрицы (1).
Определение разреженной матрицы matI подобно определению разреженного вектора (5), когда первый аргумент функции SparseArray задает список положений ненулевых элементов матрицы, а второй - ее размерность. Второй пример показывает, что преобразовать обычную матрицу в разреженную можно и непосредственно поместив ее в качестве аргумента функции SparseArray.
Предположим теперь, что квантовая схема содержит n кубитов и состояние каждого куби-та преобразуется под действием некоторых од-нокубитовых элементов. В этом случае унитарная матрица, определяющая преобразование всего квантового регистра, находится как тензорное произведение n матриц, соответствующих од-нокубитовым элементам. Напомним, что в программе QuantumCircuit эти элементы определяются символами, находящимися в одном и том же столбце матрицы, в которой закодирована вся информация о квантовой схеме (матрица mat для схемы на рис. 1). Следовательно, на первом этапе вычислений унитарной матрицы, определяемой несколькими однокубитовыми элементами, каждому символу рассмативаемого столбца требуется сопоставить матрицу
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.