Алгоритъм на Питър Шор

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

Алгоритъмът на Питър Шор е първият квантов алгоритъм за разлагане на цели числа на множители (т.н. целочислен факторинг), създаден през 1994 година. Алгоритъмът работи в полиноминално време и използва квантови порти от порядък . Това експонтенциално по-бързо от класическият алгоритъм за целочислен факторинг, сито с общо число, който работи в суб-експотенциално време и използва порти от порядък .