Алгоритм Шора - це квантовий алгоритм факторизації (розкладання числа на прості множники), що дозволяє розкласти число 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 кубітами.


1. Квантове перетворення Фур'є

Основним досягненням П. Шора є реалізація їм дискретної версією перетворення Фур'є на квантовому комп'ютері - так зване квантове перетворення Фур'є (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 , Зворотне до нього задається аналогічною формулою, тільки без знака "-" в експоненті.


2. Основні ідеї алгоритму Шора

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