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

Matrix factorizations of correlation matrices and applications

Anupam Prakash, Antonios Varvitsiotis

Published Feb 21, 2017• 1 citation
OpenAlex

Abstract

We introduce a notion of matrix valued Gram decompositions for correlation matrices whose study is motivated by quantum information theory. We show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra and thus, their size is exponential in terms of the rank of the correlation matrix. Using this we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank, recently derived in the literature. This fact also underlies and generalizes Tsirelson's seminal lower bound on the local dimension of a quantum system necessary to generate an extreme quantum correlation.

Related papers

Correlation matrices, Clifford algebras, and completely positive semidefinite rank

Anupam Prakash, Antonios Varvitsiotis

A symmetric n×n matrix X is completely positive semidefinite (cpsd) if there exist d×d positive semidefinite matrices {Pi}i=1n (for some d∈N) such that Xij=Tr(PiPj), for all i,j∈{1,…,n}. The cpsd−rank of a cpsd matrix is the smallest d∈N for which such a representation is possible. It was shown independently in Prakash A, Sikora J, Varvitsiotis A, et al. [Completely positive semidefinite rank. 2016 Apr. arXiv:1604.07199] and Gribling S, de Laat D, Laurent M. [Matrices with high completely positive semidefinite rank. Linear Algebra Appl. 2017 May;513:122–148] that there exist completely positive semidefinite matrices with sub-exponential cpsd-rank. Both proofs were obtained using fundamental results from the quantum information literature as a black-box. In this work we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank. For this, we introduce matrix valued Gram decompositions for correlation matrices and show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra. Lastly, we show that this fact underlies and generalizes Tsirelson's results concerning the structure of quantum representations for extremal quantum correlation matrices.

arXiv:1702.06305•Linear and Multilinear Algebra•Oct 8, 2018•4 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

Some upper and lower bounds on PSD-rank

Troy Lee, Zhaohui Wei, Ronald de Wolf

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.

arXiv:1407.4308•Jul 16, 2014•6 citations

On decomposable correlation matrices

Benjamin Lovitz

A correlation matrix is a positive semidefinite matrix with ones on the diagonal. In this work, we introduce and study r-decomposable correlation matrices: those that can be written as the Schur product of correlation matrices of rank at most r. We find that for all r≥ 2, every (r+1)×(r+1) correlation matrix is r-decomposable, and we construct (2r+1)×(2r+1) correlation matrices that are not r-decomposable. One question this leaves open is whether every 4×4 correlation matrix is 2-decomposable, which we make partial progress towards resolving. Motivations in quantum information are discussed.

arXiv:1812.01449•Linear and Multilinear Algebra•Aug 31, 2019•3 citations

Pairwise completely positive matrices with applications in Quantum Information Theory

Olivia R. MacLean

This thesis introduces a generalization of the set of completely positive matrices that we call “pairwise completely positive” (PCP) matrices. PCP matrix pairs are defined so that one matrix in the pair is necessarily positive semidefinite while the other is necessarily entrywise non-negative. After PCP matrices are defined we explore their basic properties and establish numerous necessary and sufficient conditions that can help test whether or not a pair meets our definition of PCP. We then relate these matrix pairs to the separability of conjugate local diagonal unitary invariant (CLDUI) quantum states. In particular, we show that determining whether or not a pair of matrices is pairwise completely positive is equivalent to determining whether or not a corresponding CLDUI state is separable.

•Apr 8, 2019•0 citations

Systematic derivation of Tsirelson bounds in arbitrary dimensions

Lorenzo Coccia, Matteo Padovan, Giuseppe Vallone

The study of Bell nonlocality and the bounds of quantum correlations, the so-called Tsirelson bounds, is fundamental to quantum information science and the exploration of the limits of quantum theory. While quantum bounds for qubit systems have been extensively characterized, determining tight quantum bounds for correlations attainable with high-dimensional quantum states and measurements remains a significant challenge. In this work, we propose a systematic derivation of bipartite Tsirelson and local bounds written in terms of sum-of-squares decompositions. Using this method, we discover novel bounds and recover established results for maximally entangled states of qubits and qu$d$its.

quant-pharXiv:2606.21626•Jun 22, 2026•0 citations
We introduce a notion of matrix valued Gram decompositions for correlation matrices whose study is motivated by quantum information theory. We show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra and thus, their size is exponential in terms of the rank of the correlation matrix. Using this we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank, recently derived in the literature. This fact also underlies and generalizes Tsirelson's seminal lower bound on the local dimension of a quantum system necessary to generate an extreme quantum correlation.
A symmetric n×n matrix X is completely positive semidefinite (cpsd) if there exist d×d positive semidefinite matrices {Pi}i=1n (for some d∈N) such that Xij=Tr(PiPj), for all i,j∈{1,…,n}. The cpsd−rank of a cpsd matrix is the smallest d∈N for which such a representation is possible. It was shown independently in Prakash A, Sikora J, Varvitsiotis A, et al. [Completely positive semidefinite rank. 2016 Apr. arXiv:1604.07199] and Gribling S, de Laat D, Laurent M. [Matrices with high completely positive semidefinite rank. Linear Algebra Appl. 2017 May;513:122–148] that there exist completely positive semidefinite matrices with sub-exponential cpsd-rank. Both proofs were obtained using fundamental results from the quantum information literature as a black-box. In this work we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank. For this, we introduce matrix valued Gram decompositions for correlation matrices and show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra. Lastly, we show that this fact underlies and generalizes Tsirelson's results concerning the structure of quantum representations for extremal quantum correlation matrices.
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.
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.
A correlation matrix is a positive semidefinite matrix with ones on the diagonal. In this work, we introduce and study r-decomposable correlation matrices: those that can be written as the Schur product of correlation matrices of rank at most r. We find that for all r≥ 2, every (r+1)×(r+1) correlation matrix is r-decomposable, and we construct (2r+1)×(2r+1) correlation matrices that are not r-decomposable. One question this leaves open is whether every 4×4 correlation matrix is 2-decomposable, which we make partial progress towards resolving. Motivations in quantum information are discussed.
This thesis introduces a generalization of the set of completely positive matrices that we call “pairwise completely positive” (PCP) matrices. PCP matrix pairs are defined so that one matrix in the pair is necessarily positive semidefinite while the other is necessarily entrywise non-negative. After PCP matrices are defined we explore their basic properties and establish numerous necessary and sufficient conditions that can help test whether or not a pair meets our definition of PCP. We then relate these matrix pairs to the separability of conjugate local diagonal unitary invariant (CLDUI) quantum states. In particular, we show that determining whether or not a pair of matrices is pairwise completely positive is equivalent to determining whether or not a corresponding CLDUI state is separable.
The study of Bell nonlocality and the bounds of quantum correlations, the so-called Tsirelson bounds, is fundamental to quantum information science and the exploration of the limits of quantum theory. While quantum bounds for qubit systems have been extensively characterized, determining tight quantum bounds for correlations attainable with high-dimensional quantum states and measurements remains a significant challenge. In this work, we propose a systematic derivation of bipartite Tsirelson and local bounds written in terms of sum-of-squares decompositions. Using this method, we discover novel bounds and recover established results for maximally entangled states of qubits and qudddits.