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

Advances in chemical physics

The Lower Bound Method for Density Matrices and Semidefinite Programming

Robert Erdahl

Published Mar 9, 2007• 12 citations
Publisher
DOI
10.1002/9780470106600.ch4

Related papers

Variational density matrix optimization using semidefinite programming

Brecht Verstichel, Helen van Aggelen, Dimitri Van Neck +2 more

arXiv:1006.3721•Computer Physics Communications•Dec 30, 2010•5 citations

Quantum Speed-ups for Semidefinite Programming

Fernando G. S. L. Brandão, Krysta M. Svore

We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time $n^{\frac{1}{2}} m^{\frac{1}{2}} s^2 \text{poly}(\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 $Ω(n^{\frac{1}{2}}+m^{\frac{1}{2}})$ 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.

arXiv:1609.05537•Sep 18, 2016•94 citations

Two algorithms for the lower bound method of reduced density matrix theory

Robert Erdahl

Reports on Mathematical Physics•Apr 1, 1979•79 citations

Jointly Constrained Semidefinite Bilinear Programming With an Application to Dobrushin Curves

Stefan Huber, Robert König, Marco Tomamichel

We propose a branch-and-bound algorithm for minimizing a bilinear functional of the form f (X, Y) = tr((X ⊗ Y) Q) +tr(AX) +tr(BY), of pairs of Hermitian matrices (X, Y) restricted by joint semidefinite programming constraints. The functional is parametrized by self-adjoint matrices Q, A and B. This problem generalizes that of a bilinear program, where X and Y belong to polyhedra. The algorithm converges to a global optimum and yields upper and lower bounds on its value in every step. Various problems in quantum information theory can be expressed in this form. As an example application, we compute Dobrushin curves of quantum channels, giving upper bounds on classical coding with energy constraints.

arXiv:1808.03182•IEEE Transactions on Information Theory•Sep 5, 2019•9 citations

Semidefinite programming and its applications to approximation algorithms

Thomas Hofmeister, Martin Hühne

Lecture notes in computer science•Jan 1, 1998•1 citation

Quantum Speed-Ups for Solving Semidefinite Programs

Fernando G. S. L. Brandão, Krysta M. Svore

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•159 citations
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n12m12s2poly(log⁡(n),log⁡(m),R,r,1/δ)n^{\frac{1}{2}} m^{\frac{1}{2}} s^2 \text{poly}(\log(n), \log(m), R, r, 1/δ)n21​m21​s2poly(log(n),log(m),R,r,1/δ), with nnn and sss the dimension and row-sparsity of the input matrices, respectively, mmm the number of constraints, δδδ the accuracy of the solution, and R,rR, rR,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 nnn and mmm. We prove the algorithm cannot be substantially improved (in terms of nnn and mmm) giving a Ω(n12+m12)Ω(n^{\frac{1}{2}}+m^{\frac{1}{2}})Ω(n21​+m21​) quantum lower bound for solving semidefinite programs with constant s,R,rs, R, rs,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 propose a branch-and-bound algorithm for minimizing a bilinear functional of the form f (X, Y) = tr((X ⊗ Y) Q) +tr(AX) +tr(BY), of pairs of Hermitian matrices (X, Y) restricted by joint semidefinite programming constraints. The functional is parametrized by self-adjoint matrices Q, A and B. This problem generalizes that of a bilinear program, where X and Y belong to polyhedra. The algorithm converges to a global optimum and yields upper and lower bounds on its value in every step. Various problems in quantum information theory can be expressed in this form. As an example application, we compute Dobrushin curves of quantum channels, giving upper bounds on classical coding with energy constraints.
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.