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:1407.4308

Some upper and lower bounds on PSD-rank

Troy Lee, Zhaohui Wei, Ronald de Wolf

Published Jul 16, 2014• 6 citations
arXivHTMLPDF

Abstract

Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.

DOI
10.48550/arxiv.1407.4308

Related papers

An approximation algorithm for approximation rank

Troy Lee, Adi Shraibman

One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.

arXiv:0809.2093•Sep 11, 2008•1 citation

Compressibility of Positive Semidefinite Factorizations and Quantum Models

Cyril Stark, Aram W. Harrow

We investigate compressibility of the dimension of positive semidefinite matrices, while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions.

arXiv:1412.7437•IEEE Transactions on Information Theory•Mar 4, 2016•15 citations

Compressibility of positive semidefinite factorizations and quantum models

Cyril Stark, Aram W. Harrow

We investigate compressibility of the dimension of positive semidefinite matrices while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•3 citations

Applications of optimization to factorization ranks and quantum information theory

Sander Gribling

Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.

Other publications TiSEM•Aug 2, 2019•1 citation

Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity

Hamza Fawzi, Pablo A. Parrilo

There has been a lot of interest recently in proving lower bounds on the size of linear programs needed to represent a given polytope P. In a breakthrough paper Fiorini et al. [Proceedings of 44th ACM Symposium on Theory of Computing 2012, pages 95-106] showed that any linear programming formulation of maximum-cut must have exponential size. A natural question to ask is whether one can prove such strong lower bounds for semidefinite programming formulations. In this paper we take a step towards this goal and we prove strong lower bounds for a certain class of SDP formulations, namely SDPs over the Cartesian product of fixed-size positive semidefinite cones. In practice this corresponds to semidefinite programs with a block-diagonal structure and where blocks have constant size d. We show that any such extended formulation of the cut polytope must have exponential size (when d is fixed). The result of Fiorini et al. for LP formulations is obtained as a special case when d=1. For blocks of size d=2 the result rules out any small formulations using second-order cone programming. Our study of SDP lifts over Cartesian product of fixed-size positive semidefinite cones is motivated mainly from practical considerations where it is well known that such SDPs can be solved more efficiently than general SDPs. The proof of our lower bound relies on new results about the sparsity pattern of certain matrices with small psd rank, combined with an induction argument inspired from the recent paper by Kaibel and Weltge [arXiv:1307.3543] on the LP extension complexity of the correlation polytope.

arXiv:1311.2571•Nov 11, 2013•5 citations

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

arXiv:2410.20094•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•1 citation
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix MMM as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
We investigate compressibility of the dimension of positive semidefinite matrices, while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions.
We investigate compressibility of the dimension of positive semidefinite matrices while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.
There has been a lot of interest recently in proving lower bounds on the size of linear programs needed to represent a given polytope P. In a breakthrough paper Fiorini et al. [Proceedings of 44th ACM Symposium on Theory of Computing 2012, pages 95-106] showed that any linear programming formulation of maximum-cut must have exponential size. A natural question to ask is whether one can prove such strong lower bounds for semidefinite programming formulations. In this paper we take a step towards this goal and we prove strong lower bounds for a certain class of SDP formulations, namely SDPs over the Cartesian product of fixed-size positive semidefinite cones. In practice this corresponds to semidefinite programs with a block-diagonal structure and where blocks have constant size d. We show that any such extended formulation of the cut polytope must have exponential size (when d is fixed). The result of Fiorini et al. for LP formulations is obtained as a special case when d=1. For blocks of size d=2 the result rules out any small formulations using second-order cone programming. Our study of SDP lifts over Cartesian product of fixed-size positive semidefinite cones is motivated mainly from practical considerations where it is well known that such SDPs can be solved more efficiently than general SDPs. The proof of our lower bound relies on new results about the sparsity pattern of certain matrices with small psd rank, combined with an induction argument inspired from the recent paper by Kaibel and Weltge [arXiv:1307.3543] on the LP extension complexity of the correlation polytope.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽n0\leqslant r < R\leqslant n0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nA, B\in \mathbb{F}^{n\times n}A,B∈Fn×nsatisfy rk(A+B)=r(A+B)=r(A+B)=rversus rk(A+B)=R(A+B)=R(A+B)=R. We show that this problem has commu-nication costΩ(r2log⁡∣F∣)\Omega(r^{2}\log\vert \mathbb{F}\vert)Ω(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability12(1−∣F∣−r/3)\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})21​(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error12(1−∣F∣−Θ(r))\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})21​(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrrrandRRR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceSSS, Bob has a subspaceTTT) and they need to approximate the dimension of the subspaceS+TS+TS+Tgenerated bySSSandTTT(equivalently, approximate the dimension ofS∩TS\cap TS∩T). As an application, we obtain anΩ(n2log⁡∣F∣)/k\Omega(n^{2}\log\vert \mathbb{F}\vert)/kΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkkkpasses that approximates the rank of an input matrixM∈Fn×nM\in \mathbb{F}^{n\times n}M∈Fn×nwithin a factor of2−δ\sqrt{2}-\delta2​−δ, for anyδ>0\delta > 0δ>0. Our result is an exponential improvement inkkkover previous work.