论文标题
最短矢量问题的两种量子ISING算法：一个现在，一个用于以后
Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
论文作者
论文摘要
预计量子计算机将在几十年内打破当今的公共密钥密码学。新的密码系统是针对后量子后时代设计和标准化的，其中很大一部分依赖于诸如最短矢量问题（量子对手）等问题的硬度。在本文中，我们描述了量子算法的两个变体来解决此问题。一种变体在空间上是有效的，仅需要o（nlogn）量子位，其中n是晶格尺寸，而另一个变体对噪声更强大。在量子退火器和数值模拟中，对算法的性能的分析表明，从长远来看，更优惠的变体的表现将超越，而另一个变体更适合于近期实现。
Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardised for the post-quantum era, and a significant proportion of these rely on the hardness of problems like the Shortest Vector Problem to a quantum adversary. In this paper we describe two variants of a quantum Ising algorithm to solve this problem. One variant is spatially efficient, requiring only O(NlogN) qubits where N is the lattice dimension, while the other variant is more robust to noise. Analysis of the algorithms' performance on a quantum annealer and in numerical simulations show that the more qubit-efficient variant will outperform in the long run, while the other variant is more suitable for near-term implementation.
