⚛️ quantum physics

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

This paper introduces a Quantum Alternating Direction Method of Multipliers (QADMM) for semidefinite programming that leverages quantum singular value transformation and an inexact framework to achieve superior scaling and convergence to an $\epsilon$ -optimal solution compared to classical and other quantum approaches.

Original authors: Hantao Nie, Dong An, Zaiwen Wen

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hantao Nie, Dong An, Zaiwen Wen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complex puzzle called Semidefinite Programming (SDP). This isn't just a simple jigsaw; it's a mathematical problem used to optimize everything from controlling robots to managing financial portfolios. The catch? The puzzle pieces are huge matrices (grids of numbers), and finding the perfect fit usually requires a supercomputer to perform incredibly expensive calculations, specifically "eigenvalue decompositions" (a fancy way of sorting and analyzing the numbers inside the grid).

This paper introduces a new way to solve these puzzles using Quantum Computers. The authors, Hantao Nie, Dong An, and Zaiwen Wen, have created a method they call QADMM (Quantum Alternating Direction Method of Multipliers).

Here is how it works, broken down into simple concepts:

1. The Problem: The "Heavy Lifting" Bottleneck

Think of solving an SDP like trying to organize a giant library.

Classical Computers (the old way) try to do this by manually checking every single book, sorting them, and rearranging shelves. As the library grows, the time it takes to sort explodes. The most expensive part is "eigenvalue decomposition," which is like trying to find the perfect angle to view every book simultaneously to see its true color. It's slow and computationally heavy.
The Goal: The authors wanted to use a quantum computer to do this "heavy lifting" much faster.

2. The Solution: A Hybrid Team (The "Inexact" Framework)

The authors didn't just throw the whole problem at a quantum computer. Instead, they built a hybrid team where classical and quantum computers work together, but they allow for some "sloppiness" (errors) along the way.

The Analogy: Imagine a classical architect (the classical computer) and a quantum wizard (the quantum computer).
- The Architect handles the easy, routine tasks: drawing the basic lines and checking the boundaries.
- The Wizard handles the magic: the difficult, complex sorting and projection steps that take forever for the architect.
The "Inexact" Twist: In the past, if the wizard made a tiny mistake (due to quantum noise or measurement errors), the whole plan might fail. The authors developed a new framework that says, "It's okay if the wizard makes a small mistake, as long as we keep the overall direction correct." They built a safety net that tolerates these small quantum errors, ensuring the team still reaches the correct solution eventually.

3. The Magic Trick: Polynomial Proxies

The hardest part of the puzzle is ensuring the solution stays "positive" (a mathematical rule called the semidefinite constraint).

The Old Way: To fix this, you have to stop, perform a massive, slow calculation (eigenvalue decomposition) to check the numbers, and then fix them.
The New Way (QADMM): The authors designed a polynomial proxy.
- Analogy: Instead of stopping to measure every single book in the library with a ruler (the slow way), the quantum computer uses a "magic lens" (Quantum Singular Value Transformation, or QSVT). This lens applies a smooth, mathematical curve (a polynomial) to the data.
- This curve acts like a filter that automatically pushes the numbers into the "positive" zone without needing the slow, detailed measurement. It's like using a sieve that only lets the right-sized grains through, instantly.

4. The Results: Speed and Efficiency

The paper proves that this new method works and offers significant advantages:

Convergence: Even with the "sloppy" quantum steps, the method is mathematically guaranteed to find the best solution (an $\epsilon$ -optimal solution) eventually.
Scaling: When the problem gets huge (large $n$ $n$ ), the quantum method scales much better than classical methods.
- Classical ADMM: As the library gets bigger, the time to sort grows very fast (like $n^6$ ).
- QADMM: The time grows much more slowly (roughly $n^2$ ), making it much more suitable for massive problems.
Comparison: It is faster than other existing quantum methods (like Quantum Interior Point Methods) for certain types of large-scale problems, specifically those where the solution isn't "too big" in terms of its total weight (Frobenius norm).

5. The Catch (Limitations)

The paper is honest about the limitations. This method currently relies on a specific type of quantum memory called QRAM (Quantum Random Access Memory).

Analogy: Think of QRAM as a magical, instant-access library card system. The algorithm assumes this system exists and works perfectly. In reality, building such a system is currently very difficult and expensive. The authors note that relaxing this assumption is a goal for future work.

Summary

The paper presents a new algorithm, QADMM, that uses quantum computers to speed up the solution of complex optimization problems. It does this by:

Letting a quantum computer handle the hardest math steps using a "magic lens" (polynomial transformation) instead of slow, detailed calculations.
Building a safety net that allows for small quantum errors without ruining the final answer.
Proving that for very large problems, this quantum approach is theoretically much faster than current classical methods.

The authors tested this on a small, simulated example (a Max-Cut problem on a graph with 8 vertices) and showed that their "fuzzy" quantum method tracked the performance of the perfect, slow classical method very closely.

Problem Statement

Semidefinite programming (SDP) is a fundamental convex optimization problem with applications in control theory, statistics, machine learning, finance, and quantum information. However, solving large-scale SDP instances remains computationally challenging for classical algorithms. The primary bottlenecks are the high cost of solving linear systems and performing eigenvalue decompositions (specifically, projecting onto the positive semidefinite cone) at each iteration. While quantum algorithms like Quantum Matrix Multiplicative Weights Updates (QMWU) and Quantum Interior Point Methods (QIPM) have been proposed to address these issues, they often face trade-offs in dimension dependence, sparsity parameters, or accuracy requirements.

Methodology

The authors propose the Quantum Alternating Direction Method of Multipliers (QADMM), a hybrid quantum-classical algorithm designed to solve SDPs by leveraging quantum speed-ups for the most expensive subroutines while maintaining the robustness of classical first-order methods.

1. Inexact ADMM Framework:
The core of the approach is an inexact ADMM framework tailored for SDPs. Unlike standard ADMM, this framework explicitly tolerates errors introduced by quantum subroutines.

Dual Variable Update: The update for the dual variable $y$ involves solving a linear system $(AA^*)y = \dots$ . In the quantum setting, this is solved using a Quantum Linear Solver (QLS).
Primal Variable Updates: The updates for the primal variables $S$ and $X$ involve projecting onto the positive semidefinite (PSD) cone. Classically, this requires an eigenvalue decomposition. The QADMM replaces this with a polynomial proximal operator.
Error Tolerance: The framework introduces error terms ( $\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$ , etc.) to account for inaccuracies from block-encoding approximations, Quantum Singular Value Transformation (QSVT), and quantum state tomography. The authors prove that the averaged iterates of this inexact scheme still converge to an $\epsilon$ -optimal solution.

2. Polynomial Proximal Operator and QSVT:
To avoid the costly eigenvalue decomposition in the projection step, the authors design a polynomial function $g(x)$ that approximates the projection operator $\text{Proj}_{S_+}(x) = \max(0, x)$ .

Using approximation theory, they construct a monotone increasing polynomial $g$ of degree $d = O(1/\epsilon)$ that approximates the ReLU function within error $\epsilon$ .
This polynomial is implemented on a quantum computer using Quantum Singular Value Transformation (QSVT) under the block-encoding model.
A "virtual" barrier function $h(S)$ is constructed such that its proximal operator corresponds to this polynomial transformation, ensuring the variational structure required for convergence analysis.

3. Algorithmic Flow:
The algorithm proceeds iteratively:

$y$ -update: Compute the linear map classically, prepare a quantum state, and solve the linear system using QLS.
$V$ -update: Compute the intermediate variable $V = C - A^*(y) - \gamma X$ using Linear Combination of Unitaries (LCU).
$S$ -update: Apply the polynomial spectral transformation (approximating the PSD projection) to $V$ using QSVT, followed by tomography to reconstruct the classical matrix.
$X$ -update: Similar to the $S$ -update, applying a polynomial transformation to update the dual variable $X$ .
Classical Post-processing: Reconstructed matrices are projected onto bounded sets (Frobenius norm constraints) to ensure feasibility.

Key Contributions

Robust Inexact ADMM Framework: The paper establishes a theoretical bridge between classical ADMM convergence theory and practical quantum computation. It proves that the averaged iterate converges to an $\epsilon$ -optimal solution with a rate of $O(1/\epsilon)$ , even when subproblem solves and dual updates contain errors bounded by quantum noise and approximation limits.
Polynomial Proximal Mapping for SDP: The authors introduce a novel method to replace the eigenvalue decomposition in ADMM with a polynomial eigenvalue transformation. This allows the use of QSVT to handle the semidefinite cone constraints efficiently, avoiding the $O(n^3)$ or $O(n^4)$ cost of classical spectral projections.
Complexity Analysis and Comparison: The paper provides a rigorous complexity analysis showing that QADMM achieves favorable scaling with respect to the problem dimension $n$ compared to classical ADMM and existing quantum solvers (QMWU and QIPM).

Results and Complexity

The authors derive the total computational complexity required to achieve an absolute accuracy $\epsilon_{abs}$ in the objective value and feasibility residual.

Iteration Complexity: The algorithm requires $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ iterations, where $R_X$ and $R_S$ are upper bounds on the Frobenius norms of the optimal primal and dual solutions.
Total Complexity:
- Classical Operations: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ , where $s_A$ is the number of non-zero entries in the constraint matrices.
- Quantum Gate Complexity: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$ .
- Here, $\kappa_A$ is the condition number of $AA^*$ , and $R_y$ is the bound on the dual variable norm.

Comparison:

Vs. Classical ADMM: QADMM offers a better dependence on the dimension $n$ (avoiding the $O(n^6)$ or $O(n^4)$ factors associated with classical eigenvalue decompositions and matrix multiplications in each iteration).
Vs. QIPM: QADMM avoids the high condition number dependence on the Newton system ( $\kappa_{newt}$ ) and offers a different trade-off in accuracy dependence.
Vs. QMWU: While QADMM has a similar dimension dependence to QMWU, it achieves a lower-order dependence on the accuracy parameter $\epsilon_{abs}$ (cubic vs. higher powers in some regimes) and is particularly advantageous when the Frobenius norm of the solution $\|X^*\|_F$ is much smaller than its trace $\text{Tr}(X^*)$ (e.g., in diagonal SDP embeddings).

Significance and Claims

The paper claims that QADMM provides a favorable scaling with respect to dimension for solving large-scale SDPs, making it a promising candidate for problems where classical solvers struggle with the cost of eigenvalue decompositions.

The authors emphasize that their approach:

Integrates Quantum Speed-ups: It successfully leverages QSVT and QLS to accelerate the most computationally intensive parts of the ADMM algorithm.
Maintains Convergence Guarantees: By developing an inexact framework, they ensure that quantum errors do not prevent convergence to an optimal solution.
Relies on Specific Assumptions: The algorithm assumes the availability of polynomial-size QRAM for data access and block-encoding of the input matrices. The authors acknowledge this as a strong assumption and note that future work will focus on relaxing this requirement.

The paper concludes that while the algorithm is limited by the QRAM assumption, it represents a significant step forward in applying quantum computing to large-scale convex optimization, specifically offering a viable alternative to both classical first-order methods and other quantum SDP solvers in specific regimes of dimension and accuracy.