A variational quantum eigensolver-based cutting plane framework for semidefinite programming problems

• URL: http://arxiv.org/abs/2609.02139v1
• Date: Wed, 02 Sep 2026 05:49:11 GMT
• Title: A variational quantum eigensolver-based cutting plane framework for semidefinite programming problems
• Abstract summary: We present the first end-to-end implementation of a variational quantum eigensolver within a cutting-plane framework.<n>We show that the variational oracle closes 32 to 82% of the initial optimality gap against a near-constant 75 to 82% for the exact oracle.<n>We report these findings and discuss their implications for near-term hybrid quantum-classical approaches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programming plays a key role in optimization, with broad impact across control theory, machine learning, and combinatorial optimization. Although semidefinite programs are polynomially solvable, several commonly used algorithms rest on a linear-algebraic step whose running time grows cubically with the matrix dimension and which requires the matrix itself to be held in memory, at quadratic cost. In this study, we propose replacing it with a variational quantum eigensolver, whose qubit requirement is logarithmic in the matrix dimension, and present the first end-to-end implementation of such an approach within a cutting-plane framework, together with an operator-derived ansatz whose entanglement structure is read directly from the Pauli support of the candidate matrix. Evaluated on the control family of SDPLIB against an identical scheme driven by an exact eigendecomposition, the variational oracle produces valid cuts throughout, closing 32 to 82% of the initial optimality gap against a near-constant 75 to 82% for the exact oracle. Implementing and measuring the method end to end surfaces several effects not visible from theoretical analyses alone: where memory is actually consumed, how the padding required to fit a matrix onto a quantum register can mislead the variational optimizer, and why the candidate matrices prove dense in the Pauli basis, reducing the operator-derived ansatz to full entanglement. We report these findings and discuss their implications for near-term hybrid quantum-classical approaches.

Related papers

• Let the Qudit Do the Jacobi: A Structured Quantum Algorithm for Spectral Decomposition [0.0]
  We develop a qudit-native quantum realization of the Jacobi diagonalization algorithm for unknown unitary operators.<n>The proposed framework avoids explicit reconstruction of the operator and controlled-unitary operations.
  arXiv  Detail & Related papers  (2026-07-14T20:14:44Z)
• Efficient Complex-Valued State Preparation on Bucket Brigade QRAM [47.72095699729477]
  Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data.<n>We present two improvements within the same architecture-aware framework.
  arXiv  Detail & Related papers  (2026-04-28T13:43:29Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables.<n>This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver.<n>Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads.
  arXiv  Detail & Related papers  (2026-02-10T14:17:53Z)
• Amplitude-Phase Separation toward Optimal and Fast-Forwardable Simulation of Non-Unitary Dynamics [39.740772144144366]
  Amplitude-Phase Separation (APS) methods formulates any non-unitary evolution into separate simulation of a unitary operator and a Hermitian operator.<n>APS provides an effective and generic pathway for developing efficient quantum algorithms for general non-unitary dynamics.
  arXiv  Detail & Related papers  (2026-02-10T09:23:55Z)
• Quantum-Inspired Algorithm for Classical Spin Hamiltonians Based on Matrix Product Operators [0.18665975431697432]
  We propose a tensor-network (TN) approach for solving classical optimization problems inspired by spectral filtering and sampling on quantum states.<n>We represent the transformed Hamiltonian as a matrix product operator (MPO) and form an immense power of this object via truncated MPO-MPO contractions.<n>In contrast to the density-matrix renormalization group, our approach provides a straightforward route to systematic improvement by increasing the bond dimension and is better at avoiding local minima.
  arXiv  Detail & Related papers  (2026-02-05T02:29:37Z)
• Efficient Variational Quantum Linear Solver for Structured Sparse Matrices [0.6138671548064355]
  We show that by using an alternate basis one can better exploit the sparsity and underlying structure of matrix. We employ the concept of unitary completion to design efficient quantum circuits for computing the global/local VQLS cost functions.
  arXiv  Detail & Related papers  (2024-04-25T19:22:05Z)
• Optimization of Quantum Systems Emulation via a Variant of the Bandwidth Minimization Problem [41.94295877935867]
  weighted-BMP is a variant of the Bandwidth Minimization Problem (BMP) We formulate the problem using a Mixed Linear Program (MILP) and solve it to optimality with a state of the art solver. numerical tests show that the weighted-BMP approach outperforms the Reverse Cuthill-McKee (RCM) algorithm.
  arXiv  Detail & Related papers  (2024-04-23T16:04:37Z)
• Tensor networks based quantum optimization algorithm [0.0]
  In optimization, one of the well-known classical algorithms is power iterations. We propose a quantum realiziation to circumvent this pitfall. Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
  arXiv  Detail & Related papers  (2024-04-23T13:49:11Z)
• A doubly stochastic matrices-based approach to optimal qubit routing [0.0]
  Swap mapping is a quantum compiler optimization that, by SWAP gates, maps a logical quantum circuit to an equivalent physically implementable one. In this work, we employ a structure called doubly convex matrix, which is defined as a combination of permutation matrices. We show that the proposed algorithm, at the cost of additional time, can deliver significant depth reduction when compared to the state of the art algorithm SABRE.
  arXiv  Detail & Related papers  (2022-11-14T09:25:35Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

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.