Quantum Mathematics Learning Guide 68: Quantum Semidefinite Programming, Matrix Multiplicative Weights, Convex Optimisation and Quantum SDP Solvers

Semidefinite programming optimises a linear objective over the cone of positive semidefinite matrices subject to linear constraints. Quantum SDP algorithms try to accelerate parts of that convex optimisation pipeline by representing matrices as quantum states, estimating traces quantumly, and using Gibbs-state or matrix-multiplicative-weights subroutines.

This guide owns the convex-optimisation lane. Guide 61 owns QAOA for discrete combinatorial optimisation; Guide 14 owns variational eigensolvers; Guide 67 owns Gibbs-state preparation itself. Here Gibbs states appear as a computational primitive inside a matrix optimisation method.

The central caution is input/output modelling. Quantum SDP solvers can show polynomial or square-root improvements in matrix dimension and number of constraints under sparse-oracle, QRAM or block-encoding assumptions, but dependence on precision, rank, condition parameters and classical output size can dominate. A solver that returns an implicit quantum state is not equivalent to a classical algorithm that prints every entry of the optimal matrix.

Convex matrix constraints → primal/dual certificates → matrix multiplicative weights → Gibbs-state/exponential updates → quantum trace estimation → approximate optimum or implicit solution state.

1. Positive semidefinite matrices

A Hermitian matrix X is positive semidefinite, written X≥0, when

v†Xv≥0

for every vector v.

Equivalently, all eigenvalues of X are nonnegative.

Density matrices are PSD with unit trace, so quantum information naturally lives inside the semidefinite cone.

2. Canonical primal SDP

One common primal form is

maximise Tr(CX)

subject to

• Tr(A_iX)≤b_i for i=1,…,m;
• X≥0.

Variants use equality constraints or minimisation; they can be converted by slack variables/sign changes when assumptions permit.

3. Dual SDP

A corresponding dual is

minimise b·y

subject to

Σ_i y_iA_i−C≥0, y_i≥0.

Every feasible primal X and dual y satisfy weak duality:

Tr(CX)≤b·y.

Under Slater-type regularity conditions, strong duality makes the optimal values equal.

4. Why duality matters computationally

A primal candidate gives a lower bound on a maximisation optimum; a dual candidate gives an upper bound.

When the gap between them is at most ε, the optimum is certified to additive ε.

Quantum SDP solvers often target approximate objective values and implicit certificates rather than an exact matrix description.

5. Tiny worked SDP

Consider

max Tr(ZX)

subject to

• Tr(X)=1;
• X≥0.

X is any qubit density matrix.

The maximum expectation of Z is its largest eigenvalue 1, attained by

X=|0⟩⟨0|.

The minimum would be −1 at |1⟩⟨1|.

6. MaxCut SDP relaxation

Classical MaxCut has binary signs s_i∈{±1}. Write X_ij=s_is_j.

The exact rank-one matrix X=ss^T satisfies X≥0 and X_ii=1.

Dropping the rank-one constraint gives the Goemans–Williamson SDP relaxation:

max (1/4)Σ_{ij}w_{ij}(1−X_{ij})

subject to X≥0 and X_ii=1.

This shows why SDPs are powerful classical baselines for QAOA-style combinatorial optimisation.

7. Matrix multiplicative weights

The matrix multiplicative-weights method generalises scalar multiplicative weights from probability vectors to PSD matrices.

Maintain a density-like matrix

ρ_t=exp(−ηΣ_{τ<t}M_τ)/Tr exp(−ηΣ_{τ<t}M_τ)

where M_τ is a Hermitian loss/separation matrix and η is a learning rate.

This is exactly a Gibbs state of an accumulated loss Hamiltonian.

8. Why Gibbs states appear inside SDP solvers

At iteration t, the matrix-weight update requires expectation values

Tr(A_iρ_t).

If ρ_t can be prepared as a quantum Gibbs state, quantum measurement routines can estimate many constraint violations without explicitly materialising the full matrix.

This is the algorithmic link between Guide 67 and quantum SDP solvers such as Brandão–Svore.

9. Separation-oracle viewpoint

Given candidate ρ, ask whether all constraints satisfy

Tr(A_iρ)≤b_i+ε.

If not, return a violated constraint i.

The multiplicative-weights update penalises that direction and produces a new ρ.

After enough iterations, either the average iterate is approximately feasible or the accumulated violated constraints produce a dual certificate.

10. Width parameter

Multiplicative-weights convergence depends on operator-norm bounds such as

||M_t||≤w.

w is often called a width or scale parameter.

Rescaling constraints can normalise w, but that rescaling changes required precision and oracle normalisation elsewhere.

Complexity claims should report width/norm assumptions rather than suppress them inside O-notation.

11. Iteration count

Matrix multiplicative weights typically needs a number of iterations polynomial in

w² log n / ε²

under standard normalisations.

The exact theorem depends on the primal/dual form and oracle accuracy.

This makes precision dependence a major practical issue even when matrix dimension n enters only logarithmically in some subroutines.

12. Quantum trace estimation

If one can prepare ρ and implement measurement/block encoding of A, estimate

Tr(Aρ).

Direct sampling has O(1/ε²) shot dependence for bounded observables.

Amplitude estimation can reduce this to O(1/ε) coherent queries under stronger reversible-access assumptions.

The choice changes circuit depth and fault-tolerance requirements.

13. Input models

An SDP instance contains n×n matrices A_i,C and m constraints.

Quantum speedups require structured access, for example:

• sparse-matrix oracles;
• block encodings;
• QRAM/state-preparation oracles;
• succinct formula/circuit descriptions.

If all mn² matrix entries arrive as ordinary classical input and must first be read, no algorithm can avoid that input size.

14. Sparse-oracle access

A common model assumes each row of A_i has at most s nonzero entries and an oracle returns their positions and values.

Hamiltonian-simulation/Gibbs-state subroutines then scale polynomially in s and polylogarithmically in n under ideal oracle access.

Dense matrices can remove this advantage unless low-rank/factorised structure provides another efficient encoding.

15. QRAM model

Some quantum optimisation algorithms assume coherent access to classical data in QRAM:

Σ_i α_i|i⟩|0⟩→Σ_i α_i|i⟩|data_i⟩.

If QRAM construction/loading is counted, the end-to-end advantage can shrink.

A complexity theorem using QRAM should not be compared directly with a classical algorithm charged for every memory access under a different model.

16. Brandão–Svore quantum SDP solver

Brandão and Svore gave a quantum SDP algorithm combining matrix multiplicative weights, Gibbs-state preparation and quantum search/trace estimation. [1]

The result demonstrated polynomial quantum improvements in dimension/constraint dependence for important parameter regimes and access models.

Later work substantially improved dependence on problem parameters and clarified lower bounds and input-model limitations.

17. Later quantum SDP improvements

van Apeldoorn, Gilyén, Gribling and de Wolf developed improved quantum SDP solvers using modern quantum linear algebra, amplitude amplification/estimation and refined multiplicative-weights frameworks. [2]

These algorithms reveal a general lesson: quantum speedups often shift bottlenecks rather than remove them. Precision ε, width, trace bounds, rank and state-preparation cost remain central.

18. Output model

A classical interior-point SDP solver can output an explicit n×n approximate matrix X.

A quantum solver may instead output:

• an approximate optimal objective value;
• a quantum state proportional to/representing X;
• a sampler for measurements on X;
• a small number of requested observables;
• an implicit dual certificate.

Printing all n² entries of X would require Ω(n²) classical output in general, eliminating polylogarithmic dimension scaling.

19. Low-rank solutions

Many SDPs admit or approximately admit low-rank optimal solutions.

If X≈VV† with rank r≪n, storing V takes O(nr) classical numbers rather than n².

Low-rank structure can help both classical algorithms and quantum state preparation.

A fair comparison should allow both sides to exploit the same structure.

20. Precision dependence

Quantum algorithms with favourable √n or √m scaling can have worse dependence on 1/ε than classical interior-point methods.

For high-precision optimisation, this can erase a dimension-based speedup.

Quantum SDP methods are therefore especially interesting when moderate additive precision is sufficient and the matrix dimension/constraint count is extremely large.

21. Approximate feasibility

A numerical solver often guarantees

Tr(A_iX)≤b_i+ε

rather than exact feasibility.

If the downstream application requires a hard safety constraint, one must convert additive residuals into a robust feasible solution or prove the violation tolerance is acceptable.

Optimisation precision is not merely a mathematical decoration; it changes whether a returned design is admissible.

22. SDP applications in quantum information

Semidefinite programs naturally appear in:

• state discrimination;
• entanglement witnesses;
• Bell/nonlocality bounds;
• channel optimisation;
• quantum error-correction bounds;
• causal witnesses from Guide 60;
• tomographic maximum-likelihood relaxations.

Quantum computers may therefore use SDP solvers on optimisation problems generated by quantum information itself.

23. SDP applications beyond quantum information

Classical applications include combinatorial relaxations, control theory, robust optimisation, polynomial sum-of-squares hierarchies, matrix completion and covariance estimation.

The quantum solver’s relevance depends on whether these applications admit efficient coherent input and compressed useful output.

24. Interior-point classical baselines

Modern classical SDP solvers use interior-point, first-order, low-rank and problem-specific methods.

For sparse structured instances, specialised classical solvers can be dramatically faster than generic worst-case dense bounds.

A quantum speedup claim should therefore compare against the strongest relevant classical algorithm under matched input/output and precision models.

25. Common misconception: PSD constraint is just elementwise nonnegativity

X≥0 means nonnegative eigenvalues/quadratic forms. Individual off-diagonal entries may be negative or complex.

26. Common misconception: quantum SDP speedup means the optimal matrix can be printed exponentially faster

An explicit n×n matrix contains n² classical numbers. Quantum advantage requires an implicit state/value/observable output or additional low-rank structure.

27. Common misconception: Gibbs sampling is a minor implementation detail

In multiplicative-weights quantum SDP algorithms, preparing exponential matrix weights can be one of the dominant subroutines. Poor Gibbs-state complexity can eliminate the theoretical improvement.

28. Worked synthesis problem

Consider the SDP

max Tr(ZX) subject to TrX=1, X≥0.

Step 1: Spectral bound. For every density matrix X, Tr(ZX)≤λ_max(Z)=1.

Step 2: Feasible witness. X=|0⟩⟨0| is PSD with trace one.

Step 3: Objective. Tr(Z|0⟩⟨0|)=1.

Step 4: Optimality. The feasible value reaches the spectral upper bound, so optimum is exactly 1.

Step 5: Quantum-solver lesson. A large SDP solver would rarely reconstruct X entry by entry. It might estimate the optimum and prepare a state approximating X so downstream observables can be measured directly.

29. Practice set

1. Define X≥0.
2. Write the primal SDP form used here.
3. Write its dual inequality.
4. What does weak duality provide?
5. What is matrix multiplicative weights?
6. Why is its iterate a Gibbs state?
7. What does a separation oracle return?
8. Why does width matter?
9. Name two quantum input models.
10. Why can QRAM assumptions change the practical comparison?
11. What outputs can preserve quantum dimension speedups?
12. Why does high precision threaten a quantum SDP advantage?

Answers

1. X is Hermitian and v†Xv≥0 for all v, equivalently all eigenvalues are nonnegative.
2. Maximise Tr(CX) subject to Tr(A_iX)≤b_i and X≥0.
3. Σ_i y_iA_i−C≥0 with y_i≥0.
4. Every feasible dual objective upper-bounds every feasible primal objective for this maximisation convention.
5. An iterative exponential-update method for matrix-valued losses/constraints.
6. ρ_t∝exp(−ηΣM_τ) has the Gibbs form of an accumulated loss Hamiltonian.
7. A violated constraint or a statement that all constraints are satisfied within tolerance.
8. It controls loss-operator norm and therefore learning rate/iteration complexity.
9. Examples: sparse-entry oracles, block encodings and QRAM/state-preparation access.
10. Coherent memory loading/access can hide O(input size) costs not charged in the query model.
11. Objective values, implicit solution states, selected observables or compact certificates—not a full dense classical matrix.
12. Iteration counts, trace estimation and Gibbs sampling can scale polynomially with 1/ε and dominate dimension improvements.

Sources and further study

[1] Fernando G. S. L. Brandão and Krysta M. Svore, Quantum Speed-ups for Semidefinite Programming, FOCS 2017. Introduces a quantum matrix-multiplicative-weights SDP solver using Gibbs-state and search primitives.

[2] Joran van Apeldoorn, András Gilyén, Sander Gribling and Ronald de Wolf, Quantum SDP-Solvers: Better upper and lower bounds. Improves quantum SDP complexity and proves limitations in several input models.

[3] Sanjeev Arora and Satyen Kale, A Combinatorial, Primal-Dual Approach to Semidefinite Programs, Journal of the ACM / Theory of Computing. Matrix multiplicative-weights framework underlying many SDP solvers.

[4] Michel X. Goemans and David P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal of the ACM 42, 1115–1145 (1995). A canonical SDP relaxation and rounding application.

Batch 17 series navigation

• Guide 65: Shor’s Algorithm, Order Finding, Period Finding, Modular Exponentiation and Integer Factoring
• Guide 66: Hidden Subgroup Problems, Simon’s Algorithm, Fourier Sampling and Abelian Quantum Algorithms
• Guide 67: Quantum Gibbs-State Preparation, Thermal Sampling, Partition Functions and Quantum Metropolis Methods
• Guide 68: Quantum Semidefinite Programming, Matrix Multiplicative Weights, Convex Optimisation and Quantum SDP Solvers
• Return to the BTT Mathematics Learning Hub

Educational note: quantum optimisation speedups are always conditional on input access, output requirements, precision and state-preparation assumptions. Complexity comparisons should match those models explicitly.