% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  Signed low-entropy reweightings to rank one on the sphere.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{SIGNED REWEIGHTINGS TO RANK ONE}

\newcommand{\Expect}{\operatorname*{\mathbb{E}}}
\newcommand{\Sph}{\mathbb{S}^{n-1}}
\newcommand{\Ot}{\tilde{O}}
\newcommand{\Reals}{\mathbb{R}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\KL}{\Delta_{\mathrm{KL}}}
\newcommand{\BSS}{\mathrm{BSS}}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Signed Low-Entropy Reweightings to Rank One on the Sphere}
\cjsubtitle{Entropy cost below the square-root barrier}
\cjstatus{Statement: AI-written from Boaz Barak, Pravesh K. Kothari,
  David Steurer, \emph{Quantum entanglement, sum of squares, and the
  log rank conjecture}, arXiv preprint (quant-ph), v2 submitted 9 July
  2017, not yet checked by a human. Settled for $\delta \ge 1/2$ by
  the paper's own Theorem~2.3, even with the stronger requirement that
  $r$ be nonnegative, and open for every $\delta < 1/2$; the paper
  additionally states that the nonnegative-$r$ version of the question
  is false, so a positive answer must use cancellation.}
\cjcategory{\emph{Quantum}.}

\vspace{0.4em}

\begin{informalconjecture}
Take any probability distribution over unit vectors in
$n$-dimensional space. Its second moment is the average of the outer
products of those vectors, an $n$-by-$n$ matrix, and in general it
looks nothing like a rank one matrix. But you are allowed to reweight
the distribution before averaging: multiply by a function that has
average absolute value one, and pay a cost equal to the average of the
absolute weight times its logarithm, which is the usual entropy price
of tilting a distribution. The known result is that you can always buy
an approximately rank one second moment for a price of about the
square root of $n$, and that price is exactly right if the weights are
required to be nonnegative, which is the case where reweighting means
conditioning on an event. The question asked here is whether allowing
the weights to be negative --- so that cancellation, not just
conditioning, is available --- lets you buy the same thing for a price
of $n$ raised to an arbitrarily small positive power. The authors note
that a positive answer below the square-root threshold may improve the
best known bound for the log rank conjecture to $\Ot(n^{\delta})$ ---
subject to the caveats of their footnotes~7 and~8 about which notion
of ``approximate'' is needed and how the bound depends on $\varepsilon$
--- and that, if appropriately extended to pseudo-distributions, it
would improve their algorithm's running time to
$\exp(\Ot(n^{\delta}))$.
\end{informalconjecture}

\section{The setting}\label{sec:setting}

The Best Separable State problem $\BSS_{c,s}$ asks, given an $n^{2}
\times n^{2}$ quantum measurement operator, to distinguish the case
that some separable (non-entangled) state is accepted with probability
at least $c$ from the case that every separable state is accepted with
probability at most $s$. Equivalently, in its non-quantum form, it
asks whether a given linear subspace of $n \times n$ matrices contains
a rank one matrix or is $\varepsilon$-far from every rank one matrix.
The paper's algorithm is the first for the problem that beats the
brute-force $2^{O(n)}$ bound for general measurements; the earlier
sos-based algorithm of Doherty, Parrilo and Spedalieri applies to
general measurements but is not known to beat brute force, and
Brand\~{a}o--Christandl--Yard's quasi-polynomial guarantee is
restricted to 1-LOCC measurements.

That algorithm runs the sum-of-squares hierarchy for $\Ot(\sqrt{n})$
rounds and rounds the resulting pseudo-distribution using a
\emph{structure theorem}: every pseudo-distribution over the unit
sphere admits a degree-$\Ot(\sqrt{n})$ reweighting whose second moment
is $\varepsilon$-close to rank one in Frobenius norm. The paper's
Theorem~2.3 (``rank one reweighting'') is stated for an arbitrary
distribution over rank one $n \times n$ matrices $X$; in the setting
of honest probability distributions, Theorem~2.3 specialises, on
taking $X = vv^{\top}$, to the $\delta = 1/2$, nonnegative-$r$
instance of the statement below. The paper also gives an equivalent
combinatorial dual form (Theorem~2.4): every $N \times N$ real matrix
of rank at most $n$ has a principal submatrix on an index set of
measure $\exp(-\sqrt{n}\,\poly(1/\varepsilon))$ that is
$\varepsilon$-close to rank one.

The technique is a lift of Lovett's $\Ot(\sqrt{n})$ bound on the
deterministic communication complexity of rank-$n$ Boolean
matrices~\cite{Lov14} (following Rothvo{\ss}'s proof~\cite{Rot14}),
which is in turn the best known progress on the log rank conjecture of
Lov\'{a}sz and Saks~\cite{LS88}; the equivalence between small
monochromatic rectangles and low communication complexity is due to
Nisan and Wigderson~\cite{NW94}. The paper's contribution is that
Booleanity can be dropped if ``exactly rank one'' is relaxed to
``approximately rank one'', and that the whole argument can be
embedded in the sum-of-squares proof system~\cite{BKS16}.

The $\sqrt{n}$ in the exponent is therefore the same $\sqrt{n}$ that
blocks progress on the log rank conjecture. The paper observes that
its own Theorem~2.3 is tight as stated, so the exponent cannot be
improved within the nonnegative-reweighting formulation, and that a
black-box reduction from the log rank conjecture to a faster BSS
algorithm looks unlikely because one needs statements that are not
restricted to Boolean matrices. Question~8.1 is the authors' proposal
for such a statement: relax nonnegativity of the reweighting and ask
for entropy cost $n^{\delta}$ instead. Footnote~7 of the paper records
a caveat, due to Gavinsky and Lovett~\cite{GL14}, that the exact
notion of ``approximate'' matters for the log rank application, and
footnote~8 warns that the dependence of the bound on $\varepsilon$
would need better control than the paper's own setting requires.

\textbf{Progress to date.} The paper proves the $\delta = 1/2$ case,
in fact with a nonnegative $r$: its Theorem~2.3 gives, for every
distribution $\mu$ over rank one $n$-by-$n$ matrices and every
$\varepsilon > 0$, a nonnegative reweighting of Kullback--Leibler cost
at most $\sqrt{n}\,\poly(1/\varepsilon)$ whose mean is within
$\varepsilon$ (relative Frobenius) of a rank one matrix, and
Theorem~5.1 lifts this to degree-$\Ot(\sqrt{n})$ sum-of-squares
reweightings of pseudo-distributions. The paper further asserts that
as stated Theorem~2.3 is tight, and states outright that the answer to
Question~8.1 is No if negative reweighting functions are disallowed.
So the nonnegative branch is closed and every $\delta < 1/2$ requires
cancellation. The paper reports no partial result for signed $r$ at
any $\delta < 1/2$.

\textbf{Why it matters.} A positive answer for any $\delta < 1/2$
would be the first improvement in a decade on the best known upper
bound for the log rank conjecture, taking it from $\Ot(\sqrt{n})$ to
$\Ot(n^{\delta})$, and --- if the argument can be run inside the
sum-of-squares proof system, which is what the paper's whole machinery
is designed to make possible --- would simultaneously improve the
running time of the only known sub-exponential algorithm for Best
Separable State from $\exp(\Ot(\sqrt{n}))$ to $\exp(\Ot(n^{\delta}))$.
Two problems that have resisted independently would move together. A
negative answer would be almost as informative: it would say that the
cancellation available to signed reweightings buys nothing over
conditioning, closing off the route the authors identify as the most
promising one and forcing the search for a genuinely different notion
of closeness to rank one.

\textbf{Why it is clean.} The statement is three lines of elementary
real analysis and linear algebra: a probability measure on a sphere, a
signed function with a normalisation and an entropy bound, and a
Frobenius-norm distance to a rank one matrix. It mentions no quantum
mechanics, no communication complexity, no semidefinite programming
and no pseudo-distributions, even though it was extracted from a paper
about all four. There is nothing to install and nothing unpublished to
rely on; a reader can start attacking it from the statement alone. The
known boundary case is equally clean, which makes it easy to check
whether a proposed construction is actually doing anything new.

\section{Notation and parameters}\label{sec:notation}

\begin{itemize}[leftmargin=1.2em]
\item $n \in \Nat$ is the ambient dimension, and $\Sph = \{ v \in
  \Reals^{n} : \|v\|_{2} = 1 \}$ is the real unit sphere.
\item For $A \in \Reals^{n \times n}$, $\|A\|_{F} = \big(\sum_{i,j}
  A_{i,j}^{2}\big)^{1/2}$ denotes the Frobenius norm.
\item A matrix $L \in \Reals^{n \times n}$ is \emph{rank one} if $L =
  a b^{\top}$ for some $a, b \in \Reals^{n}$; it is \emph{nonzero} if
  $L \neq 0$.
\item $\mu$ denotes a Borel probability measure on $\Sph$, and $r :
  \Sph \to \Reals$ a Borel measurable function that is \emph{not}
  required to be nonnegative.
\item $\Expect_{v \sim \mu}[\, r(v) v v^{\top} \,]$ denotes the $n
  \times n$ matrix whose $(i,j)$ entry is $\Expect_{v \sim \mu}[\,
  r(v) v_{i} v_{j} \,]$.
\item $\varepsilon > 0$ is the accuracy parameter (relative Frobenius
  distance to rank one) and $\delta > 0$ is the entropy exponent.
\item Throughout, $0 \log 0 := 0$.
\end{itemize}

\textbf{Parameters.}
\begin{itemize}[leftmargin=1.2em]
\item $n$ --- ambient dimension; the sphere is the unit sphere of
  $\Reals^{n}$ and the second-moment matrix is $n$ by $n$.
\item $\varepsilon$ --- relative Frobenius accuracy: how close the
  reweighted second moment must be to a rank one matrix.
\item $\delta$ --- entropy exponent: the reweighting is allowed
  entropy cost $O(n^{\delta})$. The content of the question is the
  regime $\delta < 1/2$.
\item $C(\varepsilon, \delta)$ --- the constant hidden by the paper's
  $O(n^{\delta})$; it may depend on $\varepsilon$ and $\delta$ but not
  on $n$ or $\mu$.
\item $r$ --- the signed reweighting function; the point of the
  question is that $r$ is not required to be nonnegative.
\item $L$ --- the nonzero rank one $n$-by-$n$ matrix that the
  reweighted second moment must approximate.
\end{itemize}

\section{The conjecture}\label{sec:conjectures}

\begin{definition}[Signed reweighting and its entropy
cost]\label{def:signed}
Let $\mu$ be a Borel probability measure on $\Sph$ and let $K \ge 0$.
A Borel measurable function $r : \Sph \to \Reals$ is called a
\emph{signed reweighting of $\mu$ with entropy cost at most $K$} if
$r$ is $\mu$-integrable and
\[
\begin{gathered}
  \Expect_{v \sim \mu} \big| r(v) \big| \;=\; 1, \\[0.25em]
  \Expect_{v \sim \mu} \Big[\, \big| r(v) \big| \,
    \log \big| r(v) \big| \,\Big] \;\le\; K .
\end{gathered}
\]
If in addition $r \ge 0$ holds $\mu$-almost everywhere, then $r$ is a
\emph{nonnegative} reweighting; in that case $d\mu' := r \, d\mu$ is a
probability measure and the entropy cost is exactly the
Kullback--Leibler divergence $\KL(\mu' \,\|\, \mu) = \Expect_{v \sim
\mu'} \log\big( d\mu'/d\mu \big)$.
\end{definition}

\begin{conjecture}[signed low-entropy reweighting to rank
one]\label{conj:main}
For every $\varepsilon > 0$ and every $\delta > 0$ there exists a
finite constant $C = C(\varepsilon, \delta)$ such that the following
holds for every $n \in \Nat$ and every Borel probability measure $\mu$
on $\Sph$: there exist a signed reweighting $r$ of $\mu$ with entropy
cost at most $C \cdot n^{\delta}$ (in the sense of
Definition~\ref{def:signed}) and a nonzero rank one matrix $L \in
\Reals^{n \times n}$ such that
\[
  \Big\| \Expect_{v \sim \mu}\big[\, r(v)\, v v^{\top} \,\big]
    \;-\; L \Big\|_{F} \;\le\; \varepsilon \, \|L\|_{F}.
\]
\end{conjecture}

\begin{remark}[three harvester-side readings a reviewer should
check]\label{rem:reading}
First, quantifier placement on the constant: the paper writes the
entropy bound as $O(n^{\delta})$, which by convention hides a constant
that may depend on $\varepsilon$ and $\delta$ but not on $n$ or $\mu$;
that constant is made explicit above as $C(\varepsilon, \delta)$.
Footnote~8 of the paper explicitly warns that for the log rank
application one needs better control of the $\varepsilon$-dependence
than the paper's own setting requires, so a solver should track $C$'s
dependence on $\varepsilon$ rather than treat it as free. Second,
regularity: the paper says only ``distribution over $\Sph$'' and does
not specify measurability or integrability conditions on $r$;
Definition~\ref{def:signed} writes Borel measurable and
$\mu$-integrable. The essential case is finitely supported $\mu$
(this is what the sum-of-squares application produces), and the
general case should follow by approximation, but this is the
harvester's reading and not the paper's words. Third, currency: the
paper's assertion that the nonnegative-$r$ answer is No is stated
without proof, resting on the remark that Theorem~2.3 is tight as
stated; and the claims that Lovett's $\Ot(\sqrt{n})$ remains the best
known bound for the log rank conjecture~\cite{Lov14} and that
Question~8.1 has not been answered for $\delta < 1/2$ are recalled
from memory rather than from the paper. The log rank literature has
moved since 2017 and a reviewer should verify both before publishing;
no resolution is known to the harvester, but this is not certain.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[BKS16]{BKS16}
B. Barak, P. Kothari, D. Steurer.
\emph{Proofs, beliefs, and algorithms through the lens of
sum-of-squares}.
Lecture notes in preparation, available on
\url{http://sumofsquares.org}, 2016.

\bibitem[GL14]{GL14}
D. Gavinsky, S. Lovett.
\emph{En route to the log-rank conjecture: New reductions and
equivalent formulations}.
ICALP~(1), Lecture Notes in Computer Science, vol.~8572, Springer,
pages 514--524, 2014.

\bibitem[Lov14]{Lov14}
S. Lovett.
\emph{Communication is bounded by root of rank}.
STOC, ACM, pages 842--846, 2014.

\bibitem[LS88]{LS88}
L. Lov\'{a}sz, M. E. Saks.
\emph{Lattices, m\"{o}bius functions and communication complexity}.
FOCS, IEEE Computer Society, pages 81--90, 1988.

\bibitem[NW94]{NW94}
N. Nisan, A. Wigderson.
\emph{On rank vs.\ communication complexity}.
FOCS, IEEE Computer Society, pages 831--836, 1994.

\bibitem[Rot14]{Rot14}
T. Rothvo{\ss}.
\emph{A direct proof for Lovett's bound on the communication
complexity of low rank matrices}.
CoRR abs/1409.6366, 2014.

\end{conjurabibliography}

\end{document}
