Доказано ли, что квантовые вычисления не лучше в решении полных задач NP, чем классические вычисления?

14

Доказано ли, что квантовые вычисления не лучше в решении полных задач NP, чем классические вычисления, или в это просто верят?

kptlronyttcna
источник

Ответы:

11

Предполагается, что NP-полные задачи не могут быть решены за квантовое полиномиальное время (т. Е. Они не входят в BQP), но это не было доказано. Мы не ожидаем доказательства в ближайшем будущем, поскольку это будет означать, что P отличается от NP.

Юваль Фильмус
источник
3
А как же наоборот? Если NP-complete оказываются в BQP, говорит ли это что-нибудь о P против NP?
kptlronyttcna
1
В 2007 году ничего не было известно , хотя это было довольно давно.
Юваль
1
@kptlronyttcna Я думаю, что это ничего не скажет о P против NP, поскольку P против BQP также еще не установлено.
Петр