Повышение быстродействия квантового алгоритма факторизации Питера Шора путём усовершенствования его классической части

Современные наукоемкие технологии. 2019. Т. 1. С. 114–118.

Смирнов И. А., Черкесова Л. В., Разумов П. В., Пилипенко И. А., Сафарьян О. А.

В предлагаемой статье произведено сравнение квантового алгоритма факторизации Питера Шора и алгоритма факторизации ?-метода Джона Полларда. Как известно, квантовый алгоритм факторизации Шора состоит из классической и квантовой частей. В классической части для нахождения наибольшего общего делителя чисел (НОД) предлагается использовать алгоритм Евклида. Однако существует достаточно большое количество алгоритмов нахождения наибольшего общего делителя чисел. Авторами данной статьи рассмотрены результаты вычислений восьми алгоритмов, среди которых был найден алгоритм с наибольшим быстродействием поиска НОД. Это позволяет квантовому алгоритму в целом работать быстрее. В свою очередь, это обеспечивает большой потенциал для практического применения квантового алгоритма Шора. Таким образом, авторы модифицировали стандартный квантовый алгоритм П. Шора путем замены бинарного алгоритма поиска НОД итерационным алгоритмом со сдвигом, отмены операции генерации случайного числа и использования алгоритма аддитивных цепочек для быстрого возведения в степень. Полученный модифицированный алгоритм Шора отличается более высокой производительностью и быстродействием при осуществлении факторизации. Эффективность данного модифицированного алгоритма оказалась, в целом выше, чем у стандартного алгоритма Шора, за счёт усовершенствования его классической части. В результате быстродействие алгоритма повысилось на 50?%.

Ключевые слова: recursive algorithms, факторизация, qubit, кубит, quantum algorithms, factorization, the greatest common divisor, binary algorithm, iterative algorithm, квантовый алгоритм, наибольший общий делитель, бинарный алгоритм, рекурсивный алгоритм, итерационный алгоритм