Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

• URL: http://arxiv.org/abs/2510.10056v3
• Date: Thu, 04 Dec 2025 12:40:44 GMT
• Title: Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
• Authors: Hantao Nie, Dong An, Zaiwen Wen,
• Abstract summary: We present a quantum alternating direction method of multipliers (QADMM) for SDPs.<n>An inexact ADMM framework is developed, which tolerates errors in the iterate approximations arising from block-encoding approximations and quantum measurement.<n>We prove that the scheme converges to an $$-optimal solution of the SDP problem under the strong duality assumption.
• Score: 9.11785675254736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an $ε$-optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.

Related papers

• Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
  We propose the Distributed Variational Quantum Algorithm (DVQA) for solving Combinatorial Optimization Problems (COPs)<n>A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement.<n> Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization.
  arXiv  Detail & Related papers  (2026-01-20T13:31:02Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Quantum-Efficient Reinforcement Learning Solutions for Last-Mile On-Demand Delivery [1.8262547855491453]
  We investigate quantum computing to solve the large-scale Capacitated Pickup and Delivery Problem with Time Windows.<n>A novel problem-specific encoding quantum circuit with an entangling and variational layer is proposed.
  arXiv  Detail & Related papers  (2025-08-07T13:50:43Z)
• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  Independent Domination Problem (IDP) has practical implications in various real-world scenarios.<n>Existing classical algorithms for IDP are plagued by high computational complexity.<n>This paper introduces a Quantum Approximate Optimization (QAOA)-based approach to address the IDP.
  arXiv  Detail & Related papers  (2024-10-22T17:49:00Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
  A semidefinite program (SDP) is a convex optimization problem with applications in operations research, optimization, quantum information science, and beyond. We propose variational quantum algorithms for approximately solving SDPs.
  arXiv  Detail & Related papers  (2021-12-16T13:10:48Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems. We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms) The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
  arXiv  Detail & Related papers  (2020-01-07T14:43:13Z)

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.