text:
\section{Introduction}

Let $\mathbb{N}$ denote the set of nonnegative integers and $\mathbb{Z}$ be the set of integers. For $A,B\subseteq \mathbb{Z}$ and $k \in \mathbb{Z}$, let $A+B=\{a+b:~a\in A,~b\in B\}$ and $kA = \{ka: a \in A\}$.
If $A+B=\mathbb{Z}$, then $A$ is called an additive complement to
$B$ in $\mathbb{Z}$. If no proper subset of $A$ is a complement to
$B$, then $A$ is called a minimal complement to $B$ in
$\mathbb{Z}$.

It is easy to see that if $A\subseteq \mathbb{Z}$ is a (minimal) complement to $B \subseteq \mathbb{Z}$, then $A$ is also a (minimal) complement to $B+d$, $d\in \mathbb{Z}$, where $B+d=\{ b+d:b\in B\} $.

In 2011, Nathanson \cite{nath} proved the following theorem.

\noindent{\bf  Nathanson's theorem} {\rm (See \cite[Theorem
8]{nath}).} {\em  Let $W$ be a nonempty, finite set of integers.
In $\mathbb{Z}$, every complement to $W$ contains a minimal
complement to $W$.}

In the same paper, Nathanson also posed the following problem.

\noindent{\bf  Problem} {\rm (See \cite[Problem 11]{nath}).} Let
$W$ be an infinite set of integers. Does there exist a minimal
complement to $W$? Does there exist a complement to $W$ that does not
contain a minimal complement?

For the second part of the above problem, in 2012, Chen and Yang \cite{chenyang} gave two infinite sets $W_1$ and $W_2$ of integers such that there exists a complement to $W_1$ that does not contain a minimal complement and every complement to $W_2$ contains a minimal complement.

For the first part of the above problem, in 2012, Chen and Yang \cite{chenyang} proved the following results.

\noindent{\bf  Theorem A} (See \cite[Theorem 1]{chenyang}).~{\em
Let $W$ be a set of integers with $\inf W=-\infty$ and $\sup
W=+\infty$. Then there exists a minimal complement to $W$.}

By Theorem A, now we only need to consider the cases $\inf W>-\infty$
or $\sup W<+\infty$. Without loss of generality, we may assume
that $\inf W>-\infty$.

\noindent{\bf  Theorem B} (See \cite[Theorem 2]{chenyang}).~{\em
Let $W=\{1=w_1<w_2<\cdots\}$ be a set of integers and
$$\overline{W}=(\mathbb{Z} \cap (0, +\infty)) \setminus W=\{\overline{w_1}
<\overline{w_2}<\cdots\}.$$

(a) If $\limsup_{i\rightarrow +\infty}(w_{i+1}-w_i)=+\infty$, then
there exists a minimal complement to $W$.

(b) If $\lim_{i\rightarrow
+\infty}(\overline{w_{i+1}}-\overline{w_i})=+\infty$, then there
does not exist a minimal complement to $W$.}

Let $W=\cup_{k=0}^{\infty} [10^k,2\times 10^k]$. Then it is clear
that both $\limsup_{i\rightarrow +\infty}(w_{i+1}-w_i)=+\infty$
and $\limsup_{i\rightarrow
+\infty}(\overline{w_{i+1}}-\overline{w_i})=+\infty$ hold. Hence
$\lim_{i\rightarrow
+\infty}(\overline{w_{i+1}}-\overline{w_i})=+\infty$ in Theorem B
(b) cannot be changed to $\limsup_{i\rightarrow
+\infty}(\overline{w_{i+1}}-\overline{w_i})=+\infty$.

In this paper, we will give further results on Nathanson's problem
and deal with some sets $W$ do not satisfy the conditions of
Theorem B.

First we give some definitions. Let $S\subseteq \mathbb{N}$. Denote by $S\mod m$ the set of residues of $S$ modulo $m$, i.e.,
$$S\mod m =\{ r: r\in \{0,1,\dots ,m-1\}, r\equiv s~(\text{mod}~m)\text{ for some }s\in S\}.$$
Let $X\subseteq \mathbb{N}$. If
there exists a positive integer $T$ such that $x+T\in X$ for all
$x\in X$, then we call $X$ {\em{periodic with period $T$}}. If
$X\cup C$ is a periodic set for some finite set $C\subseteq
\mathbb{N}$, then we call $X$ {\em{quasiperiodic}}. If there exists
a positive integer $T$ such that $x+T\in X$ for all sufficiently
large integers $x\in X$, then we call $X$ {\em {eventually
periodic with period $T$}}. Clearly, a periodic set must be
quasiperiodic and a quasiperiodic set must be eventually periodic.
If $W$ is eventually periodic with $|\mathbb{N}\setminus W| = +\infty$, then both $\lim_{i\rightarrow
+\infty}(w_{i+1}-w_i)<+\infty$ and $\lim_{i\rightarrow
+\infty}(\overline{w_{i+1}}-\overline{w_i})<+\infty$ hold. Hence
$W$ does not satisfy the conditions of Theorem B.

Suppose that $W$
is an eventually periodic set and $m$ is a positive
period. By shifting a number, we may assume that $W$ has the
following structure:
\begin{eqnarray}\label{def1}W=(m\mathbb{N}+X_m)\cup
Y^{(0)}\cup Y^{(1)},\end{eqnarray}
where $X_m\subseteq \{0, 1, \dots{}, m-1\}, Y^{(0)}\subseteq \mathbb{Z}^{-},Y^{(1)}$ are finite sets with
$Y^{(0)}~\text{mod}~ m\subseteq
X_m$ and
$(Y^{(1)}~\text{mod}~m) \cap X_m = \emptyset$.

For example, if $W=\{2,4,7,8,9,12,13,17,18,22,23,27,28,\ldots\}$, then by shifting a number $5$, we may assume that
$$W=\{-3,-1,2,3,4,7,8,12,13,17,18,22,23,\ldots\}.$$ Hence $m=5$, $X_m=\{2,3\}$, $Y^{(0)}=\{-3\}$, $Y^{(1)}=\{-1,4\}$.

In this paper, we study that what conditions are needed to ensure the existence of a minimal complement to $W$. First we prove a sufficient condition.

\begin{theorem}\label{thm3} Let $W$ be defined in \eqref{def1}. If there exists a minimal complement
to $W$, then there exists $C\subseteq \{0,1,\dots ,m-1\}$ such that the
following two conditions hold:

(a) $C+(X_m\cup Y^{(1)}) \mod m=\{0,1,\dots ,m-1\}$;

(b) For any $c\in C$, there exists $y\in Y^{(1)}$ such that
$c+y\not \equiv c'+x~(\text{mod}~m)$ for any $c'\in C$ and $x\in X_m$.
\end{theorem}

\begin{remark}\label{remark2} By the proof of Theorem \ref{thm3},
we know that Theorem \ref{thm3} also holds when $Y^{(1)}$ is an
infinite set with $|Y^{(1)}\cap \mathbb{Z}^{-}|<+\infty$.
\end{remark}

Let $m=3$, $X_m=\{0\}$, $Y^{(1)}\subseteq 3\mathbb{N}+1$. By
Theorem \ref{thm3}, we have the following corollary.

\begin{corollary}\label{coro1} Let $Y\subseteq 3\mathbb{N}+1$ and
$W=3\mathbb{N}\cup Y$. Then there does not exist a minimal
complement to $W$.
\end{corollary}

\begin{remark}\label{remark2} We can choose an infinite set
$Y$ in Corollary \ref{coro1} such that $W$ is not eventually
periodic. Hence, there exists an infinite, not eventually periodic
set $W\subseteq \mathbb{N}$ such that $w_{i+1}-w_i\in \{1,2,3\}$
for all $i$, and there does not exist a minimal complement to $W$.
\end{remark}

\begin{remark}\label{remark1} If $W\subseteq \mathbb{N}$ is a
quasiperiodic set, then $Y^{(1)}=\emptyset$ and the condition (b)
in Theorem \ref{thm3} does not hold. Hence there does not exist a
minimal complement to $W$.
\end{remark}

In the next step we prove a necessary condition.

\begin{theorem}\label{thm4} Let $W$ be defined in \eqref{def1}. Suppose that there exists $C\subseteq
\{0,1,\dots ,m-1\}$ such that the following two conditions hold:

(a) $C+(X_m\cup Y^{(1)})\mod m=\{0,1,\dots ,m-1\}$;

(b) For any $c\in C$, there exists $y\in Y^{(1)}$ such that $c+y\not \equiv c'+x~(\text{mod}~m)$ for
any $c'\in C \setminus \{c\}$ and $x\in X_m \cup Y^{(1)}$.

Then there exists a minimal complement to $W$.
\end{theorem}

By Theorems \ref{thm3} and \ref{thm4}, we have the following
corollary.

\begin{corollary} Let $W=(m\mathbb{N}+X_m)\cup Y^{(0)}\cup \{a\},$
where $X_m\subseteq \{0,1,\dots ,m-1\},~(Y^{(0)}\mod m)\subseteq X_m$ and $a\not \equiv x~(\text{mod}~m)$ if $x\in X_m$. Then there exists a minimal complement to $W$
if and only if there exists a subset $C\subseteq \{0,1,\dots ,m-1\}$ such that:

(a) $C+(X_m\cup\{ a\})\mod m =\{0,1,\dots ,m-1\}$;

(b) For any $c\in C$, $c+a\not \equiv c'+x~(\text{mod}~m)$, where $c'\in C \setminus \{c\}$ and $x\in X_m$.
\end{corollary}

We see that Theorems \ref{thm3} and \ref{thm4} transfer
Nathanson's problem into a finite modulo version when $W$ is an eventually periodic set.
In the next theorem, we give a sufficient and necessary condition, but we
cannot bound the module.

\begin{theorem}\label{thm5} Let W be defined in (1). There exists a minimal complement to $W$
if and only if there exists $T\in \mathbb{Z}^{+},m\mid T$,
and $C\subseteq \{0,1,\dots ,T-1\}$ such that

(a) $C+(X_T\cup Y^{(1)})\mod T=\{0,1,\dots ,T-1\}$, where $X_{T} = \cup_{i=0}^{\frac{T}{m}-1}\{im+X_{m}\}$;

(b) for any $c\in C$, there exists $y\in Y^{(1)}$ such that
$c+y\not \equiv c'+x~(\text{mod}~T)$ for any $c'\in C \setminus \{c\}$ and $x\in X_T\cup Y^{(1)}$.
\end{theorem}

Finally, as a complement to Remark \ref{remark2}, we give the
following theorem.

\begin{theorem}\label{thm2} There exists an infinite, not
eventually periodic set $W\subseteq \mathbb{N}$ such that
$w_{i+1}-w_i\in \{1,2\}$ for all $i$ and there exists a minimal
complement to $W$.
\end{theorem}

Now we pose two problems for further research.

\begin{problem} We know that Theorem \ref{thm3} also holds when
$Y^{(1)}$ is infinite. Is Theorem \ref{thm4} also true when
$Y^{(1)}$ is infinite?
\end{problem}

\begin{problem} Does there exist an explicit formula for the upper bound of $T$ in Theorem 3
using $m,Y^{(0)}$ and $Y^{(1)}$?
\end{problem}

\section{Proofs}

\begin{proof}[Proof of Theorem \ref{thm3}] Suppose that $D$ is a
minimal complement to $W$. For $i\in \{0,1,\ldots,m-1\}$, let
$D_i=\{d\in D:~d\equiv i~(\text{mod}~m)\}$ and
$$C=\{j:~0\le j\le m-1~\text{and}~|D_j\cap
\mathbb{Z}^{-}|=+\infty\}.$$ For any $t\in
\{0,1,\ldots,m-1\}\setminus C$, the set $\{d\in D:~d\equiv
t~(\text{mod}~m)\}+W$ does not contain any sufficiently small
negative integers. It follows from $D+W=\mathbb{Z}$ that
$C+W~\text{mod}~m =\{0,1,\dots ,m-1\}$. That is, $C+(X_m\cup Y^{(1)})~\text{mod}~m=\{0,1,\dots ,m-1\}$.

Next we shall prove (b). Suppose that there exists $c\in C$ such
that for any $y\in Y^{(1)}$ there exist $c'\in C$ and $x\in X_m$ with  $c+y\equiv c'+x~(\text{mod}~m)$. We take an integer $d\in D$ such that $d\equiv
c~(\text{mod}~m)$ and we shall prove that $D\setminus \{d\}$ is
also a complement to $W$. For any integer $n$, write $n=d'+w$,
where $d'\in D$ and $w\in W$.

Case 1. $d'\not=d$. Then $n=d'+w\in (D\setminus \{d\})+W$.

Case 2. $d'=d$.

Subcase 2.1. $(\{w\}~\text{mod}~m) \subseteq X_m$. In this case, there exists
a positive integer $k_0$ such that $w+km\in W$ for all integers
$k\ge k_0$. Since $|D_c\cap \mathbb{Z}^{-}|=+\infty$, it follows
that there exists an integer $k\ge k_0$ such that $d-km\in D$.
Hence $n=(d-km)+(w+km)$, where $d-km\in D\setminus \{d\}$ and
$w+km\in W$. That is, $n\in (D\setminus \{d\})+W$.

Subcase 2.2. $w\in Y^{(1)}$. Since $\{c+y\}~\text{mod}~m\subseteq C+X_m ~\text{mod}~m$
for any $y\in Y^{(1)}$ and $d\equiv c~(\text{mod}~m),~w\in
Y^{(1)}$, it follows that ~$\{n\}~\text{mod}~m=\{d+w\}~\text{mod}~m\subseteq C+X_m ~\text{mod}~m$. Hence
there exist a $c'\in D$ with $c'~(\text{mod}~m)\in C$ and $x\in W$
with $x~\text{mod}~m\in X_m$ such that $n\equiv
~c'+x~(\text{mod}~m)$. We choose a sufficiently large integer $k$
such that $c'-km\in D$,~$c'-km\not=d$ and $x+km\in W$. Hence
$n=(c'-km)+(x+km)$, where $c'-km\in D \setminus \{d\}$ and $x+km\in W$.

Hence, $(D\setminus \{d\})+W=\mathbb{Z}$ which contradicts the fact that $D$
is a minimal complement. Therefore, (b) holds.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm4}] Let
$C_1=C+X_m~\text{mod}~m$,~$C_2=\{0,1,\dots ,m-1\}\setminus C_1$,
$$C'=\{d\in\mathbb{Z}:~d\equiv c~(\text{mod}~m)~\text{for some}~c\in C\},$$
$$C_1'=\{d\in\mathbb{Z}:~d\equiv c~(\text{mod}~m)~\text{for some}~c\in C_1\},$$
$$C_2'=\{d\in\mathbb{Z}:~d\equiv c~(\text{mod}~m)~\text{for some}~c\in C_2\}.$$
By (a), we have $C'+W=\mathbb{Z}$. Since $C+X_m~\text{mod}~m=C_1$, it follows
that $$C'+(W\setminus
Y^{(1)})~\text{mod}~m=C+X_m~\text{mod}~m=C_1,$$ and so
$\left(C'+(W\setminus Y^{(1)})\right)\cap C_2'=\emptyset$. It follows from (b) that $C_2' \ne \emptyset$. Noting
that $C'+W=\mathbb{Z}$, we have $C'+Y^{(1)}\supseteq C_2'$. Since
$Y^{(1)}$ is a finite set, by the proof of Nathanson's theorem
(See \cite[Theorem 4, page 2015]{nath}), there exists $D'\subseteq C'$ such
that $D'+Y^{(1)}\supseteq C_2'$ and for any $d\in D'$,
$$(D'\setminus \{d\})+Y^{(1)}\not\supseteq C_2'.$$

Next we shall prove that $D'$ is a minimal complement to $W$.

For $i\in C$, let $D_i'=\{d\in D':d\equiv i~(\text{mod}~m)\}$. First we prove that $|D_i'\cap \mathbb{Z}^{-}|=+\infty$ for all $i\in
C$. Suppose that there exists a $j\in C$ such that $|D_j'\cap
\mathbb{Z}^{-}|<+\infty$. By (b), there exists a $y\in Y^{(1)}$ such
that $j+y\not \equiv c+x~(\text{mod}~m)$, where $c\in C\setminus \{j\}$, $x\in X_m\cup Y^{(1)}$ and so
$$D'+Y^{(1)}\not\supseteq \{d\in \mathbb{Z}:d\equiv  j+y~(\text{mod}~m)\}.$$

Noting that $(\{j+y\}~\text{mod}~m) \not\subseteq C+X_m ~\text{mod}~m=C_1$, we have $(\{j+y\}~\text{mod}~m)\subseteq
C_2$. It follows that $D'+Y^{(1)}\not\supseteq
C_2'$, a contradiction. Hence, $|D_i'\cap \mathbb{Z}^{-}|=+\infty$
for all $i\in C$.

Next we prove that $D^{'}$ is a complement.
For any integer $n\in C_1'$, by $C+X_m ~\text{mod}~m=C_1$, there exists $c\in C$
and $x\in X_m$ such that $n\equiv c+x~(\text{mod}~m)$. Since
$|D_c'\cap \mathbb{Z}^{-}|=+\infty$, there exists a sufficiently
small negative integer $d\in D_c'$ such that $n-d>0$. The congruences $n\equiv c+x ~(\text{mod}~m)$ and $d\equiv c ~(\text{mod}~m)$ imply that $n-d\equiv x ~(\text{mod}~m)$. Hence, $n-d\in m\mathbb{N}+X_m$ and so
$$n=d+(n-d)\in D_c'+(m\mathbb{N}+X_m)\subseteq D'+W.$$
Hence $C_1'\subseteq D'+W.$ On the other hand, $D'+W\supseteq
D'+Y^{(1)}\supseteq C_2'$. Therefore, $D'+W=\mathbb{Z}$.

Finally, we prove that $D^{'}$ is a minimal complement.
For any $d\in D'$,
we have $$\Big((D'\setminus \{d\})+(W\setminus
Y^{(1)})~\text{mod}~m\Big) \subseteq C+X_m ~\text{mod}~m=C_1.$$ It follows that $$\Big((D'\setminus
\{d\})+(W\setminus Y^{(1)})\Big)\cap C_2'=\emptyset,$$ and so
$(D'\setminus \{d\})+W\not\supseteq C_2'$. Hence $(D'\setminus
\{d\})+W\not=\mathbb{Z}$.

Therefore, $D'$ is a minimal complement to $W$.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm5}] Assume that the set $W$ satisfies the conditions of Theorem 3.
Applying Theorem 2 with $m = T$, it follows that $W$ has a
minimal complement.

Suppose that $W$ has a minimal complement $E$. We
will prove that there exist a positive integer $T$ and a set $C
\subseteq \{0,1, \dots{}, T-1\}$ satisfying the conditions of Theorem 3.

For $0 \le i < m$, let
\[
E^{-}_{i} = \{e: e < 0,e\in E, e \equiv i~(\text{mod}~m)\}.
\]
Let $0 \le i_{1} < i_{2} < \dots{} < i_{t} < m$ be the sequence of
indices with $|E^{-}_{i_{j}}| = \infty$. It is clear that there
exists an integer $N_{0}$ such that, $e \in E$ and $e \le
N_{0}$ imply that $e \in E_{i_{j}}$ for some $i_{j}$. It follows from Theorem 1 that $Y^{(0)} \cup Y^{(1)} \ne \emptyset$. Let
\[
y_{+} = \text{max}\{y: y \in Y^{(0)} \cup Y^{(1)}\},
\]
\[
y_{-} = \text{min}\{y: y \in Y^{(0)} \cup Y^{(1)}\},
\]
and $y_{0} = \max\{y_{+},-y_{-},y_{+}-y_{-}\}$. Let $\chi_{E}(k)$ denote the
characteristic function of the set $E$, i.e.,
\[
\chi_{E}(k) = \left\{
\begin{aligned}
1 \textnormal{, if } k \in E; \\
0 \textnormal{, if } k \notin E.
\end{aligned} \hspace*{3mm}
\right.
\]
Let $A = N_{0} + \text{min}\{0, y_{-}\}$. We consider the
following vectors:
\begin{align*}
\textbf{v}_{A} & = \left( \chi_{E}(A-y_0),\chi_{E}(A-y_0+1), \dots{}, \chi_{E}(A+y_0)\right), \\
\textbf{v}_{A-m} & = \left( \chi_{E}(A-m-y_0),\chi_{E}(A-m-y_0+1), \dots{}, \chi_{E}(A-m+y_0)\right), \\
&\mathrel{\makebox[\widthof{=}]{\vdots}} \\
\textbf{v}_{A-im} & = \left( \chi_{E}(A-im-y_0),\chi_{E}(A-im-y_0+1), \dots{}, \chi_{E}(A-im+y_0)\right) ,\\
&\mathrel{\makebox[\widthof{=}]{\vdots}}
\end{align*}
It is clear that there are infinitely many vectors
$\textbf{v}_{A}, \textbf{v}_{A-m}, \dots{},  \textbf{v}_{A-im},
\dots{},$ each of them has $2y_{0}+1$ coordinates, which are $0$ or
$1$. Since there are at most $2^{2y_{0}+1}$ different vectors,
by the pigeon hole principle, there exist a vector $\textbf{v}$
and an infinite sequence $0\le k_{1} < k_{2} <
\cdots{}$ such that $\textbf{v}_{A-k_{i}m} =  \textbf{v}$ for all positive integer $i$.

Define $L = A-k_{1}m$ and choose a sufficiently large integer $k_{i}$ such that
$k_{i}m - k_{1}m \ge y_{0}$
and $[A-k_{i}m, A-k_{1}m[ \cap E_{i_{j}} \ne \emptyset$ for every index $i_{j}$. Let $K = A - k_{i}m$,
$T = L-K$ and
\[
C = \{l: K \le l < L, ~ l \in E\}~\text{mod}~T.
\]

Now we shall prove that such an integer $T$ and a set $C$ satisfy the conditions of Theorem 3.
By definitions, $K$ and $L$ have the following properties.
\begin{equation}
L \le N_{0} + \text{min}\{0, y_{-}\},
\end{equation}
\begin{equation}
L-K\ge y_{0},
\end{equation}
\begin{equation}
m \mid L - K,
\end{equation}
\begin{equation}
\chi_{E}(K+i) = \chi_{E}(L+i)~ for~
-y_{0} \le i \le +y_{0},
\end{equation}
\begin{equation}
[K, L[ \cap E_{i_{j}} \ne \emptyset~\text{for all}~i_j.
\end{equation}

First we prove that $C + (X_{T} \cup Y^{(1)})~\text{mod}~T =
\{0,1,\ldots, T-1\}$, where $X_{T} = \bigcup_{i=0}^{\frac{T}{m}-1}\{im+X_{m}\}$.
For any integer $l$ with $K \le l < L$, there exist $e \in E$ and $w \in W$ such that $l = e + w$.
As $w \ge \text{min}\{0, y_{-}\}$,
it follows from (2) that $e = l - w < L - \text{min}\{0, y_{-}\}
\le N_{0}$, and so $e \in E_{i_{j}}^{-}$ for some integer $i_j$.
Suppose that $w \in  Y^{(0)} \cup Y^{(1)}$. Then we have $y_{-}
\le w \le y_{+}$ and $K-y_{+}
\le e =l-w< L-y_{-}$. We have three cases.

Case 1. $K - y_{+} \le e < K$. Noting that
$$K-y_0\le K-y_+\le e<K<K+y_0,$$
by (5), we have $e+(L-K)\in E$. By $K - y_{+} \le e < K$ and (3), it follows that
$K\le L-y_+\le e+(L-K)<L$. Let $c=e+(L-K)$. Then $c~\text{mod}~T \in C$ and $l\equiv c+w~(\text{mod}~T)$.
Hence $l~\text{mod}~T\in C + (X_{T} \cup Y^{(1)})~\text{mod}~T$.

Case 2. $K \le e < L$. It follows that $e~\text{mod}~T\in C$ and so
$l~\text{mod}~T \in C + (X_{T} \cup Y^{(1)})~\text{mod}~T$.

Case 3. $L \le e < L - y_{-}$. Noting that
$$L-y_0\le L\le e<L-y_{-}\le L+y_0,$$
by (5), we have $e - (L - K) \in E$. Since $L \le e < L - y_{-}$ and (3), it follows that
$K \le e - (L - K) < K - y_{-}<L$. Let $c=e-(L-K)$. Then $c~\text{mod}~T \in C$ and
$l\equiv c+w~(\text{mod}~T)$. Hence $l~\text{mod}~T\in C + (X_{T} \cup Y^{(1)})~\text{mod}~T$.

Suppose that $w \in T\mathbb{N} + X_{T}$. Since $w \ge 0$ and $e = l - w < L \le N_{0}$, we have $e \in E_{i_{j}}^{-}$ for some integer
$i_j$, and so $e \equiv i_{j}~(\text{mod}~m)$. It follows from (6) that
there exists an integer $e^{'}$ such that $e^{'} \in E_{i_{j}}^{-}$, $K \le
e^{'} < L$ and $e^{'} \equiv i_{j}~(\text{mod}~m)$. Let $w
\equiv x~(\text{mod}~m)$, where $x\in X_m$. Obviously, $l
\equiv e + w \equiv i_{j} + x \equiv e^{'} + x~(\text{mod}~m)$. By
(4) there exists an integer $u$ with $0 \le u < \frac{T}{m}$
such that $l \equiv e^{'} + um + x~(\text{mod}~T)$. Thus $l~\text{mod}~T\in C + (X_{T} \cup Y^{(1)})~\text{mod}~T$.

Therefore, $C + (X_{T} \cup Y^{(1)})~\text{mod}~T=\{0,1,\ldots,T-1\}$.

In the next step we show that the second condition of Theorem 3
holds. For any integer $e\in E$ with $K \le e < L$, there
exists a $w \in W$ such that $e + w \ne e^{'} + w^{'}$ for any $e' \ne
e$, $e'\in E$ and $w'\in W$.

If $w \in (m\mathbb{N} + X_{m}) \cup Y^{(0)}$, by $e<L\le N_0$ and $e\in E$,
then there
exists a positive integer $s$ such that $e + w = (e - sm) + (w +
sm)$, where $e - sm \in E$ and $w + sm \in W$. This is a contradiction.

Now we may assume that $w \in Y^{(1)}$. It is enough to prove
that $e + w \not\equiv e^{'} + w^{'}~(\text{mod}~T)$ for any $e^{'}(\not=e)\in E$, $K \le
e^{'} < L$ and $w^{'} \in X_{T} \cup (Y^{(1)}~\text{mod}~T)$. Suppose that such $e'$ and $w'$
exist, i.e., $e+w\equiv e'+w'~(\text{mod}~T)$.

If $w^{'} \in X_{T}$, then $e + w = e^{'} + w^{'}
+ tT$ for some integer $t$. Hence there exists a positive integer $s$ such that
$e + w = (e^{'} - sm) + (w^{'} + sm + tT)$, where
$e^{'} - sm  \in E$ and $w^{'} + sm + tT \in W$. This is a contradiction.

Now we assume $w^{'} \in Y^{(1)}$. Then $K + y_{-} \le  e +
w, e^{'} + w^{'} < L + y_{+}$. By $T=L-K\ge y_0\ge y_+-y_-$, it follows that either $e + w = e^{'} +
w^{'}$ or $e + w = e^{'} + w^{'} +T$ or $e + w = e^{'} +
w^{'} - T$.

Case 1. $e + w = e^{'} + w^{'}$. Then we have $e =
e^{'}$ and $w = w^{'}$, a contradiction.

Case 2. $e + w = e^{'} +
w^{'} +T$. It follows that $K + y_{-} \le e^{'} + w^{'} < K +
y_{+}$, and so $$K-y_0\le K + y_{-} -  y_{+} \le e^{'} < K + y_{+} -
y_{-}\le K+y_0.$$
By (5), we have $e^{'} + T\in E$, and then $e + w$ has another representation $(e^{'} +T) + w^{'}$.
Therefore $w
= w^{'}$ and $e = e^{'} + T$, which contradicts with $K \le
e, e^{'} < L$.

Case 3. $e + w = e^{'} + w^{'} - T$. Then we have
$L + y_{-} \le e^{'} + w^{'} < L + y_{+}$. Thus $L-y_0\le L +
y_{-} -  y_{+} \le e^{'} < L + y_{+} - y_{-}\le L+y_0$. It follows from
(5) that $e^{'} - T \in E$ which implies that $e + w =
(e^{'} - T) + w^{'}$. Therefore $w = w^{'}$ and $e =
e^{'} -T$, which is a contradiction because $K \le e, e^{'}
< L$.

The proof of Theorem 3 is completed.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm2}]

By induction we can construct
$\{d_i\}_{i=1}^{\infty},~\{W_i\}_{i=1}^{\infty}$ and
~$\{c_i\}_{i=1}^{\infty}$ such that

(i) $d_1=-1,~W_1=\{1,2,\ldots,12\},~c_1=-3$;

(ii) $d_i$ is the largest negative integer $\not\in
W_{i-1}+\{c_1,c_2,\ldots,c_{i-1}\}$ for $i\ge 2$;

(iii) $c_i<d_i+2c_{i-1}$ for all $i\ge 2$;

(iv) for $i\ge 2$, let $W_i=W_{i-1}\cup
\left([-2c_{i-1},-2c_i-1]\setminus \cup_{j=1}^{i-1}
\{-c_i+d_{j}\}\right).$

Let $W=\cup_{i=1}^{\infty}W_i$ and $C=\{c_i\}_{i=1}^{\infty}$.

Now we prove that $C$ is a minimal complement to $W$.

First we prove $d_{i+1}-d_i\le -2$ for all integers $i\ge 1$.
Clearly $d_2=-3,~d_2-d_1=-2$. Suppose that $d_{i+1}-d_i\le -2$ for
all integers $i<k~(k\ge 2)$. Since
$$d_k=(d_k-c_k)+c_k,\quad d_k-1=(d_k-1-c_k)+c_k,$$
$$-2c_{k-1}\le d_k-1-c_k<d_k-c_k<-c_k+d_{k-1},$$
it follows that $d_k-c_k,~d_k-1-c_k\in W_k$ and then
~$d_k,d_k-1\in W_k+\{c_k\}$. Hence $d_{k+1}\le d_k-2$. By (iv), we
have $w_{j+1}-w_j\in \{1,2\}$. Since $d_k\rightarrow -\infty$, by (ii) we
have $(-\infty,9]\subseteq W+C$. For any integer $n\ge 10$, there
exists an $i$ such that $-c_{i-1}\le n<-c_i$. Hence
$$-c_i+d_1<-c_{i-1}-c_i\le n-c_i<-2c_i,$$
and so $n-c_i\in W_i$, that is, $n\in W_i+\{c_i\}$. Therefore,
$W+C=\mathbb{Z}$.

Next, we prove that the complement $C$ is minimal. For any
positive integer $i$, we write $d_i=c+w$ with $c\in C$ and $w\in
W$. Now we shall prove that $c=c_i$. By (iv), we have
$d_i-c_j\not\in W$ for all integers $j>i$. Hence $c\not=c_j$ for
all integers $j>i$. Since $-2c_{i-1}$ is the minimal value of
$W\setminus W_{i-1}$ and for any positive integers $j\le i-1$,
$d_i-c_j\le d_i-c_{i-1}<-2c_{i-1}$, it follows that
$d_i-c_j\not\in W\setminus W_{i-1}$ for all positive integer $j\le
i-1$. Noting that $d_i\not\in W_{i-1}+\{c_1,\ldots,c_{i-1}\}$, we
have $d_i\not\in W+\{c_1,c_2,\ldots,c_{i-1}\}$. Hence $c=c_i$.

Therefore, $C$ is a minimal complement to $W$. Furthermore, by
(iii), we can choose suitable $c_i$ such that $W$ is infinite and
not eventually periodic.
\end{proof}

\section{Acknowledgement} This work was done during the third author visiting to Budapest
University of Technology and Economics. He would like to thank Dr.
S\'andor Kiss and Dr. Csaba S\'{a}ndor for their warm hospitality. We would like
to thank the anonymous referee very much for the detailed comments.

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}
\label{sec:intro}
Commitment schemes are powerful cryptographic primitives. In a bit
commitment scheme $\mathsf {Alice}$, the committer is supposed to commit a bit $b
\in \{0,1\}$ to $\mathsf {Bob}$ in such a way that after the {\em commit phase}
she cannot change her choice of the committed bit. This is referred to
as the binding property. Also at this stage $\mathsf {Bob}$ should not be able to
figure out what the committed bit is. This is referred to as the
concealing property. Later in the {\em reveal phase} $\mathsf {Alice}$ is supposed
to reveal the bit $b$ and convince $\mathsf {Bob}$ that this was indeed the bit
which she committed earlier. Bit commitment schemes have been very
well studied in both the classical and quantum models since existence
of such schemes imply several interesting results in cryptography. It
has been shown that bit commitment schemes imply existence of {\em
quantum oblivious transfer}~\cite{yao:oblivious} which in turn
provides a way to do any two-party secure
computation~\cite{killian:oblivious}. They are also useful in
constructing {\em zero knowledge proofs}~\cite{goldreich:crypto} and
imply another very useful cryptographic primitive called secure {\em
coin tossing}~\cite{blum:coin}. But unfortunately strong negative
results are known about them in case $\mathsf {Alice}$ and $\mathsf {Bob}$ are assumed to
possess arbitrary computation power and information theoretic security
is required. In this paper we are concerned with this setting of
information theoretic security with unbounded computational resources with cheating
parties.  Classically bit commitment schemes are known to be
impossible. In the quantum setting several schemes were proposed but
later several impossibility results were
shown~\cite{mayer:imp,hklo:bitcomm1,hklo:bitcomm2,Dariano07}. Negative results
were also shown for approximate implementations of bit commitment
schemes~\cite{terry:bitcomm,Dariano07} in which trade-offs were shown for
cheating probabilities of $\mathsf {Alice}$ and $\mathsf {Bob}$, referred to as
binding-concealing trade-offs. Interestingly however
Kent~\cite{kent:relative} has exhibited that bit-commitment can be
achieved using relativistic constraints. However we point out that in
this work we do not keep considerations of relativity into picture and
our setting is non-relativistic.

Now suppose instead of wanting to commit a bit $b \in \{0,1\}$, $\mathsf {Alice}$
wants to commit an entire string $x \in \{0,1\}^n $. One way to do
this might be to commit all the bits of $x$
separately. Binding-concealing trade-offs of such schemes will be
limited by the binding-concealing trade-offs allowable for bit
commitment schemes. But it is conceivable that there might exist
cleverer schemes which allow for better binding and concealing
properties? This question was originally raised by
Kent~\cite{kent:bitcomm}. Let us first begin by formally defining a quantum string
commitment protocol.  Our definition is similar to the one considered
by Buhrman et al.~\cite{harry:QSC}
\begin{definition}[Quantum string commitment]
\label{def:QSC}
Let $P = \{p_x: x \in \{0,1\}^n \}$ be a probability distribution and
let $B$ be a {\em measure of information} (we define several measures
of information later). A $(n,a,b)-B-\mathsf{ QSC}$ protocol for $P$ is a {\em
quantum communication protocol~\cite{yao:oblivious,hklo:bitcomm2}}
between $\mathsf {Alice}$ and $\mathsf {Bob}$. $\mathsf {Alice}$ gets an input $x \in \{0,1\}^n$ (chosen
according to the distribution $P$), which is supposed to be the
string to be committed. The starting joint state of the
qubits of $\mathsf {Alice}$ and $\mathsf {Bob}$ is some pure state. There are
no intermediate measurements during the protocol and $\mathsf {Bob}$ has a final
checking $\mathsf{POVM}$ measurement $\{M_y | y \in
\{0,1\}^n\} \cup \{I - \sum_y M_y\}$ (please see Sec.~\ref{sec:prelim} for definition of
$\mathsf{POVM}$) to determine the value of the committed string by $\mathsf {Alice}$ or to
detect her cheating. The protocol runs in two phases called the commit
phase followed by the reveal phase.  The following properties need to
be satisfied.
\begin{enumerate}
\item {\bf (Correctness)} Let $\mathsf {Alice}$ and $\mathsf {Bob}$ act honestly. Let $\rho_x$
be the state of $\mathsf {Bob}$'s qubits
at the end of the reveal phase of the protocol when $\mathsf {Alice}$ gets input
$x$. Then $\forall x,y ~~ {\mathsf{Tr}} M_y
\rho_x = 1$ iff $x=y$ and 0 otherwise.
\item {\bf (Concealing)} Let $\mathsf {Alice}$ act honestly and $\mathsf {Bob}$ be possibly
cheating. Let $\sigma_x$ be the state of $\mathsf {Bob}$'s qubits after the commit
phase when $\mathsf {Alice}$ gets input $x$. Then the $B$ information of the
ensemble ${\cal E} = \{p_x, \sigma_x \}$ is at most $b$. In particular this
is also true for both $\mathsf {Alice}$ and $\mathsf {Bob}$ acting honestly.
\item {\bf (Binding)} Let $\mathsf {Bob}$ act honestly and $\mathsf {Alice}$ be possibly
cheating. Let $c \in \{0,1\}^n$ be a string in a special cheating
register $C$ with $\mathsf {Alice}$ that she keeps independent of the rest of the registers
till the end of the commit phase. Let $\rho_c'$ be the state of $\mathsf {Bob}$'s
qubits at the end of the reveal phase when $\mathsf {Alice}$ has $c$ in the
cheating register. Let $\tilde{p}_c \stackrel{\mathsf{def}}{=}
{\mathsf{Tr}} M_c \rho_c'$. Then for all input strings $x$, $$ \sum_{c \in
\{0,1\}^n } p_c \tilde{p}_c \quad \leq \quad 2^{a-n}.$$
\end{enumerate}
\end{definition}

The idea behind the above definition is as follows.  At the end of the
reveal phase of an honest run of the protocol $\mathsf {Bob}$ figures out $x$ from
$\rho_x$ by performing the $\mathsf{POVM}$ measurement $\{M_x\} \cup \{ I -
\sum_x M_x \}$. He accepts the committed string to be $x$ iff $M_x$
succeeds and this happens with probability ${\mathsf{Tr}} M_x \rho_x$. He
declares $\mathsf {Alice}$ cheating if $I - \sum_x M_x$ succeeds. Thus due to the
first condition, at the end of an honest run of the protocol, $\mathsf {Bob}$
accepts the committed string to be exactly the input string of $\mathsf {Alice}$
with probability 1. The second condition above takes care of the
concealing property stating that the amount of $B$ information about
$x$ that a possibly cheating $\mathsf {Bob}$ gets is bounded by $b$. In
bit-commitment protocols, the concealing property was quantified in
terms of the probability with which $\mathsf {Bob}$ can guess $\mathsf {Alice}$'s bit.
Buhrman et al.~\cite{harry:QSC} in fact do consider $\mathsf {Bob}$'s probability of guessing
$\mathsf {Alice}$'s input string as quantifying the concealing property. However
in the proof of their trade-off result, they consider a related notion
of information as a quantification of the concealing property.  In
this paper, we use various notions of information to quantify the
concealing property of the protocol.  The third condition guarantees
the binding property. It makes sure that if a cheating $\mathsf {Alice}$ wants to
postpone committing or wants to change her choice at the end of the commit phase, then
she cannot succeed in making an honest $\mathsf {Bob}$ accept her new choice with good
probability, for a lot of different strings of her choice.

A few points regarding the above definition are important to note.  We
assume that the combined state of $\mathsf {Alice}$ and $\mathsf {Bob}$ at the beginning
of the protocol is a pure state. Given this assumption, it can be
assumed without loss of generality (due to the arguments
of~\cite{yao:oblivious,hklo:bitcomm2}) that it remains a pure state
till the end of the protocol (in an honest run). This is because
$\mathsf {Alice}$ and $\mathsf {Bob}$ need not apply any intermediate measurements,
before $\mathsf {Bob}$ applies the final checking $\mathsf{POVM}$ at the end of the
protocol. Our impossibility result makes a critical use of this fact
and fails to hold if the starting combined state is not a pure
state. However, there are no restrictions on the starting pure state
shared between $\mathsf {Alice}$ and $\mathsf {Bob}$, it could even be an entangled
state between them. The impossibility result in~\cite{harry:QSC} has
also been shown under this assumption. This assumption has also been
made in showing impossibility results for bit-commitment
schemes~\cite{mayer:imp,hklo:bitcomm1,hklo:bitcomm2}. The main reason
why these arguments do not work, both for bit commitment and string
commitment schemes, if the combined state is not a pure state is that
the {\em Local Transition Theorem} (Thm.~\ref{thm:loctrans}
mentioned later) fails to hold for mixed states. It is conceivable
that, and will be interesting to see if better $\mathsf{ QSC}$ schemes exist
when $\mathsf {Alice}$ and $\mathsf {Bob}$ are forced (by some third party say) to start
in some mixed state. Please look at~\cite{Dariano07} for extension of
impossibility results for bit-commitment to a very large class of protocols.

\subsection{Measures of information} As we will see later, the notion of information
used in the above definition is very important and therefore let us
briefly define various notions of information that we will be
concerned with in this paper. The following notion of information,
referred to as the quantum mutual information or the Holevo-$\chi$
information is one of the most commonly used.
\begin{definition}[Holevo-$\chi$ information]
Given a quantum state $\rho$, the {\em von-Neumann} entropy of $\rho$
is defined as $\mathsf{S}(\rho) \stackrel{\mathsf{def}}{=} - {\mathsf{Tr}} \rho \log_2 \rho$. Given quantum
states $\rho, \sigma$, the {\em Kullback-Leibler divergence} or {\em
relative entropy} between them is defined as $\mathsf{S}(\rho \| \sigma) \stackrel{\mathsf{def}}{=}
{\mathsf{Tr}} \rho (\log_2 \rho - \log_2 \sigma)$. Given an ensemble ${\cal E} = \{p_x,
\rho_x
\}$, let $\rho \stackrel{\mathsf{def}}{=} \sum_x p_x \rho_x$, then its Holevo-$\chi$ information
is defined as $$\chi({\cal E}) \quad \stackrel{\mathsf{def}}{=} \quad \sum_x p_x (\mathsf{S}(\rho) -
\mathsf{S}(\rho_x)) \quad = \quad \sum_x p_x \mathsf{S}(\rho_x \| \rho). $$
\label{def:holevo}
\end{definition}

The following notion captures the amount of information
that can be made available to the real world through measurements on
the quantum encoding of a classical random variable.

\begin{definition}[Accessible information]
Let ${\cal E} = \{p_x,\rho_x\}$ be an ensemble and let $X$ be a classical random
variable such that $\Pr(X=x) \stackrel{\mathsf{def}}{=} p_x$.  Let $Y^{\mathcal{M}}$, correlated with
$X$, be the classical random variable that represents the result of a
$\mathsf{POVM}$ measurement ${\mathcal{M}}$ performed on ${\cal E}$. The {\em accessible
information\/}~$I_{{\mathrm{acc}}}({\cal E})$ of the ensemble~${\cal E}$ is then defined
to be
\begin{equation}
\label{eqn-acc}
I_{{\mathrm{acc}}}({\cal E}) \quad  \stackrel{\mathsf{def}}{=} \quad \max_{{\mathcal{M}}} I(X:Y^{\mathcal{M}}).
\end{equation}
\end{definition}

As mentioned before Buhrman et al. used $\mathsf {Bob}$'s probability of guessing
$\mathsf {Alice}$'s input string as the measure of concealment of the
protocol.  However in the proofs of their impossibility result, they used
the following notion of information.
\begin{definition}[$\xi$ information~\cite{harry:QSC}]
The $\xi$ information of an ensemble ${\cal E} =
\{p_x, \rho_x \}$ is defined as
$$\xi({\cal E}) \quad \stackrel{\mathsf{def}}{=} \quad n + \log_2 \sum_x {\mathsf{Tr}}(p_x\rho^{-1/2} \rho_x)^2 $$
where $\rho = \sum_x p_x \rho_x$.
\end{definition}
Let $q_x$ be the probability that $\mathsf {Bob}$ correctly guesses $\mathsf {Alice}$'s input
string $x$ (with $\mathsf {Alice}$ honest) before the start of the reveal phase.  \cite{harry:QSC}
showed that any $(n,a,b)-\mathsf{ QSC}$ protocol with $\sum_{x \in \{0,1\}^n} q_x \leq 2^b$, is
also a $(n,a,b)-\xi-\mathsf{ QSC}$ protocol. Hence their impossibility results for
$(n,a,b)-\xi-\mathsf{ QSC}$ protocols implied same impossibility results for
$(n,a,b)-\mathsf{ QSC}$ protocols with $\sum_{x \in \{0,1\}^n} q_x \leq 2^b$.

In this paper we also consider a notion of {\em divergence
information}. It is based on the following notion of distance between
two quantum states, considered by Jain, Radhakrishnan and Sen~\cite{jain:substate}.
\begin{definition}[Observational divergence~\cite{jain:substate}]
 Let $\rho, \sigma$ be two quantum states. The observational divergence between them denoted $\mathsf{D}(\rho \|
\sigma)$, is defined as, $$\mathsf{D}(\rho \| \sigma) \quad \stackrel{\mathsf{def}}{=} \quad
\max_{\mathsf{M:POVM~element}} {\mathsf{Tr}} M \rho \log_2 \frac{{\mathsf{Tr}} M \rho} {{\mathsf{Tr}} M
\sigma}.$$
\end{definition}

The definition of divergence information of an ensemble is similar to
the Holevo-$\chi$ information except the notion of distance between
quantum states used is now observational divergence instead of
 relative entropy.
\begin{definition}[Divergence information]
\label{def:divinf}
Let ${\cal E} = \{p_x,\rho_x\}$ be an ensemble and let $\rho \stackrel{\mathsf{def}}{=} \sum_x
p_x \rho_x$. Its divergence information
is defined $${\cal D}({\cal E}) \quad \stackrel{\mathsf{def}}{=} \quad \sum_x p_x \mathsf{D}(\rho_x \| \rho).$$
\end{definition}

\subsection{Previous results} The impossibility of a strong string
commitment protocol, in which both $a,b$ are required to be 0, is
immediately implied by the impossibility of strong bit-commitment
protocols.  The question of a trade-off between $a$ and $b$ was
studied by Buhrman et al. They studied this trade-off both in the
scenario of single execution of the protocol and also in the
asymptotic regime with several parallel executions of the protocol. In
the scenario of single execution of the protocol they showed the
following result.
\begin{theorem}[\cite{harry:QSC}]
\label{thm:harrysingle}
For single execution of the protocol of a $(n,a,b)$-${\xi}$-$\mathsf{ QSC}$,
$a + b + 5 \log_2 5 - 4 \geq n$.
\end{theorem}
This then (as argued before) implied similar trade-off for a
$(n,a,b)$-$\mathsf{ QSC}$ with $\sum_{x \in \{0,1\}^n} q_x \leq 2^b$ (where $q_x$
be the probability that $\mathsf {Bob}$ correctly guesses $\mathsf {Alice}$'s input string
$x$, with $\mathsf {Alice}$ honest, before the start of the reveal phase.)  In the
asymptotic regime they showed the following result in terms of the
Holevo-$\chi$ information.

\begin{theorem}[\cite{harry:QSC}]
\label{thm:avgasym}
Let $\Pi$ be a  $(n, *, b)-\chi-\mathsf{ QSC}$ scheme. Let $\Pi_m$ represent
$m$ parallel executions of $\Pi$.  Let $a_m$ represent the
binding parameter of $\Pi_m$ and let $a \stackrel{\mathsf{def}}{=} \lim_{m \rightarrow
\infty} \frac{a_m}{m}$.  Then, $ a + b \geq  n $.
\end{theorem}
There are two reason why Thm.~\ref{thm:avgasym} may appear stronger than
Thm.~\ref{thm:harrysingle}. One because there is no additive constant
and the other because for many ensembles ${\cal E}$, $\chi({\cal E}) \leq
\xi({\cal E})$ as we show in Sec.~\ref{sec:separation}. In fact, as we also
show in Sec.~\ref{sec:separation}, there exists ensembles ${\cal E}$ for
which $\xi({\cal E})$ is exponentially (in $n$) larger than $\chi({\cal E})$.

Along with these impossibility results Buhrman et al. interestingly
also showed that if the measure of information considered is the
accessible information, the above trade-offs no longer hold. For
example there exists a $\mathsf{ QSC}$ scheme where $a = 4 \log_2 n + O(1)$ and
$b = 4$ when measure of information is the accessible information. This
therefore asserts that the choice of measure of information is crucial
to (im)possibility. Previously Kent~\cite{kent:bitcomm} also exhibited
trade-offs for some schemes on $\mathsf {Alice}$'s probability of cheating and the
amount of accessible information that $\mathsf {Bob}$ gets about the committed
string.  However he did not allow $\mathsf {Alice}$ to be arbitrarily cheating, in
particular $\mathsf {Alice}$ could not have started with a superposition of
strings in the input register. Therefore the schemes that he
considered were truly not $\mathsf{ QSC}$s as we have defined them.

\subsection{Our results}
We show the following binding-concealing trade-off for $\mathsf{ QSC}$s.

\begin{theorem}
\label{thm:avg}
For single execution of the protocol of a $(n,a,b)-{\cal D}-\mathsf{ QSC}$ scheme,
$$ a + b + 8 \sqrt{b + 1} + 16  \quad \geq \quad  n. $$
\end{theorem}

It was shown by Jain, Radhakrishnan and
Sen~\cite{jain:substate} that for any two states
$\rho, \sigma$, $\mathsf{D}(\rho \| \sigma) \leq \mathsf{S}(\rho \| \sigma) + 1$, which
implies from Defn.~\ref{def:holevo} and~\ref{def:divinf}
that for any ensemble ${\cal E}, {\cal D}({\cal E}) \leq \chi({\cal E}) + 1$. This
immediately gives us the following impossibility result in terms of
Holevo-$\chi$ information.
\begin{theorem}
\label{thm:avgchi}
For single execution of the protocol of a $(n,a,b)-\chi-\mathsf{ QSC}$ scheme
$$ a + b + 8 \sqrt{b + 2} +17  \quad \geq \quad  n. $$
\end{theorem}

We also consider the notion of {\em maximum possible
divergence information} (similar to the notion of maximum possible
Holevo-$\chi$ information considered by Jain~\cite{jain:remote}) of an
{\em encoding} $E: x \mapsto \rho_x$. For a probability
distribution $\mu \stackrel{\mathsf{def}}{=} \{p_x\}$ over $\{0,1\}^n$, let the ensemble
${\cal E}_{\mu}(E) \stackrel{\mathsf{def}}{=} \{p_x, \rho_x \}$.  Let $\rho_{\mu} \stackrel{\mathsf{def}}{=} \sum_x p_x \rho_x$.

\begin{definition}(Maximum possible divergence information)
{\em Maximum possible divergence information} of an encoding $E: x \mapsto
\rho_x$ is defined as $\tilde{{\cal D}}(E) \stackrel{\mathsf{def}}{=} \max_{\mu} {\cal D}({\cal E}_{\mu}(E))$.
\end{definition}
We show the following theorem which states that if the maximum
possible divergence information in the qubits of $\mathsf {Bob}$ at the end of the commit
phase is small then $\mathsf {Alice}$ can actually cheat with good probability for
any string $x \in \{0,1\}^n$ and not just on the average.
\begin{theorem}
\label{thm:worst}
For a $\mathsf{ QSC}$ scheme let $\sigma_x$ be as in Defn.~\ref{def:QSC} when
$\mathsf {Alice}$ and $\mathsf {Bob}$ act honestly in the commit phase.  If for the encoding
$E:x \mapsto \sigma_x,
\tilde{{\cal D}}(E) \leq b$ then for all strings $c \in \{0,1\}^n$, $$ \tilde{p}_c
\quad \geq \quad 2^{-(b + 8 \sqrt{b + 1} + 16)}, $$
where $\tilde{p}_c$ (as in Defn.~\ref{def:QSC}) represents the probability of
successfully revealing string $c$ (in the cheating string) by cheating $\mathsf {Alice}$.
\end{theorem}
Again using the fact that for all ensembles
$\mathsf{D}(\rho \| \sigma) \leq \mathsf{S}(\rho \| \sigma) + 1$ we immediately get the
following theorem in terms of maximum possible Holevo-$\chi$
information $\tilde{\chi}(E)$ (which is similar to maximum possible divergence
information and obtained by just replacing divergence with relative
entropy.)
\begin{theorem}
\label{thm:worstchi}
For a $\mathsf{ QSC}$ scheme let $\sigma_x$ be as in Defn.~\ref{def:QSC} when
$\mathsf {Alice}$ and $\mathsf {Bob}$ act honestly in the commit phase.  If for the encoding
$E:x \mapsto \sigma_x,
\tilde{\chi}(E) \leq b$ then for all strings $c \in \{0,1\}^n$, $$ \tilde{p}_c
\quad \geq \quad 2^{-(b + 8 \sqrt{b + 2} + 17)}, $$
where $\tilde{p}_c$ (as in Defn.~\ref{def:QSC}) represents the probability of
successfully revealing string $c$ (in the cheating string) by cheating $\mathsf {Alice}$.
\end{theorem}

Now let us now discuss some aspects of our results.

\begin{enumerate}

\item
In Thm.~\ref{thm:avgchi} the trade-off between $a$ and $b$ is similar
(up to lower order terms of $b$) to the one shown by Buhrman et
al.~\cite{harry:QSC} as in Thm.~\ref{thm:harrysingle}. However the fact
that $b$ in Thm.~\ref{thm:avgchi} represents the Holevo-$\chi$
information instead of the $\xi$-information (as in
Thm.~\ref{thm:harrysingle}) makes it significantly stronger in certain
cases as follows.  We show in Sec.~\ref{sec:separation} that for any
ensemble ${\cal E} \stackrel{\mathsf{def}}{=} \{2^{-n}, \rho_x \}$, where for all $x$, $\rho_x$ commutes with
$\rho \stackrel{\mathsf{def}}{=} \sum_x 2^{-n}\rho_x$, we have, $\xi({\cal E}) \geq
\chi({\cal E})$. In fact, as we also show in Sec.~\ref{sec:separation},
there exists ensembles ${\cal E}$ for which $\xi({\cal E})$ is exponentially (in $n$) larger than
$\chi({\cal E})$.  Thm.~\ref{thm:avgchi} therefore becomes much stronger
than Thm.~\ref{thm:harrysingle} for ensembles where $\xi({\cal E}) \gg \chi({\cal E})$.

\item As mentioned before, Jain, Radhakrishnan and Sen~\cite{jain:substate}
have shown that for any ensemble ${\cal E}, {\cal D}({\cal E}) \leq \chi({\cal E}) +
1$. However recently, Jain, Nayak and Su~\cite{JainNS08} have shown that
there exists ensembles ${\cal E}$ such that $\chi({\cal E}) \gg
{\cal D}({\cal E})$ ($\chi({\cal E}) = \Omega(\log_2 n \cdot {\cal D}({\cal E}))$ for some ensembles
${\cal E}$ supported on $\{0,1\}^n$). For ensembles where this holds,
Thm.~\ref{thm:avg} becomes much stronger than Thm.~\ref{thm:avgchi}.

\item As we show in Sec.~\ref{sec:proof}, our one shot result
Thm.~\ref{thm:avgchi} immediately implies the asymptotic result
Thm.~\ref{thm:avgasym} of Buhrman et al.

\item No counterparts of Thm.~\ref{thm:worst} and
Thm.~\ref{thm:worstchi} were shown by Buhrman et al. and are therefore
completely new.

\item If $b$ is large then the cheating attack (that we present) of $\mathsf {Alice}$ would
succeed with low probability (like $2^{-b}$). However, as we show in a
remark in Sec.~\ref{sec:proof}, in case $\mathsf {Alice}$'s cheating attack succeeds with
low probability, she would still be able to 'reverse' her cheating
operations and reveal, with a high probability, at least some $x' \in
\{0,1\}^n$ to $\mathsf {Bob}$. That is, with a high probability, $\mathsf {Alice}$ will
be able to prevent herself from being detected cheating by $\mathsf {Bob}$.

\item It is easily seen that up to lower order terms in $b$, the above trade-offs are
achieved by trivial protocols. For Thm.~\ref{thm:avg} above
consider the following protocol. $\mathsf {Alice}$ in the concealing phase sends
the first $b$ bits of the $n$-bit string $x$. In this case $\mathsf {Bob}$ gets to
know $b$ bits of divergence information about $x$. In the reveal phase
a cheating $\mathsf {Alice}$ can now reveal any of the $2^{n-b}$ strings $x$
(consistent with the first $b$ bits being the ones sent) with
probability 1. Hence $a = \log_2 2^{n-b} = n-b$. For
Thm.~\ref{thm:worst} above let $\mathsf {Alice}$ send one of the $2^b$ strings
$s \in \{0,1\}^b$ uniformly to $\mathsf {Bob}$ representing the first $b$ bits of
$x$. The condition of Thm.~\ref{thm:worst} is satisfied. Now if in
the reveal phase she wants to commit any $x$, she can do so with
probability $2^{-b}$ (in the event that the sent $s$ is consistent
with $x$).

\end{enumerate}

In the next section we state some quantum information theoretic facts
that will be useful in the proofs of the impossibility results that we
present in Sec.~\ref{sec:proof}.

\section{Preliminaries}
\label{sec:prelim}
All logarithms in this paper are taken with base 2 unless otherwise
specified. Let ${\cal H}, {\cal K}$ be finite dimensional Hilbert spaces. For a
linear operator $A$ let $|A| = \sqrt{A^{\dagger}A}$ and let ${\mathsf{Tr}} A$
denote the trace of $A$.  Given a state $\rho \in {\cal H}$ and a pure
state $\ket{\phi} \in {\cal H} \otimes
{\cal K}$, we call $\ket{\phi}$ a {\em purification} of $\rho$ iff
${\mathsf{Tr}}_{{\cal K}}
\ketbra{\phi} = \rho $. A {\em positive operator-valued
measurement $(\mathsf{POVM})$ element} $M$ is a positive semi-definite operator
such that $I - M$ is also positive semi-definite, where $I$ is the
identity operator.  A $\mathsf{POVM}$ is defined as follows.
\begin{definition}[$\mathsf{POVM}$]
An $m$ valued $\mathsf{POVM}$ measurement ${\mathcal{M}}$ on a Hilbert space ${\cal H}$ is a set of operators
$\{M_i, i \in [m]\}$ on ${\cal H}$ such that $\forall i, M_i$
is positive semi-definite and $\sum_{i \in [m]} M_i = I$ where $I$ is the
identity operator on ${\cal H}$. A classical random variable $Y^{{\mathcal{M}}}$
representing the result of the measurement ${\mathcal{M}}$ on a state $\rho$ is an $m$ valued
random variable such that $\forall i \in [m], \Pr[Y^{{\mathcal{M}}} = i ] \stackrel{\mathsf{def}}{=} {\mathsf{Tr}} M_i\rho$.
\end{definition}

Following fact follows easily from definition of von-Neumann entropy.
\begin{lemma}
\label{lem:sadd}
Let $\rho_1, \rho_2$ be quantum states. Then $\mathsf{S}(\rho_1 \otimes \rho_2)
= \mathsf{S}(\rho_1) + \mathsf{S}(\rho_2)$.
\end{lemma}

We make a central use the following information-theoretic result called
the substate theorem due to Jain, Radhakrishnan, and
Sen~\cite{jain:substate}.
\begin{theorem}[Substate theorem, \cite{jain:substate}]
\label{thm:substate}
Let ${\cal H}, {\cal K}$ be two finite dimensional Hilbert spaces and $\dim({\cal K})
\geq \dim({\cal H})$. Let ${\mathbb C}^2$ denote the two dimensional complex Hilbert
space.  Let $\sigma, \tau$ be density matrices in ${\cal H}$ such that
$\mathsf{D}(\sigma \| \tau) < \infty$.  Let $\ket{\overline{\sigma}}$ be a
purification of $\sigma$ in ${\cal H} \otimes {\cal K}$. Then, for $r > 1$, there
exist pure states $\ket{\phi}, \ket{\theta} \in {\cal H}
\otimes {\cal K}$ and
$\ket{\overline{\tau}} \in {\cal H} \otimes {\cal K} \otimes {\mathbb C}^2$, depending
on $r$, such that $\ket{\overline{\tau}}$ is a purification of
$\tau$ and ${\mathsf{Tr}} |\ketbra{\overline{\sigma}} - \ketbra{\phi}| \leq \frac{2}{\sqrt{r}}$, where
\begin{displaymath}
\ket{\overline{\tau}} \stackrel{\mathsf{def}}{=}
\sqrt{\frac{r-1}{r 2^{r k}}} \, \ket{\phi}\ket{1} +
\sqrt{1 - \frac{r-1}{r 2^{r k}}} \, \ket{\theta}\ket{0}
\end{displaymath}
and $k \stackrel{\mathsf{def}}{=} \mathsf{D}(\sigma \| \tau) +
6 \sqrt{\mathsf{D}(\sigma \| \tau) + 1} + 4$.
\end{theorem}

\paragraph{Remarks:}
\begin{enumerate}
\item In the above theorem if the last qubit in
$\ket{\overline{\tau}}$ is measured in the computational basis, then
probability of obtaining 1 is $(1 - 1/r) 2^{-r k}$.
\item  Later in a proof below we will let $\sigma \stackrel{\mathsf{def}}{=} \rho_c$
, $\tau \stackrel{\mathsf{def}}{=} \rho_B$ and $\ket{\overline{\sigma}}
\stackrel{\mathsf{def}}{=} \ket{\phi_c}$ which will be explained later.
\end{enumerate}

Following theorem is implicit
in~~\cite{jozsa:loctrans,mayer:imp,hklo:bitcomm1,hklo:bitcomm2}
although not called explicitly by the same name.
\begin{theorem}[Local transition theorem]
\label{thm:loctrans}
Let $\rho$ be a quantum state in ${\cal K}$. Let $\ket{\phi_1}$ and $
\ket{\phi_2}$ be two purification of $\rho$ in ${\cal H} \otimes {\cal K}$. Then
there is a local unitary transformation $U$ acting on ${\cal H}$ such that
$(U \otimes I) \ket{\phi_1} = \ket{\phi_2}$.
\end{theorem}

We would also need the following theorem which follows from arguments
similar to the one in Jain~\cite{jain:remote} for a similar theorem
about relative entropy.
\begin{theorem}
\label{thm:remote}
Let $X$ be a finite set. Let $E: x \mapsto \rho_x$ be an encoding. Let
$\tilde{{\cal D}}(E) \leq b$, then there exists a distribution
$\mu \stackrel{\mathsf{def}}{=} \{q_x \}$ on $X$ such that $$\forall x \in X, \quad \mathsf{D}(\rho_x \| \rho) \quad \leq \quad
b,$$ where $\rho \stackrel{\mathsf{def}}{=} \sum_x q_x \rho_x$.
\end{theorem}

The following theorem is shown by Helstrom~\cite{Helstrom67}.
\begin{theorem}
\label{thm:dist}
Given two quantum states $\rho$ and $\sigma$, the probability of
identifying the correct state is at most $\frac{1}{2} + \frac{{\mathsf{Tr}} |\rho - \sigma
|}{4}$, or in other words the probability of distinguishing them is at
most $\frac{{\mathsf{Tr}} |\rho - \sigma |}{2}$.
\end{theorem}

\section{Proofs of impossibility}
\label{sec:proof}
\noindent
\begin{proofof}{Thm.~\ref{thm:avg}} Let us consider a $\mathsf{ QSC}$ scheme
and let $\mathsf {Alice}$ get input $x$. After an honest run of the commit phase,
let $\ket{\phi_x}$ be the combined state of $\mathsf {Alice}$ and $\mathsf {Bob}$ and $\rho_x$
be the state of $\mathsf {Bob}$'s qubits.  Let ${\cal E} = \{p_x,
\rho_x\}$. From the concealing property of the $\mathsf{ QSC}$ it follows
$\mathsf{D}({\cal E}) \leq b$. Let $c$ be the string in the cheating register $C$
of $\mathsf {Alice}$. Consider a cheating run of the protocol by $\mathsf {Alice}$ in
which she starts with the superposition $\sum_x
\sqrt{p_x}\ket{x}$ in the input register and proceeds with the rest
of the commit phase as before in the honest protocol. Let $\mathsf {Bob}$ be
honest all throughout our arguments.  Since the input is classical and
$\mathsf {Alice}$ can make its copy we can assume without loss of generality
that the operations of $\mathsf {Alice}$ in the honest run are such that they
do not disturb the input register. Let $\ket{\psi}$ be the combined
state of $\mathsf {Alice}$ and $\mathsf {Bob}$ in this cheating run at the end of the
commit phase.  Let $A, B$ correspond to $\mathsf {Alice}$ and $\mathsf {Bob}$'s systems
respectively. Now it can be seen that in the cheating run, at the end
of the commit phase the qubits of $\mathsf {Bob}$ are in the state $\rho_B
\stackrel{\mathsf{def}}{=} {\mathsf{Tr}}_A
\ketbra{\psi} = \sum_x p_x \rho_x$. Let $r > 1$ to be chosen
later. Let us now invoke substate theorem (Thm.~\ref{thm:substate}) by
putting $\sigma \stackrel{\mathsf{def}}{=} \rho_c,
\ket{\overline{\sigma}} \stackrel{\mathsf{def}}{=} \ket{\phi_c}$,
$\tau \stackrel{\mathsf{def}}{=} \rho_B$ and $r \stackrel{\mathsf{def}}{=} r$. Let $\ket{\psi_c} \stackrel{\mathsf{def}}{=}
\ket{\overline{\tau}}$ be obtained from
Thm.~\ref{thm:substate} such that the extra single qubit register
${\mathbb C}^2$ is also with $\mathsf {Alice}$.  Since ${\mathsf{Tr}}_{A} \ketbra{\psi_c} =
{\mathsf{Tr}}_{A} \ketbra{\psi} = \rho_B$, from Local transition theorem
(Thm.~\ref{thm:loctrans}) there exists a
unitary transformation $A_c$ acting just on $\mathsf {Alice}$'s system $A$ such
that $(A_c \otimes I_B)\ket{\psi} = \ket{\psi_c}$, where $I_B$ is the
identity transformation on $\mathsf {Bob}$'s system. Now the cheating $\mathsf {Alice}$ (who's
intention is to reveal string $c$), applies the transformation $A_c$
to $\ket{\psi}$ and then continues with the rest of the reveal phase
as in the honest run. Let $\ket{\phi_c'}
\stackrel{\mathsf{def}}{=} \ket{\phi}$ be obtained from Thm.~\ref{thm:substate} and
hence, ${\mathsf{Tr}} |\ketbra{\phi_c} - \ketbra{\phi_c'}| \leq 2/\sqrt{r}$. Now
it can be seen that when $\mathsf {Bob}$ makes the final checking $\mathsf{POVM}$, the
probability of success $\tilde{p}_c$ for $\mathsf {Alice}$ is at least $(1 -
1/r)2^{-rk_c}(1 - 1/\sqrt{r})$ where $ k_c = \mathsf{D}(\rho_c \| \rho_B) + 6
\sqrt{\mathsf{D}(\rho_c \| \rho_B) + 1} + 4$. One way to see this is to imagine
that $\mathsf {Alice}$ first measures the single qubit register ${\mathbb C}^2$ and then
proceeds with the rest of the reveal phase.  Now imagine that she
obtains one on this measurement which from Thm.~\ref{thm:substate} has
probability $(1 - 1/r)2^{-rk_c}$. Also once she obtains one, the
combined joint state of $\mathsf {Alice}$ and $\mathsf {Bob}$ is $\ket{\phi_c'}$ whose
trace distance with $\ket{\phi_c}$ is at most $2/\sqrt{r}$. Since
trace distance is preserved by unitary operations and is only smaller
for subsystems and since after this $\mathsf {Alice}$ follows the rest of the
reveal phase honestly, we can conclude the following: the final state resulting
with $\mathsf {Bob}$ will have trace distance at most $2/\sqrt{r}$ with the
state with him at the end of a completely honest run of the protocol
in which Alice starts with $c$ in the input register. Hence it follows from
Thm.~\ref{thm:dist} that $\mathsf {Bob}$ will accept at the end with
probability at least $1 - 1/\sqrt{r}$ since he was accepting with
probability 1 in the complete honest run of the protocol . Hence the
overall cheating probability $\tilde{p}_c$ of $\mathsf {Alice}$ is at least $(1 -
1/r)2^{-rk_c}(1 - 1/\sqrt{r})$.

Although here we have imagined $\mathsf {Alice}$ doing an intermediate
measurement on the single qubit register ${\mathbb C}^2$, it is not necessary
and she will have the same cheating probability when she proceeds with
the rest of the honest protocol after just applying the cheating
transformation $A_c$ since the final qubits of $\mathsf {Bob}$ will be in the same
state in either case. Now,
\begin{eqnarray*}
2^{a-n} & \geq & \sum_c p_c \tilde{p}_c  \\
& \geq & (1 - 1/r)(1 - 1/\sqrt{r}) \left( \sum_c  p_c 2^{-r(\mathsf{D}(\rho_c
\| \rho_B) + 6 \sqrt{\mathsf{D}(\rho_c \| \rho_B) + 1} + 4)} \right) \\
& \geq & (1 - 1/r)(1 - 1/\sqrt{r})2^{\sum_c -r  p_c(\mathsf{D}(\rho_c \|
\rho_B) + 6 \sqrt{\mathsf{D}(\rho_c \| \rho_B) + 1} +  4)} \\
& \geq &  (1 - 1/r)(1 - 1/\sqrt{r}) 2^{ -r(b + 6 \sqrt{b + 1} +  4) }
\end{eqnarray*}
The first inequality comes from definition of $a$ in
Defn.~\ref{def:QSC}. The third inequality comes from the convexity of
the exponential function and the fourth inequality comes from
definition of $b$ in Defn.~\ref{def:QSC}, Defn.~\ref{def:divinf} and
concavity of the square root function.

Now when $b > 15$, we let $r = 1 + \frac{1}{b}$ and therefore,
\begin{eqnarray*}
(1 - 1/r)(1 - 1/\sqrt{r}) 2^{ -r(b + 6 \sqrt{b + 1} +  4) }
& \geq & \frac{0.5}{(b + 1)^2} 2^{ -(b + 6 \sqrt{b + 1} +  7) } \\
& \geq & 2^{ -(b + 8 \sqrt{b + 1} +  8) }
\end{eqnarray*}

When $b \leq 15$, we let $r = 1 + 1/15$ and therefore,
\begin{eqnarray*}
(1 - 1/r)(1 - 1/\sqrt{r}) 2^{ -r(b + 6 \sqrt{b + 1} +  4) }
& \geq & 2^{ -(b + 6 \sqrt{b + 1} + 16) }
\end{eqnarray*}
Therefore we get always, $2^{a - n} \geq 2^{ -(b + 8 \sqrt{b + 1} +
16) } $ which finally implies,
$$ a + b + 8 \sqrt{b + 1} + 16  \geq  n .$$
\end{proofof}

\vspace{0.1cm}
\begin{proofof}{Thm.~\ref{thm:avgasym}}
Let $b_m$ represent the concealing parameter for $\Pi_m$.  It is easy to
verify from Lem.~\ref{lem:sadd} and definition of Holevo-$\chi$
information, Defn.~\ref{def:holevo}, that $b = b_m/m$.  Then
Thm.~\ref{thm:avgchi} when applied to $\Pi_m$ implies,
\begin{eqnarray*}
& \Rightarrow & a_m + b_m + 8 \sqrt{b_m + 2} + 17  \geq  mn \\
& \Rightarrow & \lim_{m \rightarrow \infty} \frac{1}{m}(a_m + b_m + 8 \sqrt{b_m +
2} + 17)  \geq  n \\
& \Rightarrow & a + b \geq n
\end{eqnarray*}
\end{proofof}

\vspace{0.1cm}
\noindent
\begin{proofof}{Thm.~\ref{thm:worst}} Let $\mu = \{\lambda_x\}$ be the
distribution on $\{0,1\}^n$ obtained from
Thm.~\ref{thm:remote}. Consider a cheating strategy of $\mathsf {Alice}$ in
which she puts the superposition $\sum_x
\sqrt{\lambda_x} \ket{x}$ in the register where she keeps the commit
string. Let $c$ be the string in the cheating register of
$\mathsf {Alice}$. Now by arguments as above probability of success $\tilde{p}_c$ for
$\mathsf {Alice}$ is at least $(1 - 1/\sqrt{r})(1 - 1/r)2^{-rk_c}$ where $ k_c,
\rho_c, \rho$ being as before. Since for all $c, \mathsf{D}(\rho_c \| \rho)
\leq b$ it implies (by setting $r$ appropriately) $\forall c,
\tilde{p}_c \geq 2^{-(b + 8 \sqrt{b + 1} + 16)}. $
\end{proofof}

\paragraph{Remark:} Let us now see how, with a good
probability overall, $\mathsf {Alice}$ will be able to prevent herself from being
detected cheating by $\mathsf {Bob}$. Let $\mathsf {Alice}$ have $c$ in the cheating
register. Let $r_c$ be the probability of getting one on performing
the two outcome measurement (obtained from  Thm.~\ref{thm:substate})
after the commit phase as in the cheating strategy described above in
proof of Thm.~\ref{thm:avg}. In
case she gets one, she proceeds with the cheating strategy. In case
she gets zero, she tries to rollback so that she can successfully
reveal at least some string to $\mathsf {Bob}$. For this she does the
following.

\begin{enumerate}

\item She applies the transformation $A_c^\dagger$ (that is inverse of $A_c$).
\item She measures the input register in the computational basis and
say she obtains $x'$.
\item She proceeds with the rest of the reveal phase as if her actual input was $x'$.

\end{enumerate}

Assume that $\mathsf {Alice}$ obtains zero on performing the two-outcome
measurement as in the cheating strategy described above which happens
with probability $1 - r_c$. Now it can be verified that the trace
distance between $\ketbra{\psi_c}$ and the combined state of $\mathsf {Alice}$ and $\mathsf {Bob}$
after obtaining zero on performing the measurement is at most
$2r_c$. Since, $A_c^\dagger$ is unitary, this implies that the combined state of
$\mathsf {Alice}$ and $\mathsf {Bob}$ after applying $A_c^\dagger$,
and $\ketbra{\psi}$ will be at most $2r_c$. Now we can argue as before
that $\mathsf {Alice}$ can reveal some string successfully to $\mathsf {Bob}$ with
probability at least $1 - r_c$. Therefore overall, the probability
that $\mathsf {Alice}$ will be able to reveal some string is at least $r_c + (1
- r_c)^2 \geq 1 - r_c$. Now since typically $r_c$ is quite small (like
$2^{-b}$), $1 - r_c$ is quite close to 1.

\subsection*{Acknowledgment} We thank Harry Buhrman, Matthias Christandl,
Hoi-Kwong Lo, Jaikumar Radhakrishnan, and Pranab Sen for
discussions. We also thank anonymous referees for suggestions
on an earlier draft.

\newcommand{\etalchar}[1]{$^{#1}$}