Квантовое моделирование алгоритма Дойча в среде Matlab/Simulink

Перчёнок Олег Владимирович

КВАНТОВОЕ МОДЕЛИРОВАНИЕ АЛГОРИТМА ДОЙЧА В СРЕДЕ МАТЬАВ^ШиЬШК

Аннотация

Статья посвящена имитационному моделированию квантового алгоритма Дойча в среде МЛТЬЛБ/БтиИпк.

Ключевые слова: квантовый алгоритм Дойча, МЛТЬЛБ, 81ши1шк.

ВВЕДЕНИЕ

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

Вторая причина, которая стимулирует исследования в области квантовых компьютеров, - это проявляющиеся принципиальные ограничения, которые возникают при использовании классических компьютеров для исполнения многих практически важных алгоритмов. Например, для факторизации (разложения на простые множители) 250-значного числа на существующих компьютерах потребуется примерно миллион лет! На квантовом компьютере разложение даже 1000-значного числа завершится всего за миллион шагов. Ввиду того, что данный алгоритм широко используется в криптографии, нельзя недооценивать возможность возникновения квантового компьютера. Кроме этого, принципиальным достоин-

© О.В. Перчёнок, 2010

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

В Санкт-Петербургском Государственном Электротехническом Университете (СПбГЭТУ «ЛЭТИ») исследованиями в области квантовых компьютеров занимается кафедра Систем автоматического проектирования (САПР) факультета Компьютерных технологий и информатики (ФКТИ). Автор статьи под руководством старшего преподавателя кафедры САПР Матвеевой И.В. в ноябре-декабре 2009 года выполнил работу по моделированию нескольких квантовых объектов информации в среде МЛТЬЛБ/81ши1тк. Среди них - квантовая цепь алгоритма Дойча, которому посвящена данная статья.

1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ [1; 2]

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

В квантовой теории информации аналогом классического бита является квантовый бит (кубит). Классический бит обладает двумя булевыми состояниями 0 или 1, принимаемыми с вероятностями либо P(0) = 1, либо P(1) = 1. Кубит, в отличие от него, находится одновременно сразу в обоих своих базисных состояниях, то есть образует когерентную суперпозицию базисные квантовыа состояний, которая в случае чистого (когерентного) квантового состояния описывается одним из двух эквивалентных способов, а именно:

а) вектором состояния, представляемым вектором-столбцом длиной 2:

\y) = a\ 0) + b i) =

a4

a2+b2=1,

где а, | - комплексные амплитуды, \а\ ||2 - вероятности, с которыми кубит находится в базисных состояниях 0) =

11 =

0

0

V /

1

\ /

б) матрицей плотности:

2

D

\

* t

ab

a b b\

У /

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

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

Для того чтобы получить вектор состояния результирующего кубита \yout), необходимо умножить вектор состояния исход-

ного кубита на матрицу преобразо-

вания М:

Ю = Ю М .

Для того чтобы получить матрицу плотности результирующего регистра Боц4 из

матрицы плотности исходного регистра Б1п с помощью матрицы преобразования М, необходимо воспользоваться следующей формулой:

D

M • D • M

T

, t ^ .

out in v /

Рассмотрим однокубитные гейты: Ада-мара и NOT. Приведем их матрицы (H и NOT соответственно):

H

1

42

11 i -1

NOT =

01 10

Набор N кубитов составляет квантовыш регистр. Принципиальным моментом теории является то, что этот регистр в общем случае также подчиняется принципу суперпозиции и находится одновременно во всех своих базовых классических состояниях, число которых Q = 2^

Общее состояние такой системы куби-тов описывается тензорным произведением входящих в нее кубитов. Для матриц произведение Кронекера (тензорное) выполняется по правилу:

а Ь \ (а В Ь В4

В = её сВ ёВ

A  B =

Одним из базовых двухкубитных преобразователей является преобразователь контролируемое НЕ (CNOT). При своем воздействии на двухкубитный регистр этот оператор оставляет первый кубит (Control) без изменения, а второй (Target) инвертирует, если Control равен 11, иначе оставляет без изменения. На рис. 1 помещено схематическое изображение CNOT. Приведем матрицу CNOT:

CNOT =

00 00

00 00

Далее перейдем к рассмотрению задачи Дойча и алгоритма, обеспечивающего ее решение [2].

Пусть имеются четыре бинарные функции /г (х) от двоичной переменной х = 0,1. При этом функции /1 и /2 постоянны и принимают значения /1 (х) = 0, /2 (х) = 1, функции /3 и /4 принимают значения /3( х) = х, /4( х) = |Х. Говорят, что функции

Рис. 1. Оператор СШТ

/3 и /4 сбалансированы. В задаче Дойча требуется определить, к какой группе (постоянные или сбалансированные) относится функция / (х).

Классическое решение такой задачи предполагает проведение как минимум двух операций - вычисление / (0) и / (1). Квантовый алгоритм позволяет решить задачу за одну операцию - квантовую цепь (цепь из квантовых гейтов) алгоритма Дойча (рис. 2).

На входе цепи находится двухкубитный регистр, состояние которого постоянно:

Уо) = I0)  11 = I01) .

Сначала на каждый из кубитов входного регистра действуем преобразованием Адамара Н. Далее к получившемуся регистру применяем оператор и, который представляется четырьмя матрицами размерности 4 X 4, определяющими четыре возможные функции / (х):

U =

U =

U =

U =

где I =

0 0 0 0

1 0 00 00 01

00 10 00 01

10 00 01 00

= I  I;

= I  NOT;

= CNOT;

И, наконец, воздействуя на первый из результирующих кубитов оператором Ада-мара, получим выходной регистр, состояние которого зависит от функции / (х):

10 -11

42

Таким образом, измеряя состояние первого выходного кубита, можно получить значение f (0) © f (1), то есть квантовая цепь дает возможность определить глобальное свойство функции f (x), используя только одно вычисление f (x). Это явление называется квантовым параллелизмом.

Если состояние первого кубита на выходе цепи Ю, то f12(x) - постоянные функции. Если состояние первого кубита на выходе цепи Ц , то f3 4 (x) - сбалансированные функции. Существенно, что при этом не вычисляются значения самих функций. Квантовый компьютер выделяет «глобальную» информацию из суперпозиции состояний.

2. ОПИСАНИЕ СРЕДЫ МОДЕЛИРОВАНИЯ [3]

MATLAB (сокращение от англ. «Matrix Laboratory») - термин, относящийся к пакету прикладных программ фирмы Mathworks Inc. для решения задач технических вычислений и имитационного моделирования, а также к используемому в этом пакете языку программирования.

Язык MATLAB является высокоуровневым интерпретируемым языком программирования, включающим основанные на матрицах структуры данных, широкий спектр функций, интегрированную среду разработ-

= CNOT(I  NOT) ,

единичная матрица.

Рис. 2. Квантовая цепь алгоритма Дойча

ки, объектно-ориентированные возможности и интерфейсы к программам, написанным на других языках программирования.

Программы, написанные на MATLAB, бывают двух типов - функции и сценарии (англ. scripts). Функции имеют входные и выходные аргументы, а также собственное рабочее пространство для хранения промежуточных результатов вычислений и переменных. Сценарии же используют общее рабочее пространство. Как сценарии, так и функции не компилируются в машинный код и сохраняются в виде текстовых файлов. Основной особенностью языка MATLAB является его широкие возможности по работе с матрицами, которые создатели языка выразили в лозунге «думай векторно».

Simulink - это компонент среды MATLAB, предназначенный для структурно-функционального имитационного моделирования и анализа динамических систем. Он состоит из инструмента составления блочных диаграмм и изменяемого набора библиотек блоков (элементов). Simulink позволяет провести интеграцию построенных диаграмм c остальной средой MATLAB. Возможен вызов на выполнение моделей Simulink из сценариев и функций MATLAB и вызов функций MATLAB из блоков Simulink. Компонент широко используется в области теории управления и цифровой обработки сигналов для моделирования и проектирования.

3. ОПИСАНИЕ МОДЕЛИ

Модель квантовой цепи алгоритма Дойча была построена в Simulink. Изобразим ее на рис. 3.

На вход цепи подаются вектора состояний двух кубитов Q1 и Q2 и номер функции (Number of function) i. На каждый из кубитов действуем оператором Адамара (функция H1, см. п. 4.1). Далее к преобразованным кубитам применяем оператор Uf. Данное преобразование реализуется с помощью функции apply_Uf (см. п. 4.2). И наконец, к первому из результирующих ку-битов применяем оператор Адамара (функция H_on_1, см. п. 4.3). На выходе получаем вектора состояний двух результирующих кубитов Q1' и Q2'.

Модель может функционировать в двух режимах.

Режим «калькулятора» (РК) - режим демонстрации модели, при котором входные величины вводятся непосредственно во входные блоки, а запуск модели происходит в окне модели Simulink. Выходные значения изображаются в блоках Display, напоминающих дисплей калькулятора.

Режим временных диаграмм (РВД) - режим демонстрации модели, при котором входные величины вводятся во входные блоки через сценарий визуализации, который изображает временные диаграммы. Непосредственно в блоки ставятся имена переменных. Запуск модели осуществляется в

Щ MAT LAS P*1!

U J Function

Q1

НИ

Г

ш

MATLAE Function

Р*11

Q2

H1(uL

Number of function

[5*1]

MATLAB ;4x4^ MATLAB

Function Function

д p p ly_ Uffu')

H_on_1

St!

нНШ

Щ

si m out

Рис. 3

To Woitepace

среде MATLAB с помощью сценария визуализации.

Для ввода исходных кубитов используется элемент Constant, в котором указываются непосредственно векторы состояния кубитов. Для ввода номера функции используется элемент Constant, в котором указывается непосредственно число (при функционировании модели в РК) или переменная i (при функционировании модели в РВД).

Для вызова функций H1, apply_Uf, H_on_1 используются блоки MATLAB Function.

Для вывода выходных кубитов Q1' и Q2' используются блоки Display (обеспечивают РК) и блок To Workspace (обеспечивает вывод объединенного вектора из векторов состояния Q1', Q2' в переменную simout для демонстрации модели в РВД). Блок Display, выводящий кубит Q2' свернут, так как значение вектора состояния этого ку-бита нас не интересует.

4. ОПИСАНИЕ ФУНКЦИЙ MATLAB, ИСПОЛЬЗУЕМЫХ В МОДЕЛИ

4.1. ФУНКЦИЯ H1

Для осуществления преобразования Ада-мара разработана функция H1.

Формат вы13ова: Q1=H1(Q).

Параметрыi: Q - вектор состояния исходного кубита.

Возвращаемое значение: Q1 - вектор состояния выходного кубита.

Приведем листинг функции H1 (см. листинг 1).

Описание алгоритма.

Осуществляется вычисление вектора состояния выходного кубита на основе вектора состояния входного кубита и матрицы Адамара по формуле (3).

В функции используется глобальная переменная (фактически константа) Hadamard. Она представляет собой матрицу Адамара и, как и все последующие используемые константы, задается в специально разработанной функции define_globals.

4.2. ФУНКЦИЯ APPLY_UF

Для осуществления преобразования разработана функция apply_Uf.

Формат вы1зова: newstate = apply_Uf

Параметры : QQ - вектор, представляющий собой последовательное объединение векторов состояний исходных кубитов и номера функции.

Возвращаемое значение: newstate - матрица плотности выходного регистра.

Приведем листинг функции apply_Uf (см. листинг 2).

Описание алгоритма.

Формируем трехмерный массив, другими словами, массив матриц операторов.

Из частей исходного объединенного вектора QQ c помощью специально разработанной функции density, действующей по формуле (2), получаем матрицы плотности исходных кубитов, выделяем номер функции i. Далее посредством встроенной функции MATLAB kron, реализующей тензорное произведение матриц - формула (5) -формируем матрицу плотности входного регистра. На полученную матрицу действуем оператором по формуле (4), извлекая нужную матрицу из трехмерного массива.

4.3. ФУНКЦИЯ H_ON_1

Для воздействия оператором Адамара на первый кубит в двухкубитном регистре разработана функция H_on_1.

Листинг 1

% hi.m однокубитное преобразование Адамара function Q1 = H1(Q) global Hadamard; Q1=Hadamard*Q;

Листинг 2

% apply_Uf.m Применение операторов Uf1-Uf4 в алгоритме Дойча function newstate = apply_Uf

global I2x2; global NotGate; global CNotGate; % определение операторов постоянных функций Uf(:,:,1)=eye(4); Uf(:,:,2)=kron(I2x2,NotGate);

% определение операторов сбалансированных функций

Uf(:,:,3)=CNotGate;

Uf(:,:,4)=CNotGate*Uf(:,:,2);

pq1=density(QQ(1:2)); % получение матриц плотностей исходных кубитов pq2=density(QQ(3:4)); % по векторам состояния i=QQ(5); % получение заданного номера функции

state = kron(pq1,pq2); % получение состояния исходного регистра % применение оператора заданной функции newstate = Uf(:,:,i) * state * Uf(:,:,i)';

Формат вызова: newQQ=H_on_1(state1) Параметры: state1 - матрица плотности входного регистра

Возвращаемое значение: newQQ - вектор, представляющий собой последовательное объединение векторов состояний выходных кубитов.

Приведем листинг функции Н_оп_1 (см. листинг 3).

Описание алгоритма. Формируем матрицу М оператора с помощью функции кгоп из матрицы Адамара и единичной матрицы. На матрицу плотности исходного регистра действуем оператором М по формуле (4). После этого из результирующей матрицы выделяем плотности выходных кубитов с помощью функции den_from_state, из которых, в свою очередь, восстанавливаем вектора состоя-

ний посредством функции restore_qubit. И, наконец, формируем выходной объединенный вектор из векторов состояний кубитов результирующего регистра.

Функции den_from_state и restore_qubit разработаны автором статьи.

5. ДЕМОНСТРАЦИЯ РАБОТЫ МОДЕЛИ

Приведем извлечение из протокола тестирования модели в PK:

Проделана следующая последовательность действий:

1. Вызов функции define_globals из командной строки MATLAB.

2. Открытие файла модели Simulink «Deutsch. mdl».

3. Перебор всех возможный значений входны1х номера функции в модели Simulink:

Листинг 3

% H_on_1.m Воздействие преобразователя Адамара на первый кубит % в двухкубитном состоянии function newQQ=H_on_1

global Hadamard; global I2x2;

M=kron(Hadamard,I2x2); % подготовка матрицы оператора state = M * state1 * M'; % применение оператора

pq1=den_from_state(1,state); % получение матриц плотностей кубитов из pq2=den_from_state(2,state); % состояния результирующего регистра q1=restore_qubit(pq1); % получение векторов состояния из q2=restore_qubit(pq2); % матриц плотности newQQ=[q1 q2]';

Рис. 4. Вид окна модели при тестировании в режиме «калькулятора»

1,2,3,4. Для каждого значения осуществлялся его ввод в блок Constant «Number of function» модели Simulink и производился запуск. После окончания работы модели на верхнем блоке Display отображались результатыi, совпадающие с теоретическими. На рис. 4 изобразим вид окна модели после запуска со входным значением i = 1.

Перейдем к описанию демонстрации модели в РВД. Для данной демонстрации был разработан сценарий визуализации, выводящий временные диаграммы векторов состояний входных кубитов, номера функции и вектора состояния первого выходного ку-бита. Приведем извлечение из протокола тестирования модели в РВД:

Проделана следующая последовательность действий:

1. Открытие файла сценария визуализации «DeutschSim.m» в среде MATLAB.

2. Запуск сценария. В процессе его отработки сформировалось окно «Figure 1» («Изображение 1»). Содержимое окна представляет собой временныье диаграммыь (см. рис. 5). По диаграммам установлено, что результаты моделирования совпадают с теоретическими.

Рис. 5. Вид окна изображения при тестировании в режиме вектроных диаграмм

ЗАКЛЮЧЕНИЕ

У читателя может возникнуть вопрос: «Почему для моделирования использовалась именно среда MATLAB/Simulink?» Действительно, существуют и другие средства, которые используются для моделирования квантовых объектов (так называемые квантовые си-муляторы). Например [4]:

• Библиотеки функций для языков программирования

• Симуляторы, созданные в математических пакетах

• Online-симуляторы

Однако перечисленные выше средства не столь известны среди ученых различного профиля, как

MATLAB. Этот инструмент используют более миллиона инженерных и научных работников, он функционирует на большинстве современных операционных систем, включая GNU/Linux, Mac OS, Solaris и Microsoft Windows [3].

Существуют также библиотеки функций и сценариев MATLAB, моделирующие работу квантового компьютера [4] (например, CS 596 Quantum Computing, QLib). Но в этих решениях не используется Simulink, из-за этого они менее наглядны, чем описанная работа.

Привлечеиие специалистов из разных областей к исследованиям, связанным с квантовым компьютером, ускорило бы приближение к конечной цели - физической реализации квантового компьютера. Данная статья вносит некоторый вклад в такую «РЯ-кампанию». Кроме этого, МАТЬАБ изучают во многих технических вузах. Введение курса лабораторных работ по квантовому моделированию в среде МАТЬАБ вовлекло бы заинтересовавшихся студентов в эту область информатики будущего, которое постепенно становится настоящим.

Литература

1. Герасимов И.В., Калмычков В.А., Лозовой Л.Н. Комплементарное моделирование в средах САПР: виртуализация квантовых объектов информации. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2007.

2. Deutsch D. Quantum Theory the Church-Turing Principle and the Universal Quantum Computer. Proc. Roy. Soc. London, 1985, V A400, # 1818, p. 57 / Перевод с англ. под ред. В.А. Садовничего: Сборник «Квантовый компьютер и квантовые вычисления». Ижевск. Ред. журн. «Регулярная и хаотическая динамика», 1999.

3. Википедия - свободная энциклопедия: http://www.wikipedia.org

4. Quantiki - энциклопедия по квантовому компьютеру: http://www.quantiki.org/wiki/index.php/ List of QC simulators

5. И.В. Герасимов, В.А. Калмычков, И.В. Матвеева, Л.А. Чугунов. Представление данных, исследования и визуализация в среде «Matlab». Практикум по дисциплине: «Информатика». СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2006.

6. Потемкин В.Г. MATLAB 6: среда проектирования инженерных приложений. М.: Диалог-МИФИ, 2003.

Abstract

The article is devoted to quantum Deutsch's algorithm simulation in the MATLAB/ Simulink environment.

Keywords: quantum Deutsch's algorithm, MATLAB, Simulink.

© Наши авторы, 2010. Our authors, 2010.

Перчёнок Олег Владимирович, магистрант 2 курса магистратуры СПбГЭТУ «ЛЭТИ», факультет Компьютерные технологий и информатики

olegperch @mail. ru