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