© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1905.08322 · SIAM Journal on Scientific Computing

Semidefinite Relaxation of Multimarginal Optimal Transport for Strictly Correlated Electrons in Second Quantization

Yuehaw Khoo, Lin Lin, Michael Lindsey, Lexing Ying B

Published Jan 1, 2020• 13 citations

Abstract

We consider the strictly correlated electron (SCE) limit of the fermionic quantum many-body problem in the second-quantized formalism. This limit gives rise to a multimarginal optimal transport (MMOT) problem. Here the marginal state space for our MMOT problem is the binary set 0,1, and the number of marginals is the number L of sites in the model. The costs of storing and computing the exact solution of the MMOT problem both scale exponentially with respect to L. We propose an efficient convex relaxation to the MMOT which can be solved by semidefinite programming (SDP). In particular, the semidefinite constraint is only of size 2 L X 2 L. We further prove that the SDP has dual attainment, in spite of the lack of Slater's condition (i.e., the primal SDP does not have any strictly feasible point). In the context of determining the lowest energy of electrons via density functional theory, such dual attainment implies the existence of an effective potential needed to solve a nonlinear Schrödinger equation via self-consistent field iteration. We demonstrate the effectiveness of our methods on computing the ground state energy of spinless and spinful Hubbard-type models. Numerical results indicate that our SDP formulation yields comparable results when using the unrelaxed MMOT formulation. We also describe how our relaxation methods generalize to arbitrary MMOT problems with pairwise cost functions.

DOI: 10.1137/20m1310977

Related papers

Solving Condensed-Matter Ground-State Problems by Semidefinite Relaxations

Thomas Barthel, R. Hübener

We present a generic approach to the condensed-matter ground-state problem which is complementary to variational techniques and works directly in the thermodynamic limit. Relaxing the ground-state problem, we obtain semidefinite programs (SDP). These can be solved efficiently, yielding strict lower bounds to the ground-state energy and approximations to the few-particle Green's functions. As the method is applicable for all particle statistics, it represents, in particular, a novel route for the study of strongly correlated fermionic and frustrated spin systems in D>1 spatial dimensions. It is demonstrated for the XXZ model and the Hubbard model of spinless fermions. The results are compared against exact solutions, quantum Monte Carlo calculations, and Anderson bounds, showing the competitiveness of the SDP method.

arXiv:1106.4966•Physical Review Letters•May 17, 2012•42 citations

Variational Embedding for Quantum Many‐Body Problems

Lin Lin, Michael Lindsey

Abstract Quantum embedding theories are powerful tools for approximately solving large‐scale, strongly correlated quantum many‐body problems. The main idea of quantum embedding is to glue together a highly accurate quantum theory at the local scale and a less accurate quantum theory at the global scale. We introduce the first quantum embedding theory that is also variational, in that it is guaranteed to provide a one‐sided bound for the exact ground‐state energy. Our method, which we call the variational embedding method, provides a lower bound for this quantity. The method relaxes the representability conditions for quantum marginals to a set of linear and semidefinite constraints that operate at both local and global scales, resulting in a semidefinite program (SDP) to be solved numerically. The accuracy of the method can be systematically improved. The method is versatile and can be applied, in particular, to quantum many‐body problems for both quantum spin systems and fermionic systems, such as those arising from electronic structure calculations. We describe how the proper notion of quantum marginal, sufficiently general to accommodate both of these settings, should be phrased in terms of certain algebras of operators. We also investigate the duality theory for our SDPs, which offers valuable perspective on our method as an embedding theory. As a byproduct of this investigation, we describe a formulation for efficiently implementing the variational embedding method via a partial dualization procedure and the solution of quantum analogues of the Kantorovich problem from optimal transport theory. © 2021 Wiley Periodicals LLC.

arXiv:1910.00560•Communications on Pure and Applied Mathematics•Feb 27, 2021•10 citations

Solving cluster moment relaxation with hierarchical matrix

Yi Wang, Huang, Rizheng, Yuehaw Khoo

Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy.

arXiv:2408.00235•Aug 1, 2024•0 citations

Computation of the smooth max-mutual information via semidefinite programming

Christopher Popp, Tobias C. Sutter, Beatrix C. Hiesmayr

Abstract We present an iterative algorithm based on semidefinite programming (SDP) for computing the quantum smooth max-mutual information $$I^\varepsilon _{\max }(\rho _{AB})$$ I max ε ( ρ AB ) of bipartite quantum states in any dimension. The algorithm is accurate if a rank condition for marginal states within the smoothing environment is satisfied and provides an upper bound otherwise. Central to our method is a novel SDP, for which we establish primal and dual formulations and prove strong duality. With the direct application of bounding the one-shot distillable key of a quantum state, this contribution extends SDP-based techniques in quantum information theory. Thereby it improves the capabilities to compute or estimate information measures with application to various quantum information processing tasks.

arXiv:2509.07743•Quantum Information Processing•Feb 25, 2026•1 citation

Large-Scale Semidefinite Programming for Many-Electron Quantum Mechanics

David A. Mazziotti

The energy of a many-electron quantum system can be approximated by a constrained optimization of the two-electron reduced density matrix (2-RDM) that is solvable in polynomial time by semidefinite programming (SDP). Here we develop a SDP method for computing strongly correlated 2-RDMs that is 10-20 times faster than previous methods [D. A. Mazziotti, Phys. Rev. Lett. 93, 213001 (2004)]. We illustrate with (i) the dissociation of N(2) and (ii) the metal-to-insulator transition of H(50). For H(50) the SDP problem has 9.4×10(6) variables. This advance also expands the feasibility of large-scale applications in quantum information, control, statistics, and economics.

Physical Review Letters•Feb 23, 2011•151 citations

Quantum Semidefinite Programming with Thermal Pure Quantum States

Oscar Watts, Yuta Kikuchi, Luuk Coopmans

Semidefinite programs (SDPs) are a particular class of convex optimization problems with applications in combinatorial optimization, operational research, and quantum information science. Seminal work by Brandão and Svore shows that a ``quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms by using a quantum computer as a Gibbs-state sampler. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states. While our methodology incurs an additional problem-dependent error, which decreases as the problem size grows, it avoids the preparation of purified Gibbs states, potentially saving a number of ancilla qubits. In addition, we identify a spectral condition which, when met, reduces the resources further, and shifts the computational bottleneck from Gibbs state preparation to ground-state energy estimation. With classical state-vector simulations, we verify the efficiency of the algorithm for particular cases of Hamiltonian learning problems. We are able to obtain approximate solutions for two-dimensional spinless Hubbard and one-dimensional Heisenberg XXZ models for sizes of up to $N=2^{10}$ variables. For the Hubbard model, we provide an estimate of the resource requirements of our algorithm, including the number of Toffoli gates and the number of qubits.

arXiv:2310.07774•Oct 11, 2023•0 citations

We consider the strictly correlated electron (SCE) limit of the fermionic quantum many-body problem in the second-quantized formalism. This limit gives rise to a multimarginal optimal transport (MMOT) problem. Here the marginal state space for our MMOT problem is the binary set 0,1, and the number of marginals is the number L of sites in the model. The costs of storing and computing the exact solution of the MMOT problem both scale exponentially with respect to L. We propose an efficient convex relaxation to the MMOT which can be solved by semidefinite programming (SDP). In particular, the semidefinite constraint is only of size 2 L X 2 L. We further prove that the SDP has dual attainment, in spite of the lack of Slater's condition (i.e., the primal SDP does not have any strictly feasible point). In the context of determining the lowest energy of electrons via density functional theory, such dual attainment implies the existence of an effective potential needed to solve a nonlinear Schrödinger equation via self-consistent field iteration. We demonstrate the effectiveness of our methods on computing the ground state energy of spinless and spinful Hubbard-type models. Numerical results indicate that our SDP formulation yields comparable results when using the unrelaxed MMOT formulation. We also describe how our relaxation methods generalize to arbitrary MMOT problems with pairwise cost functions.

We present a generic approach to the condensed-matter ground-state problem which is complementary to variational techniques and works directly in the thermodynamic limit. Relaxing the ground-state problem, we obtain semidefinite programs (SDP). These can be solved efficiently, yielding strict lower bounds to the ground-state energy and approximations to the few-particle Green's functions. As the method is applicable for all particle statistics, it represents, in particular, a novel route for the study of strongly correlated fermionic and frustrated spin systems in D>1 spatial dimensions. It is demonstrated for the XXZ model and the Hubbard model of spinless fermions. The results are compared against exact solutions, quantum Monte Carlo calculations, and Anderson bounds, showing the competitiveness of the SDP method.

Abstract Quantum embedding theories are powerful tools for approximately solving large‐scale, strongly correlated quantum many‐body problems. The main idea of quantum embedding is to glue together a highly accurate quantum theory at the local scale and a less accurate quantum theory at the global scale. We introduce the first quantum embedding theory that is also variational, in that it is guaranteed to provide a one‐sided bound for the exact ground‐state energy. Our method, which we call the variational embedding method, provides a lower bound for this quantity. The method relaxes the representability conditions for quantum marginals to a set of linear and semidefinite constraints that operate at both local and global scales, resulting in a semidefinite program (SDP) to be solved numerically. The accuracy of the method can be systematically improved. The method is versatile and can be applied, in particular, to quantum many‐body problems for both quantum spin systems and fermionic systems, such as those arising from electronic structure calculations. We describe how the proper notion of quantum marginal, sufficiently general to accommodate both of these settings, should be phrased in terms of certain algebras of operators. We also investigate the duality theory for our SDPs, which offers valuable perspective on our method as an embedding theory. As a byproduct of this investigation, we describe a formulation for efficiently implementing the variational embedding method via a partial dualization procedure and the solution of quantum analogues of the Kantorovich problem from optimal transport theory. © 2021 Wiley Periodicals LLC.

Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy.

Abstract We present an iterative algorithm based on semidefinite programming (SDP) for computing the quantum smooth max-mutual information

I^\varepsilon _{\max }(\rho _{AB})

I max ε ( ρ AB ) of bipartite quantum states in any dimension. The algorithm is accurate if a rank condition for marginal states within the smoothing environment is satisfied and provides an upper bound otherwise. Central to our method is a novel SDP, for which we establish primal and dual formulations and prove strong duality. With the direct application of bounding the one-shot distillable key of a quantum state, this contribution extends SDP-based techniques in quantum information theory. Thereby it improves the capabilities to compute or estimate information measures with application to various quantum information processing tasks.

The energy of a many-electron quantum system can be approximated by a constrained optimization of the two-electron reduced density matrix (2-RDM) that is solvable in polynomial time by semidefinite programming (SDP). Here we develop a SDP method for computing strongly correlated 2-RDMs that is 10-20 times faster than previous methods [D. A. Mazziotti, Phys. Rev. Lett. 93, 213001 (2004)]. We illustrate with (i) the dissociation of N(2) and (ii) the metal-to-insulator transition of H(50). For H(50) the SDP problem has 9.4×10(6) variables. This advance also expands the feasibility of large-scale applications in quantum information, control, statistics, and economics.

Semidefinite programs (SDPs) are a particular class of convex optimization problems with applications in combinatorial optimization, operational research, and quantum information science. Seminal work by Brandão and Svore shows that a ``quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms by using a quantum computer as a Gibbs-state sampler. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states. While our methodology incurs an additional problem-dependent error, which decreases as the problem size grows, it avoids the preparation of purified Gibbs states, potentially saving a number of ancilla qubits. In addition, we identify a spectral condition which, when met, reduces the resources further, and shifts the computational bottleneck from Gibbs state preparation to ground-state energy estimation. With classical state-vector simulations, we verify the efficiency of the algorithm for particular cases of Hamiltonian learning problems. We are able to obtain approximate solutions for two-dimensional spinless Hubbard and one-dimensional Heisenberg XXZ models for sizes of up to

N=2^{10}

variables. For the Hubbard model, we provide an estimate of the resource requirements of our algorithm, including the number of Toffoli gates and the number of qubits.