Two quantum Ising algorithms for the shortest-vector problem
Two quantum Ising algorithms for the shortest-vector problem
复制标题
最短向量问题的两个量子Ising算法
DOI：
10.1103/physreva.103.032433
复制
发表时间：
2021-03-26
影响因子：
2.9
通讯作者：
Mintert, Florian
中科院分区：
文献类型：
--
作者：
Joseph, David;Callison, Adam;Mintert, Florian
量子计算机有望在几十年内打破当今的公钥密码学。新的密码系统正在为后量子时代设计和标准化，其中很大一部分依赖于量子对手的最短向量问题等问题的难度。在本文中，我们描述了两个变种的量子伊辛算法来解决这个问题。一种变体是空间有效的，只需要O（N log（2）N）个量子比特，其中N是晶格维数，而另一种变体对噪声更鲁棒。在量子退火机和数值模拟中对算法性能的分析表明，从长远来看，量子比特效率更高的变体将优于其他变体，而另一种变体更适合于短期实现。
Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardized for the postquantum 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(N log(2) N) 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 shows that the more qubit-efficient variant will outperform in the long run, while the other variant is more suitable for near-term implementation.