Complementarity of Private and Correctable Subsystems in Quantum Cryptography and Error Correction

We make an explicit connection between fundamental notions in quantum cryptography and quantum error correction. Error-correcting subsystems (and subspaces) for quantum channels are the key vehicles for contending with noise in physical implementations of quantum information-processing. Private subsystems (and subspaces) for quantum channels play a central role in cryptographic schemes such as quantum secret sharing and private quantum communication. We show that a subsystem is private for a channel precisely when it is correctable for a complementary channel. This result is shown to hold even for approximate notions of private and correctable defined in terms of the diamond norm for superoperators.

In operator quantum error correction, a correctable subsystem for a noise map is one upon which the action of the noise can be corrected [1,2]. Equivalently, it is one that merely suffers a unitary change of representation and therefore does not decohere at all [3,4]. A private subsystem is the extreme opposite: it is one that completely decoheres under the action of the noise in the sense that no information about the state of the subsystem remains at the output of the map [5]. This concept is very useful in quantum cryptography. For instance, it finds application in the context of private quantum communication schemes. If Alice encodes quantum information using a secret key that she shares with Bob, then Eve's ignorance of this key can be modelled as a noisy channel. As an example, suppose Alice and Bob share a secret classical key in the form of a random variable X with distribution p which they use to select a unitary from a set {U x } to implement on a system prior to transmitting it. Then Eve's description of the system is E(ρ) = x p(x)U x ρU † x . The private subsystems of this channel are precisely the subsystems about which Eve obtains no information [5,6,7]. Another cryptographic application is quantum secret sharing [8,9]. Suppose a system is mapped by a channel C to n systems, distributed among n parties. How can one encode quantum information into this system in such a way that any set of parties with less than k members can learn nothing about it? The answer is that it must be encoded into subsystems that are private for the reduction of C to any k − 1 or fewer parties.
Finding the private subsystems for an arbitrary map is therefore a problem with significant applications in quantum cryptography.
It is in fact the counter-part of one of the central problems in quantum error correction -finding the correctable subsystems for an arbitrary noise map. This problem, which encompasses that of finding the error-correcting subspace codes [10,11,12,13,14] and the decoherence-free subspaces and noiseless subsystems [15,16,17,18,19,20,21], has been the subject of intensive investigations of late [3,4,22,23,24,25,26,27,28,29]. On the other hand, almost no work has been done on the private subsystem problem. At first glance then, one might expect the road to progress to be a long one. However, the duality of the two problems provides a shortcut. Indeed, a central result of our paper is that the private subsystems for a map are simply the correctable subsystems for a complementary map, where the notion of complementarity of maps is the one introduced in [30]. Because it is straightforward to obtain the complements of a map, it follows that all the techniques and progress on finding correctable subsystems can be immediately appropriated for the problem of finding private subsystems.
The implication also holds in the opposite direction: the correctable subsystems for a map are the private subsystems for a complementary map. Consequently, results from the field of cryptography may also provide novel insights for error correction.
This duality between private and correctable in the case of subspaces has already been used implicitly in previous work, such as [8,31], where results from error correction are exploited to derive conclusions for cryptography. Our result is therefore likely to be intuitive to most quantum information theorists. Nonetheless, it is a surprisingly powerful tool. Indeed, many well-known results in quantum information (and generalizations thereof) can be derived as simple consequences of it.
In real-world applications, demanding perfect recovery or complete decoherence of quantum information is too restrictive. We therefore also consider approximate notions of error correction and privacy, defined in terms of the diamond norm for superoperators [32,33], which can be computed algorithmically [34]. We demonstrate that if a subsystem is approximately correctable (respectively private) for a map then it is approximately private (respectively correctable) for a complementary map. While an approximate version of the ideal result is not unexpected, it is still surprising that simple dimensionindependent bounds can be derived. To accomplish this, we make use of recently developed techniques from [35]. We now describe preliminary notation and nomenclature. Given a quantum system S represented on a (finitedimensional) Hilbert space, also denoted by S, we say a quantum system B is a subsystem of S if there is a representation of B such that S = (A⊗B)⊕(A⊗B) ⊥ , where A is also a subsystem of S. The subspaces of S can be identified with subsystems B for which A is one-dimensional. We adopt the convention that A, B are subsystems of S, and A ′ , B ′ are subsystems of S ′ . We also adopt the convention that ρ denotes a density operator, and σ, τ denote arbitrary operators. A subscript such as σ B refers to the subsystem on which the operator is defined. The set of linear operators on S is denoted by L(S).
Linear maps on L(S), or "superoperators", can be regarded as operators acting on the space L(S) with the Hilbert-Schmidt inner product (σ, τ ) = tr(σ † τ ). We use the term channel to mean a trace-preserving completely positive linear map E : L(S) → L(S ′ ) between Hilbert spaces S and S ′ . Such maps describe (discrete) time evolution of open quantum systems in the Schrödinger picture. The composition of two maps will be denoted by where id is the identity map, and is implemented by a unitary operator U via U(σ) = U σU † . An isometric channel V satisfies only V † • V = id and is implemented by an isometry V via V(σ) = V σV † . Let P AB be the map defined by P AB (σ) = P AB σP AB where P AB is the projector onto the subspace A ⊗ B, and let id B be the identity map on L(B). If we are given maps E A , E B on the subsystems, as a notational convenience we write E A ⊗ E B both for the map on L(A ⊗ B) and for the natural extension of the map to L(S). Finally, the input and output spaces of operators and superoperators will often be denoted by whether they appear on the right or left of a conditional in the subscript, e.g., The absence of a conditional implies equality of input and output spaces, e.g.
The norm distance · ⋄ that we use to quantify the approximate cases of the main result is the diamond norm for superoperators, originally introduced in the context of quantum computing and error correction [32,33]. It is defined by E − F ♦ := sup k≥1 id k ⊗ (E − F) 1 where id k denotes the identity operation on the complex-valued (k × k) matrices, and · 1 denotes the superoperator 1-norm E 1 := sup σ 1 ≤1 E(σ) 1 where σ 1 = tr|σ|. The diamond norm stabilizes in the sense that this supremum is attained for k equal to the dimension of the output Hilbert space for the superoperator. (In fact, it is the dual of the completely bounded norm, [36].) Channels E and F are said to be ǫ-close if E − F ♦ ≤ ǫ. If two channels are ǫ-close, then the maximum probability of distinguishing the output states of the channels, in an optimization over all input states entangled with an ancilla of arbitrary dimension, is 1/2 + ǫ/4. This follows from the fact that 1 2 We introduce the term deletion channel for a channel that has a 1-dimensional output space, that is, for all Note that the completely depolarizing channel is a special case of a deletion channel where ω B ′ ∝ I B ′ . A pure deletion channel is one for which ω B ′ is a pure state. The trace is a special case of a pure deletion channel.
We now define what we mean by private and correctable subsystems.
Definition 1 Given ǫ ≥ 0, we say B is an ǫ-private subsystem for E S ′ |S if there is a channel M A ′ |A and a deletion channel D B ′ |B such that If Eq. (1) holds with ǫ = 0, we call B a private subsystem.
This can be seen as an improved definition of ǫ-private relative to the one presented in [7], because it guarantees privacy even if the eavesdropper holds a purification of the state. The term "completely" private was used in [5] to describe private subsystems, but we drop this term here for succinctness. In the ǫ = 0 case for which B is a subspace, and so dim A = 1, this notion coincides with the private quantum channel [6] and private subspace [5,7]. Note that if the definition is satisfied for M A ′ |A and D B ′ |B where the latter is a deletion channel that maps all states on B to a mixed state ω B ′ , then we can always define M ′ S ′ |A = M A ′ |A ⊗ ω B ′ and a pure deletion channel D C|B = tr B such that the definition is satisfied. Consequently, the definition of a private subsystem could equally well specify that E • P AB be ǫ-close to a channel of the form M ′ S ′ |A ⊗ tr B . The use of diamond norms in quantum computing motivates the following definition for approximately correctable codes. The ǫ = 0 case was introduced in [1, 2]. Definition 2 Given ǫ ≥ 0, we say B is an ǫ-correctable subsystem for E S ′ |S if there is a channel R S|S ′ and a channel N A such that where id B is the identity channel on B. If Eq. (2) holds with ǫ = 0, we say that B is a correctable subsystem.
Finally, we define the notion of a complementary pair of channels, which has arisen recently in the analysis of channel capacity problems [30,37,38] and a continuity theorem for the Stinespring dilation [35,39].
Definition 3 Let E S ′ |S and E ♯ S ′′ |S be channels on a system S with output spaces S ′ and S ′′ respectively. Then we say E, E ♯ form a complementary pair if there is an isometric channel V S ′ S ′′ |S such that The Hilbert space S ′′ (respectively S ′ ) is a dilation space for E (respectively E ♯ ), and V S ′ S ′′ |S is an isometric dilation of both. Complementary pairs arise frequently in quantum information theory. As a consequence of the Stinespring Dilation Theorem [40], every channel may be seen to arise from an environment Hilbert space E (of dimension at most the product of the input and output Hilbert space dimensions if the dilation is minimal), a pure state |ψ on the environment, and a unitary operator U on the composite SE in the following sense: E(σ) = tr E U(σ ⊗ |ψ ψ|) . Tracing out the system instead yields a complementary channel: E ♯ (σ) = tr S U(σ ⊗ |ψ ψ|) .
The corresponding isometric form is E ♯ (σ) = tr S V(σ) , where V is implemented by the isometry V |φ = U |φ |ψ . A simple example is useful in illustrating the concept.

Lemma 4
The identity channel and the trace channel form a complementary pair.
The proof is straightforward. A dilation space for id S need only be one-dimensional, E = C, and an isometric dilation V may be chosen to be simply multiplication by a phase factor. The complement defined by this dilation is simply tr S . We now state our main result.
Theorem 5 Let E and E ♯ be complementary channels. If a subsystem B is ǫ-correctable (respectively ǫ-private) for E, then it is 2 √ ǫ-private (respectively 2 √ ǫ-correctable) for E ♯ . The ideal result, obtained by setting ǫ = 0 implies that B is a correctable subsystem for E if and only if B is a private subsystem for E ♯ .
The key technical device in the proof is the continuity theorem of [35], which we state for completeness. Theorem 6 Let E, E ′ : L(X) → L(Y ) be arbitrary quantum channels, and let V and V ′ be two corresponding isometric dilations with a common dilation space Z. Then where the minimum is taken over all unitary U on Z.
We note that the continuity theorem has recently been extended to completely positive maps between arbitrary C * -algebras [39]. This should allow for the extension of the complementarity theorem from finite-dimensional matrix algebras to infinite-dimensional ones. Proof of Theorem 5: It suffices to prove the result in the case S = A ⊗ B. The general case can then be obtained by considering the restricted channels E • P AB and E ♯ • P AB (which are complementary). Let V E : S → S ′ ⊗ S ′′ be the dilation isometry for E and E ♯ . First, suppose B is ǫ-private for E in the sense of Def. 1. It is then ǫ-close to a channel F := M S ′ |A ⊗ tr B . By possibly enlarging the dilation spaces of E and F , we may always assume without loss of generality that these spaces are isomorphic to one another and satisfy the dimension bounds of Theorem 6. Eq. (5) then guarantees the existence of a unitary U R on the common dilation space S ′′ such that Define F ♯ := tr S ′ • V F . By Eq. (4), we infer that Define A ′′ by S ′′ = A ′′ ⊗ B. Note that by Lemma 4,  7), noting that the diamond norm is nonincreasing under partial trace, and using Eq. (6), we obtain which implies that B is 2 √ ǫ-correctable for E ♯ . Suppose now that B is ǫ-correctable for E in the sense of Def. 2, so that there exists a channel R such that R • E is ǫ-close to a channel G := N A ⊗ id B . Again, we may assume that the dilation spaces of R • E and G are isomorphic and satisfy the dimension bounds of Theorem 6. If we denote the dilation spaces of E and R by S ′′ and S 0 respectively, then the common dilation space of R • E and G is S 0 ⊗ S ′′ . Letting V E , V R and V G denote the isometric dilations of E, R and G, we infer from Eq. (5) that there exists a unitary U on S 0 ⊗ S ′′ such that By Lemma 4, we have S0S ′′ |A , and take the trace over S 0 on the left-hand side of Eq. (10) (noting that the diamond norm is nonincreasing under partial trace), we find Hence, B is 2 √ ǫ-private for E ♯ , as claimed.
FIG. 2: Channels involved in the inference from correctable to private in Theorem 5.
Quantum secret sharing provides a nice example of the utility of the complementarity theorem. A ((k, n)) threshold scheme for quantum secret sharing is a protocol that encodes the quantum state of a system S (the quantum secret) into n systems, one held by each party, such that k parties or more can recover the secret, while k − 1 or fewer cannot gain any information about it [8].
Our result demonstrates that one can achieve a scheme that approximates the ideal functionality as follows: the reduction of the encoding map to any k or more parties is ǫ-correctable while to any k − 1 or fewer parties it is 2 √ ǫ-private. As long as the encoding map is an isometry, then by our theorem and the definition of complementary maps, if the input space is ǫ-correctible for the reduction of the encoding map to any k or more parties, then it is 2 √ ǫ-private for the reduction to any n − k or fewer parties. Therefore, as long as k −1 = n−k, or n = 2k −1, we obtain the desired approximation to ideal functionality. This is the generalization of Corollary 9 of [8]. Furthermore, every nonisometric encoding among n parties can be understood as some isometric encoding among n ′ > n parties where the extra n ′ −n shares are discarded. Given that n ′ = 2k − 1, we infer that n < 2k − 1. Therefore, the approximation to ideal functionality described above is impossible if n ≥ 2k. This is the generalization of Theorem 2 of [8].
Our result also finds a simple application in the standard paradigm of quantum communication where it is presumed that any dilation space for the channel E linking Alice to Bob ends up in the hands of an adversary. The theorem then implies that any subsystem that is ǫcorrectable for Bob is 2 √ ǫ-private for the adversary.