Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Шора - Квантовое преобразование Фурье

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

Квантовое преобразование Фурье действует на базисных векторах согласно формуле

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

Обратный к QFT оператор может быть задан квантовой схемой из вентилей следующего вида.

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

Алгоритм Шора основан на возможности быстро вычислить собственные значения унитарного оператора с высокой точностью, если можно эффективно вычислять любые его степени. Взяв в качестве такого оператора умножение на x по модулю N), мы сможем вычислить такое n, что x = 1, что позволяет разложить N на множители на обычном компьютере.