Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Society for Industrial and Applied Mathematics eBooks

Chapter 8: Quantum algorithms for SDP using mirror descent

Giacomo Nannicini

Published Dec 17, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1137/1.9781611978766.ch8

Related papers

Fast Convex Optimization with Quantum Gradient Methods

Brandon Augustino, Dylan Herman, Enrico Fontana +4 more

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.

arXiv:2503.17356•Mar 21, 2025•8 citations

Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li +3 more

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 $\epsilon$ by using $\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-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 $\rho$, we show we can find in time $\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})$ a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as $\rho$ on the $m$ measurements up to error $\epsilon$. 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.

•Oct 6, 2017•15 citations

Quantum Algorithms for Optimizers

Giacomo Nannicini

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.

arXiv:2408.07086•Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•5 citations

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

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 $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx 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/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ 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.

quant-pharXiv:2609.40302•Oct 1, 2026•0 citations

Slack-variable approach for variational quantum semidefinite programming

Jingxuan Chen, Hanna Westerheim, Zoë Holmes +6 more

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.

Physical Review A•Jun 20, 2025•8 citations

Semidefinite Programming for Quantum Channel Learning

Mikhail Gennadievich Belov, Victor Victorovich Dubov, Vadim Konstantinovich Ivanov +3 more

The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.

cs.LGCross-listedarXiv:2601.12502•Physical review. E•Jan 20, 2026•0 citations
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 mmm constraint matrices of dimension nnn, each of rank at most rrr, 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 ϵ\epsilonϵ by using mlog⁡m⋅poly(log⁡n,r,ϵ−1)\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})m​logm⋅poly(logn,r,ϵ−1) quantum gates. The dependence on nnn 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 mmm and rrr 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 mmm measurements and a supply of copies of an unknown state ρ\rhoρ, we show we can find in time mlog⁡m⋅poly(log⁡n,r,ϵ−1)\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})m​logm⋅poly(logn,r,ϵ−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ\rhoρ on the mmm measurements up to error ϵ\epsilonϵ. 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.
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.
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)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈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 sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.
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.
The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.