Нет, классические компьютеры могут решать проблемы NP, но не очень быстро для больших размеров задач.
Практическая производительность вовсе не является проблемой проблемы P против NP.
Я думаю (но не уверен), что могут существовать некоторые проблемы классического полиномиального времени, которые квантовый компьютер мог бы решить быстрее, чем классический компьютер сопоставимого технологического уровня.
Смысл P против NP заключается в том, что мы даже не доказали , что недетерминированные задачи за полиномиальное время (решение проверяется за полиномиальное время) на самом деле сложнее, чем любая / каждая возможная проблема P.
т.е. что совокупность всех задач NP не идентична совокупности задач P.
В настоящее время мы не знаем, как решать задачи, полные NP, за полиномиальное время, но никто не доказал, что мы не можем, и это то, о чем https://en.wikipedia.org/wiki/P_versus_NP_problem.
Квантовые вычисления - это супер-набор классических вычислений, поэтому квантовый компьютер может решить любую P-задачу за полиномиальное время. Но необязательно использовать квантовый алгоритм, который фактически обрабатывает любые биты как имеющие значения, отличные от чистого 0 или чистого 1.
Но мы не знаем, могут ли квантовые компьютеры решить каждую проблему NP за полиномиальное время. Это еще одна открытая проблема . (См. Комментарии: мы не знаем, если BQP = NP, а также не знаем, если P = NP.)
Независимо от того, существуют ли квантовые компьютеры, которые могут решать (некоторые?) Проблемы NP за разумное время, P vs NP все еще остается открытым вопросом в теоретической CS. Классические вычисления - все еще очень интересная и актуальная тема 1 .
Учитывая, что никто еще не нашел способ решения NP-полных задач за полиномиальное время, маловероятно, что он существует, и если есть, то он маловероятен для практических задач. (Возможно, очень большие масштабные коэффициенты или показатели для очень быстро растущего полинома, который все еще меньше, чем любая экспоненциальная функция, когда n приближается к бесконечности.)
Требование квантового компьютера для эффективного решения (для больших размеров задач) связано с тем, известен ли какой-либо алгоритм P для классических компьютеров.
Квантовые вычисления не решают и не устаревают вопрос P против NP.
Сноска 1: Я ожидаю, что классические вычисления будут, по крайней мере, теоретически интересны даже в гипотетическом будущем, где дешевые микроконтроллеры могут включать некоторую квантовую логику, не увеличивая их стоимость и не требуя крио-охлаждения или других дорогостоящих эксплуатационных требований.
Но это гипотетическое будущее маловероятно. Даже учитывая время, необходимое для наращивания производственных линий квантовых компьютеров в соответствии с существующей огромной экономией от масштаба и технологической зрелостью легированного кремния, декогеренция является основной нерешенной проблемой. Нет никаких оснований ожидать, что квантовые вычисления когда-либо полностью вытеснят классические; кремний в основном довольно прочный и может хорошо работать при комнатной температуре.
В будущем он может стать важным компонентом настольных компьютеров (в настоящее время аппаратное обеспечение или графические процессоры с плавающей запятой распространены повсеместно на высокопроизводительных ЦП, но по-прежнему отсутствуют на микроконтроллерах). Но все равно будут чисто классические компоненты.