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

arXiv:1506.08810 · SIAM Journal on Optimization

Quantum Bilinear Optimization

Mario Berta, Omar Fawzi, Volkher B. Scholz

Published Jan 1, 2016• 31 citations
arXivHTMLPDF

Abstract

We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.

DOI
10.1137/15m1037731

Related papers

Semidefinite programming hierarchies for constrained bilinear optimization

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

Abstract We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $${\mathrm {Tr}}\big [H(D\otimes E)\big ]$$ Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from $$O(d^{k/2})$$ O ( d k / 2 ) to $${\mathrm {poly}}(d,k)$$ poly ( d , k ) , where d denotes local dimension and k the number of copies.

arXiv:1810.12197•Mathematical Programming•Apr 15, 2021•32 citations

Semidefinite programming hierarchies for quantum error correction

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies.

•Jan 23, 2019•5 citations

Semidefinite Programs for Randomness Extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz

Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.

Leibniz international proceedings in informatics•Jan 1, 2015•2 citations

Characterizing finite-dimensional quantum behavior

Miguel Navascués, Adrien Feix, Mateus Araújo +1 more

We study and extend the semidefinite programming (SDP) hierarchies introduced in Navascu\'es and V\'ertesi [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of the statistical correlations arising from finite-dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device-independent and semi-device-independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive a number of dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.

arXiv:1507.07521•Physical Review A•Oct 21, 2015•46 citations

State polynomial optimization for nonlinear Bell inequalities

Victor Magron

This talk focuses on optimization over state polynomials, i.e., polynomials in noncommuting variables and formal states of their products.An archimedean Positivstellensatz in the spirit of Putinar and Helton-McCullough is presented leading to a hierarchy of semidefinite relaxations converging monotonically to the optimum of a state polynomial subject to state constraints. This hierarchy can be seen as a state analog of the Lasserre hierarchy for optimization of polynomials, and the Navascués-Pironio-Acín scheme for optimization of noncommutative polynomials.The motivation behind this theory arises from the study of correlations in quantum networks. Determining the maximal quantum violation of a polynomial Bell inequality for an arbitrary network is reformulated as a state polynomial optimization problem. Several examples of quadratic Bell inequalities in the bipartite scenario are analyzed.To reduce the size of the semidefinite programs, sparsity, sign symmetry and conditional expectation of the observables' group structure are exploited.This is based on the joint work with Igor Klep, Jurij Volčič, and Jie Wang.

•Jul 29, 2024•0 citations

Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables

S. Pironio, Miguel Navascués, A. Acín

We consider optimization problems with polynomial inequality constraints in noncommuting variables. These noncommuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.

arXiv:0903.4368•SIAM Journal on Optimization•Jan 1, 2010•194 citations
We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
Abstract We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D⊗E)]{\mathrm {Tr}}\big [H(D\otimes E)\big ]Tr[H(D⊗E)] Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2)O(d^{k/2})O(dk/2) O ( d k / 2 ) to poly(d,k){\mathrm {poly}}(d,k)poly(d,k) poly ( d , k ) , where d denotes local dimension and k the number of copies.
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[M(X⊗Y)]\mathrm{Tr}\big[M(X\otimes Y)\big]Tr[M(X⊗Y)], maximized with respect to semidefinite constraints on XXX and YYY. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2)O(d^{k/2})O(dk/2) to poly(d,k)\mathrm{poly}(d,k)poly(d,k), where ddd denotes local dimension and kkk the number of copies.
Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.
We study and extend the semidefinite programming (SDP) hierarchies introduced in Navascu\'es and V\'ertesi [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of the statistical correlations arising from finite-dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device-independent and semi-device-independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive a number of dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.
This talk focuses on optimization over state polynomials, i.e., polynomials in noncommuting variables and formal states of their products.An archimedean Positivstellensatz in the spirit of Putinar and Helton-McCullough is presented leading to a hierarchy of semidefinite relaxations converging monotonically to the optimum of a state polynomial subject to state constraints. This hierarchy can be seen as a state analog of the Lasserre hierarchy for optimization of polynomials, and the Navascués-Pironio-Acín scheme for optimization of noncommutative polynomials.The motivation behind this theory arises from the study of correlations in quantum networks. Determining the maximal quantum violation of a polynomial Bell inequality for an arbitrary network is reformulated as a state polynomial optimization problem. Several examples of quadratic Bell inequalities in the bipartite scenario are analyzed.To reduce the size of the semidefinite programs, sparsity, sign symmetry and conditional expectation of the observables' group structure are exploited.This is based on the joint work with Igor Klep, Jurij Volčič, and Jie Wang.
We consider optimization problems with polynomial inequality constraints in noncommuting variables. These noncommuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.