Квантовый алгоритм - это пошаговая процедура, выполняемая квантовым компьютером. Хотя любой алгоритм может работать на квантовом компьютере, квантовый алгоритм извлекает выгоду из уникальных характеристик кубитов, таких как квантовая запутанность и квантовая суперпозиция.

Примером квантового алгоритма является алгоритм Шора, который можно использовать для нахождения простых множителей целого числа. На классическом компьютере этот процесс факторизации выполняется за NP (недетерминированное полиномиальное) время, что означает, что чем сложнее становится проблема, тем больше экспоненциально. Однако на квантовом компьютере это выполняется за полиномиальное время, в результате чего задача масштабируется линейно, а не экспоненциально, поэтому факторинг очень большого числа не становится невозможным. Большинство современных криптографических шифров основаны на предположении, что разложение больших полиномов является проблемой времени NP. Таким образом, очень большие числа не являются факториальными, учитывая разумное количество времени и разумное количество ресурсов. Однако алгоритм Шора, выполняемый на квантовом компьютере, теоретически может нарушить любое такое шифрование, поскольку большие числа могут быть учтены за полиномиальное время.

Алгоритм, Шифрование, Аппаратные термины, Квант, Квантовый компьютер, Кубит