Brandao and Svore 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 is approximately n, which is the same as classical.
Brandao and Svore 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 is approximately n, which is the same as classical.
Brandão and Svore \cite{brandao2016QSDPSpeedup} 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 optimization 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.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n1/2m1/2s2poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r upper bounds on the size of the optimal primal and dual solutions, respectively. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n1/2+ m2) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O(n+m) dependence on matrix dimension n and constraint number m. Compared with the O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs.
Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let s denote the the input matrix sparsity and γ:=Rr/ε capture dependence on the primal (R) and dual (r) radii as well as target accuracy (ε). When γ2≤min{m,n/s}, our solver runs in time O(nsγ4.5+msγ2). For γ=O(1), this is O((n+m)s) and sublinear in the O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to m and n, up to logarithmic factors. This implies that, with respect to dimensions m and n, there is no super-quadratic quantum advantage for generic sparse SDP solving.
Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore in 2016, rapid developments has been made on quantum optimization algorithms. Recently Brandão et al. improved the quantum SDP-solver in the so-called quantum state input model, where the input matrices of the SDP are given as purified mixed states. They also gave the first non-trivial application of quantum SDP-solving by obtaining a more efficient algorithm for the problem of shadow tomography (proposed by Aaronson in 2017). In this paper we improve on all previous quantum SDP-solvers. Mainly we construct better Gibbs-samplers for both input models, which directly gives better bounds for SDP-solving. For an SDP with m constraints involving n×n matrices, our improvements yield an O((m+nγ)sγ4) upper bound on SDP-solving in the sparse matrix input model and an O((m+B2.5γ3.5)Bγ4) upper bound in the quantum state input model. We then apply these results to the problem of shadow tomography to simultaneously improve the best known upper bounds on sample complexity due to Aaronson and complexity due Brandao et al. Furthermore, we apply our quantum SDP-solvers to the problems of quantum state discrimination and E-optimal design. In both cases we beat the classical lower bound in terms of some parameters, at the expense of heavy dependence on some other parameters. Finally we prove two lowers bounds for solving SDPs using quantum algorithms: (1) $\tildeΩ(\sqrt{m}B/\eps)$ in the quantum state input model, and (2) $\tildeΩ(\sqrt{m}α/\eps)$ in the quantum operator input model. These lower bounds show that the m factor and the polynomial dependence on the parameters B,α, and $1/\eps$ are necessary.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n21m21s2poly(log(n),log(m),R,r,1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R,r a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n21+m21) quantum lower bound for solving semidefinite programs with constant s,R,r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ϵ by using mlogm⋅poly(logn,r,ϵ−1) quantum gates. The dependence on n provides an exponential improvement over the work of Brand\~ao and Svore and the work of van Apeldoorn et al., and demonstrates an exponential quantum speed-up when m and r are small.
We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ, we show we can find in time mlogm⋅poly(logn,r,ϵ−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ϵ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle.
As in previous work, we obtain our algorithm by quantizing classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest.