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

Optimization methods & software

A projected gradient method for optimization over density matrices

Douglas Soares Gonçalves, Márcia A. Gomes-Ruggiero, Carlile Lavor

Published Sep 23, 2015• 34 citations
Publisher

Abstract

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.

DOI
10.1080/10556788.2015.1082105

Related papers

Quantum relative entropy regularization for quantum state tomography

Florian Oberender, Thorsten Hohage

The density matrix is a positive semidefinite operator of trace 1 characterizing the state of a quantum system. We consider the inverse problem to reconstruct such density matrices from indirect measurements, also known as quantum state tomography. To solve such inverse problems in high or infinite dimensional settings, we study variational regularization using the quantum relative entropy as penalty functional. Quantum relative entropy is an analog of the well-known maximum entropy functional with compositions of functions replaced by the spectral functional calculus. The main aim of this paper is to establish the regularizing property of this scheme. As a crucial intermediate step, we establish lower semi-compactness of the penalty functional with respect to the weak-$*$-topology. Moreover, we compute the subgradient, proximal operator, and conjugate functional of the quantum relative entropy on finite dimensional spaces. This enables us to apply iterative algorithms from convex optimization to solve the regularized problems numerically. To show the validity and practical value of our results, we apply our theory to the examples of Photon-Induced Near-field Electron Microscopy (PINEM) and to optical homodyne tomography.

arXiv:2603.04922•Mar 5, 2026•0 citations

Projection methods in quantum information science

Yuen-Lam Cheung, Dmitriy Drusvyatskiy, Chi-Kwong Li +2 more

We consider the problem of constructing quantum operations or channels, if they exist, that transform a given set of quantum states $\{ρ_1, \dots, ρ_k\}$ to another such set $\{\hatρ_1, \dots, \hatρ_k\}$. In other words, we must find a {\em completely positive linear map}, if it exists, that maps a given set of density matrices to another given set of density matrices. This problem, in turn, is an instance of a positive semi-definite feasibility problem, but with highly structured constraints. The nature of the constraints makes projection based algorithms very appealing when the number of variables is huge and standard interior point-methods for semi-definite programming are not applicable. We provide emperical evidence to this effect. We moreover present heuristics for finding both high rank and low rank solutions. Our experiments are based on the \emph{method of alternating projections} and the \emph{Douglas-Rachford} reflection method.

arXiv:1407.6604•Jul 24, 2014•1 citation

Interior Point Methods for Structured Quantum Relative Entropy Optimization Problems

Kerry He, James Saunderson, Hamza Fawzi

Abstract Quantum relative entropy optimization refers to a class of convex problems in which a linear functional is minimized over an affine section of the epigraph of the quantum relative entropy function. Recently, the self-concordance of a natural barrier function was proved for this set, and various implementations of interior-point methods have been made available to solve this class of optimization problems. In this paper, we show how common structures arising from applications in quantum information theory can be exploited to improve the efficiency of solving quantum relative entropy optimization problems using interior-point methods. First, we show that the natural barrier function for the epigraph of the quantum relative entropy composed with positive linear operators is self-concordant, even when these linear operators map to singular matrices. Compared to modeling problems using the full quantum relative entropy cone, this allows us to remove redundant log-determinant expressions from the barrier function and reduce the overall barrier parameter. Second, we show how certain slices of the quantum relative entropy cone exhibit useful properties which should be exploited whenever possible to perform certain key steps of interior-point methods more efficiently. We demonstrate how these methods can be applied to applications in quantum information theory, including quantifying quantum key rates, quantum rate-distortion functions, quantum channel capacities, and the ground state energy of Hamiltonians. Our numerical results show that these techniques improve computation times by up to several orders of magnitude, and allow previously intractable problems to be solved.

arXiv:2407.00241•Mathematical Programming Computation•Nov 17, 2025•17 citations

Chapter 8: Quantum algorithms for SDP using mirror descent

Giacomo Nannicini

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.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Maximum Entropy Methods for Quantum State Compatibility Problems

Shi‐Yao Hou, Zipeng Wu, Jinfeng Zeng +4 more

Abstract Inferring a quantum system from incomplete information is a common problem in many aspects of quantum information science and applications, where the principle of maximum entropy (MaxEnt) plays an important role. The quantum state compatibility problem asks whether there exists a density matrix compatible with some given measurement results. Such a compatibility problem can be naturally formulated as a semidefinite programming (SDP), which searches directly for the existence of a . However, for large system dimensions, it is hard to represent directly, since it requires too many parameters. In this work, MaxEnt is applied to solve various quantum state compatibility problems, including the quantum marginal problem. An immediate advantage of the MaxEnt method is that it only needs to represent via a relatively small number of parameters, which is exactly the number of the operators measured. Furthermore, in case of incompatible measurement results, the method will further return a witness that is a supporting hyperplane of the compatible set. The method has a clear geometric meaning and can be computed effectively with hybrid quantum‐classical algorithms.

arXiv:2207.11645•Advanced Quantum Technologies•Oct 11, 2024•2 citations

Rigorous maximum-likelihood estimation for quantum states

K. Aditi, Stephen Becker

Existing quantum state tomography methods are limited in scalability due to their high computation and memory demands, making them impractical for the recovery of large quantum states. In this work, we address these limitations by reformulating the maximum likelihood estimation problem using the Burer--Monteiro factorization, resulting in a nonconvex but low-rank parametrization of the density matrix. We derive a fully unconstrained formulation by analytically eliminating the trace-one and positive-semidefinite constraints, thereby avoiding the need for projection steps during optimization. Furthermore, we determine the Lagrange multiplier associated with the unit-trace constraint a priori, reducing computational overhead. The resulting formulation is amenable to scalable first-order optimization, and we demonstrate its tractability using the limited-memory Broyden-Fletcher-Goldfarb-Shanno method. Importantly, we also propose a low-memory version of the above algorithm to fully recover certain large quantum states with Pauli-based positive-operator-value measurements. Our low-memory algorithm avoids explicitly forming any density matrix, and does not require the density matrix to have a matrix product state or other tensor structure. For a fixed number of measurements and fixed rank, our algorithm requires just $O(d{log}_{2}d)$ complexity per iteration to recover a $d\ifmmode\times\else\texttimes\fi{}d$ density matrix. Additionally, we derive a useful error bound that can be used to give a rigorous termination criterion. We numerically demonstrate that our method is competitive with state-of-the-art algorithms for moderately sized problems, and then demonstrate that our method can solve a 20-qubit problem on a laptop in under 5 hours.

arXiv:2506.16646•Physical Review A•Nov 19, 2025•1 citation
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.
The density matrix is a positive semidefinite operator of trace 1 characterizing the state of a quantum system. We consider the inverse problem to reconstruct such density matrices from indirect measurements, also known as quantum state tomography. To solve such inverse problems in high or infinite dimensional settings, we study variational regularization using the quantum relative entropy as penalty functional. Quantum relative entropy is an analog of the well-known maximum entropy functional with compositions of functions replaced by the spectral functional calculus. The main aim of this paper is to establish the regularizing property of this scheme. As a crucial intermediate step, we establish lower semi-compactness of the penalty functional with respect to the weak-∗*∗-topology. Moreover, we compute the subgradient, proximal operator, and conjugate functional of the quantum relative entropy on finite dimensional spaces. This enables us to apply iterative algorithms from convex optimization to solve the regularized problems numerically. To show the validity and practical value of our results, we apply our theory to the examples of Photon-Induced Near-field Electron Microscopy (PINEM) and to optical homodyne tomography.
We consider the problem of constructing quantum operations or channels, if they exist, that transform a given set of quantum states {ρ1,…,ρk}\{ρ_1, \dots, ρ_k\}{ρ1​,…,ρk​} to another such set {ρ^1,…,ρ^k}\{\hatρ_1, \dots, \hatρ_k\}{ρ^​1​,…,ρ^​k​}. In other words, we must find a {\em completely positive linear map}, if it exists, that maps a given set of density matrices to another given set of density matrices. This problem, in turn, is an instance of a positive semi-definite feasibility problem, but with highly structured constraints. The nature of the constraints makes projection based algorithms very appealing when the number of variables is huge and standard interior point-methods for semi-definite programming are not applicable. We provide emperical evidence to this effect. We moreover present heuristics for finding both high rank and low rank solutions. Our experiments are based on the \emph{method of alternating projections} and the \emph{Douglas-Rachford} reflection method.
Abstract Quantum relative entropy optimization refers to a class of convex problems in which a linear functional is minimized over an affine section of the epigraph of the quantum relative entropy function. Recently, the self-concordance of a natural barrier function was proved for this set, and various implementations of interior-point methods have been made available to solve this class of optimization problems. In this paper, we show how common structures arising from applications in quantum information theory can be exploited to improve the efficiency of solving quantum relative entropy optimization problems using interior-point methods. First, we show that the natural barrier function for the epigraph of the quantum relative entropy composed with positive linear operators is self-concordant, even when these linear operators map to singular matrices. Compared to modeling problems using the full quantum relative entropy cone, this allows us to remove redundant log-determinant expressions from the barrier function and reduce the overall barrier parameter. Second, we show how certain slices of the quantum relative entropy cone exhibit useful properties which should be exploited whenever possible to perform certain key steps of interior-point methods more efficiently. We demonstrate how these methods can be applied to applications in quantum information theory, including quantifying quantum key rates, quantum rate-distortion functions, quantum channel capacities, and the ground state energy of Hamiltonians. Our numerical results show that these techniques improve computation times by up to several orders of magnitude, and allow previously intractable problems to be solved.
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.
Abstract Inferring a quantum system from incomplete information is a common problem in many aspects of quantum information science and applications, where the principle of maximum entropy (MaxEnt) plays an important role. The quantum state compatibility problem asks whether there exists a density matrix compatible with some given measurement results. Such a compatibility problem can be naturally formulated as a semidefinite programming (SDP), which searches directly for the existence of a . However, for large system dimensions, it is hard to represent directly, since it requires too many parameters. In this work, MaxEnt is applied to solve various quantum state compatibility problems, including the quantum marginal problem. An immediate advantage of the MaxEnt method is that it only needs to represent via a relatively small number of parameters, which is exactly the number of the operators measured. Furthermore, in case of incompatible measurement results, the method will further return a witness that is a supporting hyperplane of the compatible set. The method has a clear geometric meaning and can be computed effectively with hybrid quantum‐classical algorithms.
Existing quantum state tomography methods are limited in scalability due to their high computation and memory demands, making them impractical for the recovery of large quantum states. In this work, we address these limitations by reformulating the maximum likelihood estimation problem using the Burer--Monteiro factorization, resulting in a nonconvex but low-rank parametrization of the density matrix. We derive a fully unconstrained formulation by analytically eliminating the trace-one and positive-semidefinite constraints, thereby avoiding the need for projection steps during optimization. Furthermore, we determine the Lagrange multiplier associated with the unit-trace constraint a priori, reducing computational overhead. The resulting formulation is amenable to scalable first-order optimization, and we demonstrate its tractability using the limited-memory Broyden-Fletcher-Goldfarb-Shanno method. Importantly, we also propose a low-memory version of the above algorithm to fully recover certain large quantum states with Pauli-based positive-operator-value measurements. Our low-memory algorithm avoids explicitly forming any density matrix, and does not require the density matrix to have a matrix product state or other tensor structure. For a fixed number of measurements and fixed rank, our algorithm requires just O(dlog2d)O(d{log}_{2}d)O(dlog2​d) complexity per iteration to recover a $d\ifmmode\times\else\texttimes\fi{}d$ density matrix. Additionally, we derive a useful error bound that can be used to give a rigorous termination criterion. We numerically demonstrate that our method is competitive with state-of-the-art algorithms for moderately sized problems, and then demonstrate that our method can solve a 20-qubit problem on a laptop in under 5 hours.