Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning

1 Introduction

• The introduction formulates approximate SDP feasibility as a general and convenient target because optimization reduces to feasibility, trace bounds can be normalized, and the formulation supports quantum-state learning.The conversion may rescale ε, and the approach avoids explicitly formulating the dual program.Source: §1 · pp. 2–3

1.1 Quantum SDP solvers with optimal dependence on m and n

• The quantum SDP solver decouples dependence on m and n, achieves optimal dependence on both, and provides quantum speed-ups for instances with mild 1/ε dependence.Polynomial dependence on 1/ε makes direct application to classical combinatorial SDPs such as Max-Cut nontrivial.Source: §1.1 · p. 4

1.2 Quantum SDP solvers with quantum inputs

• The quantum-input model provides a rigorous alternative based on quantum state and measurement oracles, yielding polylogarithmic dependence on n and polynomial dependence on rank r.The resulting runtime is (√m + poly(r))·poly(log m, log n, B, ε^-1), without the sparsity assumption required in the plain model; its √m dependence is optimal when B, r, and ε are constant.Source: §1.2 · pp. 5–6

1.3 Related works on quantum SDP solvers

• Relative to prior work [9, 5], the paper contributes a new SDP-solving framework, a fast quantum OR lemma, a rigorous quantum-input formulation, and the first Gibbs sampler with quantum inputs.The quantum-input model is incomparable to classical solvers because its access assumptions differ, motivating its relevance through applications such as learning quantum states.Source: §1.2 · pp. 6–7, §1.3 · p. 7
• The quantum input model improves prior complexity to ˜O(B√(ǫ^-7.5)) without explicit rank dependence, though rank may be implicit in B.Source: §1.3 · p. 7

1.4 Techniques

• The solvers quantize classical MMWU through a zero-sum game formulation, avoiding dependence on dual-solution size while preserving efficiency.An independent work [4] achieved the same quantum-SDP complexity using both primal-dual and zero-sum approaches.Source: §1.4 · pp. 7–8
• A fast quantum OR lemma detects a violated constraint using one copy of the state with O(√m) gate complexity, which is tight by Grover-search embedding.The test uses one copy of ρ and has acceptance guarantees depending on ε, ϕ, and ξ.Source: §1.4 · pp. 8–9
• The low-rank quantum Gibbs sampler prepares exp(−K)/Tr(exp(−K)) with poly(log n, rK, B, ǫ^-1) gates, removing sparsity assumptions and replacing plain-input Θ(√n) dimension dependence.It uses quantum oracles preparing normalized positive and negative parts of K and estimates of their traces, with Hamiltonian simulation techniques from quantum PCA [23, 20].Source: §1.4 · p. 9

1.5 Application: Efficient learnability of quantum states

• The learning application outputs a Gibbs-state circuit matching an unknown state’s m measurement expectations within ε using at most poly(log m, log n, r, ǫ^-1) copies and √m·poly(log m, log n, r, ǫ^-1) gates.The method solves an SDP feasibility problem for a trace-one PSD state and outputs the λi parameters, avoiding separate estimation of all m expectations and its Ω(m) cost.Source: §1.5 · pp. 10–11
• For low-rank efficiently implementable measurements, the procedure has ˜O(√m poly log(n)) gate complexity and solves an open problem proposed in Ref. [1].The sample and gate complexities have poly-logarithmic dependence on the state dimension n.Source: §1.5 · pp. 11–12

1.6 Open questions

• The approach remains limited because most measurements of interest are not low rank, and its practical applicability beyond low-rank measurements is unresolved.Source: §1.6 · p. 12

Feasibility formulation

• Binary search converts SDP optimization into repeated feasibility tests by adding a guessed objective value as a constraint.This reduces approximation of the optimum to feasibility checking.Source: A Feasibility of SDPs · p. 14

Zero-sum game approach

• The game view replaces a primal-dual formulation with equilibrium search, while retaining quantum Gibbs sampling as a way to generate candidate solution states.The approach is related to classical game-based SDP methods and matrix multiplicative-weight updates.Source: A Feasibility of SDPs · pp. 14–15
• The violation-search oracle returns a violated constraint index or reports FEASIBLE for a proposed density matrix.This oracle supplies the second player’s move in the zero-sum game.Source: A Feasibility of SDPs · p. 14

Master algorithm

• Matrix multiplicative weights updates a weight matrix using gain matrices and guarantees a feasibility bound after T rounds.The algorithm initializes W(1)=I_n, observes each gain matrix, and applies the matrix multiplicative-weights proposition.Source: A Feasibility of SDPs · p. 15
• O(ln n/ε^2) oracle queries suffice to test SDP feasibility with the master matrix-multiplicative-weights algorithm.The guarantee applies to the feasibility formulation defined by constraints on a density matrix.Source: A Feasibility of SDPs · p. 15

Motivation

• Fast amplification replaces the original quantum OR implementation’s costly projections and enables a quadratic speed-up in m.The resulting improvement separates the √m dependence from the other costs and yields an optimal SDP bound when remaining parameters are constant.Source: B Fast quantum OR lemma · p. 17

Fast quantum OR lemma

• The fast quantum OR test accepts with probability at least (1−ε)^2/4−ξ when some projector has overlap at least 1−ε, and at most 3ϕm+ξ when total overlap is at most ϕ.The parameters must satisfy (1−ε)^2/4−ξ > 3ϕm+ξ.Source: B Fast quantum OR lemma · p. 17

Complexity

• If the controlled reflection costs at most p operations, the test uses O(ξ^-1√m(p+poly(log m))) operations.The projection combines the controlled reflections associated with the indexed projectors.Source: B Fast quantum OR lemma · p. 17

Analysis

• With λ = (1 − ε)/(2m), Algorithm 3 accepts with probability at least (1 − ε)^2/4 − ξ in Case 1 and at most 3mϕ + ξ in Case 2.Source: B Fast quantum OR lemma · pp. 17–18

Optimality

• The √m gate complexity is optimal because a special case reduces to Grover search for whether an unknown index lies in [m].The lower bound requires Ω(√m) gates.Source: B Fast quantum OR lemma · p. 18

C Quantum SDP solver in the plain model

• The plain-model algorithm prepares Gibbs states of sparse Hamiltonians and estimates matrix traces to construct measurements that detect violated constraints.Trace estimation computes Tr[Hρ], while Gibbs sampling prepares states proportional to e^-H.Source: C Quantum SDP solver in the plain model · pp. 18–19
• Under the plain model, the solver tests SDP feasibility with success probability at least 0.96 and complexity given by the stated s^2-dependent bound.The theorem uses sparse constraint matrices and access through Oracle 1.1.Source: C Quantum SDP solver in the plain model · pp. 18, 20

D.1 The quantum input model

• The quantum input model assumes trace-norm-bounded matrices and provides oracles for traces, state preparation, and constraint values.These oracles are used to implement the violation-search oracle for the SDP solver.Source: §D.1 · p. 21
• The input-model framework defines low-rank Gibbs sampling for Hamiltonians decomposed into positive and negative parts, with complexity parameterized by rank and trace bounds.The Gibbs state is prepared to specified trace-distance precision using the quantum input oracles.Source: §D.1 · p. 22

Fast quantum OR

• Fast amplification supplies the square-root dependence on m when the controlled reflection over the indexed projectors is implemented.The reflection construction uses the quantum input oracles and the controlled projector sum.Source: §D.2 · p. 22

Oracle implementation

• The violation-search procedure finds a constraint j with Tr(A_jρ)≥a_j+ε or returns FEASIBLE when all constraints satisfy Tr(A_jρ)≤a_j.The algorithm achieves success probability 1−δ under the stated promise.Source: §D.2 · p. 22
• Trace-estimation POVMs decide whether Tr(A_jρ)−a_j>ε, after which reversible oracle access expresses each POVM through a projector suitable for the fast OR lemma.The construction uses copies of ρ and purifications of the positive parts A_j^+.Source: §D.2 · p. 22

Complexity

• The procedure uses log(1/δ)·Õ(√m TTr(B,ε)) gates and oracle queries, with an additional poly(log m) overhead for binary search.It uses trace-estimation samples of ρ and quantum input access to the matrices and thresholds.Source: §D.2 · p. 22

D.3 Quantum SDP solvers with quantum inputs

• The implementation uses Definition 2 for Gibbs-state generation and Lemma 3 for constructing the constraint-search oracle from the quantum input oracles.Oracle D.1, Oracle D.2, and Oracle D.3 provide the access needed for efficient gate complexity.Source: §D.3 · p. 23
• Algorithm 5 initializes W(1) = I_n and sets T = 16 ln n, then prepares ˜O(STr(B, ε)) samples of ρ(t) = W(t)/Tr[W(t)] and searches for j(t) ∈ [m].Source: §D.3 · p. 23
• (√m + poly(r)) · poly(log m, log n, B, ǫ−1) quantum gates and oracle queries suffice for feasibility testing with success probability at least 0.96.The result assumes Tr[A+_j] ≤ B and rank(A_j) ≤ r for all constraints.Source: §D.3 · pp. 23–24
• The solver’s dependence on m is optimal up to polylogarithmic factors, while later techniques can improve the explicit parameter dependence in the stated complexity.The paper notes that the √m dependence is optimal and discusses a refinement from Ref. [4].Source: §D.3 · p. 24

D.4 Trace estimation

• O(B^2 log m/ǫ^2) copies and oracle-based operations suffice to distinguish Tr(A_jρ) > a_j + ǫ from Tr(A_jρ) ≤ a_j with high probability.Algorithm 6 implements the required measurement using SWAP tests and Chernoff bounds.Source: §D.4 · pp. 25–26
• The trace-estimation primitive uses SWAP tests on ρ and normalized positive or negative parts of A_j, then compares empirical frequencies against the threshold.The positive and negative contributions are handled separately before combining the estimates.Source: §D.4 · p. 25

D.5 Gibbs state preparation

• For K = K+ − K− built from low-rank components, the Gibbs state exp(−K)/Tr(exp(−K)) can be prepared to ǫ trace-distance precision in |S| · poly(log n, r_K, B_K, ǫ−1) complexity.The construction first prepares normalized K+ and K− states using |S| samples to Oracle D.1 and one sample to Oracle D.2.Source: §D.5 · p. 26

D.6 Lower bound for quantum SDP solvers with quantum inputs

• When B, r, and ǫ are Θ(1), some SDP feasibility problems require Ω(√m) calls to Oracle D.1 and Oracle D.2.The lower bound reduces distinguishing two SDP instances to Grover search over the exceptional constraint.Source: §D.6 · pp. 26–27
• Combining the upper and lower bounds gives an optimal quantum-input SDP feasibility complexity up to polylogarithmic factors.The lower bound applies to the oracle model used by the fully quantum solver.Source: §D.6 · pp. 26–27

E Application: efficient learnability of quantum states

• The learning problem asks for a circuit-preparable state σ whose expectations match those of an unknown ρ on m two-outcome POVMs within ǫ.The reduction encodes these expectation constraints as an SDP feasibility problem.Source: E Application: efficient learnability… · p. 27, §E.1 · pp. 27–28

E.2 Finding the violated constraint using ˜O(√

• With rank-bounded POVMs and the quantum input oracles, violated-constraint search uses √m · poly(log m, log n, r, ǫ−1, log δ−1) gates and queries.The procedure either finds a measurement with error at least ǫ or returns FEASIBLE when all errors are at most ǫ/2.Source: §E.2 · p. 28

E.3 Gate complexity of learning quantum states

• Each iteration prepares a Gibbs state ρ(t), uses copies of ρ and ρ(t) to search for a violated measurement, and terminates when none is found.The algorithm runs for at most 16 ln n iterations.Source: §E.3 · pp. 28–29
• √m · poly(log m, log n, r, ǫ−1) gates and oracle queries, plus poly(log m, log n, r, ǫ−1) copies of ρ, solve the measurement-learning problem with success probability at least 0.96.The output is a circuit description of a state matching the unknown state’s measurement expectations within the target accuracy.Source: §E.3 · pp. 28–29
• Low-rank Gibbs-state preparation contributes only poly(log m, log n, r, ǫ−1) cost across the iterations.The rank and trace bounds of the accumulated Hamiltonian enable Lemma 12 to provide the required preparation complexity.Source: §E.3 · p. 29
• The learning complexity is optimal up to polylogarithmic factors because some shadow-tomography instances require Ω(√m) oracle calls when r and ǫ are Θ(1).The lower bound applies to the same quantum measurement-oracle setting.Source: §E.3 · pp. 28, 30

F Gibbs sampling of low-rank Hamiltonians

• The Gibbs sampler uses Hamiltonian simulation and eigenvalue estimation for low-rank Hamiltonians supplied through quantum state oracles.The exact-eigenvalue assumption used for exposition is removed in Appendix G.Source: F Gibbs sampling of low-rank… · p. 30

Partition-function estimation

• The partition function Z is estimated for K = K+ − K− when K+ and K− have bounded trace and rank, using quantum access to their normalized states.The procedure achieves multiplicative error ǫ with polynomial quantum gates in log n, rK, B, ǫ−1, and ξ−1.Source: §F.1 · p. 30

Supported spectrum

• Phase estimation on ρ+ and ρ− produces a random variable X whose expectation is proportional to the supported partition function Zsupp.Thus, a multiplicative estimate of E[X] gives a multiplicative estimate of Zsupp.Source: §F.1 · p. 31
• O(B2δ−2ǫ−2) repetitions suffice for a constant-probability multiplicative estimate of E[X] using its second-moment bound.Chebyshev’s inequality gives the stated repetition count from E[X2] ≤ B2δ−2E[X]2.Source: §F.1 · p. 32

Final estimate

• Setting δ = O(ǫ) and combining the supported-spectrum and small-eigenvalue estimates gives an O(ǫ)-error multiplicative estimate of Z.The total number of phase-estimation uses is O(B2ǫ−4 + rKǫ−2).Source: §F.1 · p. 32

Small eigenvalues

• The contribution of eigenvalues below δ is estimated by sampling a uniformly random state and determining whether its measured eigenvalue satisfies |λ| < δ.O(rKǫ−2) repetitions estimate n − R multiplicatively, where R is the number of eigenvalues with magnitude at least δ.Source: §F.1 · p. 32

Gibbs-state preparation

• Theorem 4 prepares ρG = exp(−K)/Tr(exp(−K)) to trace-distance error ǫ with poly(log n, rK, B, ǫ−1) quantum gates.The input consists of oracles preparing ρ+ and ρ− and providing Tr(K+) and Tr(K−), with bounded rank and total trace.Source: §F.2 · p. 32

Supported spectrum

• The protocol first samples ρsupp, the Gibbs state restricted to eigenvalues with magnitude at least δ, by phase estimation followed by eigenvalue-dependent acceptance.The acceptance correction changes factors based on λ+ and λ− into the desired Gibbs weights e−λi.Source: §F.2 · p. 33
• Repeating the supported-spectrum procedure yields ρsupp efficiently, requiring O(B/δ) expected trials when K has an eigenvalue with magnitude at least δ.The procedure prepares the supported Gibbs state after postselection on the acceptance event.Source: §F.2 · p. 33

Kernel contribution

• The small-eigenvalue contribution is obtained by phase-estimating a uniformly random state and accepting only outcomes with |λ| < δ.This supplies the approximately uniform state on the orthogonal complement of the approximate support.Source: §F.2 · p. 34

Final construction

• Combining the supported and kernel procedures with δ = O(ǫ) prepares ρG up to O(ǫ) trace-distance error using poly(log n, rK, B, ǫ−1) gates.The construction also uses multiplicative estimates of Zsupp, Z, and n − R.Source: §F.2 · p. 34

• The complete proof of Lemma 3 and Theorem 4 is provided in Appendix G.Source: G Proof for Gibbs sampling of low-rank… · p. 34

Consistent phase estimation

• Ordinary phase estimation can give inconsistent threshold decisions across runs, motivating Ta-Shma’s consistent phase estimation algorithm.A random shift makes the estimated eigenvalue depend only on the true eigenvalue rather than the measurement outcome, with high probability.Source: §G.1 · pp. 34–35
• Lemma 1 provides consistent eigenvalue estimates for a unitary using poly(ξ−1, δ−1) controlled-unitary operations and gates.The estimate f(s, λ) differs from λ by less than δ for all eigenstates under a good random shift.Source: §G.1 · p. 35

Hamiltonian estimation

• For H = a+ρ+ − a−ρ− with rank at most r, consistent phase estimation works simultaneously over all eigenstates with failure probability at most 2rξ.This extends the unitary procedure to low-rank Hamiltonians accessed through copies of ρ+ and ρ−.Source: §G.1 · p. 35

Eigenvalue estimation

• The resulting procedure estimates eigenvalues of K = K+ − K− using poly(log n, B, ξ−1, δ−1) total operations.A minimum-eigenvalue routine repeats consistent estimates and returns the smallest estimated eigenvalue whose magnitude exceeds δ.Source: §G.1 · p. 35

G.2 Computing the partition function

• poly(log n, rK, B, ε^-1, ξ^-1) quantum gates suffice to estimate Z = Tr(exp(−K)) to multiplicative error ε with success probability at least 1 − ξ.The result assumes quantum access to normalized K+ and K− states, their traces, trace bound B, and rank bound rK.Source: §G.2 · p. 36
• Consistent phase estimation estimates K's eigenvalues on oracle-prepared states and retains eigenvalues with magnitude at least δ, while discarding values below an approximate minimum eigenvalue.The thresholding controls the expectation of the estimator and addresses errors introduced by phase estimation.Source: §G.2 · p. 36
• Approximate eigenvalue degeneracies are handled by grouping eigenvectors mapped to the same estimated eigenvalue and working in an approximate eigenbasis.The resulting basis need not equal K's exact eigenbasis because its vectors are only approximate eigenvectors.Source: §G.2 · pp. 36–37
• The full partition function is obtained by summing the estimated approximate-support contribution and the estimated near-zero-eigenvalue contribution, achieving O(ε)-multiplicative error.The support term is estimated by repeated sampling, while the kernel-size contribution is estimated from consistent phase estimation on the maximally mixed state.Source: §G.2 · pp. 37–38

G.3 Computing the Gibbs function

• poly(log n, rK, B, ε^-1) quantum gates suffice to prepare ρG = exp(−K)/Tr(exp(−K)) within ε trace distance.The construction approximates Gibbs states separately on the approximate support and approximate kernel, then combines them using multiplicative estimates of the relevant partition functions.Source: §G.3 · pp. 38, 40