Квантовые компьютеры и NP-проблемы

[Мельхеор]

Узнал что квантовые компьютеры все-таки не могут решать НП-полные проблемы.
http://www.scottaaronson.com/writings/limitsqc-draft.pdf

@темы: Техника, Наука

Comments

[just normal]

Последний пункт -- самый классный. Особенно мне понравилось про вычисления с помощью машины времени =D

[Memfis.]

first generate a random solution, then kill yourself if the solution is incorrect

[Заедает]

Очень много букв
Разве для квантовых компьютеров нет p алгоритмов разложения на простые множители?

[just normal]

Да, алгоритм Шора это делает. Но пока не доказано, что факторизация простых чисел является NP-полной задачей.