Алгоритм Шора
В 1994 году Питер Шор, вдохновленный работой Даниеля Саймона, открыл ограниченно — вероятностный алгоритм разложения на множители n-разрядных чисел за полиномиальное время на квантовом компьютере. Начиная с семидесятых, люди ищут эффективные алгоритмы для разложения целых чисел. Наиболее эффективным классическим алгоритмом, известным на сегодняшний день, является алгоритм Ленстра, который экспоненциален по размеру входа. Вход — это набор цифр числа, имеющий размер. Люди были настолько уверены в том, что эффективного алгоритма разложения не существует, что были созданы криптографические системы, например, RSA, которые опираются на сложность этой проблемы. Результат Шора был ошеломляющим для большинства учёных и побудил их к широкомасштабным исследованиям в области квантовых вычислений.
В большинстве алгоритмов, включая алгоритм Шора, используется стандартный способ сведения задачи разложения к задаче поиска периода функции. Шор использует квантовый параллелизм для получения суперпозиции всех значений функции за один шаг. Затем он производит квантовое преобразование Фурье, результатом которого, как для классического преобразовании Фурье, является функция, аргумент которой кратен величине, обратной периоду. С высокой вероятностью измерение состояния возвращает период, который в свою очередь, служит для разложения целого числа М.
Все что было сказано выше, раскрывает суть квантового алгоритма, но в очень упрощённом виде. Наибольшая трудность заключается в том, что квантовое преобразование Фурье основано на быстром преобразовании Фурье и, таким образом, дает только приблизительный результат в большинстве случаев.
