Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem

• URL: http://arxiv.org/abs/2508.18996v1
• Date: Tue, 26 Aug 2025 12:53:02 GMT
• Title: Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem
• Authors: Zi-Wen Huang, Xiao-Hui Ni, Jia-Cheng Fan, Su-Juan Qin, Wei Huang, Bing-Jie Xu, Fei Gao,
• Abstract summary: We propose the Iterative Partition Search Algorithm (IPSA) for solving the Shortest Vector Problem (SVP)<n>Our algorithm inherits the core idea of partitioning to circumvent the zero vector" from PSA and the iterative lattice basis reduction" framework from IQOAP.<n>A key feature of IPSA is the 1-tailed search spaces", which can be viewed as a highly constrained variant of PSA's partitioning strategy.
• Score: 5.7878635559750515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Partition Search Algorithm (PSA) and the Iterative Quantum Optimization with an Adaptive Problem (IQOAP) framework are two existing Variational Quantum Algorithms (VQAs) for solving the Shortest Vector Problem (SVP), but both suffer from certain limitations. In this work, we proposed the Iterative Partition Search Algorithm (IPSA), which is a targeted synthesis and refinement of these preceding methods. Our algorithm inherits the core idea of ``partitioning to circumvent the zero vector" from PSA and the ``iterative lattice basis reduction" framework from IQOAP. A key feature of IPSA is the ``1-tailed search spaces", which can be viewed as a highly constrained variant of PSA's partitioning strategy, specifically designed for optimal performance within IQOAP's iterative structure. We supplant IQOAP's fixed iteration count with a dynamic, stack-managed process and substitute a more expressive and shallower circuit structure for its original ansatz. Crucially, the 1-tailed design fundamentally ensures that every successful VQA execution yields an effective lattice basis update, thereby eliminating the issue of ineffective iterations in IQOAP. This evolutionary path of refinement allows IPSA to overcome the drawbacks of its predecessors precisely. Numerical simulations on 4- to 6-dimensional SVP instances demonstrate that IPSA achieves at least a 73\% improvement in success rate for finding optimal solutions and over a 35\% improvement in average solution quality compared with the methods above while maintaining comparable total circuit depth.

Related papers

• QAOA-Predictor: Forecasting Success Probabilities and Minimal Depths for Efficient Fixed-Parameter Optimization [0.9558392439655014]
  We propose a novel approach using a Graph Neural Network (GNN) to predict Quantum Approximate Optimization Algorithm (QAOA) performance.<n>We demonstrate that the GNN accurately predicts QAOA performance within a 10% margin of the true values.
  arXiv  Detail & Related papers  (2026-03-03T13:43:44Z)
• Automated Design of Structured Variational Quantum Circuits with Reinforcement Learning [10.136215038345012]
  This work represents the synthesis of variational quantum circuits as a sequential decision-making problem.<n>We introduce two reinforcement learning-based methods, RLVQC Global and RLVQC Block, tailored to optimization problems.<n>Our results show that both RLVQC methods exhibit strong results with RLVQC Block consistently outperforming QAOA and generally surpassing RLVQC Global.
  arXiv  Detail & Related papers  (2025-07-21T18:40:59Z)
• A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
  We consider a novel optimization design for multi-waveguide pinching-antenna systems.<n>The proposed GML-JO algorithm is robust to different choices and better performance compared with the existing optimization methods.
  arXiv  Detail & Related papers  (2025-06-14T17:35:27Z)
• Adam assisted Fully informed Particle Swarm Optimization ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  The Quantum Approximate Optimization Algorithm (QAOA) is a prominent variational algorithm used for solving optimization problems such as the Max-Cut problem.<n>A key challenge in QAOA lies in efficiently identifying suitable parameters that lead to high-quality solutions.
  arXiv  Detail & Related papers  (2025-06-07T13:14:41Z)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
  We address the problem of semi-bandits, where a player selects among P actions from the power set of a set containing d base items. We show that our approach efficiently leverages the semi-bandit feedback and outperforms bandit feedback approaches.
  arXiv  Detail & Related papers  (2024-02-23T08:07:54Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  We propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz. This ansatz applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence.
  arXiv  Detail & Related papers  (2023-12-12T01:36:49Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  We argue that noise makes evaluations of the objective function via quantum circuits biased. We derive the missing guarantees and find that the rate of convergence is unaffected.
  arXiv  Detail & Related papers  (2022-09-21T19:18:41Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42: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.