P vs NP问题真的是个问题吗？难道我们不能说 P 问题是经典计算机可以解决的问题，因为它适合其体系结构，而 NP 问题本质上是量子的，可以由量子体系结构的计算机解决？
最佳答案
不，经典计算机可以解决 NP 问题，只是不能快速解决大问题。
实际性能根本不是 P 与 NP 问题的重点。
我认为(但不确定)可能存在一些经典多项式时间问题，量子计算机可以比技术水平相当的经典计算机更快地解决这些问题。
P vs. NP 的重点是我们甚至还没有证明非确定性多项式时间问题(可在多项式时间内验证的解决方案)实际上比< em>任何/每一个可能的 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:我希望经典计算至少在理论上很有趣，即使在假设的 future ，廉价的微 Controller 可以包含一些量子逻辑，而不会增加它们的成本或不需要低温冷却或其他昂贵的操作要求。
但这种假设的 future 不太可能发生。即使给定时间来增加量子计算机生产线以匹配当前巨大的规模经济和掺杂硅的技术成熟度，退相干仍然是一个尚未解决的主要问题。没有理由期望量子计算会完全取代经典计算；硅从根本上来说非常坚固，可以在室温下运行良好。
它可能会在未来成为台式计算机的重要组成部分(浮点硬件或 GPU 现在的方式:在高端 CPU 上无处不在，但在微 Controller 上仍不存在)。但是仍然会有纯经典的组件。
关于algorithm - P 与 NP 是否与经典计算机与量子计算机可解决的问题相同？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52241425/