Variational quantum solutions to the Shortest Vector Problem
Variational quantum solutions to the Shortest Vector Problem
复制标题
DOI：
10.22331/q-2023-03-02-933
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Martin R. Albrecht;Milos Prokop;Yixin Shen;P. Wallden
中科院分区：
文献类型：
--
作者：
Martin R. Albrecht;Milos Prokop;Yixin Shen;P. Wallden
一个基本的计算问题是在欧几里得格中找到一个最短的非零向量，这个问题被称为最短向量问题（SVP）。这个问题被认为即使在量子计算机上也很难，因此在后量子密码学中起着关键作用。在这项工作中，我们将探讨如何（有效地）噪声中间尺度量子（NISQ）设备可用于解决SVP。具体来说，我们映射的问题，找到一个合适的哈密顿的基态。特别地，（i）我们建立了格枚举的新边界，这使得我们可以获得新的边界（分别是）。估计）对于任何晶格的每维所需的量子比特的数量（分别为随机q元格）来求解SVP;（ii）我们通过提出（a）不同的经典优化循环或（B）到Hamilton算子的新映射来从优化空间中排除零向量。这些改进使我们能够在量子仿真中解决高达28维的SVP，即使在特殊情况下也比以前实现的要多得多。最后，我们外推了NISQ设备的大小，该设备需要能够解决即使对于最好的经典算法也很难解决的晶格实例，并发现使用大约103个噪声量子位可以解决这些实例。
A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.