Mirror descent is a powerful framework to solve nonlinear optimization problems by taking advantage of the geometry of the space in which the problem lives [155]. Mirror descent relies on the same concepts as projected (sub)gradient descent, with the significant variation that the descent takes place in a “mirror” space, which is the vector space dual to the original space. When dealing with optimization problems over the cone of positive semidefinite matrices, it is possible to apply mirror descent using the quantum relative entropy as the mirror map, resulting in an iterative optimization scheme for semidefinite programming that simultaneously operates in two spaces: the space of primal iterates, which are positive semidefinite matrices expressed as matrix exponentials, and the space of (vector) dual iterates (i.e., the mirror space), which are the matrix logarithms of the primal iterates. This choice of the mirror map is natural in the context of quantum algorithms that want to take advantage of the ability of quantum computers to efficiently compute Gibbs states, i.e., matrix exponentials of a certain kind; see Sect. 7.2.4 and in particular Prop. 7.38. Since the mirror descent framework has proven very fruitful for the development of quantum optimization algorithms, in this chapter we discuss its main components, with an emphasis on those that (almost) directly lead to quantum algorithms with an expectation of quantum advantage of some type.
Mirror descent is a powerful framework to solve nonlinear optimization problems by taking advantage of the geometry of the space in which the problem lives [155]. Mirror descent relies on the same concepts as projected (sub)gradient descent, with the significant variation that the descent takes place in a “mirror” space, which is the vector space dual to the original space. When dealing with optimization problems over the cone of positive semidefinite matrices, it is possible to apply mirror descent using the quantum relative entropy as the mirror map, resulting in an iterative optimization scheme for semidefinite programming that simultaneously operates in two spaces: the space of primal iterates, which are positive semidefinite matrices expressed as matrix exponentials, and the space of (vector) dual iterates (i.e., the mirror space), which are the matrix logarithms of the primal iterates. This choice of the mirror map is natural in the context of quantum algorithms that want to take advantage of the ability of quantum computers to efficiently compute Gibbs states, i.e., matrix exponentials of a certain kind; see Sect. 7.2.4 and in particular Prop. 7.38. Since the mirror descent framework has proven very fruitful for the development of quantum optimization algorithms, in this chapter we discuss its main components, with an emphasis on those that (almost) directly lead to quantum algorithms with an expectation of quantum advantage of some type.
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.
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.
Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms. Particular classes of optimization problems including semidefinite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semidefinite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems. We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by (1) introducing slack variables to transform inequality constraints to equality constraints, (2) transforming a constrained optimization to an unconstrained one via the penalty method, and (3) replacing the optimizations over all possible nonnegative variables by optimizations over parameterized quantum states and parameterized probability distributions. Under the assumption that the SDP and LP inputs are efficiently measurable observables, it follows that all terms in the resulting objective functions are efficiently estimable by either a quantum computer in the SDP case or a quantum or probabilistic computer in the LP case. Furthermore, by making use of SDP and LP duality theory, we prove that these methods provide a theoretical guarantee that, if one could find global optima of the objective functions, then the resulting values sandwich the true optimal values from both above and below. Finally, we showcase the QSlack and CSlack methods on a variety of example optimization problems and discuss details of our implementation, as well as the resulting performance. We find that our implementations of both the primal and dual for these problems approach the ground truth, typically achieving errors of the order 10-2.
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.
This is a set of lecture notes for a graduate-level course on quantum algorithms, with an emphasis on quantum optimization algorithms. It is developed for applied mathematicians and engineers, and requires no previous background in quantum mechanics. The main topics of this course, in addition to a rigorous introduction to the computational model, are: input/output models, quantum search, the quantum gradient algorithm, matrix manipulation algorithms, the mirror descent framework for semidefinite optimization (including the matrix multiplicative weights update algorithm), adiabatic optimization. This is a preprint for personal use only. Please refer to the printed version of the material.
An ensemble of quantum states can be described by a Hermitian, positive semidefinite and unit trace matrix called density matrix. Thus, the study of methods for optimizing a certain function (energy, entropy) over the set of density matrices has a direct application to important problems in quantum information and computation. We propose a projected gradient method for solving such problems. By exploiting the geometry of the feasible set, which is the intersection of the cone of Hermitian positive semidefinite matrices with the hyperplane defined by the unit trace constraint, we describe an efficient procedure to compute the projection onto this set using the Frobenius norm. Some important applications, such as quantum state tomography, are described and numerical experiments illustrate the effectiveness of the method when compared to previous methods based on fixed-point iterations or semidefinite programming.