# Quantum SDP-Solvers: Better upper and lower bounds

arXiv: https://arxiv.org/abs/1705.01843 · HTML: https://mlsanity.com/paper/1705.01843/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2017.

## Built on by (most cited first, 27 of 27)

- [Recent Advances for Quantum Neural Networks in Generative Learning](https://mlsanity.com/paper/2206.03066/) (2022)
- [On quantum backpropagation, information reuse, and cheating measurement collapse](https://mlsanity.com/paper/2305.13362/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Learning quantum data with the quantum Earth Mover's distance](https://mlsanity.com/paper/2101.03037/) (2021)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Natural gradient and parameter estimation for quantum Boltzmann machines](https://mlsanity.com/paper/2410.24058/) (2024)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Quantum thermodynamics and semi-definite optimization](https://mlsanity.com/paper/2505.04514/) (2025)
- [Fermi-Dirac thermal measurements: A framework for quantum hypothesis testing and semidefinite optimization](https://mlsanity.com/paper/2603.04061/) (2026)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems](https://mlsanity.com/paper/2508.09103/) (2025)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [Predicting adaptively chosen observables in quantum systems](https://mlsanity.com/paper/2410.15501/) (2024)
- [Differentiable Quantum Computing for Large-scale Linear Control](https://mlsanity.com/paper/2411.01391/) (2024)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Unifying quantum measurement constructions via a relative-entropy minimum change principle](https://mlsanity.com/paper/2608.04055/) (2026)

## Abstract (arXiv)

Brand~ao 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≈ n, which is the same as classical.