论文标题
最短矢量问题的变异量子解决方案
Variational quantum solutions to the Shortest Vector Problem
论文作者
论文摘要
一个基本的计算问题是在欧几里得晶格中找到最短的非零矢量，这是一个被称为最短矢量问题（SVP）的问题。甚至在量子计算机上，这个问题也很难，因此在量子后加密术中起着关键作用。在这项工作中，我们探讨了如何使用（有效的）嘈杂的中间尺度量子（NISQ）设备来求解SVP。具体来说，我们将问题的问题映射到了找到合适的哈密顿量的基态。特别是（i）我们为晶格枚举建立了新的界限，这使我们能够获得任何晶格所需的量子数（resp。〜随机Q- ARY Lattices）求解SVP的新界限（分别〜估计）； （ii）我们通过提出（a）不同的经典优化环或（b）对哈密顿量的新映射来排除优化空间中的零向量。这些改进使我们能够在量子仿真中求解高达28个尺寸的SVP，即使在特殊情况下，也比以前所取得的成就要多得多。最后，我们推断了能够解决晶格实例所需的NISQ设备的大小，即使对于最好的经典算法也很难，发现可以解决这些实例的$ 10^3 $噪声。
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 $10^3$ noisy qubits such instances can be tackled.
