Откуда вообще пошла идея квантовых компьютеров?

Ричард Фейнман обратил внимание, что задача моделирования квантово-механической системы на компьютере получается NP-полной задачей.
Поскольку квантово-механические системы могут моделировать друг друга за линейное время, то выходит, что они способны решать NP-полные задачи.
Общепризнанно, но не доказано, что для вычисления NP-полной задачи на классическом компьютере требуется экспоненциальное время.
Отсюда и идеи о перспективности квантовых вычислений.

А что, если на самом деле NP = P, то есть, существует алгоритм, способный решать NP-полные задачи на машине Тьюринга?
Это ведь еще ни доказано, ни опровергнуто. Это первая из задач тысячелетия.
Тогда где-то в глубинах квантовой теории этот алгоритм лежит в основе мироздания. И если математики не додумаются до него сами, то возможно его раскопают физики.

Откуда вообще пошла идея квантовых компьютеров?

Ричард Фейнман обратил внимание, что задача моделирования квантово-механической системы на компьютере получается NP-полной задачей.
Поскольку квантово-механические системы могут моделировать друг друга за линейное время, то выходит, что они способны решать NP-полные задачи.
Общепризнанно, но не доказано, что для вычисления NP-полной задачи на классическом компьютере требуется экспоненциальное время.
Отсюда и идеи о перспективности квантовых вычислений.

А что, если на самом деле NP = P, то есть, существует алгоритм, способный решать NP-полные задачи на машине Тьюринга за полиномиальное время?
Это ведь еще ни доказано, ни опровергнуто. Это первая из задач тысячелетия.
Тогда где-то в глубинах квантовой теории этот алгоритм лежит в основе мироздания. И если математики не додумаются до него сами, то возможно его раскопают физики.