научная статья по теме МОДЕЛИРОВАНИЕ КВАНТОВОГО АЛГОРИТМА ОПРЕДЕЛЕНИЯ ФАЗЫ Математика

Текст научной статьи на тему «МОДЕЛИРОВАНИЕ КВАНТОВОГО АЛГОРИТМА ОПРЕДЕЛЕНИЯ ФАЗЫ»

ПРОГРАММИРОВАНИЕ, 2015, No 2, с. 37-45

КОМПЬЮТЕРНАЯ АЛГЕБРА -

УДК 530.145+004.42

МОДЕЛИРОВАНИЕ КВАНТОВОГО АЛГОРИТМА ОПРЕДЕЛЕНИЯ ФАЗЫ

© 2015 г. А. Н. Прокопеня

Варшавский университет естественных наук - SGGW 02-776 Варшава, ул. Новоурсыновска, 159 E-mail: alexander_prokopenya@sggw.pl Поступила в редакцию 17.07.2014

В статье обсуждается квантовый алгоритм оценки фазы, которая определяет собственное значение унитарного оператора. Предполагается, что собственный вектор оператора и соответствующая ему квантовая схема заданы. Регистр памяти, в который записывается приближеное значение фазы, содержит n кубитов, что позволяет определить фазу с точностью до 2-n с вероятностью большей, чем 8/п2. В качестве примера выполнены вычисления в случае квантового оператора сдвига фазы. Моделирование квантового алгоритма и вычисление собственного значения производится с помощью пакета "QuantumCircuit", написанного на языке системы компьютерной алгебры Wolfram Mathematica, которая также используется для выполнения всех расчетов и визуализации полученных результатов.

1. ВВЕДЕНИЕ

Открытие квантовых алгоритмов факторизации целых чисел [1, 2] и поиска элемента в неупорядоченной базе данных [3] показало, что квантовый компьютер способен эффективно решать задачи, которые являются трудными для классических компьютеров. Новые вычислительные возможности квантового компьютера связаны с эффективным использованием квантовых свойств природы, таких как возможность суперпозиции состояний квантовых битов и их переплетения (см. [4, 5]). Такие свойства не встречаются у классических битов и противоречат нашей интуиции, что затрудняет понимание квантовых вычислений и разработку новых квантовых алгоритмов. И поскольку реалистичный квантовый компьютер еще не создан, представляет интерес моделирование квантовых алгоритмов на классическом компьютере, что помогает разобраться в особенностях квантовых вычислений и может способствовать поиску новых задач и алгоритмов их решения с помощью квантового компьютера.

В работах [6, 7] представлен пакет

С^иапШтСЛгсий, написанный на языке системы компьютерной алгебры МаШетаМса [8], позволяющий моделировать различные квантовые алгоритмы, задаваемые квантовыми схемами. С его помощью смоделированы известные квантовые алгоритмы Шора и Гровера [9], а также продемонстрированы возможности квантовой коррекции ошибок с помощью кодов, исправляющих ошибки [10, 11].

В настоящей работе мы продолжаем моделирование наиболее важных квантовых алгоритмов и рассматриваем проблему вычисления собственного числа унитарного оператора, которая является составной частью многих квантовых алгоритмов [12, 13]. После краткого описания идеи алгоритма и оценки вероятности успешного определения фазы с требуемой точностью мы иллюстрируем его реализацию на примере квантового оператора сдвига фазы. Построение необходимых квантовых схем и вычисление соответствующих унитарных матриц выполняется с помощью пакета (^иапШтСи-сий, а система компьютерной алгебры МаШетаИса используется для выполнения всех расчетов и визуализации полученных результатов.

Следует отметить, что имеются и другие примеры реализации квантового алгоритма оценки фазы. В работе [14], например, описывается моделирование этого алгоритма с помощью пакета Quantum, также написанного на языке системы Mathematiea. Однако в [14] рассмотрены .лишь простейшие квантовые схемы, в которых квантовые регистры памяти, предназначенные для записи фазы, содержат не более 4 кубитов.

В пакете QuantumCircuit вся информация о квантовом алгоритме содержится в символьной матрице, размерность которой определяется количеством кубитов и квантовых вентилей в квантовой схеме (см. [6, 7]). Используемые символы соответствуют стандартным обозначениям квантовых вентилей, а их расположение в матрице полностью определяет структуру квантовой схемы. В рамках такого подхода можно моделировать различные квантовые алгоритмы, что обеспечивает универсальность пакета QuantumCircuit. Отметим также, что символьная матрица может быть не только задана явно, но и определена в виде функции, которая содержит число кубитов в схеме в качестве параметра. Это позволяет легко выполнить моделирование квантового алгоритма для регистров памяти различного размера и продемонстрировать зависимость точности получаемых результатов от числа используемых кубитов.

2. ОПИСАНИЕ АЛГОРИТМА

Рассмотрим унитарный оператор U, который имеет собственный вектор |u) с собственным значением где г - мнимая единица, ар-неизвестное действительное число из интервала 0 < ф < 1, называемое фазой. Для собственного вектора |u) мы используем стандартное обозначение, принятое в квантовых вычислениях (см. |4|). Будем считать, что квантовая схема,

U

регистр памяти может быть приготовлен в состоянии |u). Проблема состоит в построении квантовой схемы, позволяющей определелить неизвестную фазу р.

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

к появлению фазового множителя е2пг^, модуль которого равен 1,

и|и) = е2™» , (1)

измерение этого состояния не дает никакой информации о р. Используя управляемый опера-

и

состояние ^(|0) + |1)) из состояния |и) с помощью преобразования Адамара, информацию о фазе можно перенести на управляющий кубит (см. рис. 1).

Рис. 1.

Квантовая схема для преобразования состояния |ж)|и) в ^и'^).

и

к раз, выполняя преобразование "управляемое ик", то управляющий кубит перейдет в состояние ^(|0) + е2пг^|1)), которое содержит информацию о кратной фазе кр. При этом состояние регистра, приготовленного первоначально в состоянии ^^ не изменяется. Не изменяются так-

| 0)

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

Будем считать, что кроме регистра памяти,

приготовленного в собственном состоянии ^^

р

рой регистр памяти из п кубитов. Произвольное состояние этого регистра |ж)га можно пред-

ставить в виде суперпозиции векторов вычислительного базиса |к)п (см. [4])

2"-1

|х)п = аи 1к)п,

(2)

к=0

где комплексные числа аи удовлетворяют условию нормировки |ао|2 + |а112 + ... + |а2"—112 = 1-Измеряя состояние (2), с вероятностью |аи|2 мы получим одно из базисных состояний

|к)п = |кп-1ки-2...к1ко),

где набор чисел kj = 0,1, 3 = 0,1,...,п — 1 в правой части соответствует двоичному представлению числа к. Ясно, что результат измерения состояния (2) определяется однозначно лишь в случае, когда только один из коэффицентов аи отличен от нуля. В общем случае результатом измерения может быть каждое из целых чисел 0 < к < 2п, для которых коэффициенты аи отличны от нуля, хотя вероятности их получения будут различны. Поэтому заданием алгоритма вычисления фазы р является приведение регистра памяти в такое состояние, при котором максимальное абсолютное значение принимает коэффициент а^, который дает наилучшее п-битовое приближение для р

кп-1 . кп-2 . Р= — + ^ + ... +

+ ^ (3) 2 п- 1 2 п

которое может отличаться от истинного значения р не более, чем на 1/2п+1. Поскольку коэффициент а^ имеет наибольшее абсолютное зна-

р

рк

гие результаты измерений, если имеются отлич-

аи

фициент а^ в конечном состоянии |х)п должен быть как можно ближе к 1, а остальные коэффициенты должны быть малы.

Предположим, что все кубиты второго квантового регистра памяти первоначально находятся в состоянии |0). Затем к каждому кубиту |xj), 3 = 0,1,..., п—1, применяется преобразование Адама-ра, приводящее его в состояние ^(|0) + 11)). Далее к первому регистру, находящемуся в состоянии |и), последовательно применяются п управляемых оператров и2,3 с управляющими кубита-

ми |xj), 3 = 0,1, ...,п — 1. В результате соответствующие фазовые множители ехр^пй-7р) переносятся на кубиты |xj) (см. Рис. 1), и второй регистр переходит в состояние

|ХП-1...Х1Х0) 4 2П/2 (|0) + ехр(2п12п-1р)11)) ®

(|0) + ехр(2п121р)|1)) ® (|0) + ехр(2п120р)|1)) =

о

1

2п/2

^ ... ^ ехр 2п1р 2п-1 кп-г х

кп_1=0 ко=0 \ 1=1

|кп-1. ..к1к0) =

1

2" — 1

2П/2 Е ехр(2п1рк)

(4)

к=0

где учтено двоичное представление числа

к = кп- 12п-1 + кп-22п-2 + ... + к121 + к020 .

Полученное выражение (4) напоминает квантовое преобразование Фурье, действие которого на состояния вычислительного базиса |к)п, к = 0,1,..., 2п — 1, можно представить в виде

(см. [4, 5])

2" 1

1 2 /2П1 \

ирт|к)п 4 Е ех^ кЯ |3)п . (5)

j=о 4 7

Поэтому представляется естественным применить к выражению (4) обратное преобразование Фурье, которое, с учетом унитарности преобразования Фурье, сводится к замене в выражении (5) г 4 —1 и подстановке полученного выражения в (4). В результате второй регистр памяти переходит в состояние

ПЕ ехр ((2Пр — 3)к))|3)п . (6) j=0 V к=0 4 7 /

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

роятность ) получения целого числа 0 < 3 < 2п равна

п

P(j) = 22П

1 - exp(2ni(2np - j))

1 - exp (2ni(2np - j)/2n)

1 sin2 (n2n(p - j/2n))

(7)

22n sin2 (n(p - j/2n))

Если искомая фаза p может быть представлена в виде n-бптовой двоичной дроби (3), то выражение (7) сводится к символу Кронекера

P(j) = j ,

что означает получение числа k в результате измерения с вероятностью 1. Если же фаза отличается от дроби (3) на величину S, т.е. p = p + S, то вероятность получения числа k в результате изменения уменьшается и появляется возможность получения других чисел, например, k - 1 или k +1, что означает уменьшение точности измерения фазы.

Чтобы оценить вероятность получения наилучшего значения к, рассмотрим функци

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком