Can all NP problems be efficiently solved in quantum polynomial time?

The Bennett–Bernstein–Brassard–Vazirani 1997 (BBBV97) paper, titled “Strengths and Weaknesses of Quantum Computing”, has had a profound and enduring impact on both theoretical computer science and cryptography. By clarifying the limitations of quantum advantage, BBBV97 indirectly influenced cryptographers to recognize that not all classical problems are vulnerable to quantum attacks.

Coupled with Shor’s algorithm showing polynomial-speed attacks on factoring, the need to identify which cryptographic constructions remain safe—or require replacement—became much sharper. This catalyzed post-quantum cryptography research and defense strategies across both symmetric and asymmetric schemes.

由于polar本科毕业需要将一篇英文文献翻译到中文，索性翻译BBBV97这篇经典的文章。polar在翻译定理和证明的过程中将自己的理解写进了remark，方便大家阅读。

翻译工作是用Latex敲完的，但试过一些格式转换过后发现效果都不好。只能先直接把PDF文件放这了。

文章中的Theorem 3.4和Corollary 3.5（在译文中是Corollary 3.6）被广泛运用在各种其他文献中。