ПОИСК Статьи Рисунки Таблицы Быстрые квантовые алгоритмы из "Классические и квантовые вычисления" Это в точности матрица плотности для случайного равномерно распределенного элемента группы Е. Теперь осталось воспользоваться следующей леммой, которую мы сформулируем в виде задачи. [c.92] Таким образом, достаточно 2к случайных элементов, чтобы породить всю группу Е с вероятностью ошибки 2 . (Такая маленькая вероятность ошибки получается без особых затрат по сравнению с 1/3. Чтобы сделать её ещё меньше, эффективнее всего воспользоваться стандартной процедурой повторить все вычисление несколько раз н выбрать наиболее часто встречающийся ответ). [c.93] Подведём итог для нахождения скрытой подгруппы В требуется 0 к] обращений к квантовому оракулу. В целом алгоритм имеет сложность 0 к ). [c.93] Мы будем строить быстрый квантовый алгоритм ие для решения задачи факторизации, а для решения другой задачи Нахождение ПЕРИОДА, к которой задача факторизации сводится с помощью классического вероятностного алгоритма. [c.93] Ниже мы построим квантовый алгоритм для решения задачи о нахождении периода чис.ча. Но начнём с того, что опишем классическое вероятностное сведение задачи факторизации к задаче вычисления периода. Читателю также предлагается вспомнить вероятностный тест простоты числа, из.чоженный в первой части (см. разде. 1. 3..3). [c.94] Процедура нахождения делителя. [c.94] Проверяем чётность у. Если у — чётное, то выдаём ответ 2 , в противном случае переходим к шагу 2. [c.94] Выбираем случайное а среди чисел от 1 до у, вычисляем г = реГу(а) (используя имеющийся по предпо.чожению алгоритм нахождения периода) и, если г — нечётное, то ответ у — простое . В противном случае находим d = — 1, у) (скажем, алгоритмом Евклида) и переходим к шагу 4. [c.94] чи d 1, то ответ А, в противном с.чучае ответ у — простое . [c.94] Докажем, что процедура выдаёт ответ у — простое тогда и только тогда, когда i l = i 2 = = i f Действительно, если i l = = = = Sk = О, то г нечётно (поскольку г — наименьшее общее кратное всех r-j]. Если s-i = S2 = = s 1, то = —1 (mod (используем цикличность (Z/pJ Z) ), а, значит, и а / = — 1 (mod у) (используем китайскую теорему об остатках). Наоборот, если не все. s, равны, то при некотором т получим а 1 = 1 (mod р ), т.е. а 1- — 1 (mod у). [c.95] Рассмотрим оператор умножения вычета на а, действующий по правилу Ua. х) axmodq). (Более корректное обозначение — Uq a, одиако число q ие меняется на протяжении всего вычисления, поэтому мы опускаем его в индексах).. Этот оператор переставляет базисные векторы при О X q (напомним, что (a,q) = 1). Будем считать, что на остальных базисных векторах он действует тождественно, 17а ж) н-)- х) прн ж д. [c.95] Поскольку для умножения вычетов есть обычная булева схема полиномиального — 0 п ) — размера, то существует и квантовая схема примерно такого же размера (использующая напрокат дополнительные q-бнты, как это объяснялось раньше). [c.96] Собственные числа для Ua А = где t — период. [c.96] Собственные векторы для Ua ia,f ) = а ). [c.96] Если бы мы могли измерять собственные числа оператора Ua, то получали бы числа k/t. Сначала разберём, как это может нам помочь в нахождении периода. [c.96] Пусть у нас есть машина М, которая прн каждом запуске выдает нам число k t, где t — искомый период, я. к — равномерно распределённое на множестве О,. . ., i — 1 случайное число. Мы предполагаем, что kjt представлено в виде несократимой дроби к jt (если бы машина выдавала число в виде k/t, то вообще ие было бы проблем). [c.96] Получив несколько дробей такого вида k[/t[, k, Jtl ,. .., k[lt, можно с большой вероятностью найти число t, приводя эти дроби к общему знаменателю. [c.96] Вернуться к основной статье