Ричард Фейнман обратил внимание, что задача моделирования квантово-механической системы на компьютере получается NP-полной задачей.
Поскольку квантово-механические системы могут моделировать друг друга за линейное время, то выходит, что они способны решать NP-полные задачи.
Общепризнанно, но не доказано, что для вычисления NP-полной задачи на классическом компьютере требуется экспоненциальное время.
Отсюда и идеи о перспективности квантовых вычислений.
А что, если на самом деле NP = P, то есть, существует алгоритм, способный решать NP-полные задачи на машине Тьюринга за полиномиальное время?
Это ведь еще ни доказано, ни опровергнуто. Это первая из задач тысячелетия.
Тогда где-то в глубинах квантовой теории этот алгоритм лежит в основе мироздания. И если математики не додумаются до него сами, то возможно его раскопают физики.
Здравствуйте, graniar, Вы писали:
G>Ричард Фейнман обратил внимание, что задача моделирования квантово-механической системы на компьютере получается NP-полной задачей. G>Поскольку квантово-механические системы могут моделировать друг друга за линейное время, то выходит, что они способны решать NP-полные задачи. G>Общепризнанно, но не доказано, что для вычисления NP-полной задачи на классическом компьютере требуется экспоненциальное время. G>Отсюда и идеи о перспективности квантовых вычислений.
Планеты солнечной системы способны моделировать движение планет солнечной системы не напрягаясь, а для компьютера это — очень сложная задача.
Движение атмосферы Земли с легкостью моделирует движение атмосферы земли, а метереологические компьютеры делают это лишь приблизительно и с трудом.
Я хочу сказать, последовательные вычисления, которыми занимается компьютер, достаточно плохо подходят для моделирования физических явлений, которые происходят основременно во всем объеме вещества.
Если какие-то физические явления напоминают (или могут быть искуственно приведены) к явлениям, имеющим практическое значение, и при этом могут быть воспроизведены в лабораторной обстановке и оцифрованы, их можно применять для решения практических задач.
Собственно, эта идея издревна лежала в основе аналоговых ЭВМ, о которых сейчас, в эпоху расцвета цифровых, мало кто помнит.
Насколько я понимаю, квантовый компьютер — как раз пример такого подхода.
G>Тогда где-то в глубинах квантовой теории этот алгоритм лежит в основе мироздания. И если математики не додумаются до него сами, то возможно его раскопают физики.
Подчеркну еще раз, компьютерные алгоритмы — последовательные. Физические процессы происходят во всем объеме вещества.
Эту разницу невозможно преодолеть, сделав компьютер с сотней или тысячей вычислительных ядер. Вот когда каждый атом будет производить свои вычисления по собственной программе, тогда можно будет говорить о новом классе алгоритмов.
Здравствуйте, Pzz, Вы писали:
Pzz>Планеты солнечной системы способны моделировать движение планет солнечной системы не напрягаясь, а для компьютера это — очень сложная задача.
Неправда. Сложная задача найти аналитическое решение для трех и более тел.
А численные методы позволяют вычислять с любой практичной точностью и с учетом ОТО.
Pzz>Подчеркну еще раз, компьютерные алгоритмы — последовательные. Физические процессы происходят во всем объеме вещества.
Pzz>Эту разницу невозможно преодолеть, сделав компьютер с сотней или тысячей вычислительных ядер. Вот когда каждый атом будет производить свои вычисления по собственной программе, тогда можно будет говорить о новом классе алгоритмов.
Здесь всего-лишь фактор N. Хоть N^1000, это все-равно не выводит из класса полиномиальности.
Квантовые вычисления немного о другом.
Там речь об экспоненте, о том, что с моделированием поведения тысячи частиц не справится и компьютер размером во вселенную.
