МИКРОЭЛЕКТРОНИКА, 2007, том 36, № 2, с. 157-160
СХЕМОТЕХНИКА
УДК 519.85:530.145
МЕТОД ПОВЫШЕНИЯ НАДЕЖНОСТИ РАБОТЫ КВАНТОВЫХ АЛГОРИТМОВ
© 2007 г. Б. Г. Коноплев, А. В. Ковалев, В. В. Кальсков
Таганрогский государственный радиотехнический университет E-mail: fep@fep.tsure.ru Поступила в редакцию 29.03.2006 г.
Предложен метод повышения вероятности правильного выполнения квантовых алгоритмов с учетом физических ограничений, основанный на подготовке кубитов к вычислениям. Метод проанализирован на фрагменте квантового алгоритма с применением гейтов NOT, SWAP, CNOT, CCNOT, CSWAP.
ВВЕДЕНИЕ
Современное развитие полупроводниковых технологий приводит к тому, что для записи единицы информации требуется все меньшие размеры объекта, на который производится запись, вплоть до размеров молекул или атомов. Такие объекты обладают неклассическими свойствами. В связи с этим необходима организация вычислений на основе квантовых объектов с использованием волновых свойств частиц.
БАЗИС КВАНТОВЫХ ВЫЧИСЛЕНИЙ
При реализации квантового алгоритма на квантовом компьютере (КК), возникают трудности, связанные с ослаблением взаимодействия электронов при увеличении физического расстояния между ними. Поэтому на квантовые алгоритмы накладывается ограничение: многокубитовые гейты могут воздействовать только на соседние куби-
ты. При реализации таких алгоритмов состояние кубита необходимо перемещать по цепочке к ку-биту, с которым будут проводиться вычисления. Таким образом, повышается вероятность правильного выполнения квантового алгоритма.
Для реализации квантовых алгоритмов используются следующие гейты: NOT, CNOT, CCNOT, SWAP, CSWAP [1].
Гейт NOT является элементом базиса при вычислениях и используется для инвертирования состояния кубита. Его действие условно можно записать в следующем виде:
NOT: (a|0> + b |1»— a |1> + b |0>.
Гейт CNOT (управляемое NOT) также является элементом базиса. Действие этого гейта заключается в инвертировании состояния контролируемого кубита, если контролирующий кубит равен 1:
CNOT( a|00> + b |01> + с |10> + d\11>) = a |00> + b|01> + с|11> + d|10>.
Гейт SWAP меняет состояния кубитов местами:
SWAP(|x>, |y>) = (ДО, |x>).
Гейт CCNOT (гейт Тоффоли) является трехкубитовым гейтом. Его действие прояв-
ляется в инвертировании состояния контролируемого кубита, если контролирующие куби-ты равны 1. В логической форме записи его действие будет выглядеть следующим образом:
CCNOT(|x>, ДО, |z>) = (|x>, ДО, |x ® y © z>).
На основе описанных гейтов, действующих на кубиты, можно разработать практически любой квантовый алгоритм.
При использовании графической формы записи квантовых алгоритмов [2] кубиты обозначаются горизонтальными линиями, гейты представляются
квадратом с буквой или словом внутри. Действие гейта на кубит отображается "нанизыванием" гейта на нужный кубит, или несколько кубитов. Таким образом, образуется сеть гейтов, которая составляет квантовый алгоритм (квантовая сеть). Слева показываются начальные, справа - конечные состоя-
Рис. 1. Исходный квантовый алгоритм (а); Квантовый алгоритм с повышенной вероятностью правильного выполнения (б).
1
2
3
4
1
2
3
4
4CNOT
—|CNOT[
(a)
CCNOT
jCNOTh
(б)
jCNOTh
| CCNOTh
1
1
2
2
S
3
3
S
4
4
CCNOT
)
1 1
2 2
3 S 3
4 4
| CCNOTh
1
2
3
S
4
ния кубитов. Квантовый алгоритм считается выполненным, если все используемые кубиты прошли до конца линий по соответствующим гейтам слева направо.
ОПИСАНИЕ МЕТОДА
Одним из способов повышения вероятности правильного решения квантового алгоритма является подготовка кубитов к вычислению, которая заключается в том, что соседние кубиты меняются своими состояниями, и по цепочке состояние от подготавливаемого кубита передается к кубиту, который расположен по "соседству" с ку-битами, входящими в вычислительный процесс. При этом данные состояния не разрушаются и предыдущее состояние кубита после вычислений по цепочке возвращается на свое место.
Для реализации КК или моделирования квантового алгоритма можно использовать SWAP гейт, который меняет состояния кубитов местами.
Отметим этапы оптимизации квантового алгоритма.
1. Если номера кубитов, входящих в вычислительный процесс, отличаются друг от друга на 1, то эти кубиты изменениям не подвергаются, и выполняется гейт, определенный исходным квантовым алгоритмом, иначе анализируются состояния кубитов, в результате чего выстраивается цепочка номеров кубитов для перемещения состояния от текущего кубита до кубита, находящегося рядом с вычисляемым состоянием кубита.
2. Применяется гейт SWAP.
3. Применяется гейт, определенный алгоритмом.
4. Если не достигнут конец алгоритма, то выбор следующего гейта (переход на п. 1), иначе переход на п. 5.
5. Конец.
Таким образом, проблема дальнего взаимодействия кубитов решается, но в этом случае, естественно, появляется задержка, которая неизбежно возникает при переносе состояния от начального кубита к конечному, линейно возрастающая при удлинении цепочки.
На рис. 1а показан исходный квантовый алгоритм, который необходимо выполнить. Тот же алгоритм, но с повышенной вероятностью правильного выполнения, показан на рис. 16.
Целью оптимизации квантового алгоритма является сокращение числа перестановок состояний кубитов. Так как не все кубиты одновременно участвуют в подготовке к вычислениям, то появляется возможность при анализе квантового алгоритма распараллелить вычисления с одновременной подготовкой кубитов.
АНАЛИЗ МЕТОДА
В результате применения метода получен квантовый алгоритм, изображенный на рис. 2. Для его реализации необходимо N кубитов. Весь фрагмент состоит из семи шагов, которые выполняются последовательно во времени. Алгоритм можно также описать в виде булевых функций.
Описание квантового алгоритма, показанного на рис. 2, в виде булевых функций имеет вид [3]:
1 NOT : |1>^|1> NOT : |N- 1> — |N- 1> 2. CNOT : |N - 1>|N> —► |N - 1>|N ©(N - 1 )> = |N ©(N - 1 )>
МЕТОД ПОВЫШЕНИЯ НАДЕЖНОСТИ
159
Рис. 2. Фрагмент квантового алгоритма в графической форме записи.
3.
г = 2..Ы - 1; CSWAP : I! - 1>|г>
4. СЫОТ : |1>|Я> —|1>|1 ©(N-1 )> = |1 ©(N©(N-1 ))> 5 г = (N -1) ..3; . CSWAP : |! - 1>|г>
6. CCNOT : |2>13>11 > —► |2>|3>|2 л 3 © 1> = |2 л 3 © 1>
г = 3..2;
7.
CSWAP : |г>|г - 1>
На 3-м шаге данного алгоритма реализуется "перемещение" состояния 1-го кубита к кубиту N для проведения вычислений с использованием 1-го и ^го кубитов. Затем на 5-м шаге 1-й кубит перемещается на третью позицию для подготовки к выполнению гейта ^N0^ На 7-м шаге состояние 1-го кубита "возвращается" на свое место.
Шаги 3-й, 5-й и 7-й подготавливают необходимые кубиты для выполнения гейта, но именно на этом этапе возникает наибольшая задержка при вычислениях, т.к. для подготовки кубита надо выполнить (п - т) шагов (п - конечный номер кубита, т - начальный номер кубита). Поэтому важной за-
дачей при разработке квантовых алгоритмов является уменьшение задержек при подготовке кубитов к вычислению.
АНАЛИЗ РЕЗУЛЬТАТОВ
Для оценки эффективности предложенного метода был проведен сравнительный анализ исходного алгоритма с измененным алгоритмом. Анализ надежности проводился на основе функциональной зависимости частоты появления ошибок
м
£ А ехр (Вкг)
V = -—-1* егг
А
(1)
где А, В - коэффициенты; А1егг - среднее время появления ошибки; М - число элементов, составляющих алгоритм; кг - число интервалов между выполняемыми кубитами (один интервал равен расстоянию между соседними кубитами).
Применение данного метода неизбежно приводит к увеличению числа используемых элементов, которые также оказывают влияние на надежность выполнения алгоритма, уменьшая ее. Поэтому при анализе необходимо учитывать число
используемых элементов. Если в исходном алгоритме число элементов составляет М1 = N то после модификации число элементов увеличивается до
М2 = N + N - 1 + N - 1 = 3 N-2.
Принимаем ki = Q - 1, где Q - число кубитов, т.е. для анализа берется наихудший случай, когда все вычисляемые кубиты находятся на максимально возможном расстоянии друг от друга. Наихудший случай в новом алгоритме будет при кг = 1.
Verr от параметров алгоритма:
40
20
0 2 4
Рис. 3. Зависимость относительной надежности выполнения алгоритма от числа кубитов (2) и числа элементов
Для оценки результатов используется отношение частоты ошибок в исходном алгоритме ve,т1 к
частоте ошибок в новом алгоритме verr2, сительная надежность 0:
т.е. отно-
V 1
0 _ - err1
Merr £ A exp (Bki 1)
i _ 1
Merr £ A exp ( Bki 2 )
_ N exp ( B(Q - 1) ) ( 3 N - 2) exp (B ) ■
(2)
=1
Из графика, показанного на рис. 3, можно сделать вывод о том, что при применении предложенного метода и увеличении числа кубитов 2 надежность выполнения квантового алгоритма повышается по сравнению с исходным алгоритмом. Однако, при большом числе элементов N надежность несколько падает.
ЗАКЛЮЧЕНИЕ
Предложен метод повышения вероятности правильного выполнения квантовых алгоритмов, что позволяет уменьшить число корректирующих кубитов [4]. Получены оценки степени повышения надежности квантовых алгоритмов, а так-
же дополнительных затрат времени и оборудования.
1.
3
СПИСОК ЛИТЕРАТУРЫ
Валиев К.А., Кокин А.А. Квантовые компьютеры: надежды и реальность. - Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001, 352 стр.
2. Kitaev Yu. Quantum measurements and the Abelian stabilizer problem (1995), in LANL e-print quant-ph/9511026, http://ru.arxiv.org/abs/quant-ph/9511026 Aharonov D. "Quantum Computation" (1998), in LANL e-print archive quant-ph/9812037, http://ru.arx-iv.org/abs/quant-ph/9812037
Preskill J., Reliable Quantum Computers (1997), in LANL e-print archive quant-ph/9705031, http://ru.arx-iv.org/abs/quant-ph/9705031
2
i _ 1
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.