论文标题
用于晶格问题的有效量子算法达到了亚指数近似因子
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
论文作者
论文摘要
我们给出了一种量子算法，用于用一类整数晶格上的次指数近似因子解决有界距离解码（BDD）问题。该量子算法在晶格上使用众所周知但具有挑战性的量子状态作为一种近似量子特征向量，将BDD实例随机自我减少到一个随机的BDD实例中，该实例可以经典地解决。对于第二范围的近似因子，量子算法的运行时间是多项式的。 我们研究的晶格子类在晶格的周期性和有限的Abelian组等级方面具有自然描述。这种观点可以从有限的阿贝尔组方面进行清洁的量子算法，从晶格理论中使用了相对较少的量子，并建议探索单独尺寸以外的其他参数中晶格问题的近似算法。 本文的演讲引发了许多生动的讨论，并导致了一种新的古典算法匹配我们的结果。我们将其视为挑战，要提供与一般情况相匹配的类算法。
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The quantum algorithm uses a well-known but challenging-to-use quantum state on lattices as a type of approximate quantum eigenvector to randomly self-reduce the BDD instance to a random BDD instance which is solvable classically. The running time of the quantum algorithm is polynomial for one range of approximation factors and subexponential time for a second range of approximation factors. The subclass of lattices we study has a natural description in terms of the lattice's periodicity and finite abelian group rank. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses very relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone. A talk on this paper sparked many lively discussions and resulted in a new classical algorithm matching part of our result. We leave it as a challenge to give a classcial algorithm matching the general case.
