---
author:
- Toby Cubitt
- David Elkouss
- William Matthews
- Maris Ozols
- 'David Pérez-García'
- Sergii Strelchuk
title: Unbounded number of channel uses are required to see quantum capacity
---

[**Transmitting data reliably over noisy communication channels is one of the most important applications of information theory, and well understood when the channel is accurately modelled by classical physics. However, when quantum effects are involved, we do not know how to compute channel capacities. The capacity to transmit quantum information is essential to quantum cryptography and computing, but the formula involves maximising the coherent information over arbitrarily many channel uses [@Lloyd_97; @Shor_02; @Devetak_05]. This is because entanglement across channel uses can increase the coherent information [@DiVincenzo_98], even from zero to non-zero [@Smith_08]! However, in all known examples, at least to detect whether the capacity is *non-zero*, two channel uses already suffice [@Smith_08; @Brandao_12]. Maybe a finite number of channel uses is always sufficient? Here, we show this is emphatically not the case: for any $n$, there are channels for which the coherent information is zero for $n$ uses, but which nonetheless have capacity. This may be a first indication that the quantum capacity is uncomputable.**]{}

In the classical case, not only can we exactly characterise the maximum rate of communication over any channel – its *capacity* – we also have practical error-correcting codes that attain this theoretical limit. It is instructive to review why the capacity of classical channels is a solved problem. Even though optimal communication over a discrete, memoryless classical channel involves encoding the information across many uses of the channel, Shannon showed that a channel’s capacity is given mathematically by optimising an entropic quantity (the *mutual information*) over a *single* use of the channel. This follows immediately from the fact that mutual information is *additive*. Thanks to this, the capacity of any classical channel can be computed efficiently. It is for this reason that additivity questions for quantum channel capacities took on such importance, and why the major recent breakthroughs proving that additivity is violated [@Hastings; @Smith_08] had such an impact. It has been known for some time [@Lloyd_97; @Shor_02; @Devetak_05] that the quantum capacity is given by a *regularised* expression—the optimisation of an entropic quantity (the *coherent information*) in the limit of arbitrarily many uses of the channel: $$\begin{aligned}
\label{eq:Q}
  Q^{(n)}(\N) &:= \frac{1}{n} \max_{\rho^{(n)}} \Ic(\N^{\otimes n}, \rho^{(n)}),\\
  Q(\N) &:= \lim_{n\to\infty} Q^{(n)}(\N),\end{aligned}$$ (Here, $Q^{(n)}(\N)$ is the coherent information $\Ic$ maximised over a joint input $\rho^{(n)}$ for $n$ uses of the channel $\N$.) However, the regularisation renders computing the quantum capacity infeasible; it involves an optimisation over an infinite parameter space.

Were the coherent information additive (i.e. $Q^{(n)}(\N) = Q^{(1)}(\N)$), the regularisation could be removed and the quantum capacity could be computed as easily as the capacity of classical channels. However, this is not the case. The first explicit examples of this *superadditivity* phenomenon were given by Di Vincenzo et al. [@DiVincenzo_98], and extended by Smith et al. [@Smith_07]. For these examples (where $\mc{N}$ is a particular depolarising channel) it was shown (numerically) that $0 \leq Q^{(1)}(\N) < Q^{(n)}(\N)$ for small values of $n\le 33$.

While the *classical* capacity of quantum channels also involves a regularised formula [@Hastings], we at least know precisely in which cases it is *zero*: simply for those channels whose output is completely independent of the input. The set of zero-*quantum*-capacity channels is much richer. Indeed, we do not even have a complete characterisation of *which* channels have zero quantum capacity. To date, we know of only two kinds of channels with zero quantum capacity: *antidegradable* channels [@BDS97; @CRS08] and *entanglement-binding* channels [@HHH00]. The former has the property that the environment can reproduce the output, thus $Q = 0$ by the no-cloning theorem [@WZ82]. The latter can only distribute PPT entanglement, which cannot be distilled by local operations and classical communication [@PPT], which again implies $Q = 0$.

This has dramatic consequences. It is possible to take two quantum channels above, $\N_1$ antidegradable and $\N_2$ entanglement-binding, which individually have no capacity whatsoever, yet when used together can transmit quantum information reliably ($Q(\N_1 \otimes \N_2) > 0$). This *superactivation* phenomenon was discovered recently by Smith and Yard [@Smith_08]. They also used their examples to construct a single channel $\N$ exhibiting an extreme form of superadditivity of the coherent information, where $0 = Q^{(1)}(\N) < Q^{(2)}(\N)$. (In their construction, having two uses of $\N$ effectively enables one use of $\N_1$ and one of $\N_2$.) Even stronger superactivation phenomena have been shown in the context of zero-error communication over quantum channels [@Alon; @Cubitt; @Cubitt!; @Cubitt!!; @Shirokov_14].

On the one hand, additivity violation means regularisation is required in formulas for computing capacities. On the other hand, it also means that *entanglement* can protect information from noise (the coherent information is additive for unentangled input states). But just how bad can this additivity violation be? One might hope that, at least in determining whether the quantum capacity is non-zero, one need only consider a finite number of uses of a channel. Indeed, since the Smith and Yard construction relies on combining the only two known types of zero-capacity channels, one might dare to hope that even two uses suffice. (Similarly, for the classical capacity of quantum channels the only known method for constructing examples of additivity violation [@HaydenWinter; @Hastings] cannot give a violation for more than two uses of a channel, and there is some evidence that this may be more than just a limitation of the proof techniques [@Ashley].) Was this indeed the case, additivity violation would be reduced to something relatively benign: entangling the inputs across more than two uses of the channel would give no advantage. And one would be able to compute the quantum capacity by optimising the coherent information over two uses of the channel, which is not substantially more difficult than the optimisation over a single channel use.

In this paper, we show for the first time that this is not the case: additivity violation is as bad as it could possible be. We prove that, for any $n$, one can construct a channel $\N$ for which the coherent information of $n$ uses is zero ($Q^{(n)}(\N)=0$), yet for a larger number of uses the coherent information is strictly positive, implying that the channel has non-zero quantum capacity ($Q(\mathcal N)>0$). This is also the first proof that there can be a gap between $Q^{(n)}(\N)$ and the quantum capacity for an arbitrarily large number $n$ of uses of the channel. Our result implies that, in general, one must consider an arbitrarily large number of uses of the channel *just to decide whether the channel has any quantum capacity at all!*

Perhaps the earliest indication that determining the quantum capacity may be a difficult problem comes from the work of Watrous [@Watrous_04], who showed that an arbitrarily large number of copies of a bipartite quantum state can be required for entanglement distillation assisted by two-way classical communication. Our result can be regarded as the counterpart of [@Watrous_04] for the quantum capacity (which is mathematically equivalent to entanglement distillation assisted by *one-way* communication). However, the proof ideas and techniques of [@Watrous_04] require two-way communication, thus they do not apply to the usual capacity setting. Our result is instead based on the ideas of Smith and Yard, in particular the intuition provided by Oppenheim’s commentary thereon [@Oppenheim_08]. This intuition comes from a class of bipartite quantum states called *pbits* (private bits) [@Horodecki_09b]: $\rho_{\Akey\Ashield\Bkey\Bshield} = \tfrac{1}{2}(\proj{\phi^+}_{\key}\otimes\sigma^+_{\shield} + \proj{\phi^-}_{\key}\otimes\sigma^-_{\shield})$, together with the standard equivalences between quantum capacity (sending entanglement over a channel) and distilling entanglement from the Choi-Jamiołkowsky state associated with the channel. Here, $\ket{\phi^{\pm}}$ are Bell states, and $\sigma^{\pm}$ are hiding states [@Eggeling_02]. The latter are orthogonal (globally perfectly distinguishable), but cannot be distinguished using local operations and classical communication (LOCC).

If $\rho_{\Akey\Ashield\Bkey\Bshield}$ is shared between Alice (who holds $\Akey\Ashield$) and Bob (who holds $\Bkey\Bshield$), then they share at least one ebit of entanglement due to the Bell states. But this entanglement is inaccessible to them unless they can determine which of the two Bell states they share. This they could do if only they could determine which hiding state they have. But $\sigma^{\pm}$ cannot be distinguished by LOCC, preventing them from extracting the entanglement from $\rho_{\Akey\Ashield\Bkey\Bshield}$. The $\key$ part of the system is usually called the “key”, and $\shield$ the “shield” (as it decouples the systems $\key$ from any external system). Now imagine they have access to a quantum erasure channel $\E_{\frac{1}{2}}$, which with probability $1/2$ transmits its input perfectly, and with probability $1/2$ completely erases it. It is well known that such a channel cannot be used to transmit any entanglement. However, if they also share $\rho_{\Akey\Ashield\Bkey\Bshield}$, Alice can use the erasure channel to send her part $\Ashield$ of the shield to Bob. If the erasure channel transmits, Bob now holds the entire $\shield$ system and can now distinguish $\sigma^{\pm}$. Thus, with probability $1/2$, Alice and Bob can now extract the entanglement from $\rho_{\Akey\Ashield\Bkey\Bshield}$.

Instead of supplying Alice and Bob with the state $\rho_{\Akey\Ashield\Bkey\Bshield}$ and an erasure channel, we instead supply them with a *switched* channel. This has an auxiliary classical input that controls whether the channel acts as $\E_{\frac{1}{2}}$ or $\Gamma$, where $\Gamma$ is the channel with Choi-Jamiołkowsky state $\rho_{\Akey\Ashield\Bkey\Bshield}$. The above argument then implies that no quantum information can be sent over a single use of the channel, but it can be sent using two uses, by switching one to $\E_{\frac{1}{2}}$ and the other to $\Gamma$.

This is the intuition behind the Smith and Yard construction [@Oppenheim_08]. However, because it is constructed out of two very particular types of quantum channels, this idea does not seem to extend to larger numbers of uses. Nonetheless, the intuition behind our result is based on a refinement of these ideas, which we now sketch.

We want to achieve two seemingly contradictory goals: (1) To prevent Alice from sending any quantum information to Bob over $n$ of uses of the channel. (2) To permit this when Alice has access to some larger number of uses $N>n$. We can achieve (1) by increasing the erasure probability of the erasure channel to something much closer to 1, and also adding noise to the $\Gamma$ channel; the noise then swamps any entanglement. The problem is that this seems to also render (2) impossible. If the channel is so noisy that it destroys all entanglement sent through it, then (by definition) no amount of coding over multiple uses of the channel can succeed in transmitting quantum information.

However, note that the information that Alice needs to send to Bob in order to extract entanglement from the pbit $\rho_{\Akey\Ashield\Bkey\Bshield}$ is essentially classical. Bob just needs to know one classical bit of information to distinguish the two hiding states. This suggests that *classical* error correction might help Alice send this information to Bob, even when the channel is very noisy. The intuition behind our proof is that a simple classical repetition code suffices. Instead of the pbit $\rho_{\Akey\Ashield\Bkey\Bshield}$, we use a pbit $\tfrac{1}{2}(\proj{\phi^+}_{\key}\otimes\sigma^+_{\A_1\B_1}\otimes\cdots\otimes\sigma^+_{\A_N\B_N} + \proj{\phi^-}_{\key}\otimes\sigma^-_{\A_1\B_1}\otimes\cdots\otimes\sigma^-_{\A_N\B_N})$ that contains $N$ copies of the shield. For Bob to distinguish the hiding states, it suffices for one copy to make it through the erasure channel. Alice now tries to send all of the copies of the shield through many uses of the erasure channel. However high the erasure probability, the probability that at least one will get through can be made arbitrarily high for sufficiently many attempts.

We now give a more precise description of our construction. The *erasure channel with erasure probability* $p$ is $\E_p^{{\A \to \Eflag\B}} := (1-p) \ketbra{0}{0}^{\Eflag} \x \id^{{\A \to \B}} + p \ketbra{1}{1}^{\Eflag}\x \1^{\B}/\dim (\B)$, where $\id^{{\A \to \B}}$ is the identity channel from $\A$ to $\B$, and $\Eflag$ is the erasure flag. The channel $\Gamma^{{\Afull \to \Bfull}}$ belongs to the class of PPT entanglement-binding channels whose Choi state is an approximate pbit [@Horodecki_09b]. We show that $\Gamma$ can be constructed with $\A := \A_1 \ldots \A_N$ and $\B := \B_1 \ldots \B_N$ consisting of $N$ parts, such that even if Bob only receives part $\A_i$ of Alice’s shield for any $i$, they obtain approximately one ebit of one-way distillable entanglement. Let $\ngam^{{\Afull \to \Eflag\Bfull}} := \E^{{\Bfull \to \Eflag\Bfull}}_{\kappa}\circ \gam^{{\Afull \to \Bfull}} $ be a noisy version of the channel $\Gamma$. Our construction uses channels of the form $$\label{eq:ourchannel}
  \chan^{{\SWin\Afull \to \SWout \Eflag\Bfull}}
  := \mc{P}_0^{{\SWin \to \SWout}}
            \otimes \ngam^{{\Afull \to \Eflag\Bfull}}
   + \mc{P}_1^{{\SWin \to \SWout}}
            \otimes \E_p^{{\Afull \to \Eflag\Bfull}}.$$ Here $\mc{P}_i^{{\SWin \to \SWout}}$ projects onto the $i$-th computational basis vector of the qubit system $\SWin$ which thereby acts as a classical switch allowing Alice to choose whether the channel acts as $\E_p$ or $\tilde{\Gamma}_{\kappa}$ on the main input $\Afull$. $\SWin$ is retained in the output which lets Bob learn which choice was made.

Making the above intuition rigorous for this channel is non-trivial: First, we must prove that the coherent information of $n$ uses of the channel is strictly zero, for *any* input to the channel (not just the input states from the above intuition). To this end, we cannot just directly use a pbit with $N$-copy shield of the form given above, as it would have distillable entanglement. Fortunately, we find that an approximate pbit construction from [@Horodecki_09b] can be adapted for the role. But then we must take this approximation into account in the proof that the channel *does* have capacity. This requires a careful analysis of the various parameters of our channel to show that both of the desired properties can hold simultaneously, which requires a somewhat delicate argument. The technical arguments are described in the Methods section.

One natural question (which we leave open) is whether we can obtain a stronger form of our result with a constant upper bound on the channel dimension. It would also be interesting to see if one can obtain a result analogous to ours for the *private* capacity of quantum channels. Finally, our result gives a first indication that the quantum capacity of a channel might well be an uncomputable quantity; uncomputability of the quantum capacity would necessarily imply the behaviour we have shown here.

Methods {#methods .unnumbered}
=======

We state and outline the proof of our main result – for any number of uses we can show that there exists a channel with positive capacity but zero coherent information. Formally, we prove the following:

Let $\chan$ be the channel defined in Eq. . For any positive integer $n$, if $\kappa \in (0,1/2)$ and $p \in [(1+\kappa^{n})^{-1/n},1]$ then we can choose $\NN$ and $\Gamma$ such that:

1.  $Q^{(n)}(\chan) = 0$ and

2.  $Q^{(\NN+1)}(\chan) > 0$, and therefore $Q(\chan) > 0$.

The proof is divided in two parts. We first prove that, given $n$ and $\kappa$, for any $\Gamma$ with zero capacity there is a range of $p$ that makes the coherent information of $\chan^{\x n}$ zero. In the second part we prove that there exists $\Gamma$ with zero capacity such that $\chan$ has positive capacity.

For the first part we can simplify the analysis of $\chan^{\x n}$ by showing that it is optimal to make a definite choice (i.e. a computational basis state input) for each of the $n$ switch registers. For each possible setting of the $n$ switches, the coherent information is a convex combination of the coherent information for three cases, weighted by their probabilities: (a) every channel erases, (b) all of the $\E_p$ erase but not all $\tilde{\Gamma}$ erase, (c) at least one of the $\E_p$ does not erase (and therefore acts as the identity channel). The coherent information for cases $(b)$ and $(c)$ can be upper bounded respectively by zero and $H({\mathsf{R}})$, where ${\mathsf{R}}$ is a system that purifies the input. For $(a)$ it is bounded above by $-H({\mathsf{R}})$. Weighting by the probabilities, we find that the total coherent information is upper-bounded by $\of[\big]{1 - (1+\kappa^n) p^n} H({\mathsf{R}})$. This allows us to conclude that for any $n$ and $\kappa$ we can find $p$ such that the coherent information of $n$ uses of the channel is zero.

To prove the second part, we show that for fixed $\kappa,p$ we can find a $\Gamma$ with an $N$-copy shield such that the coherent information of $N+1$ uses of the channel $\chan$ is positive for some $N+1>n$. We number the channel uses $0,\ldots,N$ and label the systems involved in the $i$-th use of the channel with superscript $i$. Consider the following input. The switch registers are set to choose $\tilde{\Gamma}_{\kappa}$ for use $0$ and $\mathcal E_p$ for the remaining uses $1, \ldots, N$. We maximally entangle subsystem $\A^{0}_i$ of $\Afull^{0}$ (which is acted on by $\tilde{\Gamma}_{\kappa}$) with subsystem $\A^{i}_1$ of $\Afull^{i}$ (acted on by an erasure channel). We also maximally entangle subsystem $\Akey^{0}$ of $\Afull^{0}$ with a purifying reference system $\Akey$ which is retained by Alice. The remaining input subsystems are set to an arbitrary pure state. The resulting coherent information is a convex combination of cases where (a) $\ngam$ erases, (b) $\ngam$ does not erase but all the $\mc{E}_p$ erase, and (c) $\ngam$ and at least one $\mc{E}_p$ do not erase. Case (a) contributes coherent information $-1$ weighted by its probability $\kappa$. Case (b) contributes approximately zero coherent information (due to a standard property of pbits). In case (c), after channel use $0$, Alice and Bob share the Choi state of $\Gamma$ on systems $\Akey \Bkey^{0} \A^{1}_1 \B^{0}_{1} \ldots \A^{N}_1 \B^{0}_{N}$, and after the $N$ uses of $\mc{E}_p$ at least one of $\A^{1}_1 \ldots \A^{N}_1$ reaches Bob unerased. They then share a state with approximately one ebit of one-way distillable entanglement (coherent information $+1$). This contribution is weighted by the probability $(1-\kappa)(1-p^N)$. We show that for $p\in (0,1)$, $\kappa \in (0,1/2)$, we can find a $\Gamma$ with large enough $N$ for which the overall coherent information is positive, proving that $Q(\chan) > 0$. Further mathematical details are given in the Supplementary Information.

[**Acknowledgements:**]{} DE and DP acknowledge financial support from the European CHIST-ERA project CQC (funded partially by MINECO grant PRI-PIMCHI-2011-1071). TSC is supported by the Royal Society. MO acknowledges financial support from European Union under project QALGO (Grant Agreement No. 600700).

[10]{} ifxundefined \[1\][ ifx[\#1]{} ]{}ifnum \[1\][ \#1firstoftwo secondoftwo ]{}ifx \[1\][ \#1firstoftwo secondoftwo ]{}““\#1””@noop \[0\][secondoftwo]{}sanitize@url \[0\][‘\
12‘\$12 ‘&12‘\#12‘12‘\_12‘%12]{}@startlink\[1\]@endlink\[0\]@bib@innerbibempty

[****, ()](\doibase 10.1103/PhysRevA.55.1613), . (, ). [****,  ()](\doibase 10.1109/TIT.2004.839515), . [****, ()](\doibase 10.1007/s00220-008-0624-0), . [****,  ()](\doibase 10.1038/nphys1224). [****, ()](\doibase 10.1007/s00220-013-1680-7). [****, ()](\doibase 10.1103/PhysRevA.57.830), . [****,  ()](\doibase 10.1126/science.1162242), . [****,  ()](\doibase 10.1103/PhysRevLett.98.030501), .

[****,  ()](\doibase 10.1103/PhysRevLett.78.3217), . [****, ()](\doibase 10.1063/1.2953685), . [****,  ()](\doibase 10.1080/09500340008244047), . , [ ****, ()](doi:10.1038/299802a0).

[****,  ()](\doibase 10.1103/PhysRevLett.80.5239), . [****,  ()](\doibase 10.1.1.37.7699).

[****,  ()](\doibase 10.1109/TIT.2011.2169109), .

, [****,  ()](ttp://dx.doi.org/10.1103/PhysRevLett.107.250504), .

[****,  ()](\doibase 10.1109/TIT.2011.2178157), .

.

[****,  ()](\doibase 10.1103/PhysRevLett.93.010502), . , , , , [ ****, ()](http://dx.doi.org/10.1109/TIT.2008.2009798), .

, , [ ****, ()](\doibase 10.1103/PhysRevLett.89.097905), .

, , , , [ ****, ()](http://link.aps.org/doi/10.1103/PhysRevLett.106.230502), .

[****,  ()](\doibase 10.1103/PhysRevLett.108.040501), .

, [ ****, ()](http://www.sciencemag.org/content/321/5897/1783.short).
