ПРОГРАММИРОВАНИЕ, 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 рублей.