Алгоритм Шора


Алгоритм Шора

Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время {\textstyle{O(\log^2 N \log^3(\log N))}}, используя O(log N) логических кубитов.

Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Наилучший из известных классических алгоритмов факторизации требует времени порядка N^{1/3}. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера в случае ее успеха поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).

Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (умножением) в квадратичное время, алгоритм может быть модифицирован так, что ответ будет верным с единичной вероятностью.

Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

Содержание

Квантовое преобразование Фурье

Основным достижением П. Шора является реализация им дискретной версии преобразования Фурье на квантовом компьютере — так называемое квантовое преобразование Фурье (QFT — Quantum Fourier Transform). Ключевая роль преобразования Фурье для проблемы факторизации была известна до Шора. С другой стороны, реализованное Шором QFT имеет многочисленные применения и помимо факторизации.

Квантовое преобразование Фурье действует на базисных векторах |a\rangle ,\ a=0,1,\ldots,N-1 согласно формуле

 QFT:\ |a \rangle \longrightarrow \frac{1}{\sqrt{N}}\sum\limits_{c=0}^{N-1}\exp(-2\pi\ i\ ac/N)|c \rangle .

QFT продолжается по линейности на все гильбертово пространство состояний H. QFT является унитарным оператором в H, обратное к нему задается аналогичной формулой, только без знака «−» в экспоненте.

Основные идеи алгоритма Шора

Алгоритм Шора основан на возможности быстро вычислить собственные значения унитарного оператора с высокой точностью, если можно эффективно вычислять любые его степени. Взяв в качестве такого оператора умножение на x по модулю N (этот оператор действует в 2^n мерном пространстве, где 2^{n-1}< N\le 2^n, преобразуя базисный вектор, соответствующий числу a, в базисный вектор, соответствующий числу xa(mod N)), мы сможем вычислить такое n, что x^n=1(mod N), что позволяет (с высокой вероятностью) разложить N на множители на обычном компьютере.

См. также

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Алгоритм Шора" в других словарях:

  • Алгоритм шора — …   Википедия

  • Алгоритм Гровера — Алгоритм Гровера (англ. Grover search algorithm, GSA)  квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где есть булева функция от n переменных.[1] Предполагается, что функция задана в виде чёрного… …   Википедия

  • Алгоритм Дойча — Джоза — это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой… …   Википедия

  • Алгоритм Дойча — Алгоритм Дойча  Джоза  это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря …   Википедия

  • Квантовый алгоритм — Квантовый алгоритм  это алгоритм, предназначенный для выполнения на квантовом компьютере. Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием,… …   Википедия

  • Квантовый компьютер — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе …   Википедия

  • Квантовые вычисления — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

  • Квантовые компьютеры — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия