Принцип работы квантового алгоритма Шора заключается в использовании квантового параллелизма и интерференции для эффективного нахождения периода функции, связанной с факторизуемым числом. 13

Алгоритм состоит из двух частей: классической и квантовой. 13

Классическая часть выполняется на классическом компьютере и предназначена для подготовки данных и анализа результатов. 13 Она играет важную роль в предварительной обработке данных и последующей интерпретации выходных данных квантовой части алгоритма. 1

Квантовая часть использует принципы квантовой механики, такие как суперпозиция (возможность кубитов находиться в нескольких состояниях одновременно) и интерференция (взаимодействие вероятностей различных квантовых состояний). 13 Эти принципы позволяют квантовому компьютеру параллельно обрабатывать множество данных и усиливают вероятность правильных ответов, что существенно ускоряет процесс факторизации. 1

Суть алгоритма — сведение задачи факторизации к задаче поиска периода функции. 2 Если период найден правильно, то задача решена. 2 Если же нет, то квантовая часть алгоритма прогоняется ещё раз. 2