Completely positive semidefinite rank

An \(n\times n\) matrix X is called completely positive semidefinite (cpsd) if there exist \(d\times d\) Hermitian positive semidefinite matrices \(\{P_i\}_{i=1}^n\) (for some \(d\ge 1\)) such that \(X_{ij}= \mathrm {Tr}(P_iP_j),\) for all \(i,j \in \{ 1, \ldots , n \}\). The cpsd-rank of a cpsd matrix is the smallest \(d\ge 1\) for which such a representation is possible. In this work we initiate the study of the cpsd-rank which we motivate in two ways. First, the cpsd-rank is a natural non-commutative analogue of the completely positive rank of a completely positive matrix. Second, we show that the cpsd-rank is physically motivated as it can be used to upper and lower bound the size of a quantum system needed to generate a quantum behavior. In this work we present several properties of the cpsd-rank. Unlike the completely positive rank which is at most quadratic in the size of the matrix, no general upper bound is known on the cpsd-rank of a cpsd matrix. In fact, we show that the cpsd-rank can be sub-exponential in terms of the size. Specifically, for any \(n\ge 1,\) we construct a cpsd matrix of size 2n whose cpsd-rank is \(2^{\varOmega (\sqrt{n})}\). Our construction is based on Gram matrices of Lorentz cone vectors, which we show are cpsd. The proof relies crucially on the connection between the cpsd-rank and quantum behaviors. In particular, we use a known lower bound on the size of matrix representations of extremal quantum correlations which we apply to high-rank extreme points of the n-dimensional elliptope. Lastly, we study cpsd-graphs, i.e., graphs G with the property that every doubly nonnegative matrix whose support is given by G is cpsd. We show that a graph is cpsd if and only if it has no odd cycle of length at least 5 as a subgraph. This coincides with the characterization of cp-graphs.

1. To be precise, each time this is repeated each party should receive a new copy of the box.

We thank Hamza Fawzi for bringing to our attention reference [13]. A.V., A.P., and Z.W. are supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13. J.S. is supported in part by NSERC Canada. Research at the Centre for Quantum Technologies is partially funded by the Singapore Ministry of Education and the National Research Foundation, also through the Tier 3 Grant “Random numbers from quantum processes,” (MOE2012-T3-1-009).

Authors and Affiliations

1. Nanyang Technological University, Singapore, Singapore

   Anupam Prakash, Antonios Varvitsiotis & Zhaohui Wei

2. Centre for Quantum Technologies, National University of Singapore, Singapore, Singapore

   Anupam Prakash, Jamie Sikora, Antonios Varvitsiotis & Zhaohui Wei

3. MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, Singapore, Singapore

   Jamie Sikora

Corresponding author

Correspondence to Antonios Varvitsiotis.

A Supplementary Material: Clifford algebras

Our goal in this section is to briefly introduce Clifford algebras. For additional details the reader is referred to [14, Chapter 6]. Consider a real vector space V equipped with a bilinear form \(\beta : V\times V\rightarrow \mathbb {R}\) such that (i) \(\beta (x,y)=\beta (y,x), \forall x,y\in V\) and (ii) \(\beta \) is non-degenerate, i.e., \(\forall x\in V, \beta (x,y)=0\Longrightarrow y=0 \). A Clifford algebra for \((V,\beta )\) consists of a real unital associative algebra denoted \(\mathrm{Cl}(V,\beta )\) together with a linear map \(e: V \rightarrow \mathrm{Cl}(V,\beta )\) satisfying:

1. (i)

   \({e(u)e(v)+e(v)e(u)}=\beta ( u,v)1, \) for all \(u,v\in V\);

2. (ii)

   \(\mathrm{Cl}(V,\beta )\) is generated by e(V) as an algebra;

3. (iii)

   Given a real unital associative algebra \(\mathcal {A}\) and linear map \(f: V \rightarrow \mathcal {A}\) satisfying

   $$\begin{aligned} f(u)f(v)+f(v)f(u)=\beta (u,v) 1, \text { for all } u,v\in V, \end{aligned}$$

   there exists a unique algebra homomorphism \(h: \mathrm{Cl}(V,\beta ) \rightarrow \mathcal {A} \) where \(f=h\circ e\).

A Clifford algebra for \((V,\beta )\) is explicitly defined as the quotient algebra \(\mathcal {T}(V)/\mathcal {I}(V),\) where \(\mathcal {T}(V):=\oplus _{k\ge 0 }V^{\otimes k}\) is the tensor algebra and \(\mathcal {I}(V)\) is the two-sided ideal generated by the elements of the form \(u\otimes v+v\otimes u-\beta (u,v)1,\) for all \(u,v\in V\). Any two algebras satisfying conditions (i), (ii), (iii) are isomorphic. We refer to \(\mathrm{Cl}(V,\beta )\) as the Clifford algebra over V.

A representation of an associative algebra \(\mathcal {A}\) consists of a vector space W together with an algebra homomorphism \(\varGamma : \mathcal {A} \rightarrow \mathrm{End}(W)\), i.e., a linear map preserving multiplication and the unit element, where \(\mathrm{End}(W)\) is the set of all endomorphisms of W. The dimension of a representation \((\varGamma ,W)\) is the dimension of W as a vector space. A subrepresentation of a representation \((\varGamma ,W)\) is a subspace \(U\subseteq W\) such that \(\varGamma (a)(U)\subseteq U, \ \forall a\in \mathcal {A}\). A representation is irreducible if its only subrepresentations are itself and the trivial vector space.

It is well-known that the irreducible representations of \(\mathrm{Cl}(V,\beta )\) have size exponential in terms of the dimension of V. This is the source of our sub-exponential lower bound in this paper. Specifically, it is known that (e.g. see [14, Theorem 6.1.3]):

Theorem A.1

Let \(\beta \) be a nondegenerate bilinear form on V.

1. (i)

   If \(\dim V=2\ell \) then (up to isomorphism) there exists a unique irreducible representation of \(\mathrm{Cl}(V,\beta )\) which has dimension \(2^\ell \);

2. (ii)

   If \(\dim V=2\ell +1\) then there exist two nonisomorphic irreducible representations of \(\mathrm{Cl}(V,\beta )\). Both representations have dimension \(2^\ell \).

Remark A.2

Consider a real vector space V equipped with a symmetric and non-degenerate bilinear form \(\beta : V\times V\rightarrow \mathbb {R}\). Let f be a linear map \(f: V\rightarrow ~\mathrm{End}(W)\) satisfying \(f(u)f(v)+f(v)f(u)=\beta (u,v)1_W\), for all \(u,v\in V\). Using the three defining axioms for \(\mathrm{Cl}(V,\beta )\) it follows that f can be extended to a representation for \(\mathrm{Cl}(V,\beta )\).

B Supplementary Material: Proof of Theorem 5.4

In this section we give for completeness a proof of Theorem 5.4, as this is not stated explicitly in [37]. We start with a definition.

Definition B.1

Given \( C =(c_{xy}) \in \mathrm {Cor}(n,m)\), we say that a family of real vectors \(\{u_x, v_y\}_{x,y}\) is a C -system if they satisfy \(\Vert u_x\Vert \le 1,\ \forall x,\) \(\Vert v_y\Vert \le 1,\ \forall y,\) and \( c_{xy}=\langle u_x,v_y\rangle ,\ \forall x,y.\)

As it turns out, C-systems of vectors corresponding to extremal quantum correlations have interesting properties. For our purposes we only need the following result:

Lemma B.2

[37, Lemma 3.1] For any \(C=(c_{xy})\in \mathrm {ext}(\mathrm{Cor}(n,m))\) we have that:

1. (i)

   All C-systems necessarily consist of unit vectors;

2. (ii)

   For any C-system \(\{u_x\}_{x=1}^n,\{v_y\}_{y=1}^m\) we have that \(\mathrm{span}(\{u_x\}_{x=1}^n)=\mathrm{span}(\{v_y\}_{y=1}^m)\);

3. (iii)

   There exists a unique elliptope completion of C. Denoting this by \(E_C=\left( {\begin{matrix}A&{} C\\ C^\mathsf{T}&{} B\end{matrix}}\right) \in ~\mathcal {E}_{n+m}\), we also have that \(E_C\in \mathrm {ext}(\mathcal {E}_{n+m})\) and \( \mathrm {rank}(E_C)=\mathrm {rank}(A)=\mathrm {rank}(B)=\mathrm {rank}(C).\)

The next results shows that the operators in a quantum representation of an extremal quantum correlation correspond to a representation of an appropriate Clifford algebra.

Theorem B.3

[37, Theorem 3.1] Let \(C=(c_{xy}) \in \mathrm{ext}(\mathrm{Cor}(n,m))\) and consider a family of Hermitian \(d\times d\) operators \(\{A_x\}_x,\{B_y\}_y, \rho \) such that:

1. (i)

   \(c_{xy}=\mathrm {Tr}(A_xB_y\rho ),\) for all x, y;

2. (ii)

   \(A_xB_y=B_yA_x, \) for all x, y;

3. (iii)

   \(\rho \) is a density matrix;

4. (iv)

   The eigenvalues of \(A_x,B_y\) are in \([-1,1]\);

5. (v)

   There does not exist an orthogonal projector \(P\ne I\) such that

   $$\begin{aligned} PA_x=A_xP, \ PB_y=B_yP \text { and } P\rho P=\rho . \end{aligned}$$

   (B.1)

Then, for any C-system of vectors \(\{ u_x \}_x\), \(\{ v_y \}_{y}\) we have that

where \(\{A, B \} := AB + BA\) is the anticommutator of A and B.

Using Theorem B.3 we are now ready to give a proof for Theorem 5.4.

Theorem

Let \(C=(c_{xy}) \in {\mathrm{ext}(\mathrm {Cor}(n,m))}\) and consider a family of \(d\times d\) Hermitian operators \(\{M_x\}_{x}, \{N_y\}_{y}\) with eigenvalues in \([-1,1]\) and a quantum state \(\rho \in ~\mathcal {H}^{d^2}_+\) satisfying \(c_{xy}=\mathrm {Tr}((M_x\otimes N_y)\rho ),\) for all x, y. Then we have that \({d\ge {{2}^{\lfloor \mathrm {rank}(C)/ 2\rfloor }}}.\)

Proof

For all x set \(A_x:=M_x\otimes I_d \in \mathcal {H}^{d^2}\) and for all y set \(B_y:=I_d\otimes N_y\in \mathcal {H}^{d^2}\). Note that conditions \((i)-(iv)\) of Theorem B.3 are satisfied. Furthermore, if there exists an orthogonal projector \(P\ne I\) satisfying (B.1), by restricting on the support of the matrices \(\{ PA_{x} P\}_x,\{ PB_{y} P\}_y\) and \(P\rho P\) we get a new family of operators that satisfy conditions \((i)-(v)\) from Theorem B.3 that have smaller size. This process can be repeated to obtain matrices satisfying conditions \((i)-(v)\) whose size is at most \(d^{2}\).

Setting \(r:=\mathrm {rank}(C)\), by Lemma B.2 there exists a C-system \(\{u_x,v_y\}_{x,y}\) satisfying \(\mathrm {span}(\{u_x\}_x)=\mathrm {span}(\{v_y\}_y)=\mathbb {R}^{r}.\) Furthermore, by Theorem B.3 we have

Without loss of generality let \(\{u_x\}_{x=1}^r\) be a basis for \(\mathbb {R}^r\). Set \(f_1 :\mathbb {R}^r \rightarrow \mathcal {H}^{d^2}\) where \(f_1(u_x):=A_x\), for \(1\le x\le r\) and extend linearly, i.e., \(f_1(\lambda )=\sum _{x=1}^{r} \lambda _xA_x,\) for all \(\lambda \in \mathbb {R}^\tau \), where \(\lambda =(\lambda _x)\) are the coordinates with respect to the \(\{u_x\}_{x=1}^r\) basis. Using (B.3) it follows that for \(\lambda ,\mu \in \mathbb {R}^r\) we have

Define the bilinear form \(\beta _1:\mathbb {R}^r\times \mathbb {R}^r\rightarrow \mathbb {R}\) by

Note that \(\beta _1\) is symmetric and furthermore, as \(\mathrm {Gram}(\{u_x\}_{x=1}^r)\) is full-rank, it is also nondegenerate. By (B.4), \(f_1\) can be extended to a representation \(f_1: \mathrm{Cl}(\mathbb {R}^r,\beta _1) \rightarrow \mathbb {C}[A_1,\ldots ,A_r]\) (cf. Remark A.2). In the same manner, we get a representation \(f_2: \mathrm{Cl}(\mathbb {R}^r,\beta _2) \rightarrow \mathbb {C}[B_1,\ldots ,B_r]\).

By the universal property of the tensor product of algebras, \(f_1\) and \(f_2\) induce a representation \(f: \mathrm{Cl}(\mathbb {R}^r,\beta _1) \otimes \mathrm{Cl}(\mathbb {R}^r,\beta _2)\rightarrow \mathbb {C}[A_1,\ldots ,A_r]\mathbb {C}[B_1,\ldots ,B_r]\), where \(f(x\otimes 1)=f_1(x)\) and \(f(1\otimes y)=f_2(y)\) for all \(x\in \mathrm{Cl}(\mathbb {R}^r,\beta _1) \) and \(y\in \mathrm{Cl}(\mathbb {R}^r,\beta _2)\). Each irreducible representation of \(\mathrm{Cl}(\mathbb {R}^r,\beta _1) \otimes \mathrm{Cl}(\mathbb {R}^r,\beta _2)\) is the tensor product of irreducible representations of \(\mathrm{Cl}(\mathbb {R}^r,\beta _1) \) and \(\mathrm{Cl}(\mathbb {R}^r,\beta _2)\) (e.g. see [10, Remark 2.27]). As a consequence, it follows by Theorem A.1 that \(d^2\ge 4^{\lfloor r/ 2\rfloor }\) and thus \(d\ge 2^{\lfloor r/ 2\rfloor }\). \(\square \)

Reprints and permissions