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

• URL: http://arxiv.org/abs/2505.08386v1
• Date: Tue, 13 May 2025 09:32:21 GMT
• Title: An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems
• Authors: Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu,
• Abstract summary: We propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm, which significantly reduces the qubit requirement for solving the shortest vector problem (SVP)<n>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% larger than those solvable by previous methods.
• Score: 7.839882853089659
• License: http://creativecommons.org/licenses/by/4.0/
• 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% 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.

Related papers

• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians [0.0]
  ExcLQA is a classical, physics-inspired algorithm that identifies excited states of classical Ising Hamiltonians.<n>We benchmark ExcLQA on the shortest vector problem (SVP), a fundamental lattice problem underlying the security of many postquantum cryptographic schemes.<n>Our results show that ExcLQA manages to solve SVP instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in solved ratio, number of shots, and approximation factor.
  arXiv  Detail & Related papers  (2025-07-16T16:40:49Z)
• Quantum Computing for Optimizing Aircraft Loading [1.055551340663609]
  The aircraft loading optimization problem is a computationally hard problem with the best known classical algorithm scaling exponentially with the number of objects.<n>We propose a quantum approach based on a multi-angle variant of the QAOA algorithm (MAL-VQA) designed to utilize a smaller number of two qubit gates in the quantum circuit.<n>We demonstrate the performance of the algorithm on different instances of the aircraft loading problem by execution on IonQ QPUs Aria and Forte.
  arXiv  Detail & Related papers  (2025-04-02T10:10:11Z)
• Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup [4.913177281640608]
  Gram-Schmidt process is widely used to solve Vector set normalization and matrix QR decomposition.<n>Existing methods have problems of high complexity, scaling $O(N3)$ in the system dimension $N$.<n>We propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation.
  arXiv  Detail & Related papers  (2024-12-26T07:04:34Z)
• Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method [0.0]
  We propose an alternative encoding and alternative quantum algorithm to solve the shortest vector problem. Our study shows wide potential applicability of the SVP in quantum computing frameworks.
  arXiv  Detail & Related papers  (2024-08-28T18:01:22Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum algorithmic solutions to the shortest vector problem on simulated coherent Ising machines [11.523102135577732]
  Quantum computing poses a threat to contemporary cryptosystems, with advances to a state in which it will cause problems predicted for the next few decades.<n>Many of the proposed cryptosystems designed to be quantum-secure are based on the Shortest Vector Problem and related problems.<n>In this paper we use the Quadratic Unconstrained Binary optimisation formulation of the Shortest Vector Problem implemented as a quantum Ising model on a simulated Coherent Ising Machine.
  arXiv  Detail & Related papers  (2023-04-08T17:34:10Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.