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

Алгоритъмът на Питър Шор е първият квантов алгоритъм за разлагане на цели числа на множители. Създаден е през 1994 година. Алгоритъмът работи в полиноминално време: броят на елементарните квантови операции е от порядък ${\displaystyle O\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$. Това е експоненциално по-бързо от класическия алгоритъм за разлагане на цели числа в произведение, който работи в експоненциално време: броят на елементарните квантови операции е от порядък ${\displaystyle O\left(e^{1,9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$.

Тази статия, свързана с математика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.