Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
В случае алгоритма Шора, использующего квантовое дискретное фурье-преобразование, полное число операций степенным образом зависит от L полиномиально (~ L3), то есть имеет место экспоненциальный выигрыш по сравнению с классическими методами. Однако эта зависимость не учитывает влияния паразитного взаимодействия между кубитами, которое приводит к заметной деградации квантовых вычислительных процессов с ростом L [2.29].
Далеко не ясным остается также сложный вопрос о временной цене конкретного способа реализации алгоритма Шора (см. выше параграф 2.2.5). Возможно, что решение этой проблемы может быть найдено на пути использования вместо быстрого квантового фурье-преобразования — быстрого квантового вейвлет-преобразования (quantum wavelet-transform). Для выполнения последнего требуется то же полиномиальное число элементарных унитарных операций, что и в случае квантового дискретного фурье-преобразования, то есть ~ L2 [2.30]. Однако оно не содержит операций типа контролируемого изменения фазы Bj^ и, следовательно, не содержит возрастающей экспоненциально с числом операций временной цены алгоритма Шора. Некоторые сведения о дискретных вейвлет-преобразованиях и их преимуществах перед дискретными фурье-преобразованиями смотри в приложении П.2 к главе 2.
Быстрый алгоритм факторизации, отличный от алгоритма Шора, был рассмотрен также А. Китаевым [2.31]. Он основан на измерении
92
Глава 2
собственных значений некоторого унитарного оператора. Простое и достаточно подробное изложение его можно найти в [2.32].
На выполнение алгоритма Шора существенное влияние оказывает процесс декогерентизации квантовых состояний. В частности, он определяет верхнюю границу для числа кубитов в регистре L, при котором этот алгоритм оказывается еще состоятельным. Если время декогерентизации для L-кубитового состояния ~ (Ljd)-1 (1-79), а время, затрачиваемое на каждый элементарный шаг вычислений г и число шагов в случае алгоритма Шора К ~ L2, то условие того, что когерентное выполнение всех L2 шагов произойдет, будет определяться неравенством [2.22]
rL2 < (L^d)-1
или
L < (т7?))_1/3. (2.59)
Таким образом, предел алгоритма Шора зависит от отношения (т7?>)-1 = Т?)/г, которое определяется конкретным способом реализации квантовых операций. Например, для L = 100 необходимо иметь td/t = 106.
Еще более жестким становится это условие в случае, когда время декогерентизации L-кубитового состояния ~ td/L2 (см. параграф 1.5.2).
2.2.7. Алгоритм Гровера поиска в базе данных
Пусть неотсортированная база данных состоит из N сообщений 5(0), 5(1),... 5(ж),... 5(v),... S(N — 1), представленных N = 2Ь состояниями квантового регистра из Тжубитов. Известно, что одно из сообщений, соответствующее состоянию х = v, в отличие от других удовлетворяет определенному условию S(v) = а (маркировано). Его и требуется найти. Наиболее эффективный классический алгоритм решения такой задачи состоит в простом переборе сообщений одного за другим. Такой алгоритм требует в среднем выполнения N/2 шагов для того, чтобы обнаружить сообщение S(v) с вероятностью 1/2. В 1996 году Гровером (L. Grover) был предложен быстрый квантовый алгоритм [2.33],
2.2. Некоторые квантовые алгоритмы
93
построенный на использовании трех основных элементарных унитарных операций, который позволяет произвести такой поиск за ~ y/N шагов.
Первая операция создает равновероятную (с равными амплитудами) начальную суперпозицию |s) всех N = 2Ь булевых состояний |у) = |г/?_1, г/?_2,... 2/о)> в которой все амплитуды одинаковы и равны 1 /у/N. Она осуществляется с помощью N = 2^-мерного оператора Уолша-Адамара W (2.6), действующего на каждый из L кубитов, находящихся В ИСХОДНОМ СОСТОЯНИИ |0) = |0дг-1, 0дг-2? • • • 0П,... Оо):
N-1
\8) = W |0) = y/ljN Ei у)- (2-6°)
у-О
При этом амплитуда искомого маркированного состояния v тоже оказывается равной 1 /y/N.
Сопоставим х-му начальному состоянию регистра цепочку состояний кубитов |0) и |1) |у) = |i/jv-i5 Vn-2, • • • 2/о) и аналогичную цепочку х-му результирующему состоянию, получаемую в результате второй унитарной операции Уолша-Адамара. Фаза результирующей конфигурации изменится на 7г каждый раз, когда преобразование действует на какой-либо кубит, находившийся в состоянии 11), оставляя его в том же состоянии. В результате знак амплитуды результирующего состояния после действия этой операции будет определяться четностью (parity) побитного скалярного произведения (по модулю 2) этих двух цепочек,
N-1
определяемого как х • у = ^ хп П уп (сравни с операцией квантового
п=0
фурье-преобразования (2.41)):
____N-1 ____N-1
|ж) = W\y) = л/TJn Е (-!)ж'%) = \Л/ЛГ Е ехР(*7ГЖ • у)\у)- (2-61)
у=О у=0
