Магия запутанных состояний и современная физика

Одним из первых, кто обратил внимание на возможную перспективу квантовых вычислений, был Ричард Фейнман в 1982-86 гг., но тогда его идеи не вызвали особого резонанса в научной среде. Ситуация коренным образом изменилась в 1994 г., когда Питер Шор показал, что квантовый алгоритм способен свести задачу факторизации (разложение целого числа на простые множители) к полиномиальному классу сложности, в то время как обычный алгоритм экспоненциально зависит от входных данных. Например, обычному компьютеру, выполняющему 1010 операций в секунду, потребуется около одного года, чтобы разложить на простые множители число из 34 цифр, а время, необходимое для разложения числа из 60 цифр, уже превысит возраст Вселенной (1017 сек).