我的问题是：如果有人明天会发现一个poly-LWE求解器，它将对复杂性理论产生什么影响？经典复杂性理论中是否有与量子环境类似的东西？为了进一步详细说明，我们尚不知道分解问题在复杂性类别中的归属。因此，即使某人明天发现了一种多元算法，也不会影响我们对复杂性类的当前理解。
这是否意味着我们可以预期，一种多元算法是可能的？是否也适用于LWE问题？
#1 楼
我们已经知道$ P $ $ \ subseteq $ $ BPP $ $ \ subseteq $ $ BQP $。因此，由于减少所涉及的问题是“困难的”，乍一看，这样的LWE求解器可能会对以下著名问题产生一些影响：$ P $等于$ NP $？
$ NP $$是否包含在$ BQP $中？
但是仔细分析后，我们发现第一个与该设置并没有真正的联系，因为Regev的结果，给LWE一个量子算法，我们有一个解决晶格问题的量子算法。但是$ P $和$ NP $都是针对“经典”算法定义的。
第二个问题更有意义，因为至少涉及量子算法：如果我们有一个量子多项式时间LWE和一些简化为LWE的$ NP $ -Hard问题的算法，那么对于任何$ NP $问题，我们都有一个量子多项式时间算法（因此，$ NP $将是$ BQP $的子集）。
，但是现在的细节是，不知道Regev量子还原中涉及的晶格问题是NP-Hard。
发生的原因是，大致而言，Regev的还原表明具有参数$ n $，$ q $和$ \ alpha $的LWE的量子求解器，其中$ 0 <\ alpha <1 $，为我们提供了近似值$ n $晶格上近似GapSVP和SIVP的量子求解器$ \ gamma \ approx \ frac {n} {\ alpha} $。
因此，即使LWE求解器为$ \ alpha $任意工作而接近$ 1 $，其近似因子仍会更大比$ n $。但是我们远不能证明那些晶格问题是线性逼近因子的NP-Hard。甚至对于$ \ gamma \ ge \ sqrt {n} $的近似问题的硬度也有负面结果。
因此，随着电流的减少，我们知道一个量子多项式时间算法LWE（显然）会将LWE放入$ BQP $中，但不会影响问题1和2。
当然，从实际的角度来看，这是一个巨大的突破。一方面，那些晶格问题的近似版本不知道是NP-Hard，另一方面，我们不知道解决它们的有效算法。
评论
也有分析经典硬度的问题。您可能想看看这个arxiv.org/abs/1306.0281由于floorcat不再有足够的声誉来评论非所有者的帖子，因此他们选择使用我们的聊天室-边路频道。