Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
- найти К. Точнее, мы хотим вычислить К за время 0(poly(log |G|)), где |G| - размер группы, и вычисление / на входе считается одним вычислительным шагом. (Заметим, что мы могли бы найти К за время 0(poly(|G|), просто вычислив и проверив все значения j). Начнем, как и в предыдущем примере, с создания состояния
1/>=4т2»|/<8» • <419)
y/'-J geG
и затем считаем второй регистр. Предположив, что/невырождена -
в том смысле, что /(g,) = f(g2) iff g, - g2 e К , получим в первом
регистре
И#о))=^=Хк+*) > (4-2°)
что соответствует значению f(g0) во втором регистре при случайном выборе g0. В (4.20) записана равная суперпозиция состояний из случайно выбранного подмножества К из G. При этом, G - это объединение непересекающихся подмножеств, так что, если мы считаем метку состояния в (4.20), то увидим случайный элемент случайно выбранного подмножества. То есть, с равной вероятностью будет выбра-
156 Концепция квантовых вычислений
на произвольная случайная метка из G, которая не сообщит нам никакой информации о К.
Общая конструкция «преобразования Фурье G» даст нам способ устранить g0 из меток состояний, точно так же, как и в вышеописанном примере. Получившееся в результате состояние даст непосредственную информацию о К. Пусть ^обозначает гильбертово пространство с базисом {|g):geG}, помеченным элементами G. Каждый элемент группы g,eG создает унитарный оператор «сдвига» U(gx) на Jf, определяемый как
Заметим, что состояние в (4.20) можно представить как сдвинутое на g0:
Наша основная идея состоит в том, чтобы ввести в Jf новый базис {l^'-geG} специальных состояний, инвариантных относительно сдвига в том смысле, что
то есть, состояния \% ) - это общие собственные состояния всех операторов сдвига U(g). Заметим, что все U(g) коммутируют между собой, так что такой базис общих собственных состояний гарантированно существует. Если мы теперь, согласно (4.22), запишем |м/(я0))в новом базисе, то тогда суперпозиции |&) и ЪкеК |g0+?) будут содержать состояния с метками одного и того же типа, определенными только подгруппой К. Считывание метки в этом базисе даст теперь напрямую информацию о составляющих элементах К.
Преобразование Фурье ?7 на G определяется просто как унитарное преобразование, которое приводит базис, инвариантный относительно сдвигов, обратно к стандартному базису:
Следовательно, чтобы считать |^(g0)) в новом базисе, мы просто применяем U- и производим считывание в стандартном базисе.
Чтобы в явном виде задать ?7, достаточно выписать состояния \% ) через компоненты стандартного базиса. Существует стандартный способ вычисления этих компонент, основанный на построениях из теории представлений групп. Мы здесь опустим детали; заинтересованный читатель найдет их в работах [134] и [146]. Для группы ZN получаем
(4.21)
(4.22)
для любых g],g2,
(4.23)
для всех g.
(4.24)
Квантовые алгоритмы 157
. . 1 *=| 2ffi— . л ^ • <4'25> что приводит к формуле для преобразования Фурье, данной в (4.25).
Изложенная здесь теоретико-групповая схема служит для обобщения и расширения степени применимости квантового алгоритма для определения периодичности. Например, квантовый алгоритм Саймона [134, 141,146, 147] оказывается просто нахождением периодичности на группе (Z2)" - группе всех и-битных строк с покомпонентным сложением по модулю 2. Саймон рассматривал следующую проблему: предположим, что у нас есть черный ящик, вычисляющий функцию f переводящую и-битные строки в и-битные строки. Также известно, что эта функция - вида «два к одному» в том смысле, что существует такая фиксированная л-битная строка, ? что
/(х + ?) = /(х) для всех и-битных строк х. (4.26)
Наша задача - определить
Чтобы увидеть, что это просто обобщение задачи о нахождении периодичности, заметим, что в группе (Z2)" и-битных строк каждый элемент удовлетворяет соотношению х+х=0. Следовательно, утверждение (4.26) просто означает, что функция/периодична на группе, с подгруппой периодичности К = { 0, ? }. Таким образом, чтобы найти ?, мы конструируем преобразование Фурье на группе и-битных строк и затем применяем стандартный алгоритм, описанный выше. Соответствующее гильбертово пространство Jf с базисом, помеченным и-битными строками - это просто последовательность из и кубитов. Используя общие конструкции из теории представлений групп [134], можно увидеть, что преобразование Фурье - это применение Н (из
(4.1)) к каждому из и кубитов. Квантовый алгоритм определяет ? за 0(п2) шагов, тогда как можно утверждать [141] что любому классическому алгоритму потребовалось бы для этого вычислить / как минимум 0(2") раз. Полное описание этого алгоритма можно найти в работах [141, 146, 147].
Формализм преобразования Фурье оказался самой важной составляющей частью открытых на сегодняшний день квантовых алгоритмов. Некоторое его дальнейшее развитие, включая обобщение на случай неабелевых групп, можно найти в работах [148, 149].
4.2.6 Квантовый алгоритм Шора для факторизации.
Самый знаменитый на сегодняшний день квантовый алгоритм - это алгоритм Шора для задачи факторизации (то есть, разложения на про-
