Quantum Speed-ups for Semidefinite Programming

1 Introduction

• Semidefinite programming is a broadly applicable algorithmic framework, but growing practical instance sizes motivate more efficient solvers.SDPs support combinatorial-optimization approximation, operations research, and other applications.Source: §1 · p. 1
• A quantum algorithm solves semidefinite programs with a quadratic speed-up over classical methods in both matrix dimension and number of constraints, while depending on solution-size parameters.The paper also identifies this as the first quantum speed-up for linear programming, a subclass of SDPs.Source: §1 · p. 1

1.1 Semidefinite Programs

• The input consists of n × n Hermitian matrices and real constraint values, while primal optimization ranges over positive semidefinite matrices and has a corresponding dual program.Under mild conditions, the primal and dual programs have the same optimal value, with normalization assumptions on the instance.Source: §1.1 · p. 2
• Classical SDP methods include interior-point and multiplicative-weight algorithms, with runtimes depending on matrix dimension, constraints, sparsity, accuracy, and solution-size bounds.The cited interior-point bound uses m, n, matrix-multiplication exponent, row-sparsity, and accuracy; multiplicative-weight methods introduce R and r.Source: §1.1 · p. 2

1.2 Problem Statement

• The task is to approximate the SDP optimum and output primal and/or dual solutions through an oracle-based representation.The specified outputs include an objective-value estimate and samples from the normalized dual distribution or normalized primal quantum state.Source: §1.2 · pp. 2–3
• Explicitly listing a primal or dual solution already requires Ω(n + m) time, so the quantum algorithm uses compressed outputs and still faces an Ω(n + m) classical oracle-query lower bound.The lower bound applies to outputting the specified objective estimate and samples-based solution representation.Source: §1.2 · p. 3

2.1 Main Ideas

• The paper presents a quantum SDP algorithm whose main ingredients are multiplicative weights, Gibbs-state preparation, amplitude amplification, and Hamiltonian sparsification.The approach modifies the Arora–Kale method by replacing its inner linear program with Gibbs-state preparation and maximum-entropy reasoning.Source: §2.1 · pp. 3–4, §2.2 · p. 8

2.2 The Algorithm

• Binary search reduces SDP optimization to feasibility, producing either a near-feasible dual sample or evidence that the guessed optimum is too small.The algorithm estimates matrix-state expectations through a probabilistic oracle and Gibbs samplers.Source: §2.2 · pp. 4, 5, 8
• The method depends on the solution-size parameters R and r, assumes normalized inputs and bi ≥1 after reductions, and currently omits primal-state sampling details.The authors also note that the current algorithm is costly in R and δ and that primal sampling is deferred.Source: §2.2 · pp. 5–6
• The algorithm outputs either Larger, certifying an objective value above (1 −δ)α, or a dual-feasible y = Lp with objective value at most (1 + δ)α.These guarantees hold assuming the algorithm does not fail.Source: §2.2 · p. 8

2.3 Lower Bounds

• The lower-bound construction requires Ω(√n + √m) quantum oracle calls, showing that the algorithm’s dependence on n and m cannot be substantially improved in general.The proof reduces distinguishing two SDP instances to search problems while keeping R and the constraint data constant.Source: §2.3 · pp. 8–9

2.4 Discussion and Open Questions

• The discussion identifies Gibbs sampling as the core quantum ingredient, while leaving improved R- and δ-scaling, noise tolerance, and broader applications as open questions.The algorithm is robust to Gibbs-state preparation errors of order O(ε), but its practical scaling and noise behavior remain unresolved.Source: §2.4 · p. 9

3.1 The Arora-Kale Algorithm

• Arora–Kale’s algorithm iteratively applies a matrix multiplicative-weight method, using ORACLE(ρ) to generate constraint vectors or report failure.The method initializes ρ(1)=I/n, runs for T iterations, and updates the density matrix using oracle-generated vectors.Source: §3.1 · pp. 10–11
• If ORACLE never fails for the prescribed T, the averaged output is dual feasible with objective value at most α(1 + δ).The proof combines oracle properties with the matrix multiplicative-weight lemma and selected parameter choices.Source: §3.1 · pp. 11–12

3.2 Approximately Implementing ORACLE by Gibbs Sampling

• Jaynes’ principle permits choosing ORACLE’s output as a normalized Gibbs distribution over the constraints, with parameters controlling the Hamiltonian.The construction uses an approximate finite-dimensional version of Jaynes’ principle and allows sampling from distributions close in variational distance.Source: §3.2 · pp. 12–13
• Algorithm 10 samples approximate Gibbs distributions and returns samples from y/∥y∥1 together with ∥y∥1 satisfying the oracle inequalities.Its sampling procedure uses M samples across parameter values and succeeds with probability larger than 1 − exp(−log^ξ(nm)) when ORACLE does not fail.Source: §3.2 · pp. 13–14
• Chernoff and union bounds show that the sampled estimates meet the required oracle conditions with probability larger than 1 − exp(−log^ξ(nm)).The proof identifies a suitable parameter pair and uses closeness of the approximate sampling distributions to the target Gibbs distributions.Source: §3.2 · p. 14

• The resulting probabilistic oracle supplies Hamiltonian entries with bounded error and failure probability, enabling the Gibbs-sampling subroutines of the quantum algorithm.The oracle’s entries are based on estimated values of tr(A_iρ), which are queried during Hamiltonian construction.Source: §4 · pp. 15–16
• For an s-sparse Hermitian matrix A and density matrix ρ, tr(ρA) can be estimated to additive error ε in time O(sε^-2 log^4(ns/(p_eε))).The procedure uses O(log(1/p_e)ε^-2) copies of ρ and succeeds with probability larger than 1 − p_e.Source: §4 · p. 15
• The estimator uses Hamiltonian simulation and phase estimation to measure energies, then repeats the measurement O(1/ε^2) times to obtain the expectation value.Each phase-estimation measurement achieves accuracy ε/2 before Chernoff concentration is applied.Source: §4 · p. 15
• Applying the estimator to all input matrices requires controlling the joint failure probability by a union bound over the m expectation estimates.Each individual estimate is made hprecision-close with probability at least 1 − p′_e, giving overall success probability 1 − mp′_e.Source: §4 · p. 16

5 The Quantum Algorithm: Correctness and Complexity

• If the algorithm outputs Larger, the optimal objective value exceeds (1 − δ)α; otherwise it returns a sampled dual distribution and scale whose product is approximately feasible.The returned vector y = Lp is dual feasible with objective value at most (1 + δ)α when the algorithm does not fail.Source: §5 · p. 16
• The algorithm constructs y by combining sampled oracle outputs, whose known norms determine ∥y∥1 and permit sampling from the resulting convex combination.When no iteration outputs the zero vector, the algorithm samples from y/∥y∥1 using the distributions generated at each iteration.Source: §5 · p. 16
• The remaining iterations apply matrix multiplicative weights to a sparsified payoff matrix, reducing the cost of handling sampled updates.The sparsification is introduced specifically to keep the quantum complexity low.Source: §5 · pp. 17–18
• Failure can arise from faulty Hamiltonian-oracle calls, expectation-estimation errors, or random sampling, and the analysis bounds these contributions by a union bound.The correctness proof also uses matrix concentration and Gibbs-sampler error bounds.Source: §5 · pp. 16, 19, 20
• Runtime accounting aggregates Gibbs sampling, distribution sampling, expectation estimation, and repeated iterations, with T = Õ(R^3/δ^2).The analysis separately bounds the costs of steps 2, 4, 5, and 6–7 before multiplying by the iteration count.Source: §5 · p. 19
• Algorithm 3 runs in time Õ(n^1/2m^1/2s^2R^32/δ^18) using the specified Gibbs sampler.The corollary derives this bound from the algorithmic runtime theorem and the Gibbs-sampler implementation cost.Source: §2.2 · p. 8, §5 · p. 21

A Reduction to bi ≥1

• A δ-optimal solution of the transformed SDP restricts to a δ-optimal solution of the original SDP.The proof establishes feasibility of the restricted vector and then compares its objective value with the original optimum.Source: A Reduction to bi ≥1 · pp. 21–22
• A related SDP is defined with m + 1 variables in n + 1 dimensions, and because max |bi| = R, its objective-function vector has all elements greater than or equal to one.Source: A Reduction to bi ≥1 · p. 22
• An upper bound r on the sum of the optimal dual variables determines the added objective coefficient and the reduction’s size parameter.The parameter r bounds ∑_i z_i for an optimal original solution.Source: A Reduction to bi ≥1 · p. 22
• The reduction’s feasibility argument relies on nonnegative variables and satisfaction of the augmented matrix inequality.The contradiction step shows that violating the original objective guarantee would contradict δ-optimality of the transformed solution.Source: A Reduction to bi ≥1 · pp. 22–23
• If the constructed matrix C has norm larger than one, the SDP is rescaled by 1/r, requiring additive accuracy δ/r to recover δ accuracy for the original problem.This rescaling accounts for the normalization needed by the algorithm’s input assumptions.Source: A Reduction to bi ≥1 · p. 23