Quantum SDP-Solvers: Better upper and lower bounds

Abstract

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.

arXiv commentv4: 69 pages, small corrections and clarifications. This version will appear in Quantum

References in corpus (19)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum Algorithms Revisited
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Tight bounds on quantum searching
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Preparing ground states of quantum many-body systems on a quantum computer
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Quantum query complexity of some graph problems
• Improvements in Quantum SDP-Solving with Applications
• Quantum algorithms and lower bounds for convex optimization
• Convex optimization using quantum oracles
• Quantum Adversary (Upper) Bound

Cited by in corpus (53)

• Quantum Computing for Finance: State of the Art and Future Prospects
• Quantum computing for finance
• Warm-starting quantum optimization
• Challenges and Opportunities in Quantum Optimization
• Sample-efficient learning of quantum many-body systems
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Improved quantum algorithms for linear and nonlinear differential equations
• A randomized quantum algorithm for statistical phase estimation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Learning quantum data with the quantum Earth Mover's distance
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Quantum enhancements for deep reinforcement learning in large spaces
• Thermal State Preparation via Rounding Promises
• Predicting Gibbs-State Expectation Values with Pure Thermal Shadows
• On the complexity of quantum partition functions
• Quantum many-body systems in thermal equilibrium
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Stable factorization for phase factors of quantum signal processing
• Quantum Interior Point Methods for Semidefinite Optimization
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Continuous-variable assisted thermal quantum simulation
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum-accelerated constraint programming
• Variational Quantum Algorithms for Semidefinite Programming
• Quantum algorithms for escaping from saddle points
• Quantum algorithms for hedging and the learning of Ising models
• Decay of quantum conditional mutual information for purely generated finitely correlated states
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Quantum algorithms for matrix geometric means
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Mixed-Integer Programming Using a Bosonic Quantum Computer
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Computable entanglement cost under positive partial transpose operations
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Sample Complexity of Black Box Work Extraction
• Topological obstructions to quantum computation with unitary oracles
• Quantum Lower Bounds by Sample-to-Query Lifting
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• Beating the natural Grover bound for low-energy estimation and state preparation
• Quantum Algorithm for Online Convex Optimization
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems
• Natural gradient and parameter estimation for quantum Boltzmann machines
• Block Encoding of Sparse Matrices via Coherent Permutation
• Quantum Data Structure for Range Minimum Query