An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems

Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu · 2025

Read An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems by Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08386.txt.

Introduction

Xiaokai Hou and colleagues propose a new quantum method for the shortest vector problem, a hard math task behind lattice-based codes. Their paper from two thousand twenty-five targets near-term quantum machines with few usable qubits. Older methods map the task onto a full network of linked qubits, which grows too hard at large sizes.

Their method, called VQKZ, splits the task into smaller parts on projected sublattices. This cuts the qubit count a great deal. In tests, it handled lattice sizes well beyond what older methods could reach. It also found shorter solution vectors than those older methods, which matters for testing how safe lattice codes are.

Catalog record

CREATORXiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08386

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu Abstract Noisy intermediate-scale quantum cryptanalysis focuses on the capability of near-term quantum devices to solve the mathematical problems underlying cryptography, and serves as a cornerstone for the design of post-quantum cryptographic algorithms. For the shortest vector problem (SVP), which is one of the computationally hard problems in lattice-based cryptography, existing near-term quantum cryptanalysis algorithms map the problem onto a fully-connected quantum Ising Hamiltonian, and obtain the solution by optimizing for the first excited state. However, as the quantum system scales with the problem size, determining the first excited state becomes intractable due to the exponentially increased complexity for large-scale SVP instances. In this paper, we propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm, which significantly reduces the qubit requirement for solving the SVP. Specifically, by transforming the original SVP into a series of subproblems on projected sublattices, the proposed VQKZ algorithm enables near-term quantum devices to solve SVP instances with lattice dimensions 61.39 % 61.39\% larger than those solvable by previous methods. Furthermore, numerical simulations demonstrate that the proposed VQKZ algorithm can significantly outperform existing methods in terms of the length of solution vectors. I Introduction Cryptanalysis aims to study the vulnerabilities of cryptographic algorithms for decrypting ciphertext. Traditional cryptanalysis methods include brute-force attacks tezcan2022key ; mok2019intelligence ; kumar2011investigations , statistical analysis rizzi2009statistical ; vaudenay1996experiment ; xu2021applications , theoretical attacks matsui1993linear ; langford1994differential ; biham1992differential ; mantin2005predicting , side-channel attacks standaert2010introduction ; spreitzer2017systematic ; randolph2020power , and so on. Among them, theoretical attacks exploit the mathematical properties of cryptographic algorithms to design attacks, which can be used to theoretically evaluate the security of the algorithms. Meanwhile, quantum theoretical attack has become an emerging interdisciplinary field which combines cryptanalysis with quantum computing, aiming to achieve quantum speedup in cryptanalysis. It has been demonstrated that Shor’s algorithm achieves an exponential speedup in the cryptanalysis of Rivest-Shamir-Adleman (RSA) encryption and elliptic curve cryptography (ECC), which are based on problems intractable for classical algorithms shor1999polynomial ; shor1994algorithms . In addition, recent studies show that many quantum algorithms can solve cryptographic problems with certain levels of advantages, ranging from Grover algorithm grassl2016applying ; jaques2020implementing ; fernandez2024implementing ; sarah2024practical ; cai2023quantum ; chen2025quantum ; chailloux2017efficient , Simon algorithm kaplan2016breaking ; santoli2016using ; xiang2025quantum ; canale2022simon ; cui2021applications ; dong2019quantum , HHL algorithm ding2023limitations ; chenyuao2025quantum ; roy2024new , to quantum random walk drissi2023new ; chailloux2021lattice ; bonnetain2023finding , Grover-meets-Simon algorithm sun2023quantum ; zhou2023breaking ; zhang2022quantum ; xu2023quantum ; zhang2024superposition ; guo2022quantum and quantum machine learning kim2021cryptanalysis ; ajith2022frequency ; kim2023quantum ; dai2021quantum ; hariharasitaraman2024qhopnn . These results pose significant threats to traditional cryptographic schemes. To resist quantum computing attacks, lattice-based cryptography, as a typical class of post-quantum cryptography, utilizes hard computational problems based on lattices to design cryptographic algorithms. These hard problems include the shortest vector problem (SVP), the closest vector problem (CVP), and the learning with errors (LWE) problem. Specifically, SVP involves finding the shortest non-zero vector in a Euclidean lattice and is proven to be NP-hard in the worst case 10.1145/276698.276705 ; van1981another . This problem has been widely applied in the design of encryption algorithms hoffstein1998ntru ; bos2018crystals ; yang2023fine ; prest2020falcon , digital signatures hoffstein2003ntrusign ; ducas2018crystals ; luc2023building , and key exchange protocols jun2005novel ; pablos2022design ; lei2013ntru . To solve SVP, quantum approaches to enhance classical methods were proposed, including the use of Grover’s algorithm laarhoven2015finding and quantum random walks chailloux2021lattice ; bonnetain2023finding to achieve quantum speedup for classical sieve methods, as well as the application of quantum random-access memory (QRAM) to reduce the space complexity of classical algorithms kirshanova2019quantum ; doriguello2024practicality . With the advent of the noisy intermediate-scale quantum (NISQ) era preskill2018quantum , NISQ algorithms have been developed to leverage near-term quantum devices for addressing computational problems in quantum simulation kandala2017Hardwareefficient ; huang2024Adaptive ; ma2025Experimental , combinatorial optimization li2025efficient ; wu2025Resourceefficient ; zou2025Multiscale , machine learning hou2023duplicationfree ; li2024Ensemblelearning ; wu2025Quantum , among other areas. Recently, there has been growing interest in evaluating whether the near-term quantum devices can pose challenges to cryptographic problems lv2022Using ; zheng2024quantumclassical ; joseph2020not ; joseph2021two ; zhu2022iterative ; albrecht2023variational . For SVP, existing proposals transform the SVP into the problem of searching the first excited state of a fully-connected quantum Ising model H , and leverage quantum adiabatic computing joseph2020not , quantum annealing joseph2021two , quantum approximate optimization algorithm (QAOA) zhu2022iterative , and the variational quantum eigensolver (VQE) albrecht2023variational to obtain the shortest vector. However, the number of qubits of H increases polynomially with the problem size (lattice rank) of the SVP. Due to the volume law of entanglement entropy in quantum systems bianchi2022volume , the complexity of representing the first excited state grows exponentially with the system size. This makes it computationally intractable to determine the first excited state for large-scale SVP instances. In this paper, we propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm based on VQE and rigorously prove an upper bound on the number of qubits required for its implementation. Our proposal transforms the original SVP with the lattice rank r into a series of subproblems on its projected sublattices with rank \beta ( \beta<r ) and can effectively generate a \beta -block Korkin-Zolotarev (BKZ) reduced basis to solve the SVP with only \lfloor\frac{1}{4}(\beta^{2}+3\beta)\rfloor qubits, significantly reducing the dependence of the number of qubits on the lattice rank compared to existing algorithms such as the quantum Ising algorithm (QIA) joseph2021two and the iterative quantum optimization algorithm (IQOA) zhu2022iterative , which require 1.5r\log_{2}r+r qubits to solve the SVP. Theoretical analysis shows that, based on existing quantum computing devices, VQKZ can solve SVP instances that are 61.39\% larger in scale compared to those solvable by QIA and IQOA. Furthermore, numerical simulation results demonstrate that our VQKZ can solve typical SVP instances with shorter vectors than QIA and IQOA, requiring only 6 qubits compared to the 26 qubits required by these two algorithms. II Shortest vector problem and basis reduction Let us briefly review the concept of the SVP and the basis reduction. An m -dimensional lattice \mathcal{L} , defined as a discrete subset of \mathbb{R}^{m} , can be generated by a lattice basis consisting of linearly independent vectors \bm{b}_{1},\cdots,\bm{b}_{r}\in\mathbb{R}^{m} , where r is the rank of \mathcal{L} (with r\leq m ). Formally, the lattice can be given as \mathcal{L}(\bm{b}_{1},\cdots,\bm{b}_{r}):=\left\{\sum_{i=1}^{r}v_{i}\bm{b}_{i}:v_{i}\in\mathbb{Z}\right\}. (1) By arranging these basis vectors as columns of a matrix B=[\bm{b}_{1},\cdots,\bm{b}_{r}]\in\mathbb{R}^{m\times r} , the lattice can equivalently be expressed as \mathcal{L}(\bm{B})=\left\{\bm{B}\bm{v}:\bm{v}\in\mathbb{Z}^{r}\right\}. (2) The shortest vector problem (SVP) for a lattice \mathcal{L}(B) is to find a nonzero vector \bm{v}\in\mathcal{L}(B) with minimal \ell_{2} -norm, i.e., \bm{v}=\text{argmin}_{\bm{x}\in\mathbb{Z}^{r}\setminus{\bm{0}}}\|B\bm{x}\|. (3) Since a lattice admits infinitely many distinct bases, solving SVP requires constructing a high-quality basis from a given basis B , followed by determining the shortest vector, which is far from trivial. In fact, solving SVP has been proven to be NP-hard in the worst case 10.1145/276698.276705 ; van1981another . A high-quality basis refers to a set of vectors with short norms and pairwise near-orthogonality. Such a basis can be obtained through refining the original basis B with a process called basis reduction. In most basis reduction methods, Gram-Schmidt orthogonalization

Read the complete text