Quantum Algorithms for Semidefinite Programming

Overview

A semidefinite program, or SDP, is an optimization problem in which the unknown is a symmetric matrix that must stay positive semidefinite, and the goal is to minimize a linear function of the matrix subject to linear constraints. SDPs are the workhorse of modern optimization. They give the Goemans-Williamson approximation for Max-Cut, certify bounds in control theory and polynomial optimization, and appear throughout quantum information.

Quantum SDP solvers aim to solve these programs faster by using quantum subroutines such as Gibbs sampling and amplitude estimation. The best known results give a square-root improvement in the number of constraints and the dimension, but with a heavy dependence on the required precision and on size parameters of the problem, so the speedup is conditional and has not been demonstrated in practice.

The problem it solves

Solving semidefinite programs, a generalization of linear programming used throughout combinatorial optimization, control theory, and machine learning.

History and background

SDPs became central to algorithm design after Goemans and Williamson used one to approximate Max-Cut in 1995. A key classical method is the matrix multiplicative weights approach of Arora and Kale from 2007, which solves SDPs by repeatedly updating a Gibbs-like matrix, and this is the framework that quantum algorithms speed up.

Fernando Brandão and Krysta Svore posted the first quantum SDP solver in 2016, and it appeared at FOCS in 2017. It used quantum Gibbs sampling to implement the multiplicative weights update. Van Apeldoorn, Gilyén, Gribling, and de Wolf improved the dependence on parameters in 2017 and 2020 and also proved a quantum lower bound of about the square root of the number of constraints plus the square root of the dimension. Brandão, Kalev, Li, Lin, Svore, and Wu gave further improvements in 2019, and Kerenidis and Prakash proposed a quantum interior point method in 2018. Classical researchers have also found fast sampling-based SDP methods for low-rank cases.

How it works

Uses quantum Gibbs sampling and amplitude estimation techniques to approximate solutions to the underlying optimization problem faster than the best known classical algorithms in certain regimes.

The multiplicative weights method for SDPs keeps a candidate solution in the form of a matrix exponential, which is a positive matrix of the same type as a thermal state in physics. In each round it asks whether the candidate violates any constraint, and if so, shifts the candidate away from the violation. After enough rounds, the average of the candidates is a near-feasible and near-optimal solution.

The cost is that every round involves manipulating an n by n matrix, which is expensive for large n. The quantum idea is to hold the candidate as a quantum state, a Gibbs state, and to use Gibbs sampling to prepare it. Checking constraints then amounts to estimating the expectation values of observables in that state, which amplitude estimation does with a quadratic improvement.

The result is a runtime that scales with the square roots of the number of constraints and the dimension, instead of linearly. The price is that the precision, the norm of the primal and dual solutions, and sparsity enter with high powers, and the whole algorithm assumes quantum access to the constraint matrices.

Step by step

1. Write the SDP in standard form, with constraint matrices, a right-hand side vector, and an objective matrix, and bound the sizes of the optimal primal and dual solutions.
2. Convert the optimization to a feasibility problem by guessing the optimal value and testing whether a solution exists with that value, using binary search over the guess.
3. Initialize the candidate as the maximally mixed state, which corresponds to the identity matrix.
4. In each round, prepare the current candidate as a Gibbs state using quantum Gibbs sampling with the accumulated constraint matrices as the Hamiltonian.
5. Use amplitude estimation to estimate the expectation values that measure each constraint's violation, and use quantum search to find a violated constraint.
6. Update the Hamiltonian by adding the violated constraint, repeat for the required number of rounds, and output the resulting solution or its value.

A worked example

Consider the SDP relaxation of Max-Cut on a graph with a million vertices. A classical solver must handle a million by million matrix and a million constraints, which is feasible with specialized methods but expensive. A quantum solver with the assumed data access would scale with the square root of those numbers per round, but the number of rounds grows as a high power of the inverse precision.

In practice, for a precision of one percent and realistic problem parameters, the large exponents mean that the quantum algorithm would win only for extremely large instances. This is the reason research focuses on improving those exponents, and why the claims are described as conditional speedups.

Complexity and resources

What hardware it needs

• Fault-tolerant quantum hardware with quantum random access memory.
• Efficient Gibbs state preparation, which is itself a deep subroutine.
• A classical controller to coordinate the rounds and the binary search.

Applications

• Approximating NP-hard combinatorial problems by SDP relaxations, such as Max-Cut and graph partitioning.
• Sum-of-squares optimization and polynomial optimization.
• Optimal quantum state discrimination and other problems in quantum information.
• Control theory and robust optimization.

Limitations and caveats

• The speedup is polynomial and depends on large powers of precision and norm parameters.
• It assumes quantum data access that does not currently exist at scale.
• Practical classical SDP solvers, including interior point and first-order methods, are highly optimized.
• Output is limited to estimates, not the full solution matrix.

Common misconceptions

• Quantum SDP solvers do not make hard optimization problems easy. They speed up solving the SDP relaxation, which is itself polynomial-time classically.
• The advertised square-root speedup does not apply to all instances. It depends on the problem parameters.

How it compares

• Classical interior point methods have high accuracy but poor scaling to very large problems.
• Classical matrix multiplicative weights are the direct ancestor of the quantum algorithm.
• Quantum interior point methods offer a different route, with their own assumptions.

Real-world impact

Primarily theoretical at this stage, but semidefinite programming itself is so broadly used across optimization and machine learning that even modest practical speedups could have wide-reaching effects.

Why it matters

SDPs sit at the center of optimization and approximation algorithms, so a quantum speedup would be widely useful. The line of work is also a model for how to build quantum algorithms from classical ones, by finding which step can be accelerated by Gibbs sampling and amplitude estimation.

The matching lower bounds show where improvements must stop, which helps set expectations about what quantum computers can contribute to optimization.

Frequently asked questions

Keep learning

• Related algorithm: Max-Cut with Quantum Algorithms (QAOA and Quantum Max-Cut)
• Related algorithm: Quantum Gibbs Sampling
• Related algorithm: Quantum Algorithms and Quantum Optimal Transport
• Related algorithm: Quantum Amplitude Estimation

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database