Source-linked AI summary
Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf
TL;DR
Quantum SDP-solvers had better dependence on n and m in some regimes but worse dependence on other parameters. This paper improves those algorithms with new quantum techniques, while proving restrictions from sparse outputs and worst-case lower bounds. For m ≈ n, quantum LP-solvers require Ω(mn) queries, matching classical scaling.
Problem
Existing quantum SDP-solvers can outperform classical methods in n and m in some regimes but have worse dependence on parameters such as R, r, s, and 1/ε.
Method
The paper quantizes parts of the Arora–Kale framework using purified Gibbs sampling, amplitude estimation, smooth Hamiltonian-function implementation, and generalized minimum-finding.
Results
The paper improves quantum SDP-solvers' dependence on R, r, and 1/ε and proves Ω(mn) worst-case query complexity for quantum LP-solvers when m ≈ n.
Takeaways & Limitations
Quantum SDP speed-ups in m and n remain constrained by parameter trade-offs, sparse dual outputs, and worst-case lower bounds.
Takeaways & Limitations
The quantum approach provides a speed-up only when R, r, s, and 1/ε are fairly small compared with mn, and finding suitable SDPs is open.
Abstract
from arXiv · showhide
Brandão and Svore very recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure. We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $m\approx n$, which is the same as classical.
1 Introduction
The paper improves quantum algorithms for approximately solving SDPs while identifying limits on their parameter dependence and establishing matching worst-case scaling for quantum LP-solvers when m and n are comparable.
- 1.1 Semidefinite programs: SDPs generalize LPs and can yield better approximation algorithms because of their stronger expressive power.
- 1.1 Semidefinite programs: The Goemans–Williamson SDP can be rounded to a cut whose size is within a factor ≈0.878 of MAXCUT(G).
- 1.3 Quantum SDP-solvers: Brandão–Svore quantum SDP-solvers improve dependence on m and n but worsen dependence on R, r, s, and 1/ε, giving speed-ups only when those parameters are small compared with mn.
- 1.4 Our results: The paper presents faster quantum SDP algorithms and lower bounds for quantum LP-solvers, which also apply to quantum SDP-solvers.
- 1.4.1–1.4.2 Tools: The improved solver uses purified Gibbs sampling and amplitude estimation, while its broader toolkit efficiently implements smooth functions of sparse Hamiltonians.
- 1.4.3 Lower bounds: For m ≈ n, every quantum LP-solver requires Ω(mn) queries in the worst case, matching the classical scaling and ruling out O(√mn) without polynomial dependence on Rr/ε.
2 An improved quantum SDP-solver
The paper builds a general quantum SDP-solver by combining the Arora–Kale framework with quantum trace estimation and an efficient 2-sparse oracle. It also develops new Hamiltonian and minimum-finding techniques, establishes runtime guarantees, and identifies limits requiring problem-specific oracles.
- Assumptions: The algorithm assumes bounded input norms, attained primal and dual optima, additive error, and sparse-access representations for the input matrices.The section uses r as a bound on the dual solution’s ℓ1-norm and R as a trace bound for primal solutions.
- Scope and limitations: A solver working for all SDPs must use a large width bound, so quantum speedups for specific SDP classes require oracles tuned to their structure.The paper contrasts this general-purpose design with specialized oracles such as those used for MAXCUT.
- Quantum trace estimation: The trace-estimation method prepares purified Gibbs states and uses amplitude estimation for diagonal and general matrices.The general-matrix case additionally requires smooth functions of Hamiltonians and generalized minimum-finding because eigenvectors are not known or shared.
- Efficient oracle: The 2-sparse oracle reduces finding a feasible y to finding a convex combination of two points in a geometric region.The resulting quantum procedure uses O(√m) oracle calls in the exact setting and eO(√m) calls with approximate entries, while returning a 2-sparse vector under stated feasibility guarantees.
- Solver construction: The solver instantiates Arora–Kale with a quantum trace-estimation procedure and a general oracle, producing an ε-optimal feasible dual solution with high probability.The oracle uses width-bound w := r + 1 and binary search over OPT ∈ [−R, R].
3 Downside of this method: general oracles are restrictive
The paper shows that general sparse-oracle and width-bound approaches can be restrictive when useful dual solutions are dense, especially for symmetric or combinable SDP families.
- General oracles: General sparse oracles cannot encode enough information when different symmetric SDP instances require different solutions.The counting argument uses permutation-equivalent SDPs with disjoint correct-solution sets to force many distinct dual solutions.
- Width bounds: An oracle that always returns a 2-sparse vector forces width and runtime to grow with the sparsity required by the SDP.The resulting runtime is of order ℓ^4√nms^2 when the required sparsity is ℓ, which is poor for ℓ of order n or m.
- General oracles: An ε-optimal dual solution can be converted into a correct original-problem solution without additional knowledge of the instance.
- Symmetric SDPs: For the MAXCUT-related symmetric family, any z/2-approximate dual solution has sparsity at least 2^z/√z.The result also applies to the standard linear-programming formulation of (s,t)-maxflow/(s,t)-mincut.
- Width bounds: For general width bounds, some LPs and SDPs require width at least r*/2, while combinable families can make R*r*/ε grow linearly with n and m.The construction applies under the stated parameter conditions and mild assumptions on optimal dual solutions.
4 Lower bounds on the quantum query complexity
The paper proves quantum query lower bounds for LP and SDP optimization by reducing composed Majority and OR problems to distinguishing optimal objective values.
- Reduction: The lower-bound strategy reduces a composed MAJ_a-OR_b-MAJ_c problem to determining the optimal value of an LP.The reduction exploits the known quantum query complexity of the composed promise function.
- Reduction: The constructed LP has m = c + a constraints and n = c + ab variables, with input queries simulable using at most one query to Z.
- Lower bounds: Ω(√n m^3/2) quantum queries are required to distinguish two possible integer optimal values for LPs with m ≤ n.
- Lower bounds: Distinguishing two LP or SDP optimal values with additive error ε < 1/2 requires a worst-case quantum query lower bound.The SDP statement follows from the LP result and LP duality.
- Scope: The lower bound does not contradict the solver’s √mn dependence because this LP family has R,r = Θ(min{n,m}^2).A lower bound with constant ε, R, and r remains open.
5 Conclusion
The paper improves quantum SDP algorithms and lower bounds, while identifying parameter regimes, applications, and lower-bound tightness as open directions.
- Conclusion: The paper reports improved algorithms and lower bounds for quantum SDP-solvers relative to Brandão and Svore.
- Better upper bounds: The algorithm improves dependence on m and n but remains worse in dependence on sparsity s and Rr/ε than desired.Subsequent work improved these dependencies, but further improvement remains possible.
- Applications: The known quantum speed-up applies only when mn ≫ Rr/ε, and the authors do not identify particularly interesting combinatorial-optimization problems in that regime.Many natural SDP formulations instead fall outside the regime.
- Future work: The paper suggests designing quantum oracles for specific SDPs and possibly accelerating other classical SDP solvers.
- Better lower bounds: The lower bounds are probably not optimal, especially when m and n differ substantially; tight bounds in m, n, s, and Rr/ε remain desirable.
B Implementing smooth functions of Hamiltonians
The appendix gives a general method for implementing smooth functions of sparse Hamiltonians by approximating the function with a finite Fourier series and simulating its terms.
- Fourier approximation: The method implements an approximation ˜f(H) by constructing a finite Fourier approximation ˜f of f over the spectrum of H.The approximation error is controlled over the interval [−∥H∥, ∥H∥].
- Fourier approximation: The Fourier approximation is constructed from a polynomial approximation, using Taylor series for analytic functions within the convergence radius.This avoids integration and applies to a wide range of smooth functions.
- Fourier approximation: The approach keeps the largest Fourier time parameter logarithmic in the desired approximation precision.
- Implementation: The circuit for a fixed function f depends on f rather than H, with H-dependence entering through Hamiltonian simulation.
- Implementation: Each Fourier term is implemented with Hamiltonian simulation, and the terms are combined using the LCU Lemma.
- Implementation: For a d-sparse Hamiltonian with norm at most K, controlled simulation uses O(τd log(τ/ε)/log log(τ/ε)) queries under γ = Ω(1/(Kd)).Here τ = MγK.
B.1 Implementation of smooth functions of Hamiltonians: general results
This section develops a general method for implementing smooth functions of sparse Hamiltonians by converting polynomial approximations into efficiently implementable Fourier series and combining Hamiltonian simulations.
- Fourier-series construction: A polynomial approximation of f can be converted into a Fourier series without increasing coefficient weight, enabling implementation through the LCU Lemma.The resulting coefficients can be computed efficiently on a classical computer.
- Fourier-series construction: Fourier terms are implemented with Hamiltonian simulation and combined using the LCU Lemma.The construction uses a controlled Hamiltonian simulation circuit and O(M(log(M)+1)) two-qubit gates.
- General implementation theorem: Theorem 40 turns a function with a convergent Taylor series near the Hamiltonian spectrum into an ε-precise unitary implementation of f(H).The complexity depends on the spectral-radius parameters, norm bound, sparsity, and precision.
- General implementation theorem: The implementation is efficient when f is approximated by a low-degree Fourier series, with the Hamiltonian dependence entering through controlled simulation.The circuit for a fixed function depends on f but not directly on H; H-dependence is supplied by Hamiltonian simulation.
- Complexity consequences: For suitable smooth functions, the method achieves logarithmic dependence on the approximation error and near-optimal normalization by the function’s maximum magnitude.The complexity includes an Õ(∥H∥d) query and gate factor under the stated interval-covering conditions.
B.2 Applications of smooth functions of Hamiltonians
The smooth-function framework is applied to Gibbs-state preparation and linear-system solving, yielding improved precision dependence and a shorter HHL analysis.
- Gibbs-state preparation: Theorem 43 efficiently implements e^-H when H ⪰ I, providing the main exponential-function subroutine used for Gibbs-state preparation.The construction applies the smooth-function theorem to e^-x² after suitable parameter choices.
- Gibbs-state preparation: A purified Gibbs state can be prepared using amplitude amplification, with a cost depending logarithmically on the precision parameter.The procedure uses a purified sub-normalized Gibbs state and exponential search for postselection.
- Gibbs-state preparation: The approach recovers a Gibbs sampler while avoiding the involved integral transformations used in related work.The authors state that the resulting proof is significantly shorter.
- Improved HHL algorithm: The improved HHL procedure uses O(κ) applications of the state-preparation circuit U and query complexity O(dκ² log²(κ/ε)).It applies the smooth-function method to f(x)=1/x over the separated positive and negative eigenvalue intervals.
C Generalized minimum-finding algorithm
This section generalizes quantum minimum-finding from querying individual search elements to sampling from a distribution prepared by a quantum unitary, and applies it to estimating ground-state energy.
- Algorithm and motivation: The generalized algorithm needs only a unitary that prepares a superposition over the search space, rather than queries to individual elements.This removes a logarithmic factor relative to binary search in the intended applications.
- Algorithm and motivation: The algorithm repeatedly samples values below the current threshold using amplitude amplification and exponential search.The sampled values are strictly decreasing until the minimum is reached.
- Complexity and guarantees: Lemma 48 bounds the expected number of uses of U and U^-1 before obtaining a value at most x_k by O(√(1/Pr(X≤x_k))).The bound is the basis for the finite-budget success guarantee.
- Complexity and guarantees: Theorem 49 achieves constant success probability within a budget proportional to 1/√Pr(X≤x), boostable to 1−δ with O(log(1/δ)) repetitions.The algorithm uses at most M applications of U and U^-1 and O(qM) additional gates.
- Ground-state energy application: The procedure estimates the smallest eigenvalue by preparing a maximally entangled state, applying phase estimation, and minimum-finding over the resulting phases.The estimate has additive error ε with probability at least 2/3 under sparse-oracle access.
D Sparse matrix summation
This section constructs a sparse-matrix oracle for a sum of sparse matrices by combining their row supports and summing their entries.
- Oracle construction: For H equal to a sum of k d-sparse matrices, the goal is to simulate a sparse matrix oracle for H using the individual matrix oracles.The section focuses on the oracle returning nonzero indices; element access is obtained by summing entries.
- Oracle construction: Each row of the summed matrix is formed by merging the ordered nonzero-index lists from the component matrices and removing duplicates.The resulting row remains an ordered list of the nonzero indices of H.
D.1 A lower bound
The paper proves an Ω(dk) quantum-query lower bound for distinguishing two possible sizes of a deduplicated merged list, and transfers it to sparse-matrix oracle queries via majority.
- Lemma 51: Ω(dk) quantum queries are required to distinguish |RH| ≤ d + dk/2 from |RH| ≥ d + dk/2 + 1.RH is the ordered union of k + 1 length-d lists with duplicates removed.
- Proof: The lower bound follows by reducing the MAJ problem on dk Boolean inputs to the merged-list size decision problem.The construction encodes a Boolean matrix Z ∈ {0,1}^{d×k} into the lists.
- Proof: When Zij = 1, Ri[j] is unique, whereas Zij = 0 makes Ri[j] equal R0[j], so |RH| = d + |Z|.Thus the merged-list length records the Hamming weight of Z.
- Corollary 52: A sparse matrix oracle for H inherits the same lower bound because determining the number of nonzero entries in a row decides majority.The oracle exposes enough row support information to distinguish the two cases.
D.2 An upper bound
The classical implementation constructs the sparse oracle incrementally, while the quantum implementation must rebuild the combined row information for each query, costing eO(dk) operations.
- D.2 An upper bound: Classically, the oracle for H is built by inserting each matrix’s row nonzero indices into the accumulated lists.Efficient data structures such as binary heaps support these insertions in polylogarithmic time.
- D.2 An upper bound: The classical construction takes eO(ndk) time when all rows are processed.In the meta-algorithm, only one new matrix arrives per iteration, allowing reuse of the previous oracle.
- D.2 An upper bound: Quantum oracle queries cannot store every row explicitly, so all matrices must be combined anew for each query to OI_H.This avoids the Ω(n) cost of writing every row in each iteration.
- D.2 An upper bound: To obtain the tth nonzero index, the quantum procedure merges all row lists with a heap, performs eO(dk) operations, and then uncomputes the description.The process uses insertions and membership searches before locating the requested index.
E Equivalence of R, r, and ε−1
This section shows that the SDP parameters R, r, and ε^-1 can be traded against one another through reductions, preserving equivalent solutions while changing precision and parameter bounds.
- Scaling R: R can be normalized to 1: solving the rescaled SDP to precision ε/R yields an ε-precision solution to the original problem.The feasible dual region remains unchanged, so r is preserved.
- Scaling r: r can be normalized to 1 by modifying the SDP so that precision ε/r in the transformed problem recovers precision ε for the original.The transformed parameters are R̃ = R and r̃ = 1.
- Scaling ε^-1: Constant precision can replace arbitrary ε through repeated SDP calls that progressively shrink an interval containing OPT.Each reformulation uses a 1-approximation while narrowing the interval around the optimum.
- Complexity: The reductions preserve polynomial efficiency when the solver cost is polynomial in n, m, s, R, and r at constant precision.Under this condition, the resulting cost is polynomial in n, m, s, R, and r/ε.
- Scaling ε^-1: The reformulation for shrinking OPT’s interval creates an equivalent SDP whose optimum lies in [0, 4] and whose trace parameter becomes R̃ = R + 4.Its dual optimum has a scaled form involving 4/(U − L), which determines the transformed r parameter.
- Scaling ε^-1: The interval-shrinking procedure reduces uncertainty geometrically, reaching additive error ε after k = log₂((U0 − L0)/ε) + 1 iterations.The final interval length is at most 2^-k(U0 − L0) ≤ ε.