论文标题
改进了子集的经典和量子算法
Improved Classical and Quantum Algorithms for Subset-Sum
论文作者
论文摘要
我们提出了用于解决随机子集实例的新经典和量子算法。首先，我们从$ \ tilde {\ Mathcal {o}}}（2^{0.291 N}）$降低到$ \ tilde {$ \ tilde {\ tilde {\ Mathcal {o}}（2^o}}（2^{0.283 n}）$，我们可以在$ \ tilde {\ mathcal {o}}（2^{0.291 n}}（2^{0.283 n}）$中，我们可以从$ \ tilde {\ Mathcal {o}}（2^{0.291 n}）$改进。 $ \ { - 1,0,1,2 \} $。 接下来，我们在多个方向上改善了该问题的量子算法的艺术状态。通过结合Howgrave-Graham-Joux算法（Eurocrypt 2010）和量子搜索，我们设计了一种算法，具有渐近成本$ \ tilde {\ Mathcal {o Mathcal {o}}}（2^{0.236 N}）$，低于基于同一阶段的Algorith的成本。 Meurer（Pqcrypto 2013）。该算法具有与量子随机访问使用\ emph {classical}内存的优点，而先前已知的算法使用量子步行框架，并且需要\ emph {Quantum}内存，并使用量子随机访问。 我们还提出了用于子集和子集的新量子步行，比$ \ tilde {\ Mathcal {o}}}}}}（2^{0.226 n}）$表现更好。我们将新技术结合在一起，达到一个时间$ \ tilde {\ Mathcal {o}}}（2^{0.216 N}）$。这次取决于由Helm and May正式正式的量子步行更新的启发式，这也是以前的算法所要求的。我们展示了如何部分克服这种启发式，并获得了具有量子时间$ \ tilde {\ Mathcal {o}}}}}（2^{0.218 n}）$的算法。
We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\tilde{\mathcal{O}}(2^{0.291 n})$ downto $\tilde{\mathcal{O}}(2^{0.283 n})$, using more general representations with values in $\{-1,0,1,2\}$. Next, we improve the state of the art of quantum algorithms for this problem in several directions. By combining the Howgrave-Graham-Joux algorithm (EUROCRYPT 2010) and quantum search, we devise an algorithm with asymptotic cost $\tilde{\mathcal{O}}(2^{0.236 n})$, lower than the cost of the quantum walk based on the same classical algorithm proposed by Bernstein, Jeffery, Lange and Meurer (PQCRYPTO 2013). This algorithm has the advantage of using \emph{classical} memory with quantum random access, while the previously known algorithms used the quantum walk framework, and required \emph{quantum} memory with quantum random access. We also propose new quantum walks for subset-sum, performing better than the previous best time complexity of $\tilde{\mathcal{O}}(2^{0.226 n})$ given by Helm and May (TQC 2018). We combine our new techniques to reach a time $\tilde{\mathcal{O}}(2^{0.216 n})$. This time is dependent on a heuristic on quantum walk updates, formalized by Helm and May, that is also required by the previous algorithms. We show how to partially overcome this heuristic, and we obtain an algorithm with quantum time $\tilde{\mathcal{O}}(2^{0.218 n})$ requiring only the standard classical subset-sum heuristics.
