# On relating one-way classical and quantum communication complexities

Naresh Goud Boddu<EMAIL_ADDRESS>NTT Research, Sunnyvale,
California, USA  Rahul Jain<EMAIL_ADDRESS>Centre for Quantum
Technologies and Department of Computer Science, National University of
Singapore and MajuLab, UMI 3654, Singapore  Han-Hsuan Lin
<EMAIL_ADDRESS>National Tsing Hua University, Taiwan

###### Abstract

Communication complexity is the amount of communication needed to compute a
function when the function inputs are distributed over multiple parties. In
its simplest form, one-way communication complexity, Alice and Bob compute a
function $f(x,y)$, where $x$ is given to Alice and $y$ is given to Bob, and
only one message from Alice to Bob is allowed. A fundamental question in
quantum information is the relationship between one-way quantum and classical
communication complexities, i.e., how much shorter the message can be if Alice
is sending a quantum state instead of bit strings? We make some progress
towards this question with the following results.

Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{Z}\cup\\{\bot\\}$ be a
partial function and $\mu$ be a distribution with support contained in
$f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ be the classical one-way communication
complexity of $f$; $\mathsf{Q}^{1,\mu}_{\epsilon}(f)$ be the quantum one-way
communication complexity of $f$ and $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$ be
the entanglement-assisted quantum one-way communication complexity of $f$,
each with distributional error (average error over $\mu$) at most $\epsilon$.
We show:

  1. 1.

If $\mu$ is a product distribution, $\eta>0$ and $0\leq\epsilon\leq 1-1/d$,
then,

$\displaystyle\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)+O(\log\log(1/\eta))\enspace.$

In other words for $\delta,\eta>0$ (by setting
$\epsilon=1-\frac{1}{d}-\delta$),

$\displaystyle\mathsf{R}^{1,\mu}_{1-\frac{1}{d}-\frac{d}{d-1}\delta^{2}+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu,*}_{1-\frac{1}{d}-\delta}(f)+O(\log\log(1/\eta))\enspace.$

We show similar results for other related communication models.

  2. 2.

If $\mu$ is a non-product distribution and $\mathcal{Z}=\\{0,1\\}$, then
$\forall\epsilon,\eta>0$ such that $\epsilon/\eta+\eta<0.5$,

$\mathsf{R}^{1,\mu}_{3\eta}(f)=O(\mathsf{Q}^{1,\mu}_{{\epsilon}}(f)\cdot\mathsf{CS}(f)/\eta^{3})\enspace,$

where

$\mathsf{CS}(f)=\max_{y}\min_{z\in\\{0,1\\}}|\\{x\leavevmode\nobreak\
|\leavevmode\nobreak\ f(x,y)=z\\}|\enspace.$

##  1 Introduction

Communication complexity concerns itself with characterizing the minimum
number of bits or qubits that distributed parties need to exchange in order to
accomplish a given task (such as computing a function $f$). Over the years,
different models of communication for two party and multi party communication
[4] have been proposed and studied. We consider only two party communication
models in this paper. Communication complexity models have established
striking connections with other areas in theoretical computer science, such as
data structures, streaming algorithms, circuit lower bounds, decision tree
complexity, VLSI designs, etc.

In the two-way communication model, two parties Alice and Bob receive an input
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$ respectively. They interact with each
other, communicating several messages, in order to jointly compute a given
function $f(x,y)$ of their inputs. Their goal is to do this with as little
communication as possible. Suppose if only one message is allowed, say from
Alice to Bob, and Bob outputs $f(x,y)$ without any further interaction with
Alice, then the model is called one-way. We refer readers to the textbook of
Kushilevitz and Nisan [15] for a comprehensive introduction to the field of
classical communication complexity. The work of Yao [20] introduced quantum
communication complexity, and since then various other analogous quantum
communication models are proposed and studied. In the quantum communication
models, the parties send quantum messages and are allowed to use quantum
operations.

In the current paper, we study the relation between quantum and classical one-
way communication complexities. Let $\mathsf{R}^{1}_{\epsilon}(f)$ denote the
classical one-way communication complexity of $f$ (Alice and Bob are allowed
to use public and private randomness independent of the inputs);
$\mathsf{Q}^{1}_{\epsilon}(f)$ denote the quantum one-way communication
complexity of $f$ and $\mathsf{Q}^{1,*}_{\epsilon}(f)$ denote the
entanglement-assisted quantum one-way communication complexity of $f$, each
with worst case error $\epsilon$. Let $\mu$ be a probability distribution over
$\mathcal{X}\times\mathcal{Y}$ and $\mu_{X}$ be the marginal of $\mu$ on
$\mathcal{X}$. Let $\mathsf{R}^{1,\mu}_{\epsilon}(f)$ represent the classical
one-way communication complexity of $f$; $\mathsf{Q}^{1,\mu}_{\epsilon}(f)$
denote the quantum one-way communication complexity of $f$ and
$\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$ denote the entanglement-assisted quantum
one-way communication complexity of $f$, each with distributional error
(average error over $\mu$) at most $\epsilon$. Let
$\mathsf{R}^{1,\mu_{X}}_{\epsilon}(f)$ represent the classical one-way
communication complexity of $f$ with distributional error for worst case $y$
while $x$ is averaged over the distribution $\mu_{X}$ at most $\epsilon$;
$\mathsf{Q}^{1,\mu_{X}}_{\epsilon}(f)$ denote the quantum one-way
communication complexity of $f$ and $\mathsf{Q}^{1,\mu_{X},*}_{\epsilon}(f)$
denote the entanglement-assisted quantum one-way communication complexity of
$f$, each with distributional error for worst case $y$ while $x$ is averaged
over the distribution $\mu_{X}$ at most $\epsilon$. Please refer to Section 2
[2] for precise definitions.

A fundamental question about one-way communication complexity is the relation
between $\mathsf{R}^{1}_{\epsilon}(f)$ and $\mathsf{Q}^{1}_{\epsilon}(f)$ (or
$\mathsf{Q}^{1,*}_{\epsilon}(f)$). Clearly
$\mathsf{Q}^{1,*}_{\epsilon}(f)\leq\min\\{\mathsf{Q}^{1}_{\epsilon}(f),\mathsf{R}^{1}_{\epsilon}(f)\\}$.
When $f$ is a partial function, Gavinsky et al.
[7] established an exponential separation between
$\mathsf{R}^{1}_{\epsilon}(f)$ and $\mathsf{Q}^{1}_{\epsilon}(f)$. It is a
long standing open problem to relate $\mathsf{R}^{1}_{\epsilon}(f)$ and
$\mathsf{Q}^{1,*}_{\epsilon}(f)$ for a total function $f$. Since both measures
are related to their distributional versions,
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ and $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$,
via Yao’s Lemma [19], we study the problem of relating measures
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ and $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$
for a fixed distribution $\mu$.

### Previous results

For a total function $f:\mathcal{X}\times\mathcal{Y}\to\\{0,1\\}$, its Vapnik-
Chervonenkis (VC) dimension, denoted by $\mathsf{VC}(f)$, is an important
complexity measure, widely studied specially in the context of computational
learning theory. If $\mu$ is a product distribution, Kremer, Nisan and Ron
[14] established a connection between the measures
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ and $\mathsf{VC}(f)$ as follows:

$\displaystyle\mathsf{R}^{1,\mu}_{\epsilon}(f)=O\left(\frac{1}{\epsilon}\log\left(\frac{1}{\epsilon}\right)\mathsf{VC}(f)\right).$

Ambainis et al. [1] showed the following:

$\displaystyle\max_{\text{product
}\lambda}\mathsf{Q}^{1,\lambda,*}_{\epsilon}(f)=\Omega\left(\mathsf{VC}(f)\right).$

Above equations establish that for a product distribution $\mu$,

$\max_{\text{product
}\lambda}\mathsf{Q}^{1,\lambda,*}_{\epsilon}(f)=\Omega(\mathsf{R}^{1,\mu}_{\epsilon}(f)).$

Jain and Zhang [9] extended the result of [14] when $\mu$ is any (non-product)
distribution given as follows:

$\displaystyle\mathsf{R}^{1,\mu}_{\epsilon}(f)$
$\displaystyle=O\left(\frac{1}{\epsilon}\log\left(\frac{1}{\epsilon}\right)\left(\frac{\mathrm{I}(X:Y)}{\epsilon}+1\right)\mathsf{VC}(f)\right).$

For a function $f:\mathcal{X}\times\mathcal{Y}\to\\{0,1\\}$, another measure
that is often very useful in understanding classical one-way communication
complexity, is the rectangle bound (denoted $\mathsf{rec}(f)$) a.k.a. the
corruption bound. The rectangle bound $\mathsf{rec}(f)$ is defined via a
distributional version $\mathsf{rec}^{\mu}(f)$. It is a well-studied measure
and $\mathsf{rec}^{1,\mu}(f)$ is well known to form a lower bound on
$\mathsf{R}^{1,\mu}(f)$. If $\mu$ is a product distribution, [9] showed,

$\displaystyle\mathsf{Q}^{1,\mu}_{\epsilon^{3}}(f)=\Omega\left(\mathsf{rec}_{\epsilon}^{1,\mu}(f)\right).$

For a product distribution $\mu$, Jain, Klauck and Nayak [12] showed,

$\displaystyle\max_{\text{product
}\lambda}\mathsf{rec}_{\epsilon}^{1,\lambda}(f)=\Omega(\mathsf{R}^{1,\mu}_{\epsilon}(f)).$

Above equations establish that for a product distribution $\mu$,

$\max_{\text{product
}\lambda}\mathsf{Q}^{1,\lambda}_{\epsilon^{3}}(f)=\Omega(\mathsf{R}^{1,\mu}_{\epsilon}(f)).$

However, it remained open whether $\mathsf{R}^{1,\mu}_{\epsilon}(f)$ and
$\mathsf{Q}^{1,\mu}_{\epsilon}(f)$ (or $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$)
are related for a fixed distribution $\mu$. We answer it in positive and show
the following results.

### Our results

######  Theorem 1.

Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{Z}\cup\\{\bot\\}$ be a
partial function 111A partial function under a product $\mu$ is basically same
as a total function. and $\mu$ be a product distribution supported on
$f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let $\eta>0$ and
$0\leq\epsilon\leq 1-1/d$. Then,

$\displaystyle\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq\mathsf{Q}^{1,\mu}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu_{X}}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu_{X},*}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu_{X}}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq\mathsf{Q}^{1,\mu_{X}}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right).$

Note that for entanglement-assisted protocols, there must be a factor of 2
because of super dense coding. Additionally, if $\mu$ is a non-product
distribution, we show,

######  Theorem 2.

Let $\epsilon,\eta>0$ be such that $\epsilon/\eta+\eta<0.5$. Let
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1,\bot\\}$ be a partial
function and $\mu$ be a distribution supported on $f^{-1}(0)\cup f^{-1}(1)$.
Then,

$\mathsf{R}^{1,\mu}_{3\eta}(f)=O\left(\frac{\mathsf{CS}(f)}{\eta^{3}}\mathsf{Q}^{1,\mu}_{{\epsilon}}(f)\right),$

where

$\mathsf{CS}(f)=\max_{y}\min_{z\in\\{0,1\\}}\\{|\\{x\leavevmode\nobreak\
|\leavevmode\nobreak\ f(x,y)=z\\}|\\}\enspace.$

Both Theorem 1 and Theorem 2 are proved by converting quantum protocols into
classical protocols directly.

The bound provided by Theorem 2 depends on the column sparsity
$\mathsf{CS}(f)$. Although $\mathsf{CS}(f)$ can be as large as
$O(|\mathcal{X}|)$, giving a bound exponentially worse than the
$O(\log(|\mathcal{X}|))$ brute force protocol, Theorem 2 is useful when
$\mathsf{CS}(f)$ is constant. In particular, Theorem 2 can convert the quantum
fingerprinting protocol [5] 222This protocol is proposed for simultaneous
message passing model, but it can be easily converted into one for one-way
communication model. on EQUALITY function into a classical communication
protocol with similar complexity for the worst case by combining it with Yao’s
Lemma [19].

### Proof overview

For a product distribution $\mu$, we upper bound
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ by $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$,
using ideas from König and Tehral [13] and Jain, Radhakrishnan, and Sen [10,
11]. For an entanglement-assisted quantum one-way communication protocol, let
$Q\equiv DE_{B}$ represent Alice’s quantum message $D$ and Bob’s part of the
entanglement $E_{B}$. We first replace Bob’s measurement by the pretty good
measurement (PGM) (with a small loss in the error probability). Then we use an
idea of [13] to show that we can "split" Bob’s PGM into the PGM for guessing
$X$. Since this new $X$-guessing PGM is independent of $Y$, Alice can apply it
herself on the register $Q$ (Alice’s message and Bob’s share of prior
entanglement) and send the measurement outcome $C$ to Bob, who will just
output $f(C,Y)$. The classical message that Alice sent is long (in fact it is
equal to the length of $X$) but it has low max-information with input $X$,
since (by monotonicity of the max-information)
$\mathrm{I}_{\max}(X:C)\leq\mathrm{I}_{\max}(X:Q)\leq 2\log(|D|)$. Note that
the second inequality has a factor of $2$ due to super dense coding. We then
use a compression protocol from [10, 11] to compress $C$ into another short
message $C^{\prime}$ of size $2\log(|D|)$. The same argument works for
variants of this result where the two parties does not share entanglement,
and/or where the error probability is averaged over a distribution of $x$ and
maximized over $y$.

For a non-product distribution $\mu$, we upper bound
$\mathsf{R}^{1,\mu}_{\epsilon}(f)$ by $\mathsf{Q}^{1,\mu}_{\epsilon}(f)$,
using ideas of Huang, Kueng and Preskill [8] and [10, 11]. For a quantum one-
way communication protocol with quantum message 333We assume, by at most
doubling the message size that Alice’s message for any input is a pure state.
$Q$, we first use the idea of [8] to show that there exists a "classical
shadow" $C$ of the quantum message $Q$, which will allow Bob to estimate
$\mathrm{Tr}(E^{y}_{b}Q)$ (for any $b\in\\{0,1\\}$, where
$\mathcal{M}^{y}=\\{E^{y}_{0},E^{y}_{1}\\}$ is Bob’s measurement on input
$y$). This allows Alice to send the classical shadow $C$ of quantum message
$Q$. However, the precision of the classical shadow procedure of [8] depends
on $\|E^{y}_{b}\|_{F}^{2}$, so we need to bound $\|E^{y}_{b}\|_{F}^{2}$. We
show that there exists measurement operator $\tilde{E}^{y}_{b}$ (for some
$b\in\\{0,1\\}$) such that $\|\tilde{E}^{y}_{b}\|_{F}^{2}$ is at most the
"column sparsity" of function $f$ and $\mathrm{Tr}(\tilde{E}^{y}_{b}Q)$ is
"close" to $\mathrm{Tr}(E^{y}_{b}Q)$. We again note that the classical shadow
has low max-information with input $X$, since (using the monotonicity for max-
information) $\mathrm{I}_{\max}(X:C)\leq\mathrm{I}_{\max}(X:Q)\leq\log(|Q|)$.
As before, we use the compression protocol from [10, 11] to compress $C$ into
another short message $C^{\prime}$ of size $\log(|Q|)$.

### Organization

In Section 2, we present our notations, definitions and other information
theoretic preliminaries. In Section 3, we present the proof of Theorem 1. In
Section 4, we present the proof of Theorem 2.

##  2 Preliminary

### Quantum information theory

All the logarithms are evaluated to the base $2$. Consider a finite
dimensional Hilbert space $\mathcal{H}$ endowed with an inner-product
$\langle\cdot,\cdot\rangle$ (we only consider finite dimensional Hilbert
spaces). A quantum state (or a density matrix of a state) is a positive semi-
definite matrix on $\mathcal{H}$ with trace equal to $1$. It is called pure if
and only if its rank is $1$. Let ${\left|{\psi}\right\rangle}$ be a unit
vector on $\mathcal{H}$, that is $\langle\psi,\psi\rangle=1$. With some abuse
of notation, we use $\psi$ to represent the state and also the density matrix
$|\psi\rangle\langle\psi|$, associated with ${\left|{\psi}\right\rangle}$.
Given a quantum state $\rho$ on $\mathcal{H}$, support of $\rho$, called
$\text{supp}(\rho)$ is the subspace of $\mathcal{H}$ spanned by all
eigenvectors of $\rho$ with non-zero eigenvalues.

A quantum register $A$ is associated with some Hilbert space
$\mathcal{H}_{A}$. Define
$|A|\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\dim(\mathcal{H}_{A})$ and
$\ell(A)=\log|A|$. Let $\mathcal{L}(\mathcal{H}_{A})$ represent the set of all
linear operators on $\mathcal{H}_{A}$ and $\mathcal{D}(\mathcal{H}_{A})$, the
set of all quantum states on $\mathcal{H}_{A}$. For operators
$O,O^{\prime}\in{\cal L}(\mathcal{H}_{A})$, the notation $O\leq O^{\prime}$
represents the Löwner order, that is, $O^{\prime}-O$ is a positive semi-
definite matrix. State $\rho$ with subscript $A$ indicates
$\rho_{A}\in\mathcal{D}(\mathcal{H}_{A})$. If two registers $A,B$ are
associated with the same Hilbert space, we shall represent the relation by
$A\equiv B$. For two states $\rho_{A},\sigma_{B}$, we let
$\rho_{A}\equiv\sigma_{B}$ represent that they are identical as states, just
in different registers. Composition of two registers $A$ and $B$, denoted
$AB$, is associated with the Hilbert space
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. For two quantum states
$\rho\in\mathcal{D}(\mathcal{H}_{A})$ and
$\sigma\in\mathcal{D}(\mathcal{H}_{B})$,
$\rho\otimes\sigma\in\mathcal{D}(\mathcal{H}_{AB})$ represents the tensor
product (Kronecker product) of $\rho$ and $\sigma$. The identity operator on
$\mathcal{H}_{A}$ is denoted by $\mathbb{I}_{A}$. Let $U_{A}$ denote maximally
mixed state in $\mathcal{H}_{A}$. Let
$\rho_{AB}\in\mathcal{D}(\mathcal{H}_{AB})$. Define

$\rho_{B}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\operatorname{Tr}_{A}{\rho_{AB}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i}({\left\langle{i}\right|}\otimes\mathbb{I}_{B})\rho_{AB}({\left|{i}\right\rangle}\otimes\mathbb{I}_{B}),$

where $\\{{\left|{i}\right\rangle}\\}_{i}$ is an orthonormal basis for the
Hilbert space $\mathcal{H}_{A}$. The state
$\rho_{B}\in\mathcal{D}(\mathcal{H}_{B})$ is referred to as the marginal state
of $\rho_{AB}$. Unless otherwise stated, a missing register from subscript in
a state will represent partial trace over that register. Given
$\rho_{A}\in\mathcal{D}(\mathcal{H}_{A})$, a purification of $\rho_{A}$ is a
pure state $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{AB})$ such that
$\operatorname{Tr}_{B}{\rho_{AB}}=\rho_{A}$. Purification of a quantum state
is not unique. Suppose $A\equiv B$. Given $\\{{\left|{i}\right\rangle}_{A}\\}$
and $\\{{\left|{i}\right\rangle}_{B}\\}$ as orthonormal bases over
$\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ respectively, the canonical
purification of a quantum state $\rho_{A}$ is
${\left|{\rho_{A}}\right\rangle}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\rho_{A}^{\frac{1}{2}}\otimes\mathbb{I}_{B})\left(\sum_{i}{\left|{i}\right\rangle}_{A}{\left|{i}\right\rangle}_{B}\right)$.
Note that the size (number of qubits) of the canonical purification
${\left|{\rho_{A}}\right\rangle}$ is twice the size of quantum state
$\rho_{A}$.

A quantum channel
$\mathcal{E}:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$
is a completely positive and trace preserving (CPTP) linear map (mapping
states in $\mathcal{D}(\mathcal{H}_{A})$ to states in
$\mathcal{D}(\mathcal{H}_{B})$). A unitary operator
$U_{A}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A}$ is such that
$U_{A}^{\dagger}U_{A}=U_{A}U_{A}^{\dagger}=\mathbb{I}_{A}$. The set of all
unitary operators on $\mathcal{H}_{A}$ is denoted by
$\mathcal{U}(\mathcal{H}_{A})$. An isometry
$V:\mathcal{H}_{A}\rightarrow\mathcal{H}_{B}$ is such that
$V^{\dagger}V=\mathbb{I}_{A}$ and $VV^{\dagger}=\mathbb{I}_{B}$. A POVM
element is an operator $0\leq M\leq\mathbb{I}$. We use shorthand
$\bar{M}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{I}-M$, where
$\mathbb{I}$ is clear from the context. We use shorthand $M$ to represent
$M\otimes\mathbb{I}$, where $\mathbb{I}$ is clear from the context. A
measurement $\mathcal{M}=\\{M_{1},M_{2},\ldots,M_{t}\\}$ (with POVM elements
$\\{M^{\dagger}_{1}M_{1},M^{\dagger}_{2}M_{2},\ldots,M^{\dagger}_{t}M_{t}\\}$)
is a set of operators such that
$\sum_{i=1}^{t}M^{\dagger}_{i}M_{i}=\mathbb{I}$. When $\mathcal{M}$ is
performed on a state $\rho$, we get as outcome a random variable
$\mathcal{M}(\rho)$, such that $\Pr(\mathcal{M}(\rho)=i)=\mathrm{Tr}(M_{i}\rho
M^{\dagger}_{i})$ and the state conditioned on outcome $i$ is $\frac{M_{i}\rho
M^{\dagger}_{i}}{\mathrm{Tr}(M_{i}\rho M^{\dagger}_{i})}$. A projector $\Pi$
is an operator such that $\Pi^{2}=\Pi$, i.e. its eigenvalues are either $0$ or
$1$.

For a classical random variable $X$, we use $x\leftarrow X$ to denote $x$ is
drawn from the distribution
$P_{X}(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Pr(X=x)$. A classical-
quantum state (cq-state) $\rho_{XQ}$ (with $X$ a classical random variable) is
of the form

$\rho_{XQ}=\sum_{x\in{\cal
X}}P_{X}(x){\left|{x}\right\rangle}{\left\langle{x}\right|}\otimes\rho^{x}_{Q},$

where ${\rho^{x}_{Q}}$ are states and $P_{X}(x)=\Pr(X=x)_{\rho}$. For an event
$G\subseteq{\cal X}=\operatorname{supp}(X)$, define

$\Pr(G)_{\rho}=\sum_{x\in G}P_{X}(x)\quad;\quad$
$(\rho|G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{\Pr(G)_{\rho}}\sum_{x\in
G}P_{X}(x){\left|{x}\right\rangle}{\left\langle{x}\right|}\otimes\rho^{x}_{Q}.$

For a function $Z:\mathcal{X}\rightarrow\mathcal{Z}$, define

$\rho_{ZXQ}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{x\in{\cal
X}}P_{X}(x){\left|{Z(x)}\right\rangle}{\left\langle{Z(x)}\right|}\otimes{\left|{x}\right\rangle}{\left\langle{x}\right|}\otimes\rho^{x}_{Q}.$

We also use $U_{d}$ to represent the uniform distribution over
$\\{0,1\\}^{d}$.

######  Definition 1.

  1. 1.

For $p\geq 1$ and matrix $A$, let $\|A\|_{p}$ denote the Schatten $p$-norm.
$\|A\|_{2}$ is also referred to as the Frobenius norm, denoted $\|A\|_{F}$.

  2. 2.

Let
$\Delta(\rho,\sigma)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{2}\|\rho-\sigma\|_{1}$.
We write $\approx_{\epsilon}$ to denote $\Delta(\rho,\sigma)\leq\epsilon$.

  3. 3.

For a quantum state $\rho$, and integer $t>0$, we define

$\rho^{\otimes
t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\rho\otimes\rho\otimes\cdots\otimes\rho\quad(\text{t
times}).$

We start with the following fundamental information theoretic quantities. We
refer the reader to the excellent sources for quantum information theory [18,
17] from where the facts stated below can be found.

######  Definition 2 (von Neumann entropy).

The von Neumann entropy of a quantum state $\rho$ is defined as,

$\mathrm{S}(\rho)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}-\mathrm{Tr}(\rho\log\rho).$

######  Definition 3 (Relative entropy).

Let $\rho,\sigma$ be states with
$\operatorname{supp}(\rho)\subset\operatorname{supp}(\sigma)$. The relative
entropy between $\rho$ and $\sigma$ is defined as,

$\mathrm{D}(\rho||\sigma)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{Tr}(\rho\log\rho)-\mathrm{Tr}(\rho\log\sigma).$

######  Definition 4 (Max-relative entropy [6, 10]).

Let $\rho,\sigma$ be states with
$\operatorname{supp}(\rho)\subset\operatorname{supp}(\sigma)$. The max-
relative entropy between $\rho$ and $\sigma$ is defined as,

$\mathrm{D}_{\max}\>\\!\\!\left(\rho\middle\|\sigma\right)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf\\{\lambda\in\mathbb{R}:\rho\leq
2^{\lambda}\sigma\\}.$

######  Definition 5 (Max-information [6]).

For state $\rho_{AB}$,

$\mathrm{I}_{\max}(A:B)_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf_{\sigma_{B}\in\mathcal{D}(\mathcal{H}_{B})}\mathrm{D}_{\max}\>\\!\\!\left(\rho_{AB}\middle\|\rho_{A}\otimes\sigma_{B}\right).$

If $\rho$ is a classical state (diagonal in the computational basis) then the
$\inf$ above is achieved by a classical state $\sigma_{B}$.

######  Definition 6 (Mutual information).

Let $\rho_{ABC}$ be a quantum state. We define the following measures.

$\displaystyle\text{Mutual information}:\quad\mathrm{I}(A:B)_{\rho}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{S}(\rho_{A})+\mathrm{S}(\rho_{B})-\mathrm{S}(\rho_{AB})$
$\displaystyle=\mathrm{D}(\rho_{AB}||\rho_{A}\otimes\rho_{B}).$
$\displaystyle\text{Conditional mutual
information}:\mathrm{I}(A:B\leavevmode\nobreak\ |\leavevmode\nobreak\
C)_{\rho}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{I}(A:BC)_{\rho}-\mathrm{I}(A:C)_{\rho}.$

######  Fact 1.

For a cq-state $\rho_{XA}$ ($X$ classical):
$\rho_{XA}\leq\mathbb{I}_{X}\otimes\rho_{A}$ and
$\rho_{XA}\leq\rho_{X}\otimes\mathbb{I}_{A}$.

###### Proof.

For the first inequality consider,

$\displaystyle\rho_{XA}$ $\displaystyle=\sum_{x}p_{x}|x\rangle\langle
x|\otimes\rho^{x}_{A}$ $\displaystyle\leq\sum_{x}|x\rangle\langle
x|\otimes\rho_{A}$ $\displaystyle=\mathbb{I}_{X}\otimes\rho_{A}.$

For above note that $\sum_{x}p_{x}\rho^{x}_{A}=\rho_{A}$ and hence for all
$x:p_{x}\rho^{x}_{A}\leq\rho_{A}$.

For the second inequality consider,

$\displaystyle\rho_{XA}$ $\displaystyle=\sum_{x}p_{x}|x\rangle\langle
x|\otimes\rho^{x}_{A}$ $\displaystyle\leq\sum_{x}p_{x}|x\rangle\langle
x|\otimes\mathbb{I}_{A}$ $\displaystyle=\rho_{X}\otimes\mathbb{I}_{A}.$

∎

######  Fact 2 (Monotonicity).

Let $\rho_{XA}$ be a cq-state ($X$ classical) and
$\mathcal{E}:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$
be a CPTP map. Then,

$\mathrm{I}_{\max}(X:B)_{\mathcal{E}(\rho)}\leq\mathrm{I}_{\max}(X:A)_{\rho}\leq\log{|A|}.$

###### Proof.

Let $c=\mathrm{I}_{\max}(X:A)_{\rho}$ and $\sigma_{A}$ be a state such that
$\rho_{XA}\leq 2^{c}\rho_{X}\otimes\sigma_{A}$. Since $\mathcal{E}$ preserves
positivity, $(\mathbb{I}_{X}\otimes\mathcal{E})(\rho_{XA})\leq
2^{c}\rho_{X}\otimes\mathcal{E}(\sigma_{A})$ which gives the first inequality.

From Fact 1,
$\rho_{XA}\leq\rho_{X}\otimes\mathbb{I}_{A}=2^{\log|A|}\rho_{X}\otimes U_{A}$.
The second inequality now follows from the definition of $\mathrm{I}_{\max}$.

∎

######  Fact 3 (Naimark’s theorem).

For a measurement $\mathcal{M}=\\{M_{1},M_{2},\ldots,M_{t}\\}$ and a quantum
state $\rho_{A}$, there exists a unitary
$U:\mathcal{H}_{AZ}\rightarrow\mathcal{H}_{AZ}$ such that $|Z|=t,$ and
$\mathrm{Tr}(M_{i}(\rho_{A}\otimes|0\rangle\langle
0|)M^{\dagger}_{i})=\mathrm{Tr}((\mathbb{I}\otimes|i\rangle\langle
i|)(U(\rho_{A}\otimes|0\rangle\langle
0|)U^{\dagger}))=\Pr(Z=i)_{U(\rho_{A}\otimes|0\rangle\langle 0|)U^{\dagger}}$,
for every $i\in[t].$

######  Fact 4 (Lemma B.7 in [3]).

For a state $\rho_{XY}$, $\mathrm{I}_{\max}(X:Y)_{\rho}\leq
2\log\min(|X|,|Y|)$.

######  Fact 5.

Let $\rho_{XBD}$ be a cq-state ($X$ classical) such that
$\rho_{XB}=\rho_{X}\otimes\rho_{B}$. Then,

$\mathrm{I}_{\max}(X:BD)_{\rho}\leq 2\log{(|D|)}.$

###### Proof.

From Fact 4, we have $\mathrm{I}_{\max}(XB:D)_{\rho}\leq 2\log(|D|)$. Using
Definition 5, there exist a $\sigma_{D}$ such that

$\rho_{XBD}\leq 2^{2\log(|D|)}\rho_{XB}\otimes\sigma_{D}.$

Since $\rho_{XB}=\rho_{X}\otimes\rho_{B}$, we have

$\rho_{XBD}\leq 2^{2\log(|D|)}\rho_{X}\otimes(\rho_{B}\otimes\sigma_{D}).$

Defining $\sigma_{BD}=\rho_{B}\otimes\sigma_{D}$, we have

$\rho_{XBD}\leq 2^{2\log(|D|)}\rho_{X}\otimes(\sigma_{BD}).$

From Definition 5, we have the desired, $\mathrm{I}_{\max}(X:BD)_{\rho}\leq
2\log{(|D|)}.$ ∎

######  Definition 7 (Projector on Hilbert space).

Let $\mathcal{H}$ be a Hilbert space with a basis $\\{v_{i}\\}$. The projector
on $\mathcal{H}$ is defined as:

$\mathsf{Proj}(\mathcal{H})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i}|v_{i}\rangle\langle
v_{i}|.$

######  Definition 8 (Guessing probability).

Given a cq-state, $\rho_{XQ}=\sum_{x}p_{x}|x\rangle\langle
x|\otimes\rho^{x}_{Q}$, we often want to guess $X$ by doing a measurement on
the quantum register $Q$. If we do so by a measurement $\mathcal{M}$ with POVM
elements $\\{E_{x}\\}$, its success probability averaged over $X$ is

$\Pr[X=\mathcal{M}(Q)]=\sum_{x}p_{x}\operatorname{Tr}\left(E_{x}\rho^{x}_{Q}\right).$

We use $p^{opt}_{g}(X|Q)_{\rho}$ to denote the maximum probability over all
measurements $\mathcal{M}$, i.e.

$p^{opt}_{g}(X|Q)_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{\mathcal{M}}\\{\Pr[X=\mathcal{M}(Q)]\\}.$

######  Definition 9 (Pretty good measurement (PGM)).

For a cq-state, $\rho_{XQ}=\sum_{x}p_{x}|x\rangle\langle
x|\otimes\rho^{x}_{Q},$ define

$\displaystyle A_{x}=p_{x}\rho^{x}_{Q},\quad\,A=\sum_{x}A_{x}.$

The pretty good measurement (PGM) is the measurement $\mathcal{M}^{pgm}_{X}$
with POVM elements $\\{E^{pgm}_{x}=A^{-1/2}A_{x}A^{-1/2}\\}$. We denote

$\displaystyle p^{pgm}_{g}(X|Q)_{\rho}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{x}p_{x}\operatorname{Tr}\left(E^{pgm}_{x}\rho^{x}_{Q}\right)$
$\displaystyle=\Pr[X=\mathcal{M}^{pgm}_{X}(Q)].$

######  Fact 6 (Optimality of PGM [16]).

For any cq-state $\rho_{XQ}=\sum_{x}p_{x}|x\rangle\langle
x|\otimes\rho^{x}_{Q},$ we have

$p^{pgm}_{g}(X|Q)_{\rho}\geq g(p^{opt}_{g}(X|Q)_{\rho}),$

where $g(x)=x^{2}+(1-x)^{2}/(d-1)$ and $d$ is the dimension of the register
$X$.

Note that $g(x)$ is convex everywhere and increasing when $x\in[1/d,1]$, and
$g(1/d)=1/d$. Also, note the bound from Fact 6 is better than the optimality
bound of Barnum and Knill [2] when the guessing probability is close to $1/d$.

### One-way communication complexity

In this paper we only consider the two party one-way model of communication.
Let $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}\cup\\{\bot\\}$ be a partial
function, $\mu$ be a distribution on $f^{-1}(\mathcal{Z})$ and $\epsilon\geq
0$. Let $\mu_{X}$ represent the marginal of $\mu$ on $\mathcal{X}$. In a two
party one-way communication protocol $\mathcal{P}$, Alice with input
$x\in\mathcal{X}$ communicates a message to Bob with input $y\in\mathcal{Y}$.
On receiving Alice’s message, Bob produces output of the protocol
$\mathcal{P}(x,y)$.

In a one-way classical communication protocol, Alice and Bob are allowed to
use public and private randomness (independent of the inputs). In a one-way
quantum communication protocol, Alice and Bob are allowed to do quantum
operations and Alice can send a quantum message (qubits) to Bob. In an
entanglement-assisted protocol, Alice and Bob start with a shared pure state
(independent of the inputs) and Alice communicates a quantum message to Bob.

Let $\mathcal{P}$ represent a one-way communication protocol.

######  Definition 10.

  1. 1.

$\mathrm{err}_{x,y}(\mathcal{P},f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Pr(\mathcal{P}(x,y)\neq
f(x,y)),$ 444For $(x,y)\notin
f^{-1}(\mathcal{Z}):\mathrm{err}_{x,y}(\mathcal{P},f)=0$.

  2. 2.

$\mathrm{err}(\mathcal{P},f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{x,y}\\{\mathrm{err}_{x,y}(\mathcal{P},f)\\},$

  3. 3.

$\mathrm{err}(\mathcal{P},f,\mu)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\operatorname*{\mathbb{E}}_{(x,y)\leftarrow\mu}[\mathrm{err}_{x,y}(\mathcal{P},f)],$

  4. 4.

$\mathrm{err}(\mathcal{P},f,\mu_{X})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{y}\\{\operatorname*{\mathbb{E}}_{x\leftarrow\mu_{X}}[\mathrm{err}_{x,y}(\mathcal{P},f)]\\}.$

  5. 5.

$\mathrm{CC}(\mathcal{P})$ be the maximum number of (qu)bits communicated in
$\mathcal{P}$.

######  Definition 11.

Let $\mathcal{P}$ represent a classical public-coin protocol.

  1. 1.

$\mathsf{R}^{1}_{\epsilon}(f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min\\{\mathrm{CC}(\mathcal{P})\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathrm{err}(\mathcal{P},f)\leq\epsilon\\}$.

  2. 2.

$\mathsf{R}^{1,\mu}_{\epsilon}(f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min\\{\mathrm{CC}(\mathcal{P})\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathrm{err}(\mathcal{P},f,\mu)\leq\epsilon\\}$.

  3. 3.

$\mathsf{R}^{1,\mu_{X}}_{\epsilon}(f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min\\{\mathrm{CC}(\mathcal{P})\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathrm{err}(\mathcal{P},f,\mu_{X})\leq\epsilon\\}$.

Intuitively, $\mathsf{R}^{1}_{\epsilon}(f)$ is the classical communication
complexity for worse case $(x,y)$, $\mathsf{R}^{1,\mu}_{\epsilon}(f)$ is the
classical communication complexity with $(x,y)$ averaged over the distribution
$\mu$, and $\mathsf{R}^{1,\mu_{X}}_{\epsilon}(f)$ is the classical
communication complexity with worst case $y$ while $x$ is averaged over the
distribution $\mu$.

######  Definition 12.

  1. 1.

The quantum one-way communication complexities $\mathsf{Q}^{1}_{\epsilon}(f)$,
$\mathsf{Q}^{1,\mu}_{\epsilon}(f)$ and $\mathsf{Q}^{1,\mu_{X}}_{\epsilon}(f)$
are defined similarly, by considering $\mathcal{P}$ to be a quantum one-way
protocol.

  2. 2.

The entanglement-assisted quantum one-way communication complexities
$\mathsf{Q}^{1,*}_{\epsilon}(f)$, $\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)$, and
$\mathsf{Q}^{1,\mu_{X},*}_{\epsilon}(f)$ are defined similarly, by considering
$\mathcal{P}$ to be an entanglement-assisted quantum one-way protocol.

The following result due to Yao [21] is a very useful fact connecting worst-
case and distributional communication complexities.

######  Fact 7 (Yao’s Principle [21]).

$\mathsf{R}^{1}_{\epsilon}(f)=\max_{\mu}\mathsf{R}^{1,\mu}_{\epsilon}(f)\quad;\quad$
$\mathsf{Q}^{1,*}_{\epsilon}(f)=\max_{\mu}\mathsf{Q}^{1,\mu,*}_{\epsilon}(f).$

######  Definition 13 (Column sparsity of a partial function).

For a partial function
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1,\bot\\}$, and for every
$y\in\mathcal{Y}$, let $S^{y}_{0}=\\{x|f(x,y)=0\\}$,
$S^{y}_{1}=\\{x|f(x,y)=1\\}$. We define column sparsity ($\mathsf{CS}(f)$) of
a partial function $f$ as follows:

$\mathsf{CS}(f)=\max_{y}\min\\{|S^{y}_{0}|,|S^{y}_{1}|\\}.$

######  Definition 14 (Markov-chain).

Let $ABC$ be joint random variables. We say $ABC$ forms a Markov-chain iff
$\mathrm{I}(A:C\leavevmode\nobreak\ |\leavevmode\nobreak\ B)=0$ and denote it
by $A\leftrightarrow B\leftrightarrow C$.

######  Fact 8 (Message-compression [10, 11]).

Let $XC$ be joint random variables and $\eta>0$. Define,

$\displaystyle T_{\eta}(X:C)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min_{R,M}\\{\ell(M)\leavevmode\nobreak\
|\leavevmode\nobreak\ X\leftrightarrow(R,M)\leftrightarrow
C^{\prime}\leavevmode\nobreak\ ;\leavevmode\nobreak\ $ $\displaystyle\quad
XR=X\otimes R\leavevmode\nobreak\ ;\leavevmode\nobreak\
XC\approx_{\eta}XC^{\prime}\\}.$

Above $\ell(M)$ represents the length (number of bits) of $M$. Let $(M,R)$
achieve the minimum above. This means that if Alice and Bob share the public
random string $R$, Alice can, with input $X$, generate $M$ (using $R,X$) and
send $M$ to Bob, who in turn can produce $C^{\prime}$ (using $(M,R)$). The
communication from Alice to Bob is $T_{\eta}(X:C)$. Furthermore,

$T_{\eta}(X:C)\leq\mathrm{I}_{\max}(X:C)+O(\log\log(1/\eta)).$

######  Fact 9 (Markov’s inequality).

For any nonnegative random variable $X$ and real number $a>0$,

$\Pr[X\geq a]\leq\frac{\operatorname*{\mathbb{E}}[X]}{a}.$

######  Fact 10.

For a projector $\Pi$, we have

$\|\Pi\|^{2}_{F}=\operatorname{rank}(\Pi).$

The following fact follows from Theorem $4$ in [8].

######  Fact 11 (Classical shadow [8]).

Fix $\epsilon,\delta\in(0,1)$ and $a>0$. Let
$\rho\in\mathcal{D}(\mathcal{H}_{R})$ be a quantum state on $n$ qubits and
$|R|=2^{n}$. Let
$T=O\left(a\frac{\log(\frac{1}{\delta})}{\epsilon^{2}}\right)$. Let
$\mathcal{M}^{STAB}$ be the random stabilizer measurement, i.e. do a random
Clifford unitary then measure in the computational basis. Let

$\displaystyle
S\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{M}^{STAB}(\rho)\otimes\mathcal{M}^{STAB}(\rho)$
$\displaystyle\quad\quad\quad\otimes\ldots\otimes\mathcal{M}^{STAB}(\rho)\
\text{(T times)},$

where $\mathcal{M}^{STAB}(\rho)$ is a classical representation of the post-
measurement stabilizer state. There exists a deterministic procedure $d(.)$
such that for any Hermitian matrix $A\in\mathcal{L}(\mathcal{H}_{R})$ with
$\|A\|^{2}_{F}\leq a$

$\Pr_{s\leftarrow S}(|d(A,s)-\mathrm{Tr}(A\rho)|\leq\epsilon)\geq 1-\delta.$

Additionally, $\log(\operatorname{supp}(S))\leq O(Tn^{2})$. We call $S$ a
classical shadow of $\rho$.

###### Proof.

We provide a sketch of the proof for completion. Since there are
$2^{O({n^{2}})}$ stabilizer states in $n$ qubits, $\mathcal{M}^{STAB}(\rho)$
has an efficient classical representation of $O(n^{2})$ bits, and thus $S$ can
be represented in $O(Tn^{2})$ bits. This proves that
$\log(\operatorname{supp}(S))\leq O(Tn^{2})$. Let ${\left|{x}\right\rangle}$
be the (random) stabilizer state corresponding to $\mathcal{M}^{STAB}(\rho)$.
For $x\leftarrow\mathcal{M}^{STAB}(\rho)$, we define
$d^{\prime}(A,x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{Tr}(A((2^{n}+1){\left|{x}\right\rangle}{\left\langle{x}\right|}-\mathbb{I}))$.
It can be shown that for any fixed Hermitian operator $A$,

$\operatorname*{\mathbb{E}}(d^{\prime}(A,X))=\operatorname*{\mathbb{E}}_{x\leftarrow
X}(d^{\prime}(A,x))=\mathrm{Tr}(A\rho)\quad;\quad$
$\mathsf{Var}(d^{\prime}(A,X))=O(\|A\|^{2}_{F}).$

Finally, the deterministic procedure $d(\cdot)$ uses $T$ values
$d^{\prime}(A,x_{1}),d^{\prime}(A,x_{2}),\ldots,d^{\prime}(A,x_{T})$, where
each $x_{i}\leftarrow\mathcal{M}^{STAB}(\rho)$, to estimate
$\mathrm{Tr}(A\rho)$ using the standard median-of-means approach. Using
Chebyshev’s inequality and the Chernoff bound, we obtain $\Pr_{s\leftarrow
S}(|d(A,s)-\mathrm{Tr}(A\rho)|\leq\epsilon)\geq 1-\delta.$ ∎

##  3 Product distribution proof

Here we restate Theorem 1 and provide its proof.

######  Theorem 3.

Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{Z}\cup\\{\bot\\}$ be a
partial function and $\mu$ be a product distribution supported on
$f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let $\eta>0$ and
$0\leq\epsilon\leq 1-1/d$. Then,

$\displaystyle\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu,*}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq\mathsf{Q}^{1,\mu}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu_{X}}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq
2\mathsf{Q}^{1,\mu_{X},*}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right),$
$\displaystyle\mathsf{R}^{1,\mu_{X}}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)$
$\displaystyle\quad\quad\leq\mathsf{Q}^{1,\mu_{X}}_{\epsilon}(f)+O\left(\log\log(1/\eta)\right).$

###### Proof.

The proofs of all the inequalities are all very similar. We give a detailed
proof of the first and state the differences to obtain the other inequalities
at the end. Recall we use the notation, $\psi$ to represent the state and also
the density matrix $|\psi\rangle\langle\psi|$, associated with
${\left|{\psi}\right\rangle}$.

Let $S^{y}_{z}=\\{x|f(x,y)=z\\}$ and $Q^{1,\mu,*}_{\epsilon}(f)=a$. Consider
an optimal distributional entanglement-assisted quantum communication
strategy. Let the initial state be

$\rho^{\prime}_{XYAB}=\sum_{x,y}\mu(x,y)|xy\rangle\langle
xy|\otimes|\rho^{\prime}_{AB}\rangle\langle\rho^{\prime}_{AB}|,$

where ${\left|{\rho^{\prime}_{AB}}\right\rangle}$ is the shared entanglement
between Alice and Bob (Alice, Bob hold registers $A$, $B$ respectively). Alice
applies a unitary $U:\mathcal{H}_{XA}\rightarrow\mathcal{H}_{XA^{\prime}D}$
such that $U=\sum_{x}|x\rangle\langle x|\otimes U^{x}$ (where
$U^{x}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A^{\prime}D}$ is a unitary
conditioned on $X=x$) and sends across register $D$ to Bob. Let the state at
this point be

$\rho_{XYA^{\prime}Q}=\sum_{x,y}\mu(x,y)|xy\rangle\langle
xy|\otimes\rho^{x}_{A^{\prime}Q},$

where $Q\equiv DB$. Since,
$\rho_{XB}=\rho^{\prime}_{XB}=\rho^{\prime}_{X}\otimes\rho^{\prime}_{B}=\rho_{X}\otimes\rho_{B}$,
from Fact 5 we have,

$\displaystyle\mathrm{I}_{\max}(X:Q)_{\rho}\leq 2\log(|D|)=2a.$ (3.1)

Bob performs measurement $\mathcal{M}^{y}$ with POVM elements
$\\{E^{y}_{z}:\forall z\in\mathcal{Z}\\}$ on register $Q$ conditioned on $Y=y$
to output $f(x,y)$. Then,

$\sum_{x,y}\mu(x,y)\operatorname{Tr}\left(\rho^{x}_{Q}E^{y}_{f(x,y)}\right)\geq
1-\epsilon.$

This implies,

$\displaystyle 1-\epsilon$
$\displaystyle\leq\sum_{x,y}\mu(x,y)\operatorname{Tr}\left(\rho^{x}_{Q}E^{y}_{f(x,y)}\right)$
$\displaystyle=\sum_{y}\mu(y)\operatorname{Tr}\left(\sum_{x}\mu(x)\rho^{x}_{Q}E^{y}_{f(x,y)}\right)$
$\displaystyle=\sum_{y}\mu(y)\sum_{z\in\mathcal{Z}}\operatorname{Tr}\left(\sum_{x\in
S^{y}_{z}}\mu(x)\rho^{x}_{Q}E^{y}_{z}\right)$
$\displaystyle=\sum_{y}\mu(y)\sum_{z\in\mathcal{Z}}\mu^{y}(z)\operatorname{Tr}\left(\rho_{Q}^{y,z}E^{y}_{z}\right),$
(3.2)

where we defined
$\mu^{y}(z)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{x\in
S^{y}_{z}}\mu(x)$ and
$\rho_{Q}^{y,z}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{\mu^{y}(z)}\sum_{x\in
S^{y}_{z}}\mu(x)\rho^{x}_{Q}$. Note that $\rho_{Q}^{y,z}$ are density matrices
and $\sum_{z\in\mathcal{Z}}\mu^{y}(z)=\sum_{z\in\mathcal{Z}}\sum_{x\in
S^{y}_{z}}\mu(x)=\sum_{x\in\mathcal{X}}\mu(x)=1$. We can view
$\sum_{z\in\mathcal{Z}}\mu^{y}(z)\operatorname{Tr}\left(\rho_{Q}^{y,z}E^{y}_{z}\right)$
as the success probability of distinguishing the cq-state
$\rho^{y}_{ZQ}=\sum_{z\in\mathcal{Z}}\mu^{y}(z)|z\rangle\langle
z|\otimes\rho^{y,z}_{Q}$ with measurement $\mathcal{M}^{y}$ with POVM elements
$\\{E^{y}_{z}:\forall z\in\mathcal{Z}\\}$. We have,

$\displaystyle 1-\epsilon\leq\sum_{y}\mu(y)\Pr[Z^{y}=\mathcal{M}^{y}(Q)],$

where we defined the random variable
$Z^{y}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}f(X,y)$. Applying the function
$g$ of Fact 6 to both sides and using the convexity of $g$, we have

$\displaystyle g(1-\epsilon)$ $\displaystyle\leq
g\left(\sum_{y}\mu(y)\Pr[Z^{y}=\mathcal{M}^{y}(Q)]\right)$
$\displaystyle\leq\sum_{y}\mu(y)g\left(\Pr[Z^{y}=\mathcal{M}^{y}(Q)]\right).$
(3.3)

We now fix $y$ and replace the optimal measurement Bob does by the PGM
$\mathcal{M}^{pgm,y}_{Z}$. $\mathcal{M}^{pgm,y}_{Z}$ consists of POVM elements
$E^{pgm,y}_{z}=A^{-1/2}A^{y}_{z}A^{-1/2}$ for all $z\in\mathcal{Z}$, where
$A^{y}_{z}=\mu^{y}(z)\rho^{y,z}_{Q}$, and $A=\sum_{z\in\mathcal{Z}}A^{y}_{z}$.
Note that $A^{y}_{z}=\sum_{x\in S^{y}_{z}}\mu(x)\rho^{x}_{Q}$, and
$A=\sum_{x}\mu(x)\rho^{x}_{Q}$ is independent of $y$. From Fact 6, the
optimality of PGM, we have that for all $y$,

$g\left(\Pr[Z^{y}=\mathcal{M}^{y}(Q)]\right)\leq\Pr[Z^{y}=\mathcal{M}^{pgm,y}_{Z}(Q)].$

Using Equation (3.3),

$\displaystyle g(1-\epsilon)\leq$
$\displaystyle\sum_{y}\mu(y)\Pr[Z^{y}=\mathcal{M}^{pgm,y}_{Z}(Q)]$
$\displaystyle=$
$\displaystyle\sum_{y}\mu(y)\operatorname{Tr}\left(\sum_{x}\mu(x)\rho^{x}_{Q}E^{pgm,y}_{f(x,y)}\right),$
(3.4)

where the last line follows logic similar to Equation (3). Notice that

$\displaystyle E^{pgm,y}_{z}$ $\displaystyle=A^{-1/2}A^{y}_{z}A^{-1/2}$
$\displaystyle=A^{-1/2}\left(\sum_{x\in
S^{y}_{z}}\mu(x)\rho^{x}_{Q}\right)A^{-1/2}$ $\displaystyle=\sum_{x\in
S^{y}_{z}}A^{-1/2}A_{x}A^{-1/2}$ $\displaystyle=\sum_{x\in
S^{y}_{z}}E^{pgm}_{x}=\sum_{x^{\prime}}\delta_{z,f(x^{\prime},y)}E^{pgm}_{x^{\prime}},$

where $\\{E^{pgm}_{x}:\forall x\in\mathcal{X}\\}$ are the POVM elements of the
PGM that guesses $X$ from $Q$. Therefore, instead of doing
$\mathcal{M}^{pgm,y}_{Z}$, we can measure with $\mathcal{M}^{pgm}_{X}$,
getting a guess $x^{\prime}$, and then compute $f(x^{\prime},y)$ as our guess
of $Z^{y}=f(X,y)$. That is,

$\displaystyle\operatorname{Tr}\left(\sum_{x}\mu(x)\rho^{x}_{Q}E^{pgm,y}_{f(x,y)}\right)$
$\displaystyle=\operatorname{Tr}\left(\sum_{x}\mu(x)\rho^{x}_{Q}\sum_{c\in
S^{y}_{f(x,y)}}E^{pgm}_{c}\right).$ (3.5)

More precisely, define $C\equiv\mathcal{M}^{pgm}_{X}(Q)$. Since $C$ is a
classical random variable that is independent of $y$, Alice can compute $C$ by
herself. Consider the intermediate classical one-way communication protocol
where Alice computes and sends $C=\mathcal{M}^{pgm}_{X}(Q)$ to Bob, and Bob
predicts $f(x,y)$ with $z=f(c,y)$. The success probability of this
intermediate protocol is

$\displaystyle\sum_{y}\mu(y)\sum_{x}\mu(x)\sum_{c\in S^{y}_{z}}\Pr[C=c|X=x]$
$\displaystyle=$
$\displaystyle\sum_{y}\mu(y)\operatorname{Tr}\left(\sum_{x}\mu(x)\rho^{x}_{Q}\sum_{c\in
S^{y}_{f(x,y)}}E^{pgm}_{c}\right)$ $\displaystyle\geq g(1-\epsilon),$ (3.6)

where we used Equation (3) and Equation (3) in the last line.

In this intermediate protocol, the message $C$ that Alice sent is not short.
In fact, it has the same length as $X$. However, $C$ has low max-information
with $X$. By Equation (3.1) and Fact 2 we have

$\displaystyle\mathrm{I}_{\max}(X:C)=\mathrm{I}_{\max}(X:\mathcal{M}^{pgm}_{X}(Q))$
$\displaystyle\leq\mathrm{I}_{\max}(X:Q)_{\rho}\leq 2a.$

Therefore using Fact 8, we can compress $C$ and get a classical one-way
communication protocol with message $M$ and public-coin $R$, such that

$\displaystyle\ell(M)\leq 2a+O(\log\log(1/\eta)),$ (3.7)

and success probability $g(1-\epsilon)-\eta$. Therefore
$\mathsf{R}^{1,\mu}_{2\epsilon-d\epsilon^{2}/(d-1)+\eta}(f)\leq
2a+O(\log\log(1/\eta))$ which gives the desired (bound).

To obtain the second inequality we note that Alice and Bob did not have the
starting state ${\rho^{\prime}_{AB}}$, so the register $B$ is empty, and in
Equation (3.1) we have instead

$\displaystyle\mathrm{I}_{\max}(X:Q)_{\rho}=\mathrm{I}_{\max}(X:D)_{\rho}\leq\log(|D|)=a.$
(3.8)

The inequality is because of Fact 2. Everything else follows.

To obtain the third inequality we basically condition on every possible $y$,
i.e. changing "$\sum_{y}\mu(y)$" in the proof to "for all $y$" and
"$\sum_{x,y}\mu(x,y)$" to "for all $y$ , $\sum_{x}\mu(x)$". We also do not
need to use the convexity of Fact 6.

To obtain the fourth inequality, we combine the changes to obtain the second
and the third inequalities. ∎

##  4 Non-product distribution proof

Here we restate Theorem 2 and provide a proof.

######  Theorem 4.

Let $\epsilon,\eta>0$ such that $\epsilon/\eta+\eta<0.5$. Let
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1,\bot\\}$ be a partial
function and $\mu$ be a distribution supported on $f^{-1}(0)\cup f^{-1}(1)$.
Then,
$\mathsf{R}^{1,\mu}_{3\eta}(f)=O\left(\frac{\mathsf{CS}(f)}{\eta^{3}}\mathsf{Q}^{1,\mu}_{{\epsilon}}(f)\right)$,
where

$\mathsf{CS}(f)=\max_{y}\min_{z\in\\{0,1\\}}\\{|\\{x\leavevmode\nobreak\
|\leavevmode\nobreak\ f(x,y)=z\\}|\\}\enspace.$

###### Proof.

Let $S^{y}_{0}=\\{x|f(x,y)=0\\}$, $S^{y}_{1}=\\{x|f(x,y)=1\\}$ and
$\mathsf{Q}^{1,\mu}_{\epsilon}(f)=a$. Consider an optimal quantum protocol
$\mathcal{P}$ where Alice prepares the quantum message $Q$ according to the
cq-state $\psi_{XQ}=\sum_{x}\mu(x)|x\rangle\langle x|\otimes\psi^{x}_{Q}$, and
Bob performs measurement $\mathcal{M}^{y}$ with POVM elements
$\\{E^{y}_{0},E^{y}_{1}\\}$ to output $f(x,y)$. We can assume, Alice sends
$\psi^{x}_{Q}$ along with its canonical purification since it only increases
the quantum communication by a multiplicative factor of $2$. Also, we can
assume that for every $y$, POVM elements $\\{E^{y}_{0},E^{y}_{1}\\}$ are
projectors, since Alice can send ancilla and Bob can realize POVM operators as
projectors (Fact 3). From here on, we assume $\psi^{x}_{Q}$ is a pure state
${\left|{\psi^{x}_{Q}}\right\rangle}$ and $E^{y}=\\{E^{y}_{0},E^{y}_{1}\\}$
are projectors for every $x,y$ respectively. Since
$\mathsf{Q}^{1,\mu}_{\epsilon}(f)=a$, we have $\log|Q|\leq a$ and

$\displaystyle\sum_{x,y}\mu(x,y)\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|E^{y}_{f(x,y)}\right)\geq
1-\epsilon.$

For all $y$, define,

$\displaystyle\forall x\in
S^{y}_{0},\quad{\left|{\tilde{\psi}^{x}_{Q}}\right\rangle}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{E^{y}_{0}{\left|{\psi^{x}_{Q}}\right\rangle}}\quad$
$\displaystyle\text{and}\quad\tilde{E}^{y}_{0}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathsf{Proj}\left(\operatorname{supp}\left(\sum_{x\in
S^{y}_{0}}|\tilde{\psi}^{x}_{Q}\rangle\langle\tilde{\psi}^{x}_{Q}|\right)\right),$
$\displaystyle\forall x\in
S^{y}_{1},\quad{\left|{\tilde{\psi}^{x}_{Q}}\right\rangle}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{E^{y}_{1}{\left|{\psi^{x}_{Q}}\right\rangle}}\quad$
$\displaystyle\text{and}\quad\tilde{E}^{y}_{1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathsf{Proj}\left(\operatorname{supp}\left(\sum_{x\in
S^{y}_{1}}|\tilde{\psi}^{x}_{Q}\rangle\langle\tilde{\psi}^{x}_{Q}|\right)\right),$

where ${\left|{\tilde{\psi}^{x}_{Q}}\right\rangle}$ are unnormalized vectors
with length less than $1$. Note that $\tilde{E}^{y}_{0}\leq
E^{y}_{0},\tilde{E}^{y}_{1}\leq E^{y}_{1},$
$\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|E^{y}_{0}\right)=\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{0}\right)$
for every $x\in S^{y}_{0}$ and
$\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|E^{y}_{1}\right)=\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{1}\right)$
for every $x\in S^{y}_{1}$. Also,
$\|\tilde{E}^{y}_{0}\|_{F}^{2}\leq|S^{y}_{0}|$ and
$\|\tilde{E}^{y}_{1}\|_{F}^{2}\leq|S^{y}_{1}|$ from Fact 10. Let

$\displaystyle
K=\max_{y}\min\\{\|\tilde{E}^{y}_{0}\|^{2}_{F},\|\tilde{E}^{y}_{1}\|^{2}_{F}\\}.$

Let $b_{y}=i$ be such that $|S^{y}_{i}|\leq|S^{y}_{1-i}|$. For $x$ such that
$f(x,y)=b_{y}$, we have

$\displaystyle\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{b_{y}}\right)=\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|E^{y}_{b_{y}}\right),$
(4.1)

and if $f(x,y)=1-b_{y}$, then

$\displaystyle\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{b_{y}}\right)\leq\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|E^{y}_{b_{y}}\right).$
(4.2)

The (intermediate) classical protocol $\mathcal{P}_{1}$ is as follows.

  1. 1.

Alice (on input $x$) prepares
$T=O\left(\frac{K}{\eta^{2}}\log\left(\frac{1}{\eta}\right)\right)$ copies of
${\left|{\psi^{x}_{Q}}\right\rangle}$, i.e.
${\left|{\psi^{x}_{Q}}\right\rangle}^{\otimes T}$ and measures them
independently in stabilizer measurement ($\mathcal{M}^{STAB}$) to generate a
classical random variable $S_{x}=\mathcal{M}^{STAB}(Q)^{\otimes T}$.

  2. 2.

Alice sends $S_{x}$ to Bob. Note that $\ell(S_{x})=O(T\ell(Q)^{2})=O(Ta^{2})$.

  3. 3.

Bob (on input $y$) estimates
$\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{b_{y}}\right)$
via a deterministic procedure $d(.)$ such that (from Fact 11)

$\displaystyle\Pr_{s\leftarrow
S_{x}}(|d(\tilde{E}^{y}_{b_{y}},s)-\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{b_{y}}\right)|\leq\eta)$
$\displaystyle\geq 1-\eta.$ (4.3)

  4. 4.

If Bob’s estimated value turns out to be less than $0.5$, he outputs
$1-b_{y}$, otherwise $b_{y}$.

Let $\mathcal{I}(x,y,s)$ be the indicator function such that
$\mathcal{I}(x,y,s)=1$ if subsample $s$ results in Bob (with input $y$)
estimating
$\operatorname{Tr}\left(|\psi^{x}_{Q}\rangle\langle\psi^{x}_{Q}|\tilde{E}^{y}_{b_{y}}\right)$
upto additive error $\eta$. For every $x,y$, define
$\mathsf{good}_{xy}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{s\in\operatorname{supp}(S_{x})\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{I}(x,y,s)=1\\}$ and
$\mathsf{bad}_{xy}=\operatorname{supp}(S_{x})\setminus\mathsf{good}_{xy}$.
Define,
$\mathsf{good}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{(x,y)\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathrm{err}_{x,y}(\mathcal{P},f)\leq\epsilon/\eta\\}$.
From Markov’s inequality $\Pr_{(x,y)\leftarrow\mu}((x,y)\in\mathsf{good})\geq
1-\eta$. Using Equations (3), (4.1), (4.2) and $\epsilon/\eta+\eta<0.5$, we
note that when $(x,y)\in\mathsf{good}$ and $s\in\mathsf{good}_{xy}$, Bob gives
correct answer for $f(x,y)$. Thus, the probability of correctness of
$\mathcal{P}_{1}$ is at least,

$\displaystyle\sum_{(x,y)\in\mathsf{good}}\mu(x,y)\cdot\Pr(S_{x}\in\mathsf{good}_{xy})\geq
1-2\eta.$

In $\mathcal{P}_{1}$, the message $S$ (averaged over $x$) that Alice sent is
of size $O(Ta^{2})$. However, $S$ has low mutual information with $X$. Using
Fact 2, we have

$\displaystyle\mathrm{I}_{\max}(X:S)=\mathrm{I}_{\max}(X:(\mathcal{M}^{STAB}(Q))^{\otimes
T})$ $\displaystyle\leq\mathrm{I}_{\max}(X:Q^{\otimes T})_{\psi}\leq Ta.$

Therefore using Fact 8, we can compress $S$ and get a classical one-way
communication protocol with message $M$ and public-coin $R$, such that

$\displaystyle\ell(M)\leq Ta+O(\log\log(1/\eta)),$ (4.4)

and success probability $1-2\eta-\eta=1-3\eta$. Thus, we have
$\mathsf{R}^{1,\mu}_{3\eta}(f)\leq Ta+O(\log\log(1/\eta))$. Noting
$K\leq\mathsf{CS}(f)$, we have the desired. ∎

##  5 Acknowledgment

The work of RJ was supported in part by the National Research Foundation,
Singapore, under Grant NRF2021-QEP2-02-P05; and in part by the Ministry of
Education, Singapore, through the Research Centers of Excellence Program. The
work of NGB was done while he was a graduate student at the Centre for Quantum
Technologies and was supported by the Ministry of Education, Singapore through
the Research Centers of Excellence Program. The work of HL was funded by MOST
Grant no. 110-2222-E-007-002-MY3.

## References

  * Ambainis et al. [1999] Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani.  Dense quantum coding and a lower bound for 1-way quantum automata.  In _Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing_ , STOC ’99, pages 376–383, New York, USA, 1999. Association for Computing Machinery.  ISBN 1581130678.  doi: 10.1145/301250.301347.
  * Barnum and Knill [2002] H. Barnum and E. Knill.  Reversing quantum dynamics with near-optimal quantum and classical fidelity.  _Journal of Mathematical Physics_ , 43(5):2097–2106, 04 2002.  ISSN 0022-2488.  doi: 10.1063/1.1459754.
  * Berta et al. [2011] Mario Berta, Matthias Christandl, and Renato Renner.  The quantum reverse shannon theorem based on one-shot information theory.  _Communications in Mathematical Physics_ , 306(3):579–615, 2011.  doi: 10.1007/s00220-011-1309-7.
  * Buhrman et al. [1999] Harry Buhrman, Wim van Dam, Peter Høyer, and Alain Tapp.  Multiparty quantum communication complexity.  _Physical Review A_ , 60:2737–2741, October 1999.  doi: 10.1103/PhysRevA.60.2737.
  * Buhrman et al. [2001] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  _Phys. Rev. Lett._ , 87:167902, Sep 2001.  doi: 10.1103/PhysRevLett.87.167902.  URL https://link.aps.org/doi/10.1103/PhysRevLett.87.167902.
  * Datta [2009] Nilanjana Datta.  Min- and max-relative entropies and a new entanglement monotone.  _IEEE Transactions on Information Theory_ , 55(6):2816–2826, June 2009.  doi: 10.1109/tit.2009.2018325.  URL https://doi.org/10.1109%2Ftit.2009.2018325.
  * Gavinsky et al. [2007] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf.  Exponential separations for one-way quantum communication complexity, with applications to cryptography.  In _Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing_ , STOC ’07, pages 516–525, New York, USA, 2007. Association for Computing Machinery.  ISBN 9781595936318.  doi: 10.1145/1250790.1250866.  URL https://doi.org/10.1145/1250790.1250866.
  * Huang et al. [2020] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  _Nature Physics_ , 16(10):1050–1057, 2020.  ISSN 1745-2481.  doi: 10.1038/s41567-020-0932-7.  URL https://doi.org/10.1038/s41567-020-0932-7.
  * Jain and Zhang [2009] Rahul Jain and Shengyu Zhang.  New bounds on classical and quantum one-way communication complexity.  _Theoretical Computer Science_ , 410(26):2463–2477, 2009.  ISSN 0304-3975.  doi: https://doi.org/10.1016/j.tcs.2008.10.014.  URL https://www.sciencedirect.com/science/article/pii/S0304397508007627.
  * Jain et al. [2003] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen.  A direct sum theorem in communication complexity via message compression.  In _Proceedings of the 30th international conference on Automata, languages and programming_ , ICALP’03, pages 300–315, Berlin, Heidelberg, 2003. Springer-Verlag.  ISBN 3-540-40493-7.  URL http://dl.acm.org/citation.cfm?id=1759210.1759242.
  * Jain et al. [2005] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen.  Prior entanglement, message compression and privacy in quantum communication.  In _Proceedings of the 20th Annual IEEE Conference on Computational Complexity_ , pages 285–296, Washington, DC, USA, 2005. IEEE Computer Society.  ISBN 0-7695-2364-1.  doi: 10.1109/CCC.2005.24.  URL http://dl.acm.org/citation.cfm?id=1068502.1068658.
  * Jain et al. [2008] Rahul Jain, Hartmut Klauck, and Ashwin Nayak.  Direct product theorems for classical communication complexity via subdistribution bounds: Extended abstract.  In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ , STOC ’08, pages 599–608, New York, USA, 2008. Association for Computing Machinery.  ISBN 9781605580470.  doi: 10.1145/1374376.1374462.  URL https://doi.org/10.1145/1374376.1374462.
  * Konig and Terhal [2008] Robert T. Konig and Barbara M. Terhal.  The bounded-storage model in the presence of a quantum adversary.  _IEEE Transactions on Information Theory_ , 54(2):749–762, 2008.  doi: 10.1109/TIT.2007.913245.
  * Kremer et al. [1995] Ilan Kremer, Noam Nisan, and Dana Ron.  On randomized one-round communication complexity.  In _Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’95, pages 596–605, New York, USA, 1995. Association for Computing Machinery.  ISBN 0897917189.  doi: 10.1145/225058.225277.  URL https://doi.org/10.1145/225058.225277.
  * Kushilevitz and Nisan [1996] Eyal Kushilevitz and Noam Nisan.  _Communication Complexity_.  Cambridge University Press, 1996.  doi: 10.1017/CBO9780511574948.
  * Renes [2017] Joseph M. Renes.  Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations.  _Phys. Rev. A_ , 96:042328, Oct 2017.  doi: 10.1103/PhysRevA.96.042328.  URL https://link.aps.org/doi/10.1103/PhysRevA.96.042328.
  * Watrous [2018] John Watrous.  _The Theory of Quantum Information_.  Cambridge University Press, 2018.  doi: 10.1017/9781316848142.
  * Wilde [2012] Mark M. Wilde.  _Quantum Information Theory_.  Cambridge University Press, 2012.  ISBN 9781139525343.  doi: 10.1017/CBO9781139525343.
  * Yao [1979] Andrew Chi-Chih Yao.  Some complexity questions related to distributive computing(preliminary report).  In _Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing_ , STOC ’79, pages 209–213, New York, USA, 1979. Association for Computing Machinery.  ISBN 9781450374385.  doi: 10.1145/800135.804414.  URL https://doi.org/10.1145/800135.804414.
  * Yao [1993] Andrew Chi-Chih Yao.  Quantum circuit complexity.  In _Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science_ , pages 352–361, 1993.  doi: 10.1109/SFCS.1993.366852.
  * Yao [1977] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In _18th Annual Symposium on Foundations of Computer Science (sfcs 1977)_ , pages 222–227, 1977.  doi: 10.1109/SFCS.1977.24.


# Rehabilitation Exercise Repetition Segmentation and Counting using Skeletal
Body Joints

Ali Abedi1, Paritosh Bisht2, Riddhi Chatterjee2, Rachit Agrawal2, Vyom
Sharma2,
Dinesh Babu Jayagopi2, Shehroz S. Khan1,3 1KITE Research Institute– Toronto
Rehabilitation Institute, University Health Network, Canada
2Multimodal Perception Lab, International Institute of Information Technology
Bangalor, India
3Institute of Biomedical Engineering, University of Toronto, Canada
{ali.abedi<EMAIL_ADDRESS>{paritosh.bisht, riddhi.chatterjee,
rachit.agrawal, vyom.sharma<EMAIL_ADDRESS>
###### Abstract

Physical exercise is an essential component of rehabilitation programs that
improve quality of life and reduce mortality and re-hospitalization rates. In
AI-driven virtual rehabilitation programs, patients complete their exercises
independently at home, while AI algorithms analyze the exercise data to
provide feedback to patients and report their progress to clinicians. To
analyze exercise data, the first step is to segment it into consecutive
repetitions. There has been a significant amount of research performed on
segmenting and counting the repetitive activities of healthy individuals using
raw video data, which raises concerns regarding privacy and is computationally
intensive. Previous research on patients’ rehabilitation exercise segmentation
relied on data collected by multiple wearable sensors, which are difficult to
use at home by rehabilitation patients. Compared to healthy individuals,
segmenting and counting exercise repetitions in patients is more challenging
because of the irregular repetition duration and the variation between
repetitions. This paper presents a novel approach for segmenting and counting
the repetitions of rehabilitation exercises performed by patients, based on
their skeletal body joints. Skeletal body joints can be acquired through depth
cameras or computer vision techniques applied to RGB videos of patients.
Various sequential neural networks, including many-to-many models (with binary
sequence output and density map output) and many-to-one models (with a single
output), are designed to analyze the sequences of skeletal body joints and
perform repetition segmentation and counting. Extensive experiments on three
publicly available rehabilitation exercise datasets, KIMORE, UI-PRMD, and
IntelliRehabDS, demonstrate the superiority of the proposed method compared to
previous methods. The proposed method enables accurate exercise analysis while
preserving privacy, facilitating the effective delivery of virtual
rehabilitation programs.

###### Index Terms:

exercise segmentation, exercise repetition counting, skeletal body joints,
LSTM, transformer, convolutional neural network, virtual rehabilitation

##  I Introduction

Referral of patients to rehabilitation programs following a stroke, cardiac
event, or injury is a common practice aimed at improving patients’ quality of
life and reducing re-hospitalization and death rates [1]. Central to these
programs are regular and repetitive exercises that enable patients to regain
mobility and strength [1]. Recently, Artificial Intelligence (AI)-driven
virtual rehabilitation has emerged as a promising approach to delivering
rehabilitation programs remotely to patients in their homes [2]. This approach
involves the use of various sensors to capture patients’ movements and the use
of AI algorithms to analyze patients’ movements during exercise [2, 3]. The
analysis results can be used to provide patients with feedback on the quality
or completion of their exercises [3, 4]. Additionally, clinicians can also use
the analysis results to monitor patients’ progress and take appropriate
interventions.

In rehabilitation programs, patients are typically prescribed specific
exercises with designated numbers of sets and repetitions [5, 1, 6, 7, 8].
Evaluating exercise performance relies on objective criteria such as
compliance with the prescribed number of sets and repetitions, repeating
exercises in a constant manner, proper technique and quality of movements, and
correct posture of various body parts [6, 5]. Therefore, repetition (temporal)
segmentation, the process of dividing a continuous sequence of movement data
into individual repetitions, is the first step in an AI-driven exercise
evaluation pipeline [5]. Exercise repetition counting can either be derived
from the segmentation process or executed as a separate task.

A variety of data modalities were used for repetition segmentation and
counting [20], including Inertial Measurement Unit (IMU) sensor data [9, 10,
11, 12, 13, 14, 15], video data [16, 17, 18], and skeletal body joints [19].
Existing algorithms for segmenting human movement can be divided into
unsupervised and supervised algorithms [20]. Unsupervised algorithms, which do
not require labeled data to develop, include thresholding, template matching,
and exemplar-based approaches [21, 20]. Supervised algorithms requiring
labeled data to be trained on include Support Vector Machines (SVM) [11],
Hidden Markov Model (HMM) [13], Convolutional Neural Networks (CNNs) [10], and
the combination of CNNs and Finite State Machines (FSMs) [9]. The existing
works on repetition counting [18, 19, 28, 15] are not capable of segmenting
movement data into individual repetitions, that is, they are not capable of
determining the start and end timestamps of individual repetitions. Video-
based approaches are not privacy-preserving and are computationally
prohibitive [16, 17, 18]. The IMU-based approaches require wearing multiple
IMU sensors while exercising [9, 10, 11, 12, 13, 14, 15], which is challenging
in the real world, i.e., in rehabilitation patients’ homes. The previous works
on healthy individuals [16, 17, 18, 19] cannot be directly used on
rehabilitation patients due to the fact that segmenting and counting exercise
repetitions is more challenging in patients due to irregularities in the
duration and completion of exercises resulting from their respective
impairments [6, 5].

This paper presents novel methods for rehabilitation exercise repetition
segmentation and counting from the skeletal body joints of patients. Various
many-to-many and many-to-one deep sequential neural network architectures,
including Long Short Term Memory (LSTM) and a combination of LSTM and CNN, are
designed to analyze the sequences of skeletal body joints and perform
repetition segmentation and counting. Our primary contributions are as
follows:

  * •

This is the first work on rehabilitation exercise repetition segmentation
using skeletal body joints collected by depth cameras or extracted from RGB
video using advanced computer-vision techniques.

  * •

We developed neural network architectures capable of analyzing sequences of
body joints, i.e., multivariate time series.

  * •

We conducted extensive experiments on three publicly available rehabilitation
exercise datasets and demonstrated the effectiveness of the proposed method
compared to the previous methods.

As a point of clarification, the purpose of this paper is not rehabilitation
exercise recognition/classification nor rehabilitation exercise
quality/correctness assessment. Specifically, this paper focuses on the
temporal (not spatial) segmentation of rehabilitation exercises into
individual repetitions and counting the number of repetitions.

##  II Related Work

This section reviews existing research on repetitive action segmentation and
counting, with an emphasis on rehabilitation exercise segmentation and
counting. The literature review is organized according to the data modality
used for segmentation and counting.

###  II-A Rehabilitation Exercise Segmentation from IMU sensors

Lin et al. [11] proposed an approach for segmenting rehabilitation exercises
into individual repetitions using the data collected by IMU wearable sensors
worn on the hip, knee, and ankle. Segmentation was defined as a binary
classification problem in which movement data at consecutive timestamps are
classified into segment points or non-segment points. To perform segmentation,
after several steps of preprocessing, including filtering, down-sampling, and
windowing, the IMU signal is classified into segment or non-segment classes by
an SVM. Lin et al. [13] proposed a two-stage approach in which first, segment
point candidates are identified by analyzing the velocity features extracted
from the IMU signal. Then, HMMs are used to recognize segment locations from
segment point candidates. The method was evaluated on three publicly available
IMU datasets and achieved high accuracy. Brennan et al. [9, 10] proposed a
two-stage approach in which first, a CNN classifies sliding windows of the IMU
signals into either ”dynamic” or ”dormant” classes. The classification results
are then streamed into an FSM that keeps track of the classes of consecutive
windows and outputs the starting and ending points of repetitions. They
achieved high accuracy in shoulder and knee exercises. Bevilacqua et al. [14]
proposed a joint rehabilitation exercise motion primitive segmentation and
classification using a mixture of LSTMs and boosting aggregation. Their method
was evaluated on accelerometer and gyroscope data and achieved high exercise
primitive classification accuracy.

###  II-B Rehabilitation Exercise Repetition Counting from Skeletal Body
Joints

Hsu et al. [19] proposed a rehabilitation exercise repetition counting using
Skeletal body joints data. Initially, the pairwise cosine similarity of the
skeleton time series data is calculated. A spectrogram is then constructed
based on the pairwise cosine similarity. A repetition count is then calculated
by integrating from the spectrogram. The method was evaluated on the UI-PRMD
rehabilitation exercise dataset [7] and the MM-Fit fitness exercise dataset
[34] and achieved low Mean Absolute Error (MAE).

###  II-C Repetitive Action Segmentation from Videos

Hu et al. [16] introduced a large-scale repetitive action counting dataset,
named RepCount, containing 1451 videos with about 20000 annotations of the
start and end of repetitions. The dataset contains in-the-wild videos of
healthy individuals exercising. They have also proposed a deep neural network
architecture, named TransRAC [16], for repetition counting that was trained
and evaluated on the RepCount dataset. In TransRAC, with step sizes of 1, 2,
and 4, multi-scale video sequences are generated from the input video. After
extracting features from the multi-scale video sequences by an encoder neural
network, temporal correlations are calculated between the extracted features,
and correlation matrices are created. The concatenation of the correlation
matrices is input to a transformer to output a density map as a prediction.
The ground-truth density maps are generated by approximating a Gaussian
distribution between the start and end of each repetition [16]. To overcome a
major limitation of TransRAC, its inability to handle long videos, Chung et
al. [17] proposed a video transformer equipped with class token distillation
and marginally improved the repetition counting results of TransRAC. Zhang et
al. [18] proposed an approach for repetition counting from videos
incorporating the corresponding sound of the video. An S3D-based architecture
was used for repetition counting from video, while a ResNet-18-based neural
network was used for repetition counting from audio. The results on an
audiovisual dataset showed improvements when audio data is added to video data
for repetition counting. To learn more about repetitive action segmentation
and counting from videos using deep learning algorithms, please refer to [24,
25, 26, 27, 28, 18].

The major disadvantage of the IMU-based methods [11, 13, 10, 9, 14] is that
they require the determination of various parameters, including window sizes
and thresholds. Additionally, these methods are capable of analyzing
multivariate time series with a small number of variables, corresponding to
the number of IMU sensors worn during exercise, but are unable to analyze
multivariate time series with high dimensionalities, such as all the joints of
the skeletal system. Moreover, it may be infeasible for rehabilitation
patients to wear multiple IMU sensors while exercising independently at home.
The method proposed by Hsu et al. [19] was designed for rehabilitation
exercise counting and is not capable of segmenting rehabilitation exercises.
Exercise temporal segmentation into individual repetitions is required for
accurate exercise assessment [5]. A limitation of video-based methods [16, 17,
18, 24, 25, 26, 27, 28] is their complexity and their large number of training
parameters, in addition to privacy concerns. There is no previous method for
segmenting rehabilitation exercises based on skeletal body joints [5]. In
order to fill the gap in the literature, this paper proposes deep-learning
algorithms for segmenting and counting repetitions in rehabilitation exercises
performed by patients. The proposed method facilitates exercise assessment and
feedback generation for patients in virtual rehabilitation programs without
the need for body-worn sensors.

##  III Method

The input to the proposed method is the sequence of skeletal body joints of a
patient doing rehabilitation exercises. The output is the segmented sequence
into individual exercise repetitions and the total number of repetitions. The
sequence of features extracted from the sequence of skeletal body joints is
fed to a sequential neural network for exercise repetition segmentation and
counting.

The proposed method can work with either a depth camera capable of capturing
skeletal body joints or a regular RGB camera. In the latter case, an
additional module is required in order to extract skeletal body joints from
RGB video frames. Several libraries are available for extracting body joints
from videos, including MediaPipe [22] and OpenPose [23].

The sequential neural networks in the proposed method can be provided with
three types of data, raw body joints, exercise-specific features extracted
from the body joints, and their concatenation. Inspired by Guo and Khan [29]
worked on the KIMORE dataset, exercise-specific features are those calculated
based on the angles between the body joints that are moving in specific
exercises. For instance, for upper-extremity rehabilitation exercises for
stroke patients, the shoulder-wrist angle is an exercise-specific feature [29,
6]. The body joints or features, extracted from each frame of the input data,
are provided for each timestamp of a sequential neural network.

###  III-A Sequential Neural Network

Three sequential neural networks are used to analyze the sequence of features
and perform rehabilitation exercise segmentation and counting. The core of all
the networks is an LSTM trailed by a 1D CNN followed by a fully connected
neural network.

####  III-A1 Many-to-many with Binary Sequence Output

The sequential neural network is trained to output a binary sequence.
Corresponding to the input at every timestamp (the body joints or extracted
feature vector from every frame), the network generates one or zero. The
output of one indicates that the input frame at a particular timestamp is a
frame after a repetition of an exercise is complete or before the beginning of
the next repetition, whereas an output of zero indicates that the input frame
is during a repetition of an exercise. Using the generated output binary
sequence, repetition segmentation is performed based on the occurrences of
outputs of one among outputs of zero. Repetition counting is done by counting
the number of segmented repetitions.

####  III-A2 Many-to-many with Density Map Output

The sequential neural network is trained to output a density map. A density
map is a vector consisting of the same number of elements as the number of
frames in the input, i.e., the number of timestamps in the sequential neural
network. The ground-truth density maps are generated by approximating a
Gaussian distribution between the start and end of each repetition [16].
Repetition segmentation is performed by finding the peaks in the predicted
density map. Repetition counting is done by counting the number of segmented
repetitions.

####  III-A3 Many-to-one with Repetition Counts Output

By summing the outputs of the sequential neural network at consecutive
timestamps, it will be converted to a many-to-one sequential neural network
and is trained to output the number of repetitions. Unlike the two previous
architectures, this architecture can only perform repetition counting and not
segmentation.

The details of the parameters of the sequential neural networks are explained
in Section IV-C.

##  IV Experiments

This section evaluates the performance of the proposed method on three
publicly available datasets using different evaluation metrics and in
comparison to previous methods.

###  IV-A Datasets

####  IV-A1 KIMORE

The KIMORE dataset [6] contains RGB and depth videos along with body joint
position and orientation data captured by the Kinect camera. The data were
collected from 78 subjects, including 44 healthy subjects and 34 patients with
motor dysfunction (stroke, Parkinson’s disease, and low back pain). Each data
sample in this dataset is composed of one subject performing multiple
repetitions of one of the five exercises: (1) lifting of the arms, (2) lateral
tilt of the trunk with the arms in extension, (3) trunk rotation, (4) pelvis
rotations on the transverse plane, and (5) squatting. The data samples were
annotated in terms of exercise quality and technique.

The focus of this paper is on repetition segmentation and counting. KIMORE,
however, does not contain such annotations. Two co-authors of this paper
annotated the start and end of repetitions in each data sample using RGB video
playback and the Aegisub software [35]. The annotations were verified by
another two co-authors. The annotations were used as ground-truth labels for
training and evaluation of neural network models. The annotations are
available at https://github.com/abedicodes/repetition-segmentation. The mean
(standard deviation) of the number of repetitions across the total 353 samples
in the dataset is 4.70 (2.21).

In this paper, two modalities of data from the KIMORE dataset were used. See
Section III. In the first setting, RGB videos were used as input data. The
body joints were extracted by OpenPose [23] and then inputted into the
sequential models for analysis. In the second setting, the body joints
captured by Kinect were directly considered as input to the sequential models.

####  IV-A2 UI-PRMD

UI-PRMD [7] is a dataset of physical therapy rehabilitation collected from 10
healthy individuals who performed 10 physical therapy rehabilitation exercises
correctly and incorrectly to represent the performance of patients. Each data
sample in this dataset is composed of one subject performing multiple
repetitions of one of the 10 exercises, (1) deep squat, (2) hurdle step, (3)
inline lunge, (4) side lunge, (5) sit to stand, (6) standing active straight
leg raise, (7) standing shoulder abduction, (8) standing shoulder extension,
(9) standing shoulder internal-external rotation, and (10) standing shoulder
scaption. The annotations for repetition segmentation were available in UI-
PRMD and were used in our experiments. The mean (standard deviation) of the
number of repetitions across the total 200 samples in the dataset is 10.00
(0.00). This dataset contains body joints captured by Vicon and Kinect
cameras. The Kinect data was used in our experiments.

####  IV-A3 IntelliRehabDS

IntelliRehabDS [8] is a dataset of body joints captured by the Kinect camera
collected from 29 subjects, 15 patients and 14 healthy subjects. Each data
sample in this dataset is composed of one subject performing multiple
repetitions of one of the 9 physical rehabilitation exercises, (1) elbow
flexion left, (2) elbow flexion right, (3) shoulder flexion left, (4) shoulder
flexion right, (5) shoulder abduction left, (6) shoulder abduction right, (7)
shoulder forward elevation, (8) side tap left, and (9) side tap right. The
annotations for repetition segmentation were available in IntelliRehabDS and
were used in our experiments. The mean (standard deviation) of the number of
repetitions across the total 361 samples in the dataset is 5.69 (2.48).

###  IV-B Evaluation Metrics

In accordance with the literature, Off-By-One count Accuracy (OBOA) and MAE
were used as evaluation metrics for repetition counting [16, 17, 19].
Intersection-Over-Union (IOU) [31] was used for repetition segmentation. A new
metric for evaluating repetition segmentation was developed in this study,
Mean Average Error in Frames (MAE-F). First, for every data sample, the
average number of frames by which the start and end points of the predicted
repetition deviate from those of the ground truth repetition is calculated.
Then, these deviations are averaged over all data samples.

###  IV-C Experimental Settings

The dimension of the input to the sequential neural networks is determined
based on the dimension of the feature vectors extracted from frames of the
data samples. This dimension is 75, 43, and 118, when using the Kinect body
joints, exercise-specific features [29], and their concatenation,
respectively. This dimension is the number of neurons in the input layer of
the LSTM. The number of neurons in the hidden layers of LSTM is set to two
times the dimension of the feature vectors. In different exercises of
different datasets, the number of LSTM layers varies from one to three layers.

For comparison, we implemented a modified version of the TransRAC model [16],
described in Section II-C. In place of using the encoder in TransRAC for
feature extraction from multi-scale videos, multi-scale body joints were
replaced. The other parts of the network remained unchanged and the network
was trained from scratch to predict the density map. As a video-based method,
the pre-trained TransRAC on RepCount TransRAC was also used to predict the
density map for the RGB videos of exercises in the KIMORE dataset [6].

Due to the fact that none of the datasets determined separate training and
test sets, five-fold cross-validation was used. The loss function was a linear
combination of the Kullback-Leibler divergence loss and L1 loss minimized by
the Adam optimizer [32]. The experiments were implemented in PyTorch [32] and
scikit-learn [33] on a server with 128 GB of RAM and NVIDIA 2080 Ti 12 GB GPU.
The code of our implementation is available at
https://github.com/abedicodes/repetition-segmentation.

TABLE I: (a) Mean absolute error and (b) off-by-one accuracy of repetition
counting, and (c) intersection over union and (d) mean average error in frames
of repetition segmentation on the KIMORE dataset [6] through five-fold cross-
validation. Density Map: many-to-many model with density map output, General:
One single model was trained and evaluated on all the samples in the dataset,
Pre-trained TransRAC: Pre-trained TransRAC model on RepCount video dataset
[16], Modified TransRAC: A modified version of the TransRAC model [16] by
removing the autoencoder feature extractor in TransRAC and replacing the body
joints as the features, Exercise Specific: Exercise-specific models were
trained and evaluated on the samples of specific exercises in the dataset,
Density Map (LSTM Only): many-to-many model without CNN with density map
output, Binary sequence: many-to-many model with binary sequence output,
Counts: many-to-one model with repetition counts output.

###  IV-D Experimental Results

####  IV-D1 KIMORE

Tables I (a)-(b), and (c)-(d), respectively present the results of repetition
counting, and segmentation on the KIMORE dataset [6] through five-fold cross-
validation. The body joints captured by the Kinect camera in the dataset (rows
#4-11 in tables), the raw RGB videos in the dataset (#2), and the body joints
extracted from the RGB videos by OpenPose (#1 and #3) [23] were analyzed in
the experiments in Table I. It should be noted that repetition counting was
carried out in rows #1 and #3-10 of Tables I (a)-(b) as a result of repetition
segmentation. First, repetition segmentation was undertaken, and the number of
repetitions was counted. The repetition counting was performed directly in
rows #2 and #11 of Tables I (a)-(b).

The results of the many-to-many model with density map output (#8) are
superior to those of the many-to-many model with binary sequence output (#10).
The ground-truth density maps were generated by approximating a Gaussian
distribution between the start and end of each repetition [16]. The model that
was trained on and predicted based on density maps was more robust to noise
and fluctuations in body joints, as well as irregularities and imperfections
in completing exercises in the patients in the KIMORE dataset.

There is a significant difference between the results of the two models
described above (#8 and #10) and those of the many-to-one model with
repetition counts output (#11). One reason for this is that more ground-truth
information was available for the training of the first two models. The first
two models described above were provided with labels for every timestamp;
however, the many-to-one model was provided with only one label for the entire
network.

The results based on body joints captured by the Kinect camera (#8) were far
better than those extracted from RGB videos (#1). Due to the low quality of
videos in the KIMORE dataset, the high distance of the subjects to the camera,
imperfect lighting conditions, and blurred faces in the dataset to preserve
privacy, OpenPose [23] had difficulty extracting body joints from the dataset,
resulting in low-quality body joints compared to Kinect body joints.
Therefore, the OpenPose [23] input to the models was noisy, resulting in
suboptimal performance.

Comparing the results of the many-to-many model with density map output (#8)
as described in Section III-A2 (an LSTM trailed by a 1D CNN and a linear
layer) with the results of the many-to-many model with density map with only
an LSTM trailed by a linear layer and without 1D CNN (#9) shows the importance
of including 1D CNN in the proposed model.

Across all settings, the proposed method outperformed the modified TransRAC
method (#3-4), Section IV-C. The reason for this can be attributed to two
factors: the extreme complexity of the modified TransRAC model in comparison
to the simple yet effective sequential models used in this paper, as well as
the limited number of training samples in the KIMORE dataset. It is common for
healthcare and rehabilitation datasets to have a small number of training
samples. In this regard, it illustrates the necessity of taking the amount of
data into account when selecting and designing the architecture of deep neural
networks.

The RGB videos of exercises included in the KIMORE dataset were input into the
original TransRAC model which was pre-trained on the RepCount video dataset
[16] (#2). The results are much inferior to those predicted by the proposed
architectures. The RepCount dataset contains videos of healthy subjects
performing repetitive actions perfectly, while the KIMORE dataset contains
rehabilitation exercises conducted by patients with imperfect repetitive
actions.

Comparing the results of different features provided to the many-to-many model
with density map output, body joints (#8), features extracted from body joints
(#6), and their concatenation (#7) indicates that for the repetition counting
and segmentation tasks, there is no need to extract handcrafted features from
body joints [29] and the body joints as the input to the models result in the
best performance.

According to the results of the general model trained and evaluated on all the
samples in the dataset (#8), as compared to the exercise-specific models
trained and evaluated on specific exercises (#5), exercise-specific models are
not needed for repetition counting and segmentation tasks, and general models
perform marginally better than exercise-specific models.

Comparing the performance of the models for specific exercises reveals that
almost all methods had difficulty segmenting and counting repetitions for Ex.
4 in the KIMORE dataset. This is due to the fact that Ex. 4 involved pelvis
rotations, i.e., movements along the z axis, which is relatively difficult to
capture by depth cameras and analyze by models. As the movements in Ex. 4
differed from those in other exercises, which involved movements of the hands
and feet along the x and y axes, it was difficult to generalize models to the
samples in Ex. 4.

There is a similar overall trend in the performance of different methods in
different settings across all four evaluation metrics, MAE, OBO, IOU, and
MAE-F. Overall, the general many-to-many model with density map output trained
with Kinect body joints achieved superior results with the lowest total MAE
(0.5313) and the highest total OBO (0.9233) for repetition counting, as well
as the highest total IOU (0.6886) and the lowest total MAE-F (28) for
repetition segmentation.

TABLE II: Mean Absolute Error (MAE) and Off-By-One count accuracy (OBO) of
repetition counting and Intersection-Over-Union (IOU) and Mean Average Error
in Frames (MAE-F) of repetition segmentation on (a) the UI-PRMD [7] and (b)
the IntelliRehabDS [8] dataset through five-fold cross-validation. Density Map
– General: many-to-many model with density map output trained and evaluated on
all the samples in the dataset, Counts – General: many-to-one model with
repetition counts output trained and evaluated on all the samples in the
dataset.

####  IV-D2 UI-PRMD

Table II (a) shows the results of repetition segmentation and counting on the
UI-PRMD dataset [7] using the general many-to-many model with density map
output and the general many-to-one model with repetition counts output both
trained and evaluated on Kinect body joints through five-fold cross-
validation. Table II (a) illustrates that the repetition counting results of
the many-to-many model with density map output are very similar to those of
the many-to-one model with repetition counts output having zero errors in
counting and outperforming the previous repetition counting method [19]. It is
important to note that the number of repetitions across samples in the UI-PRMD
dataset has a very low standard deviation. Using the proposed method,
repetition segmentation is successfully performed with a total IOU of 0.82 and
a total MAE-F of 12.

####  IV-D3 IntelliRehabDS

Table II (b) shows the results of repetition segmentation and counting on the
IntelliRehabDS dataset [8] using the general many-to-many model with density
map output and the general many-to-one model with repetition counts output
both trained and evaluated on Kinect body joints through five-fold cross-
validation. In Table II (b), the results of the many-to-many model with
density map output are superior to those of the many-to-one model with
repetition counts output. Using the proposed method, repetition segmentation
is successfully performed with a total IOU of 0.68 and a total MAE-F of 39.

Figure 1: The ground truth values and predictions for repetition counts of the
proposed many-to-many model with density map output on (a) healthy subjects
and (b) patients in all the exercises in the KIMORE dataset [6].

Figure 1 illustrates the ground truth values and predictions for repetition
counts of the proposed many-to-many model with density map output on (a)
healthy subjects and (b) patients in all the exercises in the KIMORE dataset
using five-fold cross-validation. The predictions closely follow ground-truth
values in both populations, however, there are some deviations in patients as
a result of irregularities in the duration and completion of exercise
repetitions in patients. Figure 1 (b) shows large deviations in predictions
for samples with a large number of repetitions, such as samples with 12 and 13
repetitions. This can be attributed to the imbalanced distribution of samples
in the dataset, i.e., having a small number of samples with large numbers of
repetitions.

##  V Conclusion and Future Works

The purpose of this study was to develop a learning-based method for
segmenting and counting repetitions in rehabilitation exercises. On three
publicly available rehabilitation exercise datasets, the proposed method
successfully segmented and counted repetitions, and outperformed previous
works, including a video-based method. This study represented the first work
on repetition segmentation using skeletal body joints and data collected from
patients, which is more challenging due to irregularities in exercise duration
and completion. Despite being much lighter than video-based models [16, 17,
24, 25, 26, 27, 28, 18], our sequential models require an initial stage of
body-joint extraction from videos or directly by the use of depth cameras. Our
body-joint-based method has the advantage of being more interpretable and
capable of being used in a framework providing patients with actionable
feedback on their exercises. The successful segmentation and counting of
rehabilitation exercises using the proposed method is the first step in the
development of an automated virtual rehabilitation platform capable of
assessing exercise quality and providing feedback to patients and reports to
clinicians. Future research may involve incorporating the attention mechanism
[30, 36] into the current sequential models and extending the models to
facilitate multi-task learning to perform exercise segmentation and assessment
jointly.

## References

  * [1] Dibben, Grace O., et al. ”Exercise-based cardiac rehabilitation for coronary heart disease: a meta-analysis.” European Heart Journal 44.6 (2023): 452-469.
  * [2] Ferreira, Ricardo, Rubim Santos, and Andreia Sousa. ”Usage of Auxiliary Systems and Artificial Intelligence in Home-Based Rehabilitation: A Review.” Exploring the Convergence of Computer and Medical Science Through Cloud Healthcare (2023): 163-196.
  * [3] Sangani, Samir, et al. ”Real-time avatar-based feedback to enhance the symmetry of spatiotemporal parameters after stroke: instantaneous effects of different avatar views.” IEEE Transactions on Neural Systems and Rehabilitation Engineering 28.4 (2020): 878-887.
  * [4] Fernandez-Cervantes, Victor, et al. ”VirtualGym: A kinect-based system for seniors exercising at home.” Entertainment Computing 27 (2018): 60-72.
  * [5] Liao, Yalin, et al. ”A review of computational approaches for evaluation of rehabilitation exercises.” Computers in biology and medicine 119 (2020): 103687.
  * [6] Capecci, Marianna, et al. ”The KIMORE dataset: KInematic assessment of MOvement and clinical scores for remote monitoring of physical REhabilitation.” IEEE Transactions on Neural Systems and Rehabilitation Engineering 27.7 (2019): 1436-1448.
  * [7] Vakanski, Aleksandar, et al. ”A data set of human body movements for physical rehabilitation exercises.” Data 3.1 (2018): 2.
  * [8] Miron, Alina, et al. ”IntelliRehabDS (IRDS)—A dataset of physical rehabilitation movements.” Data 6.5 (2021): 46.
  * [9] Bevilacqua, Antonio, et al. ”Rehabilitation exercise segmentation for autonomous biofeedback systems with ConvFSM.” 2019 41st Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). IEEE, 2019.
  * [10] Brennan, Louise, et al. ”Segmentation of shoulder rehabilitation exercises for single and multiple inertial sensor systems.” Journal of Rehabilitation and Assistive Technologies Engineering 7 (2020): 2055668320915377.
  * [11] Lin, Jonathan Feng-Shun, Vladimir Joukov, and Dana Kulić. ”Classification-based segmentation for rehabilitation exercise monitoring.” Journal of rehabilitation and assistive technologies engineering 5 (2018): 2055668318761523.
  * [12] Lin, Jonathan Feng-Shun, Vladimir Joukov, and Dana Kulic. ”Human motion segmentation by data point classification.” 2014 36th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE, 2014.
  * [13] Lin, Jonathan Feng-Shun, and Dana Kulić. ”Online segmentation of human motion for automated rehabilitation exercise analysis.” IEEE Transactions on Neural Systems and Rehabilitation Engineering 22.1 (2013): 168-180.
  * [14] Bevilacqua, Antonio, et al. ”Combining real-time segmentation and classification of rehabilitation exercises with lstm networks and pointwise boosting.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 08. 2020.
  * [15] Soro, Andrea, et al. ”Recognition and repetition counting for complex physical exercises with deep learning.” Sensors 19.3 (2019): 714.
  * [16] Hu, Huazhang, et al. ”TransRAC: Encoding Multi-scale Temporal Correlation with Transformers for Repetitive Action Counting.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
  * [17] Chung, Kevin, Alec Kerrigan, and Ishan Dave. ”Long Action Repetition Counting with Staged Layer Distillation.”
  * [18] Zhang, Yunhua, Ling Shao, and Cees GM Snoek. ”Repetitive activity counting by sight and sound.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.
  * [19] Hsu, Yu Cheng, et al. ”Viewpoint-Invariant Exercise Repetition Counting.” arXiv preprint arXiv:2107.13760 (2021).
  * [20] Lin, Jonathan Feng-Shun, Michelle Karg, and Dana Kulić. ”Movement primitive segmentation for human motion modeling: A framework for analysis.” IEEE Transactions on Human-Machine Systems 46.3 (2016): 325-339.
  * [21] Sarsfield, Joe, et al. ”Segmentation of exercise repetitions enabling real-time patient analysis and feedback using a single exemplar.” IEEE Transactions on Neural Systems and Rehabilitation Engineering 27.5 (2019): 1004-1019.
  * [22] Lugaresi, Camillo, et al. ”Mediapipe: A framework for building perception pipelines.” arXiv preprint arXiv:1906.08172 (2019).
  * [23] Pavllo, Dario, et al. ”3d human pose estimation in video with temporal convolutions and semi-supervised training.” Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.
  * [24] Dwibedi, Debidatta, et al. ”Counting out time: Class agnostic video repetition counting in the wild.” Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2020.
  * [25] Ferreira, Bruno, et al. ”Deep learning approaches for workout repetition counting and validation.” Pattern Recognition Letters 151 (2021): 259-266.
  * [26] Cheng, Sheng-Hsien, et al. ”Periodic Physical Activity Information Segmentation, Counting and Recognition from Video.” IEEE Access (2023).
  * [27] Jacquelin, Nicolas, Romain Vuillemot, and Stefan Duffner. ”Periodicity counting in videos with unsupervised learning of cyclic embeddings.” Pattern Recognition Letters 161 (2022): 59-66.
  * [28] Yu, Qingtian, et al. ”Deep Learning-Enabled Multitask System for Exercise Recognition and Counting.” Multimodal Technologies and Interaction 5.9 (2021): 55.
  * [29] Guo, Qingyang, and Shehroz S. Khan. ”Exercise-Specific Feature Extraction Approach for Assessing Physical Rehabilitation.” 4th IJCAI Workshop on AI for Aging, Rehabilitation and Intelligent Assisted Living. IJCAI. 2021.
  * [30] S. S. Khan and A. Abedi, ”Step Counting with Attention-based LSTM,” 2022 IEEE Symposium Series on Computational Intelligence (SSCI), Singapore, Singapore, 2022, pp. 559-566, doi: 10.1109/SSCI51031.2022.10022210.
  * [31] Jiang, Zhengkai, et al. ”STC: spatio-temporal contrastive learning for video instance segmentation.” Computer Vision–ECCV 2022 Workshops: Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2023.
  * [32] Paszke, Adam, et al. ”Pytorch: An imperative style, high-performance deep learning library.” Advances in neural information processing systems 32 (2019).
  * [33] Pedregosa, Fabian, et al. ”Scikit-learn: Machine learning in Python.” the Journal of machine Learning research 12 (2011): 2825-2830.
  * [34] Strömbäck, David, Sangxia Huang, and Valentin Radu. ”Mm-fit: Multimodal deep learning for automatic exercise logging across sensing devices.” Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies 4.4 (2020): 1-22.
  * [35] https://github.com/Aegisub/Aegisub
  * [36] Nikpour, Bahareh, and Narges Armanfard. ”Spatio-Temporal Hard Attention Learning for Skeleton-based Activity Recognition.” Pattern Recognition (2023): 109428.