# Absolutely $k$-Incoherent Quantum States and
Spectral Inequalities for Factor Width of a Matrix

Nathaniel Johnston,1,2 Shirin Moein,1,2,3,4 Rajesh Pereira,2 and Sarah
Plosker2,3

###### Abstract

We investigate the set of quantum states that can be shown to be
$k$-incoherent based only on their eigenvalues (equivalently, we explore which
Hermitian matrices can be shown to have small factor width based only on their
eigenvalues). In analogy with the absolute separability problem in quantum
resource theory, we call these states “absolutely $k$-incoherent”, and we
derive several necessary and sufficient conditions for membership in this set.
We obtain many of our results by making use of recent results concerning
hyperbolicity cones associated with elementary symmetric polynomials.

Keywords: spectral inequalities, quantum coherence, factor width,
hyperbolicity cones, elementary symmetric polynomials

MSC2010 Classification: 81P40, 15A18, 15B57

11footnotetext: Department of Mathematics & Computer Science, Mount Allison
University, Sackville, NB, Canada E4L 1E422footnotetext: Department of
Mathematics & Statistics, University of Guelph, Guelph, ON, Canada N1G
2W133footnotetext: Department of Mathematics & Computer Science, Brandon
University, Brandon, MB, Canada R7A 6A944footnotetext: Department of
Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran
84156-83111

##  1 Introduction

In the theory of quantum information, there are numerous resource theories
that can be used to make rigorous the idea of certain quantum states being
“useful” or “useless” [CG19]. Perhaps the most well-known of these resource
theories is that of entanglement and separability [Vid00], where separable
states are those that are “useless”, while entangled (i.e., non-separable)
states are those that are “useful” (in terms of quantum channel
discrimination, for example [PW09]).

The well-studied _absolute_ separability problem asks for a characterization
of which quantum states can be determined to be separable based only on their
spectrum (i.e., multiset of eigenvalues) [KŻ01]. A full solution to this
problem remains out of reach [AJR15], but a complete characterization is known
in small dimensions [VAM01, Joh13] and some non-trivial necessary conditions
are known in all dimensions [Hil07]. This “absolute” question has been asked
for some other resource theories and in some other contexts as well. For
example, it has been explored in the resource theory of _symmetric_
separability [CJMP22, SEM21], and it has been explored in the context of the
reduction map from quantum information theory [JLNR15].

In this work, we introduce the corresponding “absolute” question for another
resource theory: the resource theory of $k$-coherence [RBC+18], which has been
studied by several groups in many different contexts [LBT19, LSLL21, LM14,
ZGY21]. Understanding the structure of $k$-coherence would be useful in many
fields, as it helps explain the function of complex biological molecules like
those found in light-harvesting [SdMW+11] and chemical and biophysical systems
[SFC+17, LLC+12], for example, and it can be used to describe the statistical
properties of a quantum state’s interference pattern [vPRM15].

###  1.1 Measuring k-Incoherence in a Laboratory Setting

Despite widespread interest in quantifying coherence, there is a lack of
efficient methods for measuring coherence in experiments, which can make it
difficult to use in practice. One of the standard ways of using measurement
results to show that a quantum state $\rho$ is $k$-coherent is to measure it
against a $k$-coherence witness $W$: if $\operatorname{Tr}(W\rho)<0$ then
$\rho$ must be $k$-coherent. In fact, this method can be used to obtain lower
bounds on $\rho$’s robustness of $k$-coherence (see [NBC+16, WSR+21], for
example).

In the other direction, however, it seems to be much more difficult to use
measurement results to show that a quantum state is $k$-incoherent. This
problem was partially overcome in [YG19] by developing a method of estimating
the $k$-coherence in a quantum state via its spectrum. Our work on the
“absolute” version of $k$-coherence can be seen as an extension of this
idea—we ask which quantum states can be shown to be $k$-incoherent (i.e.,
“useless” in this resource theory) based only on knowledge of their spectrum.

More specifically, a quantum state acting on an $n$-dimensional space requires
$n^{2}-1$ real parameters to specify, and thus $n^{2}-1$ measurement outcomes
to reconstruct via tomography. However, it is often must easier to determine
just the state’s eigenvalues, rather than the structure of the entire state
[EAO+02, TOK+14, TSS21]. After all, the eigenvalues are just $n-1$ real
parameters instead of $n^{2}-1$. Our results thus provide tests that can be
used to show that quantum states are $k$-incoherent, just given this (easier-
to-obtain) restricted information about the state’s eigenvalues: if the
eigenvalues satisfy any of our sufficient conditions for absolute
$k$-incoherence, then the corresponding quantum state must be $k$-incoherent.

In another direction, our results shed light on how much noise must be added
to the maximally mixed state in order for it to become $k$-coherent. Indeed,
every state that is sufficiently close to the maximally mixed state (which has
all eigenvalues equal to each other) is $k$-incoherent, and our sufficient
conditions for absolute $k$-incoherence give quantitative statements about how
spread out the eigenvalues have to be before $k$-coherence is possible.
Phrased another way, our results show that if the (spectral, Frobenius, trace,
or any other unitarily-invariant) norm distance between a quantum state and
the maximally mixed state is small, then that state must be $k$-incoherent,
meaning that $k$-incoherence in this regime is resistant to errors is
measurement results. We note that results of this type have been studied
extensively in the resource theory of entanglement [GB02], but to our
knowledge no substantial results in this direction were known for
$k$-coherence prior to ours.

###  1.2 Summary of our Results and Methods

Much like known results for the absolute separability problem, we obtain a
complete characterization of absolutely $k$-incoherent states in small
dimensions, as well as non-trivial one-sided (i.e., necessary or sufficient,
but not both) conditions in all dimensions. We also obtain a complete
necessary and sufficient criterion for the $k=n-1$ case (in all dimensions),
showing that membership in this set can be determined in polynomial time. In
the terminology of pure mathematics, $k$-incoherent states are exactly the
matrices that have factor width at most $k$ [BCPT05], and our results can thus
equivalently be interpreted as spectral inequalities that can be used to show
that a matrix has small factor width.

To arrive at our results, we consider a family of matrices that we call _$k$
-locally PSD_ (in keeping with the terminology of [BDSS22], where these
matrices were introduced independently). These matrices form exactly the dual
cone of the set of $k$-incoherent quantum states, so they serve as “witnesses”
in the resource theory of $k$-coherence (in the exact same sense that
entanglement witnesses [Ter00] can be used to “witness” entanglement). In
particular, we show that the spectra of these $k$-locally PSD matrices belong
to certain sets called “hyperbolicity cones” [Ren06, Zin08], and we use recent
results about the dual of these cones to get bounds on the spectrum of
absolutely $k$-incoherent states. We also provide a tight characterization of
these cones when $k=n-1$, and recover (in a slightly more explicit way) a
result from [BDSS22].

Our paper is organized as follows: In Section 2, we review the various
definitions and concepts from quantum information theory that we will be
exploring, including $k$-incoherent states and their connection to hermitian
matrices with factor width at most $k$, and we introduce the notion of
$k$-locally PSD matrices via dual cones. In Section 3 we develop some bounds
on the possible spectra of $k$-locally PSD matrices, in Section 3.1 we present
a method for numerically constructing a $k$-locally PSD matrix with a given
spectrum, and then in Section 3.2 we discuss how our results about $k$-locally
PSD matrices relate to recent work on hyperbolicity cones. Readers who are
just interested in our results on absolute $k$-incoherence can skip Sections
3.1 and 3.2, and perhaps all of Section 3.

In Section 4, we present out main results about absolute $k$-incoherence,
which include a complete characterization of absolute $2$-incoherence in
dimension $3$ (Theorem 7), a complete characterization of absolute
$(n-1)$-incoherence in every dimension (Theorem 8), some sufficient conditions
for absolute $k$-incoherence for all values of $k$ in all dimensions (Theorems
3 and 5), as well as a corresponding necessary condition (Theorem 4). Finally,
we close in Section 5 with some open questions.

##  2 Mathematical and Quantum Information Theory Preliminaries

The notation and terminology that we use is fairly standard, so we just
introduce it briefly. For a more thorough introduction to quantum information
theory, see any of numerous standard textbooks like [NC00, Wat18].

We use $M_{n}$ to denote the set of all $n\times n$ matrices with complex
entries, $M_{n}^{\textup{H}}$ to denote the set of Hermitian matrices (i.e.,
matrices $A\in M_{n}$ having $A^{*}=A$, where $A^{*}$ is the conjugate
transpose of $A$), and $M_{n}^{+}$ for the subset of them that are (Hermitian)
positive semidefinite. We use bold lower case letters such as $\mathbf{v}$ and
$\mathbf{w}$ to denote vectors in $\mathbb{C}^{n}$, and $v_{1}$, $v_{2}$,
$\ldots$, $v_{n}$ to denote the entries of $\mathbf{v}\in\mathbb{C}^{n}$.

In quantum information theory, a mixed quantum state or density matrix is a
positive semidefinite trace-one matrix $\rho\in M_{n}^{+}$. A pure quantum
state is a unit vector in $\mathbb{C}^{n}$, which we denote using “bra-ket”
notation: $|v\rangle\in\mathbb{C}^{n}$ is a unit column vector, while $\langle
v|\stackrel{{\scriptstyle\smash{\textnormal{\tiny def}}}}{{=}}|v\rangle^{*}$
is the corresponding (dual) row vector. Whenever we use lowercase Greek
letters like $\rho$, we are assuming that it is a quantum state normalized to
have $\operatorname{Tr}(\rho)=1$ (i.e., trace one) and similarly if we use
$|v\rangle$ then we are assuming it is a _unit_ vector. We denote matrices and
vectors that are not necessarily normalized like $A\in M_{n}$ and
$\mathbf{v}\in\mathbb{C}^{n}$, respectively.

###  2.1 Incoherence and Factor Width

By the spectral decomposition, every mixed state $\rho\in M_{n}^{+}$ can be
written in the form

$\rho=\sum_{j}\mathbf{v_{j}}\mathbf{v}_{\mathbf{j}}^{*}$

for some $\\{\mathbf{v_{j}}\\}\subseteq\mathbb{C}^{n}$. In the special case
when each $\mathbf{v_{j}}$ can be chosen to have at most $k$ non-zero entries
(where $1\leq k\leq n$), $\rho$ is called $\mathbf{k}$-incoherent [RBC+18]. If
$\rho$ is _not_ $k$-incoherent then it is called $\mathbf{k}$-coherent.
Density matrices (or more generally, positive semidefinite matrices) that are
$k$-incoherent, but not $(k-1)$-incoherent, are sometimes said to have factor
width $k$ [BCPT05].

We denote the (closed and convex) set of $k$-incoherent quantum states in
$M_{n}^{+}$ by $\mathcal{I}_{k,n}$, and we note that we have the chain of
inclusions

$\mathcal{I}_{1,n}\subsetneq\mathcal{I}_{2,n}\subsetneq\cdots\subsetneq\mathcal{I}_{n-1,n}\subsetneq\mathcal{I}_{n,n}.$

In the $k=1$ case, $\mathcal{I}_{1,n}$ is exactly the set of diagonal density
matrices, which are simply said to be incoherent. At the other extreme, if
$k=n$ then $\mathcal{I}_{n,n}$ is the set of _all_ density matrices.

###  2.2 Dual Cones and Local Positivity

Let $\mathcal{C}$ be a subset of a finite-dimensional real inner product space
$\mathcal{V}$. Then the dual cone of $\mathcal{C}$, denoted by
$\mathcal{C}^{\circ}$, is defined as follows:

$\mathcal{C}^{\circ}\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\big{\\{}\mathbf{w}\in\mathcal{V}:\langle\mathbf{v},\mathbf{w}\rangle\geq
0\text{ for all }\mathbf{v}\in\mathcal{C}\big{\\}}.$

For example, if $\mathcal{V}=M_{n}^{\textup{H}}$ (equipped with the usual
Hilbert–Schmidt inner product $\langle X,Y\rangle:=\operatorname{Tr}(XY)$),
the dual cone of a set $\mathcal{C}\subseteq M_{n}^{\textup{H}}$ is

$\mathcal{C}^{\circ}\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\big{\\{}Y\in M_{n}^{\textup{H}}:\operatorname{Tr}(XY)\geq 0\text{
for all }X\in\mathcal{C}\big{\\}}.$

Similarly, if $\mathcal{V}=\mathbb{R}^{n}$ (equipped with the usual dot
product) then the dual cone of a set $\mathcal{C}\subseteq\mathbb{R}^{n}$ is

$\mathcal{C}^{\circ}\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\big{\\{}\mathbf{w}\in\mathbb{R}^{n}:\mathbf{v}\cdot\mathbf{w}\geq
0\text{ for all }\mathbf{v}\in\mathcal{C}\big{\\}}.$

Regardless of $\mathcal{V}$ and the structure of $\mathcal{C}$, every dual
cone $\mathcal{C}^{\circ}$ is (as the name suggests) a cone: if
$\mathbf{w}\in\mathcal{C}^{\circ}$ then
$\lambda\mathbf{w}\in\mathcal{C}^{\circ}$ for all $0\leq\lambda\in\mathbb{R}$.
Dual cones are also always closed and convex, and the double-dual of any cone
is the closure of its convex hull:
$\mathcal{C}^{\circ\circ}=\overline{\mathrm{conv}(\mathcal{C})}$ (see [BV04],
for example).

We will be particularly interested in the dual cone
$\mathcal{I}_{k,n}^{\circ}\subseteq M_{n}^{\textup{H}}$ of the set of
$k$-incoherent density matrices, which we characterize in a few different
ways:

######  Definition 1.

We say that a Hermitian matrix $X\in M_{n}^{\textup{H}}$ is k-locally PSD if
it has any of the following equivalent properties:

  1. a)

$X\in\mathcal{I}_{k,n}^{\circ}$ (i.e., $\operatorname{Tr}(X\rho)\geq 0$ for
all $\rho\in\mathcal{I}_{k,n}$);

  2. b)

$\langle v|X|v\rangle\geq 0$ for all $|v\rangle\in\mathbb{C}^{n}$ with at most
$k$ non-zero entries; or

  3. c)

every $k\times k$ principal submatrix of $X$ is positive semidefinite.

The terminology “$k$-locally PSD” is from [BDSS22], where the eigenstructure
of such matrices was studied. We will also explore the eigenstructure of these
matrices shortly, in Section 3.

We now show that these three defining properties really are equivalent. To see
that (a) implies (b), we prove the contrapositive: if (b) is false then there
exists a complex unit vector $|v\rangle$ with at most $k$ non-zero entries
such that $\langle v|X|v\rangle<0$. By choosing $\rho=|v\rangle\langle v|$ we
then have $\rho\in\mathcal{I}_{k,n}$ and $\operatorname{Tr}(X\rho)<0$, showing
that (a) is also false. Conversely, to see that (b) implies (a), write
$\rho=\mathbf{v_{j}}\mathbf{v}_{\mathbf{j}}^{*}$ where each $\mathbf{v_{j}}$
has at most $k$ non-zero entries. Then

$\operatorname{Tr}(X\rho)=\sum_{j}\operatorname{Tr}\big{(}X(\mathbf{v_{j}}\mathbf{v}_{\mathbf{j}}^{*})\big{)}=\sum_{j}\mathbf{v}_{\mathbf{j}}^{*}X\mathbf{v_{j}}\geq
0,$

where we used (b) to see that each in the sum is non-negative.

Finally, to see that (b) is equivalent to (c), we note that requiring $\langle
v|X|v\rangle\geq 0$ for all $|v\rangle\in\mathbb{C}^{n}$ with $k$ non-zero
entries in positions $i_{1}$, $i_{2}$, $\ldots$, $i_{k}$ is equivalent to
requiring that the $k\times k$ principal submatrix of $X$ corresponding to
rows and columns $i_{1}$, $i_{2}$, $\ldots$, $i_{k}$ is positive semidefinite.
Letting the tuple $(i_{1},i_{2},\ldots,i_{k})$ range over all possible
$k$-tuples of indices gives the equivalence of (b) and (c).

Property (a) of Definition 1 justifies thinking of these $k$-locally PSD
matrices as “$k$-coherence witnesses” (in direct analogy with entanglement
witnesses [Ter00]). Indeed, if $X$ is $k$-locally PSD and
$\operatorname{Tr}(X\rho)<0$ then we know that $\rho$ must be $k$-coherent.
Since the quantity $\operatorname{Tr}(X\rho)$ is measurable in a lab, it lets
us use $X$ to “witness” the $k$-coherence of $\rho$.

It is straightforward to see that these sets of $k$-locally PSD matrices
satisfy the chain of inclusions

$M_{n}^{+}=\mathcal{I}_{n,n}^{\circ}\subsetneq\mathcal{I}_{n-1,n}^{\circ}\subsetneq\cdots\subsetneq\mathcal{I}_{2,n}^{\circ}\subsetneq\mathcal{I}_{1,n}^{\circ},$

where $\mathcal{I}_{1,n}^{\circ}$ is the set of Hermitian matrices with non-
negative diagonal entries.

##  3 Spectra of $k$-locally PSD Matrices

In this section, we investigate some bounds on the possible spectra of
$k$-locally PSD matrices. We start with a result that tells us exactly how
many negative eigenvalues these matrices can have:

######  Theorem 1.

Every matrix $X\in\mathcal{I}_{k,n}^{\circ}$ has at most $n-k$ negative
eigenvalues. Furthermore, this bound is tight: for all $1\leq k\leq n$ there
exists $X\in\mathcal{I}_{k,n}^{\circ}$ with exactly $n-k$ negative
eigenvalues.

###### Proof.

Suppose $X\in\mathcal{I}_{k,n}^{\circ}$ has eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. To see that it has at
most $n-k$ negative eigenvalues (i.e., $\lambda_{k}\geq 0$), recall that
eigenvalue interlacing (see [LPS12, Theorem 1.1], for example) tells us if
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{k}$ are the eigenvalues of a $k\times k$
principal submatrix of $X$ then

$\displaystyle\lambda_{j}\geq\mu_{j}\geq\lambda_{n-k+j}\quad\text{for
all}\quad 1\leq j\leq k.$ (1)

Since each $k\times k$ submatrix of $X$ is positive semidefinite, we know that
$\mu_{k}\geq 0$, so taking $j=k$ in Inequality (1) gives
$\lambda_{k}\geq\mu_{k}\geq 0$, as desired.

To see that there exists $X\in\mathcal{I}_{k,n}^{\circ}$ with exactly $n-k$
negative eigenvalues, recall from [CMW08, Lemmas 8 and 9] that if
$0<v_{1}<v_{2}<\cdots<v_{n}\in\mathbb{R}$ and

$\displaystyle V$
$\displaystyle:=\begin{bmatrix}1&v_{1}&v_{1}^{2}&\cdots&v_{1}^{n-1}\\\
1&v_{2}&v_{2}^{2}&\cdots&v_{2}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&v_{n}&v_{n}^{2}&\cdots&v_{n}^{n-1}\\\ \end{bmatrix}$ (2)

is a Vandermonde matrix, then any non-zero linear combination of $n-k$ of
$V$’s columns has at most $n-k-1$ entries equal to $0$ (i.e., at least $k+1$
non-zero entries). With this in mind, we let $\mathbf{v_{j}}$ denote the
$j$-th column of $V$ and then define the subspace

$\mathcal{S}_{n-k}:=\mathrm{span}\\{\mathbf{v_{1}},\mathbf{v_{2}},\ldots,\mathbf{v_{n-k}}\\},$

which only contains vectors with at least $k+1$ non-zero entries.

If $P_{n-k}$ is the orthogonal projection onto $\mathcal{S}_{n-k}$ then it is
clear that $X:=I-cP_{n-k}$ has exactly $n-k$ negative eigenvalues whenever
$c>1$ (since the $\mathbf{v_{j}}$’s are linearly independent, so
$\mathrm{rank}(P_{n-k})=n-k$). We furthermore claim that $X$ is $k$-locally
PSD for some $c>1$. To see this, notice that if $|v\rangle\in\mathbb{C}^{n}$
has at most $k$ non-zero entries then $\langle v|P_{n-k}|v\rangle<1$.
Compactness of the set of all such $|v\rangle$ implies that there exists a
scalar $d<1$ such that $\langle v|P_{n-k}|v\rangle\leq d$ for all such
$|v\rangle$, so $\langle v|X|v\rangle=1-c\langle v|P_{n-k}|v\rangle\geq 1-cd$,
which is non-negative as long as $c\leq 1/d$. Since $1/d>1$, we can choose
$c=1/d$ to complete the proof. ∎

For example, if $k=n-1$ then the construction given in the proof of Theorem 1
says that there exists $c>1$ such that
$X:=I-cP_{1}=I-c(\mathbf{1}\mathbf{1}^{T}/n)$ is $(n-1)$-locally PSD with $1$
negative eigenvalue, where
$\mathbf{1}\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}(1,1,\ldots,1)^{T}$ is the all-ones vector. In this case, we can
explicitly compute $c=n/(n-1)$ as the largest possible value of $c$ that
results in $X$ being $(n-1)$-locally PSD.

We now investigate the question of _how_ negative the negative eigenvalues of
a $k$-locally PSD matrix can be. Our main result in this direction is a simple
bound that is in terms of the elementary symmetric polynomials

$\displaystyle
S_{k}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\sum_{1\leq i_{1}<\cdots<i_{k}\leq
n}\left(\prod_{j=1}^{k}\lambda_{i_{j}}\right).$ (3)

######  Theorem 2.

If $X\in\mathcal{I}_{k,n}^{\circ}$ has eigenvalues $\lambda_{1}$,
$\lambda_{2}$, $\ldots$, $\lambda_{n}$ then

$\displaystyle S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\geq
0\quad\text{for all}\quad 1\leq j\leq k.$ (4)

Conversely, if $k\in\\{1,n-1,n\\}$ then, for any scalars $\lambda_{1}$,
$\lambda_{2}$, $\ldots$, $\lambda_{n}\in\mathbb{R}$ satisfying Inequality (4),
there exists $X\in\mathcal{I}_{k,n}^{\circ}$ with eigenvalues $\lambda_{1}$,
$\lambda_{2}$, $\ldots$, $\lambda_{n}$.

Before we can prove this theorem, we need the following lemma:

######  Lemma 1.

[KT16, Theorem 2.1] Let $C$ be an $n\times n$ circulant matrix with the monic
characteristic polynomial $p(z)$. Then every $(n-1)\times(n-1)$ principal
submatrix of $C$ has characteristic polynomial $\frac{1}{n}p^{\prime}(z)$.

We note that, while the original statement of this result given in [KT16] is
in terms of the $(n-1)\times(n-1)$ _upper left_ principal submatrix of $C$,
the result and proof work for all $(n-1)\times(n-1)$ principal submatrices of
$C$. In fact, any two $(n-1)\times(n-1)$ principal submatrices of $C$ can be
seen to be permutationally similar and so have the same characteristic
polynomial.

###### Proof of Theorem 2.

To see that Inequality (4) holds when $\lambda_{1}$, $\lambda_{2}$, $\ldots$,
$\lambda_{n}$ are eigenvalues of $X\in\mathcal{I}_{k,n}^{\circ}$, recall from
[HJ13, Theorem 1.2.16] that
$S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})$ equals the sum of the
$j\times j$ principal minors of $X$. Since $X$ is $k$-locally PSD, those
principal minors are all non-negative whenever $1\leq j\leq k$, so
$S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\geq 0$ whenever $1\leq
j\leq k$ as well.

For the “conversely” direction, we first consider the case when $k=1$. If
$\lambda_{1}$, $\lambda_{2}$, $\ldots$, $\lambda_{n}$ are such that
$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n}\geq 0$ (i.e., Inequality (4)
holds), then the Schur–Horn theorem [HJ13, Theorem 4.3.48] tells us that there
exists $X\in M_{n}^{\textup{H}}$ with eigenvalues $\lambda_{1}$,
$\lambda_{2}$, $\ldots$, $\lambda_{n}$ and each diagonal entry equal to
$(\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n})/n$. Since these diagonal entries
are all non-negative, $X\in\mathcal{I}_{1,n}^{\circ}$ as desired.

Next, we consider the $k=n$ case. It is well-known that
$S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\geq 0$ for all $1\leq j\leq
n$ is equivalent to $\lambda_{j}\geq 0$ for all $1\leq j\leq n$. Since we can
construct a positive semidefinite matrix (i.e., a matrix $X\in
M_{n}^{+}=\mathcal{I}_{n,n}^{\circ}$) having any set of non-negative
eigenvalues, we are done with this case.

All that remains is to prove the “conversely” statement when $k=n-1$. Let
$\lambda_{1}$, $\lambda_{2}$, $\ldots$, $\lambda_{n}$ be real numbers such
that $S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\geq 0$ for all $1\leq
j\leq n-1$. Let $X\in M_{n}$ be a circulant matrix with monic characteristic
polynomial

$p(z)=\prod_{j=1}^{n}(z-\lambda_{i})=z^{n}+\sum_{j=1}^{n}(-1)^{j}S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})z^{n-j}.$

Since the roots of $p$ are all real, $X$ must be Hermitian. Furthermore,

$p^{\prime}(z)=nz^{n-1}+\sum_{j=1}^{n-1}(-1)^{j}(n-j)S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})z^{n-j-1}$

must also have all of its roots real. In fact, since the coefficients of
$p^{\prime}(z)$ are alternating, all of its roots must be non-negative. Lemma
1 then tells us that every $(n-1)\times(n-1)$ principal submatrix of $X$ has
all eigenvalues non-negative, so we conclude that
$X\in\mathcal{I}_{n-1,n}^{\circ}$, completing the proof. ∎

It is worth noting that Theorem 2 gives a complete characterization of the
possible spectra of $k$-locally PSD matrices (for all values of $k$) when
$n=3$. Given $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}\in\mathbb{R}$
satisfying Inequality (4), it is straightforward to construct
$X\in\mathcal{I}_{k,3}^{\circ}$ with eigenvalues $\lambda_{1}$, $\lambda_{2}$,
$\lambda_{3}$ when $k=1$ or $k=3$. To construct such an $X$ when $k=2$ (i.e.,
to make the “conversely” direction of the proof above a bit more explicit when
$n=3$ and $k=2$), note that in this case we have

$\lambda_{1}+\lambda_{2}+\lambda_{3}\geq
0\quad\text{and}\quad\lambda_{1}\lambda_{2}+\lambda_{1}\lambda_{3}+\lambda_{2}\lambda_{3}\geq
0.$

If $U\in M_{3}$ is the Fourier matrix (i.e.,
$u_{j,\ell}=\mathrm{exp}\big{(}2\pi i(j-1)(\ell-1)/3\big{)}$ for all $1\leq
j,\ell\leq 3$) then
$X:=U\mathrm{diag}(\lambda_{1},\lambda_{2},\lambda_{3})U^{*}$ has eigenvalues
$\lambda_{1}$, $\lambda_{2}$, and $\lambda_{3}$, and the proof of Theorem 2
shows that $X\in\mathcal{I}_{2,3}^{\circ}$. To verify this claim a bit more
directly, note that $X$ is a Hermitian circulant matrix and thus must have the
form

$X=\begin{bmatrix}a&b&\overline{b}\\\ \overline{b}&a&b\\\
b&\overline{b}&a\end{bmatrix}$

for some $a\in\mathbb{R}$ and $b\in\mathbb{C}$. Since
$\operatorname{Tr}(X)=3a=\lambda_{1}+\lambda_{2}+\lambda_{3}$, we conclude
that $a=(\lambda_{1}+\lambda_{2}+\lambda_{3})/3\geq 0$. Furthermore, the
Frobenius norm of $X$ satisfies
$\|X\|_{\textup{F}}^{2}=3a^{2}+6|b|^{2}=\lambda_{1}^{2}+\lambda_{2}^{2}+\lambda_{3}^{2}$.
If we substitute $a=(\lambda_{1}+\lambda_{2}+\lambda_{3})/3$ into this formula
and rearrange, we learn that

$\displaystyle|b|^{2}$
$\displaystyle=\frac{1}{9}\Big{(}\big{(}\lambda_{1}^{2}+\lambda_{2}^{2}+\lambda_{3}^{2}\big{)}-\big{(}\lambda_{1}\lambda_{2}+\lambda_{1}\lambda_{3}+\lambda_{2}\lambda_{3}\big{)}\Big{)}.$

Since
$\lambda_{1}\lambda_{2}+\lambda_{1}\lambda_{3}+\lambda_{2}\lambda_{3}\geq 0$,
it follows that
$|b|^{2}\leq(\lambda_{1}+\lambda_{2}+\lambda_{3})^{2}/9=a^{2}$. This implies
that every $2\times 2$ principal submatrix of $X$ is positive semidefinite, so
$X\in\mathcal{I}_{2,3}^{\circ}$, as claimed.

The smallest open case is thus $n=4$, $k=2$, where Theorem 2 gives the
necessary conditions that every $X\in\mathcal{I}_{2,4}^{\circ}$ has
eigenvalues $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$,
$\lambda_{4}\in\mathbb{R}$ satisfying

$S_{1}(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4})\geq
0\quad\text{and}\quad
S_{2}(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4})\geq 0,$

but it is not clear whether or not these conditions are tight (i.e., whether
or not, given $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$, $\lambda_{4}$
satisfying this pair of inequalities, we can construct
$X\in\mathcal{I}_{2,4}^{\circ}$ with these eigenvalues). We present a
computational method in Section 3.1 that can be used to construct a matrix
$X\in\mathcal{I}_{k,n}^{\circ}$ with a given spectrum. This method numerically
suggests that Theorem 2 might be tight in the $k=2$, $n=4$ case, but a proof
remains elusive.

###  3.1 A Computational Method for Construction

We now present a numerical method that attempts to construct a $k$-locally PSD
matrix with a given spectrum
$\bm{\lambda}=(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})$ satisfying
Inequalities (4). This algorithm is adapted from the method of [CG05, Section
3.2.4] for numerically constructing a matrix with specified eigenvalues in a
given affine space of matrices.

Our goal is to construct a matrix that is in both the set
$\mathcal{I}_{k,n}^{\circ}$ of matrices that are $k$-locally PSD, and also the
set $M(\bm{\lambda})$ of matrices with the given spectrum:

$M(\bm{\lambda})\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\big{\\{}U\mathrm{diag}(\bm{\lambda})U^{*}:U\text{ is
unitary}\big{\\}}.$

To find such a matrix, we try to compute

$\displaystyle\min_{X\in\mathcal{I}_{k,n}^{\circ},Y\in
M(\bm{\lambda})}\|X-Y\|_{\textup{F}}.$ (5)

(Here we have used the Frobenius norm, but many other matrix norms like the
operator or trace norm would work just as well for our purposes.)

Indeed, there exists a matrix in
$M(\bm{\lambda})\cap\mathcal{I}_{k,n}^{\circ}$ if and only if this quantity
equals $0$. Computing the quantity in Equation (5) explicitly is difficult due
to the fact that $M(\bm{\lambda})$ is not convex. However, we can approximate
it by iteratively bouncing back and forth between $M(\bm{\lambda})$ and
$\mathcal{I}_{k,n}^{\circ}$, decreasing the value of the quantity (5) at each
step, as illustrated schematically in Figure 1.

Figure 1: A schematic of an iterative algorithm for finding a matrix in
$M(\bm{\lambda})\cap\mathcal{I}_{k,n}^{\circ}$ by bouncing back and forth
between $M(\bm{\lambda})$ and $\mathcal{I}_{k,n}^{\circ}$.

More explicitly, we let $Y_{0}\in M(\bm{\lambda})$ be a random matrix with the
desired spectrum (obtained by choosing $U$ to be a random unitary matrix and
setting $Y_{0}=U\mathrm{diag}(\bm{\lambda})U^{*}$, for example). We then set
$j=1$ and proceed as follows:

  * •

Let

$X_{j}:=\operatorname*{argmin}_{X\in\mathcal{I}_{k,n}^{\circ}}\|X-Y_{j-1}\|_{\textup{F}}.$

We note that, since $\mathcal{I}_{k,n}^{\circ}$ is semidefinite-representable,
$X_{j}$ can be computed via a semidefinite program (we direct the interested
reader to any number of standard references, like [Wat18], for an introduction
to semidefinite programming). In particular, $X_{j}$ can be computed via the
following semidefinite program:

minimize: $\displaystyle\ \operatorname{Tr}(Z)$ subject to: $\displaystyle\
\begin{bmatrix}I_{n}&X-Y_{j-1}\\\ X-Y_{j-1}&Z\end{bmatrix}\succeq O$
$\displaystyle\ [X]_{J,J}\succeq O\text{ for each }J\subseteq[n]\text{ with
}|J|=k,$

where $[n]=\\{1,2,\ldots,n\\}$ and $[X]_{J,J}$ is the $|J|\times|J|$ principal
submatrix of $X$ that is obtained by taking the rows and columns of $X$
indexed by the members of $J$. The constraint that $[X]_{J,J}\succeq O$ for
each $J\subseteq[n]$ with $|J|=k$ is simply equivalent to
$X\in\mathcal{I}_{k,n}^{\circ}$. Furthermore, standard facts about Schur
complements imply that, in this semidefinite program, we have
$\operatorname{Tr}(Z)=\|X-Y_{j-1}\|_{\textup{F}}^{2}$.

  * •

Let

$Y_{j}:=\operatorname*{argmin}_{Y\in
M(\bm{\lambda})}\|X_{j}-Y\|_{\textup{F}}.$

It follows from the equality condition of the Hoffman–Wielandt inequality
[HW53] (which gives a lower bound for the Frobenius norm of the difference of
two normal matrices) that if $X_{j}$ has spectral decomposition
$X_{j}=UDU^{*}$, then $Y_{j}=U\Lambda U^{*}$, where $\Lambda$ is the diagonal
matrix with diagonal entries $\lambda_{1}$, $\lambda_{2}$, $\ldots$,
$\lambda_{n}$ arranged in the same relative order as the diagonal entries of
$D$ (e.g., if the diagonal entries of $D$ are arranged largest-to-smallest,
then so should be the diagonal entries of $\Lambda$).

  * •

Increment $j$ by $1$ and return to the first bullet point, or stop once the
difference between $\|X_{j}-Y_{j}\|_{\textup{F}}$ and
$\|X_{j-1}-Y_{j-1}\|_{\textup{F}}$ falls below some threshold (i.e., once the
algorithm has converged).

The above algorithm always terminates, since the sequence of values
$\|X_{j}-Y_{j}\|_{\textup{F}}$ monotonically decreases:

$\|X_{j}-Y_{j}\|_{\textup{F}}\leq\|X_{j}-Y_{j-1}\|_{\textup{F}}\leq\|X_{j-1}-Y_{j-1}\|_{\textup{F}}\quad\text{for
all}\quad j\in\mathbb{N}.$

It is not clear whether or not the sequence of values
$\|X_{j}-Y_{j}\|_{\textup{F}}$ always decreases _to zero_ (thus giving a
matrix in the intersection $M(\bm{\lambda})\cap\mathcal{I}_{k,n}^{\circ}$)
when $\bm{\lambda}$ satisfies Inequalities (4), but we have implemented this
method in MATLAB [Joh22] via the CVX package [GB14], and numerical tests
suggest that it works quite well in practice. We illustrate with an example.

######  Example 1.

Consider the problem of constructing a $4\times 4$ matrix $X$ that is
$2$-locally PSD with spectrum $\bm{\lambda}=(10,4,-1,-2)$. Since
$S_{1}(10,4,-1,-2)=11\geq 0$ and $S_{2}(10,4,-1,-2)=0$, Inequalities (4) hold
so we are hopeful that this might be possible.

After running the algorithm described above for 1,000 iterations, we find the
following matrix:

$X\approx\begin{bmatrix}1.1278&0.0384+1.5436i&-0.9027+1.9431i&1.9983+0.4081i\\\
0.0384-1.5436i&2.1138&-0.7119+2.8455i&-1.1455+2.5464i\\\
-0.9027-1.9431i&-0.7119-2.8455i&4.0701&2.9167-2.5504i\\\
1.9983-0.4081i&-1.1455-2.5464i&2.9167+2.5504i&3.6882\end{bmatrix}.$

It is straightforward to check that (within numerical precision) the
eigenvalues of $X$ are indeed $10$, $4$, $-1$, and $-2$, and every $2\times 2$
principal submatrix of $X$ is positive semidefinite (so $X$ is $2$-locally
PSD).

###  3.2 Hyperbolic Cones

One way of rephrasing Theorem 2 is as saying that the spectrum of every
$k$-locally PSD matrix $X\in\mathcal{I}_{k,n}^{\circ}$ is a member of the cone

$\displaystyle C_{k}\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\big{\\{}\bm{\lambda}\in\mathbb{R}^{n}:S_{j}(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\geq
0\ \text{for all}\ 1\leq j\leq k\big{\\}},$ (6)

where $S_{j}$ is the $j$-th elementary symmetric polynomial from Equation (3).
This cone $C_{k}$ is invariant under permutation of the entries of
$\bm{\lambda}$, and it is furthermore closed and convex. However, convexity is
not obvious, and follows from the fact that it is a hyperbolic cone—an object
that has developed significant interest in its own right recently [Brä14,
Ren06, SP15]. We now provide a brief introduction to hyperbolicity cones, and
we show that $C_{k}$ really is a hyperbolicity cone, and is thus convex.

######  Definition 2.

A homogeneous polynomial $P$ of degree $m\in\mathbb{N}$ (i.e.
$P(\alpha\mathbf{x})=\alpha^{m}P(\mathbf{x})$ for all $\alpha\in\mathbb{R}$
and $\mathbf{x}\in\mathbb{R}^{n}$) called hyperbolic with respect to direction
$\mathbf{d}\in\mathbb{R}^{n}$ if the univariate polynomial
$p(t):=P(\mathbf{x}+t\mathbf{d})$ has all roots real for every
$\mathbf{x}\in\mathbb{R}^{n}$.

We can expand $P(\mathbf{x}+t\mathbf{d})$ as

$P(\mathbf{x}+t\mathbf{d})=P(\mathbf{d})\big{(}t^{m}+P_{1}(\mathbf{x})t^{m-1}+P_{2}(\mathbf{x})t^{m-2}+\cdots+P_{m-1}(\mathbf{x})t+P_{m}(\mathbf{x})\big{)},$
(7)

for some polynomials $P_{i}(\mathbf{x})$ ($1\leq i\leq m$) that are
homogeneous of degree $i$. Then the hyperbolicity cone of $P$ with respect to
the direction $\mathbf{d}$, denoted by $\Lambda(P,\mathbf{d})$, is the set
[Ren06, Theorem 20]

$\Lambda(P,\mathbf{d})\stackrel{{\scriptstyle\smash{\textnormal{\tiny
def}}}}{{=}}\\{\mathbf{x}\in\mathbb{R}^{n}:P_{i}(\mathbf{x})\geq
0\quad\text{for all}\quad 1\leq i\leq m\\}.$ (8)

If we choose $P(\mathbf{x})=S_{n}(\mathbf{x})=x_{1}x_{2}\cdots x_{n}$ then $P$
is homogeneous of degree $n$ with respect to the direction
$\mathbf{d}=\bm{1}=(1,1,\ldots,1)$, since the univariate polynomial
$p(t)=S_{n}(\mathbf{x}+t\bm{1})=\prod_{i=1}^{n}(x_{i}+t)$ has all roots real.
Expanding $S_{n}$ as in Equation (7) then gives

$S_{n}(\mathbf{x}+t\bm{1})=t^{n}+S_{1}(\mathbf{x})t^{n-1}+\cdots+S_{n-1}(\mathbf{x})t+S_{n}(\mathbf{x}),$
(9)

where $S_{j}(\mathbf{x})$ is the elementry symmetric polynomial from Equation
(3). Equation (8) then tells us that the hyperbolicity cone of $S_{n}$ in the
direction of $\bm{1}$ is

$\Lambda(S_{n},\bm{1})=\\{\mathbf{x}\in\mathbb{R}^{n}:S_{k}(\mathbf{x})\geq
0\quad\text{for all}\quad 1\leq k\leq n\\},$

which is the cone $C_{n}$ from Equation (6). We thus conclude that $C_{n}$ is
a hyperbolic cone.

We can similarly see that $C_{k}$ is a hyperbolicity cone for all $1\leq k\leq
n-1$ by using directional derivatives, as follows. If $P$ is hyperbolic with
respect to the direction $\mathbf{d}$, then the directional derivative of $P$
in the direction of $\mathbf{d}$,

$p^{\prime}(0)=\frac{d}{dt}P(\mathbf{x}+t\mathbf{d})\Big{|}_{t=0},$

is also hyperbolic with respect to $\mathbf{d}$ [Gar59]. If we let $P^{(k)}$
denote the $k$-th directional derivative of $S_{n}$ in the direction of
$\bm{1}$, then straightforward computation from Equation (9) shows that

$P^{(k)}(\mathbf{x}+t\bm{1})=c_{n-k}t^{n-k}+c_{n-k-1}S_{1}(\mathbf{x})t^{n-k-1}+\cdots+c_{1}S_{n-k-1}(\mathbf{x})t+c_{0}S_{n-k}(\mathbf{x}),$

where $c_{i}=(i+k)!/i!$. Since $c_{i}>0$, it then follows from Equation (8)
that the hyperbolicity cone of $P^{(k)}$ with respect to the direction
$\bm{1}$ is

$\Lambda(P^{(k)},\bm{1})=\\{\mathbf{x}\in\mathbb{R}^{n}:S_{j}(\mathbf{x})\geq
0\quad\text{for all}\quad 1\leq j\leq n-k\\},$

which is exactly the cone $C_{k}$ from Equation (6). We thus conclude that
$C_{k}$ is a hyperbolicity cone for all $1\leq k\leq n$, and is thus convex by
[Gar59, Theorem 2].

##  4 Absolute k-Incoherence

We now explore the central question of our work: Which quantum states can be
determined to be $k$-incoherent based only on their spectrum (or equivalently,
which matrices can be shown to have factor width at most $k$ based only on
their spectrum)?

######  Definition 3.

A mixed quantum state $\rho\in M_{n}^{+}$ is absolutely
$\mathbf{k}$-incoherent if $U\rho U^{*}\in\mathcal{I}_{k,n}$ for all unitary
matrices $U\in M_{n}$.

We note that absolute $k$-incoherence is trivial if $k=1$, since the only
absolutely $1$-incoherent state is the maximally mixed state $\rho=I/n$ (a
fact that follows immediately from the spectral decomposition and the fact
that $\mathcal{I}_{1,n}$ is the set of diagonal density matrices). The other
extreme is also trivial: if $k=n$ then $\mathcal{I}_{n,n}$ is the set of _all_
density matrices, so every mixed quantum state is absolutely $n$-incoherent.

However, if $2\leq k\leq n-1$ then the set of absolutely $k$-incoherent states
is non-trivial, and our goal is to characterize this set in a way that makes
membership easy to check. Since absolute $k$-incoherence only depends on the
spectrum of a state, our goal is to find inequalities or other simple-to-check
properties of the spectrum that guarantee that the state is or is not
absolutely $k$-incoherent.

In order to derive bounds on the set of absolutely $k$-incoherent quantum
states, we will use duality of the convex cones $C_{k}$ defined in Equation
(6). In particular, the following result is our starting point:

######  Theorem 3.

Suppose $\rho\in M_{n}^{+}$ and let
$\bm{\lambda}=(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})$ be a vector whose
entries are eigenvalues of $\rho$ (in some order). If $\bm{\lambda}\in
C_{k}^{\circ}$ then $\rho$ is absolutely $k$-incoherent. Furthermore, the
converse holds if $k\in\\{1,n-1,n\\}$.

###### Proof.

Suppose $X\in\mathcal{I}_{k,n}^{\circ}$ and let
$\bm{\mu}=(\mu_{1},\mu_{2},\ldots,\mu_{n})$ be a vector whose entries are the
eigenvalues of $X$. Since $\bm{\lambda}\in C_{k}^{\circ}$, and we know from
Theorem 2 that $\bm{\mu}\in C_{k}$, we conclude that
$\bm{\lambda}\cdot\bm{\mu}\geq 0$. Since $C_{k}$ is invariant under
permutations of its entries, this is equivalent to

$\displaystyle\sum_{j=1}^{n}\lambda_{j}\mu_{\pi(j)}\geq 0$ (10)

for all permutations $\pi:\\{1,2,\ldots,n\\}\rightarrow\\{1,2,\ldots,n\\}$.

It then follows from [Bha97, Problem III.6.14] that this is equivalent to
$\operatorname{Tr}(XU\rho U^{*})\geq 0$ for all unitary matrices $U\in M_{n}$.
Since $X\in\mathcal{I}_{k,n}^{\circ}$ was arbitrary, it follows that $U\rho
U^{*}\in\mathcal{I}_{k,n}$ for all unitary matrices $U\in M_{n}$, which means
exactly that $\rho$ is absolutely $k$-incoherent.

For the “furthermore” statement, we just note that every step in this proof
can be reversed (for all values of $k$), except for the appeal to Theorem 2.
However if $k\in\\{1,n-1,n\\}$ then Theorem 2 does tell us that $\bm{\mu}\in
C_{k}$ implies $\bm{\mu}$ is a vector whose entries are the eigenvalues of
some $X\in\mathcal{I}_{k,n}^{\circ}$, which completes the proof. ∎

Theorem 3 raises a natural question—given a vector of eigenvalues
$\bm{\lambda}$, how can we determine whether or not it is a member of
$C_{k}^{\circ}$ (and thus whether or not the corresponding quantum state is
absolutely $k$-incoherent)? These cones are actively being researched in the
hyperbolic cone literature [Brä14], and recently it was shown that they admit
a polynomial-size semidefinite representation [SP15] (however, the specifics
of that semidefinite representation are rather complicated, so we do not
repeat them here). In particular, this means that membership in
$C_{k}^{\circ}$ can be determined in polynomial time, so the hypotheses of
Theorem 3 can be checked efficiently.

Our next result shows that absolutely $k$-incoherent states must have large
rank (this is analogous to the already-known fact that absolutely separable
states must have large rank [JLNR15, Proposition 7.3]).

######  Theorem 4.

Suppose $\rho\in M_{n}^{+}$ is a quantum state. If
$\operatorname{rank}(\rho)\leq n-k$ then $\rho$ is not absolutely
$k$-incoherent. Furthermore, this bound is tight; the rank-$(n-k+1)$ state
with its non-zero eigenvalues equal to each other is absolutely
$k$-incoherent.

We need the following lemma to help us prove the above theorem. This lemma’s
proof is from [Spe22], but we include it here for completeness.

######  Lemma 2.

Let $1\leq k\leq n$ be integers. If
$S_{j}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n})\geq 0$ for all $1\leq j\leq
k$ then

$S_{j}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n-1})\geq 0\quad\text{for
all}\quad 1\leq j\leq k-1.$

###### Proof.

For brevity, we define
$a_{j}:=S_{j}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n})$ and
$b_{j}:=S_{j}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n-1})$. Our goal is to
show that if $a_{j}\geq 0$ for all $1\leq j\leq k$ then $b_{j}\geq 0$ for all
$1\leq j\leq k-1$. We will prove the contrapositive: we will show that if
there exists $1\leq j\leq k-1$ with $b_{j}<0$ then there exists $1\leq
j^{\prime}\leq k$ with $a_{j^{\prime}}<0$ too.

Without loss of generality, we may assume that $j$ is minimal (i.e.,
$b_{j}<0$, but $b_{1},b_{2},\cdots,b_{j-1}\geq 0$). Consider the following two
cases:

  * Case 1:

$\lambda_{n}<0$. It is straightforward to show that
$a_{j}=\lambda_{n}b_{j-1}+b_{j}$, which must be strictly negative since
$\lambda_{n}<0$, $b_{j}<0$, and $b_{j-1}\geq 0$. That is, we can choose
$j^{\prime}=j$.

  * Case 2:

$\lambda_{n}\geq 0$. As in Case 1, we know that
$a_{j}=\lambda_{n}b_{j-1}+b_{j}$. It follows that if $b_{j-1}\leq 0$ then
$a_{j}<0$. A similar argument shows that if $b_{j+1}\leq 0$ then $a_{j+1}<0$.
We thus assume for the remainder of this Case that $b_{j-1},b_{j+1}>0$. By
using Newton’s inequalities, we see that

$\frac{b_{j-1}b_{j+1}}{\binom{n-1}{j-1}\binom{n-1}{j+1}}\leq\frac{b_{j}^{2}}{\binom{n-1}{j}^{2}},$

which simplifies as

$b_{j-1}b_{j+1}\leq\frac{j(n-j-1)}{(j+1)(n-j)}b_{j}^{2}<b_{j}^{2}.$

Keeping in mind that $b_{j}<0$, this tells us that

$0\leq\frac{b_{j+1}}{-b_{j}}<\frac{-b_{j}}{b_{j-1}}.$

We must either have $\lambda_{n}>\tfrac{b_{j+1}}{-b_{j}}$ or
$\lambda_{n}<\tfrac{-b_{j}}{b_{j-1}}$ (or both). If
$\lambda_{n}>\tfrac{b_{j+1}}{-b_{j}}$ then
$a_{j+1}=\lambda_{n}b_{j}+b_{j+1}<0$ (so we can choose $j^{\prime}=j+1$), and
if $\lambda_{n}<\tfrac{-b_{j}}{b_{j-1}}$ then
$a_{j}=\lambda_{n}b_{j-1}+b_{j}<0$ (so we can choose $j^{\prime}=j$).

With both cases taken care of, the proof is complete. ∎

###### Proof of Theorem 4.

To see that there does not exist an absolutely $k$-incoherent state $\rho$
with $\operatorname{rank}(\rho)\leq n-k$, recall from Theorem 1 that there
exists $X\in\mathcal{I}_{k,n}^{\circ}$ with exactly $n-k$ eigenvalues. If
$\operatorname{rank}(\rho)\leq n-k$ then there exists a unitary matrix $U\in
M_{n}$ so that $U\rho U^{*}$ is supported on that $(n-k)$-dimensional negative
eigenspace, so $\operatorname{Tr}\big{(}X(U\rho U^{*})\big{)}<0$, so $U\rho
U^{*}$ is not $k$-incoherent, so $\rho$ is not absolutely $k$-incoherent.

Now let $\rho$ be the rank-$(n-k+1)$ state with its non-zero eigenvalues equal
to each other. By using Lemma 2 a total of $k-1$ times, we see that
$(\lambda_{1},\ldots,\lambda_{n})\in C_{k}$ implies
$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n-k+1}\geq 0$. In particular, this
means that if $X\in\mathcal{I}_{k,n}^{\circ}$ has eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ then

$\operatorname{Tr}(X\rho)\geq\frac{\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n-k+1}}{n-k+1}\geq
0,$

so $\rho$ is absolutely $k$-incoherent. ∎

Theorem 4 provides us with a single non-trivial example of a mixed state that
is absolutely $k$-incoherent. Our next theorem provides many more:

######  Theorem 5.

Suppose $\rho\in M_{n}^{+}$ has maximal eigenvalue $\lambda_{\text{max}}$. If
$\lambda_{\text{max}}\leq 1/(n-k+1)$ then $\rho$ is absolutely $k$-incoherent.

Once again, we need a lemma to help us prove the above theorem. In fact, we
also need to introduce some additional notation and terminology. Recall that
if $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ then we say that $\mathbf{x}$ is
majorized by $\mathbf{y}$, denoted $\mathbf{x}\prec\mathbf{y}$, if

$\sum_{j=1}^{k}x_{j}^{\downarrow}\leq\sum_{j=1}^{k}y_{j}^{\downarrow}\quad\text{for
all}\quad 1\leq k\leq n,$

with equality when $k=n$, where $x_{j}^{\downarrow}$ refers to the $j$-th
largest entry of $\mathbf{x}$ (i.e., $x_{1}^{\downarrow}\geq
x_{2}^{\downarrow}\geq\cdots\geq x_{n}^{\downarrow}$). Given $X,Y\in
M_{n}^{\textup{H}}$, we say that $X$ is majorized by $Y$, and we write $X\prec
Y$, if the vector of eigenvalues of $X$ is majorized by the vector of
eigenvalues of $Y$.

######  Lemma 3.

Suppose $\rho,\sigma\in M_{n}^{+}$ are such that $\rho\prec\sigma$. If
$\sigma$ is absolutely $k$-incoherent, then so is $\rho$.

###### Proof.

Since $\rho\prec\sigma$, we can use Uhlmann’s Theorem [NV01, Equation (3)] to
see that there exists a probability vector $(p_{1},\cdots,p_{r})$ and a finite
collection of unitary matrices $\\{U_{j}\\}\subset M_{n}$ such that

$\rho=\sum_{j=1}^{r}p_{j}U_{j}\sigma U_{j}^{*}.$

Since $\sigma$ is absolutely $k$-incoherent, so is $U_{j}\sigma U_{j}^{*}$ for
each $1\leq j\leq r$. Since the set of absolutely $k$-incoherent states is
convex, $\rho$ must be absolutely $k$-incoherent too. ∎

It is worth noting that the argument used in the proof of the above lemma
actually works in the “absolute” version of _any_ convex quantum resource
theory, not just that of $k$-coherence [CG19]: the only properties of the set
of absolutely $k$-incoherent states that we used were the facts that it is
convex and invariant under unitary conjugation. In fact, Lemma 3 was noted in
the context of “absolute” versions of resource theories of bipartite sets of
states in [JLNR15, Lemma 2.2], via essentially the same proof.

###### Proof of Theorem 5.

Let $\rho$ be a mixed state with maximal eigenvalue satisfying
$\lambda_{\text{max}}\leq 1/(n-k+1)$, and let $\sigma$ be a mixed state of
rank $n-k+1$ with all of its non-zero eigenvalues equal to $1/(n-k+1)$. We
know from Theorem 4 that $\sigma$ is absolutely $k$-incoherent. Since $\rho$
is majorized by $\sigma$, it follows from Lemma 3 that $\rho$ is absolutely
$k$-incoherent. ∎

We now look at how we can simplify Theorem 3, and make it more explicit, for
certain specific values of $k$. In particular, we will focus on how we can
characterize the dual cones $C_{k}^{\circ}$ in a way that makes membership in
them easy to check in the $k\leq 2$ and $k\geq n-1$ cases.

It is straightforward to show that the dual cones of $C_{1}$ and $C_{n}$
satisfy $C_{1}^{\circ}=\\{c\bm{1}:c\geq 0\\}\subseteq\mathbb{R}^{n}$, where
$\bm{1}=(1,1,\ldots,1)$, and $C_{n}^{\circ}=C_{n}\subseteq\mathbb{R}^{n}$ is
the set of vectors with non-negative entries, which recovers our earlier
observations about the sets of absolutely $1$-incoherent and absolutely
$n$-incoherent states being trivial. The next two subsections are devoted to
the less straightforward $k=2$ and $k=n-1$ cases.

###  4.1 Absolute 2-Incoherence

The following theorem completely characterizes the dual cone of $C_{k}$ in the
$k=2$ case. The norm $\|\bm{\lambda}\|$ that is used in it is the standard
Euclidean norm on $\mathbb{R}^{n}$:
$\|\bm{\lambda}\|:=\sqrt{\sum_{j=1}^{n}\lambda_{j}^{2}}$.

######  Theorem 6.

Let $C_{2}$ be as defined in Equation (6). Then

$C_{2}^{\circ}=\left\\{\bm{\lambda}\in\mathbb{R}^{n}:\sum_{j=1}^{n}\lambda_{j}\geq\sqrt{n-1}\|\bm{\lambda}\|\quad\text{and}\quad\lambda_{j}\geq
0\ \text{for all}\ 1\leq j\leq n\right\\}.$

###### Proof.

We can rewrite $C_{2}$ in the following form:

$C_{2}=\big{\\{}\bm{\lambda}\in\mathbb{R}^{n}:\|\bm{\lambda}\|\leq\bm{\lambda}\cdot\bm{1}\big{\\}}=\left\\{\bm{\lambda}\in\mathbb{R}^{n}:\frac{1}{\sqrt{n}}\|\bm{\lambda}\|\leq\bm{\lambda}\cdot\big{(}\bm{1}/\sqrt{n}\big{)}\right\\},$

where $\bm{1}=(1,1,\ldots,1)\in\mathbb{R}^{n}$. It follows that $C_{2}$ is a
circular cone [ZC13] with angle $\theta$ satisfying $\cos(\theta)=1/\sqrt{n}$
(the referenced paper deals primarily with circular cones centered around
$\mathbf{e_{1}}:=(1,0,0,\ldots,0)$, whereas ours is rotated to be centered
around the unit vector $\bm{1}/\sqrt{n}$). It follows from [ZC13, Theorem
2.1(c)] that the dual of $C_{2}$ is the circular cone centered around
$\bm{1}/\sqrt{n}$ with angle $\pi/2-\theta$. That is,

$C_{2}^{\circ}=\Big{\\{}\bm{\lambda}\in\mathbb{R}^{n}:\cos\big{(}\pi/2-\arccos(1/\sqrt{n})\big{)}\|\bm{\lambda}\|_{2}\leq\bm{\lambda}\cdot\big{(}\bm{1}/\sqrt{n}\big{)}\Big{\\}}.$

Using the fact that
$\cos\big{(}\pi/2-\arccos(1/\sqrt{n})\big{)}=\sqrt{1-1/n}$, and then
rearranging and simplifying, shows that $C_{2}^{\circ}$ has the form described
in the statement of the theorem. ∎

By combining Theorem 6 with our earlier results, we immediately get simple-to-
check sufficient condition for absolute $2$-incoherence. Furthermore, this
condition is both necessary and sufficient in small dimensions:

######  Theorem 7.

Suppose $\rho\in M_{n}^{+}$ is a quantum state with eigenvalues $\lambda_{1}$,
$\lambda_{2}$, $\ldots$, $\lambda_{n}$. If

$\sum_{j=1}^{n}\lambda_{j}^{2}\leq\frac{1}{n-1}$

then $\rho$ is absolutely $2$-incoherent. The converse holds if $n\leq 3$.

###### Proof.

If $(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\in C_{2}^{\circ}$ then
Theorem 3 tells us that $\rho$ is absolutely $2$-incoherent. By Theorem 6,
membership in $C_{2}^{\circ}$ is equivalent to

$\left(\sum_{j=1}^{n}\lambda_{j}\right)^{2}\geq(n-1)\sum_{j=1}^{n}\lambda_{j}^{2},$

which (when we use the fact that $\sum_{j=1}^{n}\lambda_{j}=1$ since
$\operatorname{Tr}(\rho)=1$) is equivalent to the inequality given in the
statement of this theorem.

To see that the converse holds when $n=2$, recall that every mixed state is
absolutely $2$-incoherent in this case, and for every mixed state we have

$\sum_{j=1}^{n}\lambda_{j}^{2}=\|\rho\|_{\textup{F}}^{2}\leq\|\rho\|_{\textup{tr}}^{2}=1=\frac{1}{n-1},$

where $\|\rho\|_{\textup{F}}$ and $\|\rho\|_{\textup{tr}}$ are the Frobenius
and trace norms of $\rho$, respectively.

To see that the converse holds when $n=3$, recall from Theorem 2 that every
$\bm{\mu}=(\mu_{1},\mu_{2},\mu_{3})\in C_{2}$ occurs as a vector of
eigenvalues of some matrix $X\in\mathcal{I}_{2,3}^{\circ}$. Working through
the proof of Theorem 3 backwards then shows that if $\rho$ is absolutely
$2$-incoherent then Inequality (10) holds for _all_ $\bm{\mu}\in C_{2}$, so
$\bm{\lambda}\in C_{2}^{\circ}$. ∎

It is worth noting that the inequality in the above theorem is equivalent to
$\|\rho\|_{\textup{F}}^{2}\leq 1/(n-1)$. Alternatively, this is equivalent
(again, via the fact that $\sum_{j=1}^{n}\lambda_{j}=1$) to

$\left\|\left(\frac{n-1}{n}\right)\rho-\frac{1}{n}I\right\|_{\textup{F}}\leq\frac{1}{n}.$

In particular, if $n=3$ then we see that $\rho$ is absolutely $2$-incoherent
if and only if $\big{\|}(2/3)\rho-I/3\big{\|}_{\textup{F}}\leq 1/3$, so the
set of absolutely $2$-incoherent states is simply a ball (in the Frobenius
norm) centered at the maximally mixed state $I/3$. This is in stark contrast
with the absolute _separability_ problem, where there are indeed Frobenius
balls of absolutely separable states [GB02], but there are also absolutely
separable states in no such ball even in the smallest non-trivial dimensions
[KŻ01].

###  4.2 Absolute $(n-1)$-Incoherence

When $k=n-1$, Theorem 3 says that $\rho$ is absolutely $k$-incoherent if and
only if its vector of eigenvalues $\bm{\lambda}$ satisfies $\bm{\lambda}\in
C_{k}^{\circ}$. The following theorem illustrates how to efficiently test
whether or not $\bm{\lambda}\in C_{k}^{\circ}$, thus giving us an effective
test for absolute $(n-1)$-incoherence.

######  Theorem 8.

Suppose $\rho\in M_{n}^{+}$ is a quantum state with eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. Then $\rho$ is
absolutely $(n-1)$-incoherent if and only if there exists a positive
semidefinite matrix $\Lambda\in M_{n}^{+}(\mathbb{R})$ such that

$\displaystyle\lambda_{1}$
$\displaystyle=-\Lambda_{1,1}-\sum_{i=2}^{n}\left(\Lambda_{1,i}+\Lambda_{i,1}\right)\quad\text{and}\quad\lambda_{j}=\Lambda_{j,j}\
\ \ \text{for ${}\ 2\leq j\leq n$}.$

###### Proof.

By Theorem 3, we know that $\rho$ is absolutely $(n-1)$-incoherent if and only
if $\bm{\lambda}=(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\in
C_{n-1}^{\circ}$. This cone was characterized in [Zin08, Proposition 4.2],
which says that

$C_{n-1}^{\circ}=\bigcap_{i=1}^{n}{C^{i}}^{\circ},$

where

${C^{i}}^{\circ}=\left\\{\mathbf{y}\in\mathbb{R}^{n}:~{}-y_{i}=\sum_{k\neq
i}(\Lambda_{k,i}+\Lambda_{i,k})+\Lambda_{i,i},~{}~{}y_{j}=\Lambda_{j,j}~{}~{}\text{for}~{}~{}j\neq
i,~{}~{}\Lambda\ \text{is positive semidefinite}\right\\}.$

Since vectors in each of the ${C^{i}}^{\circ\circ}=C^{i}$ cones can have at
most $1$ negative entry (the $i$-th entry, as was discussed in [Zin08, Section
4]), are identical up to permutation of their entries, and we have sorted the
entries of $\bm{\lambda}$ so that its first entry is its largest, we conclude
that $\bm{\lambda}\in\bigcap_{i=1}^{n}{C^{i}}^{\circ}$ is equivalent to
$\bm{\lambda}\in{C^{1}}^{\circ}$. This completes the proof. ∎

The characterization of absolute $(n-1)$-incoherence that is provided by
Theorem 8 is straightforward to check numerically via semidefinite
programming. We provide MATLAB code that implements this semidefinite program,
and thus checks whether or not a given quantum state is absolutely
$(n-1)$-incoherent, via the CVX package [GB14] at [Joh22].

Theorem 8 can also be used to derive more explicit tests for absolute
$(n-1)$-incoherence, at the expense of no longer being both necessary and
sufficient. For example, we have the following necessary condition, which is a
stronger version of the observation that no pure states can possibly be
absolutely $k$-incoherent when $k\leq n-1$:

######  Corollary 1.

Suppose $\rho\in M_{n}^{+}$ is a quantum state maximal eigenvalue
$\lambda_{\text{max}}$. If $\rho$ is absolutely $(n-1)$-incoherent then

$\displaystyle\lambda_{\text{max}}\leq 1-\frac{1}{n}.$

###### Proof of Corollary 1..

Let $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0$ denote the
eigenvalues of $\rho$ (so that, in particular,
$\lambda_{1}=\lambda_{\text{max}}$). If $\rho$ is absolutely
$(n-1)$-incoherent then a matrix $\Lambda$ as described by Theorem 8 exists.
Since $\Lambda$ is positive semidefinite, so are its $2\times 2$ principal
submatrices, so we must have

$|\Lambda_{1,j}|^{2}\leq\Lambda_{1,1}\Lambda_{j,j}=\lambda_{j}\left(-\lambda_{1}-\sum_{i=2}^{n}\left(\Lambda_{1,i}+\Lambda_{i,1}\right)\right)$

for all $2\leq j\leq n$. If we move $\lambda_{1}$ to the left-hand side and
then sum over $j$, this tells us that

$\lambda_{1}\sum_{j=2}^{n}\lambda_{j}\leq-\sum_{j=2}^{n}\left(|\Lambda_{1,j}|^{2}+\lambda_{j}\sum_{i=2}^{n}\left(\Lambda_{1,i}+\Lambda_{i,1}\right)\right)=-\sum_{i=2}^{n}\left(|\Lambda_{1,i}|^{2}+\left(\sum_{j=2}^{n}\lambda_{j}\right)(\Lambda_{1,i}+\Lambda_{i,1})\right).$

Standard calculus-based optimization techniques show that the quantity on the
right (if regarded as a function in the $n-1$ variables $\Lambda_{1,i}$, for
$2\leq i\leq n$) is maximized exactly when
$\Lambda_{1,2}=\cdots=\Lambda_{1,n}=-\sum_{j=2}^{n}\lambda_{j}$, and its
maximal value is $(n-1)\left(\sum_{j=2}^{n}\lambda_{j}\right)^{2}$.
Simplifying then shows that

$\displaystyle\lambda_{1}\leq(n-1)\sum_{j=2}^{n}\lambda_{j}.$ (11)

Finally, if we use the fact that
$\operatorname{Tr}(\rho)=\sum_{j=1}^{n}\lambda_{j}=1$, then we see that
$\sum_{j=2}^{n}\lambda_{j}=1-\lambda_{1}$. Plugging this equation into
Inequality 11 gives us the inequality in the statement of the theorem. ∎

Unlike Theorem 8, Corollary 1 really is just a necessary condition for
absolute $(n-1)$-incoherence. This is illustrated by the state
$\rho=\mathrm{diag}(2/3,1/3,0)\in M_{3}^{+}$, which satisfies the hypotheses
of Corollary 1, but is not absolutely $(n-1)=2$-incoherent (as can be seen
from Theorem 7). However, Corollary 1 is still tight, in the sense that it is
the best possible inequality depending only on $\lambda_{1}$ and
$\operatorname{Tr}(\rho)$:

######  Example 2.

Suppose $X\in M_{n}^{+}$ has eigenvalues $c\geq 1$ with multiplicity $1$, and
$1$ with multiplicity $n-1$. We claim that the quantum state
$\rho=X/\operatorname{Tr}(X)$ is absolutely $(n-1)$-incoherent if and only if
$c\leq(n-1)^{2}$.

To see that $c=(n-1)^{2}$ implies absolute $(n-1)$-incoherence, choose the
matrix $\Lambda$ in Theorem 8 to be $\Lambda=DJD^{*}/\operatorname{Tr}(X)$,
where $J$ is the all-ones matrix (which is positive semidefinite, so $\Lambda$
is too) and $D=\mathrm{diag}(1-n,1,1,\ldots,1)$. Then
$\lambda_{j}=\Lambda_{j,j}=1/\operatorname{Tr}(X)$ for $2\leq j\leq n$ and

$\lambda_{1}=-\Lambda_{1,1}-\sum_{i=2}^{n}\left(\Lambda_{1,i}+\Lambda_{i,1}\right)=\frac{1}{\operatorname{Tr}(X)}\big{(}-(n-1)^{2}+2(n-1)^{2}\big{)}=\frac{c}{\operatorname{Tr}(X)},$

so Theorem 8 tells us that $\rho$ is absolutely $(n-1)$-incoherent. The fact
that $1\leq c<(n-1)^{2}$ implies absolute $(n-1)$-incoherence then follows
from convexity.

Conversely, if $\rho$ is absolutely $(n-1)$-incoherent then Corollary 1
applies, so we must have
$c/\operatorname{Tr}(X)=\lambda_{1}\leq(n-1)\sum_{j=2}^{n}\lambda_{j}/\operatorname{Tr}(X)=(n-1)^{2}/\operatorname{Tr}(X)$,
so $c\leq(n-1)^{2}$.

We already saw an explicit _sufficient_ (rather than necessary) condition for
absolute $(n-1)$-incoherence back in Theorem 5: plugging $k=n-1$ into that
theorem tells us that if the maximal eigenvalue $\lambda_{\text{max}}$ of a
quantum state $\rho\in M_{n}^{+}$ satisfies

$\lambda_{\text{max}}\leq\frac{1}{2}$

then $\rho$ must be absolutely $(n-1)$-incoherent. We summarize these
observations in Figure 2.

$\lambda_{\text{max}}$:$0$$\frac{1}{n}$$\frac{1}{2}$$1-\frac{1}{n}$$1$impossibleTheorem
5:abs. $(n-1)$-incoherentExample 2:maybe abs. $(n-1)$-incoherentCorollary
1:not abs. $(n-1)$-incoh.maximally mixed state Figure 2: How the maximal
eigenvalue $\lambda_{\text{max}}$ of a quantum state $\rho\in M_{n}^{+}$
relates to its absolute $(n-1)$-incoherence.

It is clear that any state $\rho\in M_{n}^{+}$ that is $k$-incoherent will
still be $k$-incoherent if we regard it as a member of $M_{n+1}^{+}$ by adding
rows and columns of zeroes. The following result shows that, perhaps
surprisingly, an even stronger statement is true of _absolute_
$k$-incoherence, at least when $k=n-1$:

######  Corollary 2.

A quantum state $\rho\in M_{n}^{+}$ is absolutely $(n-1)$-incoherent if and
only if the state $\widetilde{\rho}\in M_{n+1}^{+}$, obtained by appending a
row and column of zeros, is absolutely $n$-incoherent.

###### Proof.

This follows immediately from Theorem 8: if $\rho$ is absolutely
$(n-1)$-incoherent then there exists a positive semidefinite matrix
$\Lambda\in M_{n}^{+}$ satisfying the constraints described by that theorem.
Simply appending a row and column of zeros to $\Lambda$ to obtain a new matrix
$\widetilde{\Lambda}\in M_{n+1}^{+}$ shows, again via Theorem 8, that
$\widetilde{\rho}$ is absolutely $n$-incoherent.

Conversely, if $\widetilde{\rho}\in M_{n+1}^{+}$ is absolutely $n$-incoherent
and has its last row and column consisting entirely of zeros, then the matrix
$\widetilde{\Lambda}\in M_{n+1}^{+}$ described by Theorem 8 must have
$\Lambda_{n+1,n+1}=0$ and thus its last row and column must consist entirely
of zeros. Erasing that final row and column then gives a matrix $\Lambda\in
M_{n}^{+}$ that shows, again via Theorem 8, that $\rho$ is absolutely
$(n-1)$-incoherent. ∎

##  5 Conclusions and Open Questions

In this work, we explored spectral problems of interest in the quantum
resource theory of $k$-coherence. In particular, we introduced $k$-locally PSD
matrices as witnesses of $k$-coherence, and we derived bounds on the spectra
of $k$-locally PSD matrices. We also introduced the set of _absolutely_
$k$-incoherent quantum states, and used our spectral bounds for $k$-locally
PSD matrices to produce bounds on the set of $k$-incoherent quantum states.

While we have solved numerous problems, our work leaves open many questions
and avenues for future research:

  * •

The computational method of Section 3.1 for constructing $k$-locally PSD
matrices with a given spectrum seems to work well in practice. Are there
conditions under which it is _guaranteed_ to work (i.e., the iteration is
guaranteed to converge to a $k$-locally PSD matrix with the desired spectrum)?

  * •

We established numerous results about the spectrum of $k$-locally PSD matrices
and absolute $k$-incoherence. Since there is a connection between
$k$-incoherence and $k$-entanglement [SSD+15], it seems natural to ask whether
or not any of our results can be extended in a useful way to the spectrum of
$k$-entanglement witnesses and absolute $k$-entanglement.

  * •

Theorem 7 gives a sufficient condition for absolute $2$-incoherence that is
also necessary in dimension $n=3$. It is unclear whether or not it is
necessary in dimension $n=4$ or higher. Similarly, we expect that the
“conversely” statements of Theorems 2 and 3 are false when $n$ and/or $k$ are
large enough, but we do not have any explicit examples to demonstrate this.

  * •

Theorem 8 shows that absolute $(n-1)$-incoherence can be determined in
polynomial time. Is the same true of absolute $k$-incoherence for all $1\leq
k\leq n$? It is worth noting that the set of “absolutely PPT states” [Hil07]
(which we do not define here) has a similar semidefinite representation, but
membership in that set is not known to be checkable in polynomial time since
the number of matrix inequalities that need to be checked grows exponentially.

  * •

Does Corollary 2 hold for $k$-incoherence when $k\neq n-1$? That is, is it
true that absolute $k$-incoherence of $\rho\in M_{n}^{+}$ is equivalent to
absolute $(k+1)$-incoherence of $\widetilde{\rho}\in M_{n+1}^{+}$?

Acknowledgements. The authors thank David E. Speyer for providing the proof of
Lemma 2 [Spe22]. We would also like to thank the authors of [BDSS22] for
bringing our attention to this paper. N.J. was supported by NSERC Discovery
Grants RGPIN-2016-04003 and RGPIN-2022-04098. S.M. acknowledges hospitality
from Mount Allison University during her postdoctoral fellowship. R.P. was
supported by NSERC Discovery Grant number 400550. S.P. was supported by NSERC
Discovery Grant number 1174582, the Canada Foundation for Innovation (CFI)
grant number 35711, and the Canada Research Chairs (CRC) Program grant number
231250.

## References

  * [AJR15] S. Arunachalam, N. Johnston, and V. Russo.  Is absolute separability determined by the partial transpose?  Quantum Information & Computation, 15:694–720, 2015.
  * [BCPT05] E. G. Boman, D. Chen, O. Parekh, and S. Toledo.  On factor width and symmetric H-matrices.  Linear Algebra and its Applications, 405:239–248, 2005.
  * [BDSS22] Grigoriy Blekherman, Santanu S Dey, Kevin Shu, and Shengding Sun.  Hyperbolic relaxation of k-locally positive semidefinite matrices.  SIAM Journal on Optimization, 32(2):470–490, 2022.
  * [Bha97] R. Bhatia.  Matrix Analysis.  Springer, 1997.
  * [Brä14] P. Brändén.  Hyperbolicity cones of elementary symmetric polynomials are spectrahedral.  Optimization Letters, 8(5):1773–1782, 2014.
  * [BV04] S. Boyd and L. Vandenberghe.  Convex optimization.  Cambridge University Press, 2004.
  * [CG05] M. T. Chu and G. H. Golub.  Inverse Eigenvalue Problems: Theory, Algorithms, and Applications.  Oxford University Press, 2005.
  * [CG19] E. Chitambar and G. Gour.  Quantum resource theories.  Reviews of Modern Physics, 91:025001, 2019.
  * [CJMP22] G. Champagne, N. Johnston, M. MacDonald, and L. Pipes.  Spectral properties of symmetric quantum states and symmetric entanglement witnesses.  Linear Algebra and its Applications, 649:273–300, 2022.
  * [CMW08] T. S. Cubitt, A. Montanaro, and A. Winter.  On the dimension of subspaces with bounded Schmidt rank.  Journal of Mathematical Physics, 49:022107, 2008.
  * [EAO+02] A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek.  Direct estimations of linear and nonlinear functionals of a quantum state.  Physical Review Letters, 88:217901, 2002.
  * [Gar59] L. Garding.  An inequality for hyperbolic polynomials.  Journal of Mathematics and Mechanics, 8(6):957–965, 1959.
  * [GB02] L. Gurvits and H. Barnum.  Largest separable balls around the maximally mixed bipartite quantum state.  Physical Review A, 66:062311, 2002.
  * [GB14] M. Grant and S. Boyd.  CVX: MATLAB software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, March 2014.
  * [Hil07] R. Hildebrand.  Positive partial transpose from spectra.  Physical Review A, 76:052325, 2007.
  * [HJ13] R. A. Horn and C. R. Johnson.  Matrix Analysis (2nd edition).  Cambridge University Press, 2013.
  * [HW53] A. J. Hoffman and H. W. Wielandt.  The variation of the spectrum of a normal matrix.  Duke Mathematical Journal, 20:37–39, 1953.
  * [JLNR15] M. A. Jivulescu, N. Lupa, I. Nechita, and D. Reeb.  Positive reduction from spectra.  Linear Algebra and its Applications, 469:276–304, 2015.
  * [Joh13] N. Johnston.  Separability from spectrum for qubit–qudit states.  Physical Review A, 88:062330, 2013.
  * [Joh22] N. Johnston.  MATLAB code for k-factor positivity and absolute k-incoherence.  http://www.njohnston.ca/publications/absolute-k-incoherence/. Also available in the “source” files for the arXiv version of this paper, 2022\.
  * [KT16] O. Kushel and M. Tyaglov.  Circulants and critical points of polynomials.  Journal of Mathematical Analysis and Applications, 439(2):634–650, 2016.
  * [KŻ01] M. Kuś and K. Życzkowski.  Geometry of entangled states.  Physical Review A, 63:032307, 2001.
  * [LBT19] Z.W. Liu, K. Bu, and R. Takagi.  One-shot operational quantum resource theory.  Physical review letters, 123(2):020401, 2019.
  * [LLC+12] C.M. Li, N. Lambert, Y.N. Chen, G.Y. Chen, and F. Nori.  Witnessing quantum coherence: from solid-state to biological systems.  Scientific Reports, 2:885, 2012.
  * [LM14] F. Levi and F. Mintert.  A quantitative theory of coherent delocalization.  New Journal of Physics, 16(3):033007, 2014.
  * [LPS12] C.-K. Li, Y. Poon, and N.-S. Sze.  Generalized interlacing inequalities.  Linear and Multilinear Algebra, 60:1245 – 1254, 2012.
  * [LSLL21] J.W. Liu, S.Q. Shen, M. Li, and L. Li.  Lower bounds for the robustness of multilevel coherence.  International Journal of Theoretical Physics, 60(5):1712–1719, 2021\.
  * [NBC+16] C. Napoli, T. R. Bromley, M. Cianciaruso, M. Piani, N. Johnston, and G. Adesso.  Robustness of coherence: An operational and observable measure of quantum coherence.  Physical Review Letters, 116:150502, 2016.
  * [NC00] M. A. Nielsen and I. L. Chuang.  Quantum computation and quantum information.  Cambridge University Press, 2000.
  * [NV01] M. A. Nielsen and G. Vidal.  Majorization and the interconversion of bipartite states.  Quantum Information and Computation, 1(1):76–93, 2001.
  * [PW09] M. Piani and J. Watrous.  All entangled states are useful for channel discrimination.  Physical Review Letters, 102:250501, 2009.
  * [RBC+18] M. Ringbauer, T. R. Bromley, M. Cianciaruso, L. Lami, W. Y..S. Lau, G. Adesso, A. G. White, A. Fedrizzi, and M. Piani.  Certification and quantification of multilevel quantum coherence.  Physical Review X, 8:041007, 2018.
  * [Ren06] J. Renegar.  Hyperbolic programs, and their derivative relaxations.  Foundations of Computational Mathematics, 6:59–79, 2006.
  * [SdMW+11] T. Scholak, F. de Melo, T. Wellens, F. Mintert, and Andreas A. Buchleitner.  Efficient and coherent excitation transfer across disordered molecular networks.  Phys. Rev. E, 83:021912, Feb 2011.
  * [SEM21] E. Serrano-Ensástiga and J. Martin.  Maximally entangled mixed symmetric states of two qubits.  E-print: arXiv:2112.05102 [quant-ph], 2021.
  * [SFC+17] G.D. Scholes, G.R. Fleming, L.X. Chen, A. Aspuru-Guzik, A. Buchleitner, D.F. Coker, G.S. Engel, R. Van Grondelle, A. Ishizaki, D.M. Jonas, et al.  Using coherence to enhance function in chemical and biophysical systems.  Nature, 543(7647):647–656, 2017.
  * [SP15] J. Saunderson and P. A. Parrilo.  Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones.  Mathematical Programming, 153:309–331, 2015.
  * [Spe22] D. E. Speyer.  Dimension reduction for non-negativity of elementary symmetric polynomials.  MathOverflow, 2022.  URL: https://mathoverflow.net/q/417597.
  * [SSD+15] A. Streltsov, U. Singh, H. S. Dhar, M. N. Bera, and G. Adesso.  Measuring quantum coherence with entanglement.  Physical Review Letters, 115:020403, 2015.
  * [Ter00] B. M. Terhal.  Bell inequalities and separability criterion.  Physics Letters A, 271:319–326, 2000.
  * [TOK+14] T. Tanaka, Y. Ota, M. Kanazawa, G. Kimura, H. Nakazato, and F. Nori.  Determining eigenvalues of a density matrix with minimal information in a single experimental setting.  Physical Review A, 89:012117, 2014.
  * [TSS21] Y.S. Teo and L.L. Sánchez-Soto.  Modern compressive tomography for quantum information science.  International Journal of Quantum Information, 19(08):2140003, 2021\.
  * [VAM01] F. Verstraete, K. Audenaert, and B. De Moor.  Maximally entangled mixed states of two qubits.  Physical Review A, 64:012316, 2001.
  * [Vid00] G. Vidal.  Entanglement monotones.  Journal of Modern Optics, 47:355–376, 2000.
  * [vPRM15] K. von Prillwitz, Ł. Rudnicki, and F. Mintert.  Contrast in multipath interference and quantum coherence.  Physical Review A, 92:052114, Nov 2015.
  * [Wat18] J. Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [WSR+21] Kang-Da Wu, Alexander Streltsov, Bartosz Regula, Guo-Yong Xiang, Chuan-Feng Li, and Guang-Can Guo.  Experimental progress on quantum coherence: Detection, quantification, and manipulation.  Advanced Quantum Technologies, 4(9):2100040, 2021.
  * [YG19] X.-D. Yu and O. Gühne.  Detecting coherence via spectrum estimation.  Physical Review A, 99:062310, 2019.
  * [ZC13] J. Zhou and J. S. Chen.  Properties of circular cone and spectral factorization associated with circular cone.  Journal of Nonlinear and Convex Analysis, 14:807–816, 2013.
  * [ZGY21] L. M. Zhang, T. Gao, and F. L. Yan.  Transformations of multilevel coherent states under coherence-preserving operations.  Science China Physics, Mechanics & Astronomy, 64(6):1–6, 2021\.
  * [Zin08] Y. Zinchenko.  On hyperbolicity cones associated with elementary symmetric polynomials.  Optimization Letters, 2:389–402, 2008.