{'fraction_non_alphanumeric': 0.047984927433836734, 'fraction_numerical': 0.015425829432718067, 'mean_word_length': 4.039311674825694, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum decoupling via efficient ‘ classical ’ operations and the entanglement cost of one-shot quantum protocols

We address the question of efficient implementation of quantum protocols, with short depth circuits and small additional resource such as entanglement. We introduce two new methods in this direction. The first method, inspired by the technique of classical correlated sampling, is to unitarily extend a given quantum state into a quantum state uniform in a subspace. The second method involves two new versions of the convex-split lemma that use exponentially small amount of additional resource in comparison to the previous quantum version. Using these methods, we obtain the following results. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Most previous works consider the model where one applies a unitary followed by discarding a quantum system. These works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of sizeO(n log n) and depth poly(logn), or unitary 2 designs based on Clifford circuits of similar size and depth. An equivalent model of decoupling is to apply a unitary followed by discarding a classical system. These two models are related by a Clifford circuit of depth 1. We consider the second model and show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes the basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieve the circuit size of O(n log n) and logarithmic depth. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. The number of qubits of entanglement used in this protocol is proportional to the number of qubits input to the channel. Previous one-shot works were either near-optimal in communication but required exponentially more entanglement, or required small amount of entanglement but did not achieve near-optimal communication. We also achieve similar exponential improvement in the entanglement required for one-shot quantum state redistribution, while keeping the communication similar to the best known achievable communication.


Introduction
Decoupling is a fundamental tool for various protocols in classical and quantum information theory. Broadly, it refers to the process of applying some quantum operation on one of the two given systems (which share quantum correlation), so as to make the two systems independent of each other. This idea has been applied in various tasks such as quantum state merging [1,2,3,4,5,6], quantum state redistribution [7,8,9,10,11], quantum channel coding [12,13,14,15,16], randomness extraction [17,18,19], quantum thermodynamics [20] and black hole physics [21,22]. The central approach in many of these works is to perform a random unitary operation [1,2] and then discard a part of the system. This approach has been expanded upon in various works such as [23,24,25]. Due to the importance of decoupling technique and the limitation that random unitaries cannot be implemented with a short quantum circuit, there is a great interest in finding efficient circuits for the purpose of decoupling. Some techniques involve replacing random unitaries with 2-designs [26,27,28,29] which can be simulated by Clifford circuits of small depth and random quantum circuits of small depth [30].
The classical analogue of decoupling method is the random binning approach of Slepian and Wolf [31], where a random function is applied to a sample from a source, in order to 'concentrate' its information content in as less number of registers as possible. The properties of a random function can also be reproduced by a random permutation of strings (followed by discarding some number of bits), as discussed in details in [24]. The approach of random functions has important applications in the theory of randomness extractor [32,33,34], where the aim is to distill uniform bits from a non-uniform source C. While random functions extract maximum possible number of uniform bits from C, they require a large number of additional seed randomness and are not efficient. A well known solution is to replace random functions with a family of pairwise independent functions [34], which is the classical analogue of the aforementioned unitary 2-designs. More precisely, one chooses positive integers a, b uniformly at random from the set {1, 2, . . . p} (for some integer p which is usually a sufficiently small prime), and applies a function f a,b on the sample c from C to output f a,b (c). Averaged over a and b, this process mimics the action of a random function. For most applications, it suffices to choose f a,b to be a linear function, making its implementation efficient. It has been shown [17,18] that pairwise independent functions also extract randomness if the source C is correlated with a quantum system R, through a classical-quantum state Ψ RC . The number of uniform bits that can be extracted is optimally characterized by the conditional min entropy H min (C|R) Ψ . Further improvements in the seed size have been obtained in [35], based on Trevisan's construction [36].
It is natural to ask how well do random functions/permutations (or their pairwise independent counterparts) behave when applied to a quantum register C having arbitrary quantum correlations with R. This action can be implemented, for example, by choosing a basis (preferably the computational basis on register C) and applying permutations that take basis vectors to basis vectors. One would expect that such 'classical' operations may fail to remove the quantum correlations between registers C and R, owing to the quantum coherence introduced by the off-diagonal terms. Indeed, this limitation is observed in the analysis of decoupling capacity of random permutations [24,Chapter 7], where guarantees on decoupling are obtained only when H min (C|R) Ψ > 0. This can be taken as an indication that fully quantum techniques, such as random unitaries or unitary 2-designs, might be necessary for decoupling an arbitrary quantum state Ψ RC . This is shown not to be true by the method of convex-split [6], which states that adding the quantum state σ C 1 ⊗ . . . σ C N (for some large enough N ) and randomly swapping register C with one of the registers C 1 , . . . C N makes the register R independent of all the other registers. The process of swapping two registers is a 'classical' operation (that is, it takes basis vectors to basis vectors). Unfortunately, the value of N can be as large as O(|C|), and hence swapping register C with a random register C i requires a circuit of depth O(|C|), which is exponential in the number of qubits of register C. Even an alternate implementation of swap operation, by placing the registers on a three dimensional grid, would require O(|C| 1/3 ) operations. Thus, it has so far been unknown if one can achieve quantum decoupling by efficient 'classical' operations.
Recent works have shown several applications of the convex-split method in one-shot quantum information theory, along with the dual method of position-based decoding [37]. The methods have been used to obtain near-optimal communication for one-shot entanglement-assisted quantum channel coding [37], nearoptimal communication for one-shot quantum state splitting [6] (with slight improvement of the additive log log |C| factor over [5], for communicating the register C) and smallest known communication for oneshot quantum state redistribution [11]. As mentioned earlier, all these protocols use a large amount of entanglement. Other known protocols ( [38,15,16] for entanglement-assisted quantum channel coding and [10,9] for quantum state redistribution) that do not rely on these two methods use exponentially small entanglement, but their communication is not known to be near-optimal. Thus, it is an important problem to find a scheme that achieves the best of both of the lines of work.

Our results
Our main result is the introduction of two new techniques to improve the resources such as entanglement and circuit depth in quantum protocols. These technique can be viewed as generic schemes for exponentially improving the resource required in the convex-split and position-based decoding methods. We summarize the results in Figure 1.
Efficient decoupling procedures: The quantity of interest in a decoupling procedure is the number of bits or qubits that are discarded to achieve the decoupling. There are two models under which decoupling is performed. The first model involves adding a quantum state, applying a global unitary (without involving the register R) and then discarding some quantum system. The second model also involves adding a quantum state followed by a unitary, but the system that is discarded is classical and the unitary acts in a classicalquantum manner [39]. The two models can be converted into each other by a Clifford circuit of depth 1 and the number of qubits/bits discarded are the same up to a factor of 2, due to the well known duality between teleportation [40] and super-dense coding [41]. Additional quantum systems that are not discarded act as a catalyst for the decoupling process [5,6,42,43,44]. For example, the randomness used in the process of decoupling via unitary 2-design acts as a catalyst. This randomness can be fixed by standard derandomization arguments, but it leads to a loss in efficient implementation.
In this work, we consider the second model of decoupling. We construct two new convex-split lemmas (Theorems 1 and 2) which immediately lead to efficient decoupling procedures for a quantum state Ψ RC . The second procedure solves the aforementioned problem of decoupling via an efficient classical operation.
• The convex-split lemma introduced in Theorem 1 shows how to achieve decoupling using random mixture of small number of Heisenberg-Weyl (HW) operators, which generalize the Pauli X and Z operators. We can also replace HW operators with tensor products of Pauli X and Z if the register C admits a qubit decomposition. The additional shared randomness used to choose the HW operations is on 4 log |C| bits. The idea for this construction comes from the duality between convex-split and position-based decoding. Rephrasing the entanglement-assisted quantum channel coding result of [38] (and its one-shot analogue from [16]) in terms of position-based decoding, we find that the dual convexsplit result is as given in Theorem 1. The HW operators do not act in a classical manner, as they do not permute basis vectors among themselves.
• The decoupling procedure obtained in Theorem 2 and Corollary 1 is as follows. This procedure enlarges the Hilbert space Upon tracing out register L, register R becomes independent of GG ′ (Theorem 2). Furthermore, the final state on registers GG ′ is maximally mixed and the register G ′ is returned in the original state. As can be seen, the unitaries U ℓ are 'classical' as they take basis vectors to basis vectors and perform addition and multiplication modulo |G|. This makes the construction of U efficient, as discussed in Appendix A. These unitaries have another nice property that they act as a representation of the cyclic group (Lemma 2), reflecting the property of permutation operations in the convex-split method.
• In the language of resource theory of coherence, both the decoupling procedures constructed above belong to the class of Physically Incoherent Operations [46]. Thus, an immediate implication of Theorems 1 and 2 is that quantum decoupling can be performed by incoherent unitaries. The results in Theorems 1 and 2 perform the same as decoupling via random unitary [23,18,25], when we consider the size of discarded system. None of the three methods are optimal as the decoupled register C may not be maximally mixed in a general procedure. Indeed, it is known that the optimum number of discarded qubits for decoupling is characterized by the max-mutual information, rather than the conditional min-entropy [5,6,42]. We discuss this further below.
Exponential improvement in entanglement: A flattening procedure, that extends a quantum state σ C to a quantum state maximally mixed in a subspace (Definition 5), was originally used in the context of classical correlated sampling in several works [47,48,49,50,51,52,53,54]. We observe that this extension can be constructed in a unitary manner using embezzling states [55] (Section 4). This leads to the following consequences.
• We show how to achieve a near-optimal one-shot communication over a quantum channel N A→B with O(log |A|) qubits of pre-shared entanglement (Theorem 7). We also use the protocol in [38] and its one-shot analogue in [16] as a subroutine. This resolves the open question posed in [37].
• In Theorem 4 we give a new protocol for achieving decoupling in terms of the max-mutual information, using O(log |C|) additional qubits. As a consequence, we obtain near-optimal communication cost for quantum state splitting (Corollary 5), with small amount of initial entanglement. This slightly improves upon the communication cost for the same task in [5], with similar amount of initial entanglement.
• We also give various analogues of position-based decoding in Theorems 5 and 6. Along with our convex-split results, this leads to new protocols for quantum state redistribution (Corollary 4). Furthermore, it exponentially improves upon the entanglement required in the protocol for quantum state redistribution in [11], without changing the communication cost.
A new property of the embezzling procedure that we use is that the state after the embezzlement is close to the desired state in max-relative entropy (which is stronger than closeness in fidelity, see Claims 1 and 2). This is crucial to all of our applications. A different method of using embezzling states to flatten a quantum state was given in [5]  Decoupling up to "I max (R : C)"

Preliminaries
All the logarithms are evaluated to the base 2. Consider a finite dimensional Hilbert space H endowed with an inner product ·, · (In this paper, we only consider finite dimensional Hilbert-spaces). The ℓ 1 norm of an operator X on H is X 1 := Tr √ X † X and ℓ 2 norm is X 2 := √ TrXX † . A quantum state (or a density matrix or a state) is a positive semi-definite matrix on H with trace equal to 1. It is called pure if and only if its rank is 1. A sub-normalized state is a positive semi-definite matrix on H with trace less than or equal to 1. Let |ψ be a unit vector on H, that is ψ, ψ = 1. With some abuse of notation, we use ψ to represent the state and also the density matrix |ψ ψ|, associated with |ψ . Given a quantum state ρ on H, support of ρ, called supp(ρ) is the subspace of H spanned by all eigenvectors of ρ with non-zero eigenvalues.
A quantum register A is associated with some Hilbert space H A . Define are associated with the same Hilbert space, we shall represent the relation by A ≡ B. Composition of two registers A and B, denoted AB, is associated with Hilbert space H A ⊗H B . For two quantum states ρ ∈ D(A) and σ ∈ D(B), ρ ⊗ σ ∈ D(AB) represents the tensor product (Kronecker product) of ρ and σ. The identity operator on H A (and associated register A) is denoted I A . The maximally mixed state I A |A| on register A is represented by µ A .
Let ρ AB ∈ D(AB). We define where {|i } i is an orthonormal basis for the Hilbert space H A . The state ρ B ∈ D(B) is referred to as the marginal state of ρ AB . Unless otherwise stated, a missing register from subscript in a state will represent partial trace over that register. Given a ρ A ∈ D(A), a purification of ρ A is a pure state ρ AB ∈ D(AB) such that The set of all unitary operations on register A is denoted by U (A). Some standard unitaries are the X, Z, H (Pauli-X, Pauli-Z and Hadamard, respectively) gates on qubits, the CNOT gate on a pair of qubits and the Toffoli gate on three qubits [56]. We will drop the register labels on unitaries unless when it is required. We shall consider the following information theoretic quantities. We consider only normalized states in the definitions below. Let ε ∈ (0, 1).
We will use the following facts.
Following fact implies the Pinsker's inequality.
Fact 5 (Lemma 5 [70]). For quantum states ρ A , σ A ∈ D(A), Fact 6. Fix a γ ∈ (0, 1) and a quantum state ω C . It holds that • there exists a quantum state σ C such that ω C 1 1−γ σ C and the eigenvalues of σ C are integer multiples of γ |C| .
• there exists a quantum state σ C such that σ C 1 1−γ ω C and the eigenvalues of σ C are integer multiples of γ |C| .
Proof. We prove each item as follows. Let η be chosen below.
• Given the quantum state ω C , we construct an operator O by increasing each eigenvalue of ω C to the nearest multiple of η |C| , and define σ C • This follows in a similar manner. We construct an operator O by decreasing each eigenvalue of ω C to the nearest multiple of η |C| , and define σ C This completes the proof.
Fact 13. Let ε ∈ (0, 1) and ρ AB be a quantum state. It holds that Proof. From [71, Fact 12] (a corollary of an argument in [64]), for every quantum state σ A , it holds that Minimizing over all σ A , we have The proof now concludes by the definition of H ε min (B|A) ρ .

Fact 14.
It holds that for 0 < a < C, Since e 2πia C = 1 for 0 < a < C, the proof concludes.

Convex-split with improved resources: basic constructions
We begin this section by providing a construction of convex-split of a quantum state that uses small amount of additional randomness.
3.1 Convex-split using a mixture of HW operators Definition 1. Given a register C and a basis {|c } Following is a well known lemma.
In particular, this implies that for any state ρ RC , In the second equation, we have used Fact 14.
Above, δ z,z ′ is the delta function. This completes the proof.
For the ease of notation, we represent (a, b) as x and let X be the set of all x.
j=1 be a family of pairwise independent functions. That is, As discussed in [72,Example 6] or [73], there exists an efficient construction of pairwise independent function family for any X with |X | a prime power. In our setting, |X | = |C| 2 . Hence, such a construction exists whenever log |C| is an integer. The following theorem ensures that convex-split can be achieved with small amount of additional resource.
It holds that Proof. We now proceed to the desired inequality. Observe that V ( (j)) acts controlled on registers X 1 , X 2 . Thus, Thus, where we have used the convexity of relative entropy. From the pairwise independent property of the family of functions, this simplifies to Lemma 1 ensures that Using the inequality Ψ RC 2 k Ψ R ⊗ µ C and the operator monotonicity of logarithm [74], we conclude that This completes the proof.
Above construction uses HW unitaries which also involve a phase. Hence, these unitaries are not classical. Below, we provide a construction that is completely classical, that is, it permutes basis vectors to basis vectors.

Convex-split with classical unitaries
Fix a register C. Let Q be a register with |Q| = 2. We denote by G a register such that |G| ≥ |C| 2 is a prime and H G is a subspace of H Q ⊗ H C ⊗ H C . This choice of G can be made due to Bertrand's postulate [45]. on H G as follows. We relabel the vector |0 |c, c ′ as |c|C| + c ′ . This gives |C| 2 basis vectors for G. The remaining |G| − |C| 2 basis vectors are constructed by relabeling |1 |c, c ′ as ||C| 2 + c|C| + c ′ as long as |C| 2 + c|C| + c ′ ≤ |G| − 1. We note that the constraint |C| 2 + c|C| + c ′ ≤ |G| − 1 is automatically satisfied in our analysis below, as all the additions, subtractions and multiplications appearing below are performed modulo |G|, unless explicitly stated. Now, introduce registers C 0 , C 1 ≡ C and G 1 , We choose the convention that the expression in the kets for registers G 1 , G 2 are evaluated modulo |G|.
Proof. We first show that U ℓ is a unitary. Let i, i ′ , j, j ′ be such that This can be rearranged to obtain Multiplying the first equation by ℓ, the second by (1 − ℓ) and adding, we obtain j − j ′ = 0. Thus, This completes the proof.
Following is an important property of our collection of unitaries and is analogous to Lemma 1.
where we use the fact that H G 1 ⊆ H Q ⊗ H C 0 ⊗ H C 1 to change the register label.
where we have used the fact that for 0 < m < |G| and |G| prime, the quantity jm + i(1 − m) takes all possible values in {0, 1, . . . |G| − 1} as j varies in {0, 1, . . . |G| − 1}. For this, observe that for two j, j ′ , R . For any m > 0, using Equation 2, we have where we have used that fact that c|C| + c 1 = c ′ |C| + c 1 ⇐⇒ c = c ′ . This completes the proof. Now, we are in a position to prove our main result.

It holds that
From Fact 5, we conclude that Using Fact 9, we have Since µ G 1 ⊗ µ G 2 is maximally mixed in the support of U ℓ , Moreover, from Lemma 2 we have where in last operator inequality, we have used Equation 3. Using Lemma 3, we conclude that Since logarithm is operator monotone [74],

From Equations 4 and 5,
This completes the proof.
An immediate corollary is the smooth version of above result.

It holds that
Proof. From Fact 13, we conclude that Let Ψ ′ RC be the quantum state achieving the infimum above. Define We use Theorem 2 to conclude that By triangle inequality for purified distance, this implies that This concludes the proof.

Decoupling up to the max-mutual information using a flattening procedure
We introduce a close variant of the embezzling state [55]. We have the following claim, which is a variant of the property of embezzling states proved in [55].
Claim 1. Let δ ∈ (0, 1 15 ) and a, b, n be integers such that n ≥ a 1 δ , a ≥ 2 and a ≥ b. Fix registers D, E satisfying |D| ≥ n and |E| ≥ b. Let W b be the unitary that acts as

It holds that
|e e| E .
Following claim shows how to 'unembezzle' a state.
Claim 2. Fix the integers n, b, a as given in Claim 1. Let the register D satisfy n 2 ≥ |D| ≥ (n + 1)b. Let W b be as defined in Claim 1. It holds that Proof. We observe that W † b |j D |e E = |jb + e D |0 E for all j ≤ n and e < b. We leave the action of W † b unspecified for j ≥ n, e ≥ b. Consider where in the last operator inequality, we use the fact that |D| ≤ n 2 . This completes the proof.
A 'purified version' of above claims is the following restatement of the result in [55].
Proof. We have Since where we use the fact that |S(a, n) − log n a | ≤ 4. This completes the proof.
We now introduce the following definition, which shows how to extend a suitable quantum state to make it uniform in a subspace.
Definition 5. Flattening a quantum state: Fix a γ ∈ (0, 1) such that |C| γ is an integer and a quantum state σ C def = c q(c)|c c| C with eigenvalues q(c) that are integer multiples of γ |C| . For a register E satisfying |E| = |C| γ max c q(c), define the quantum state σ CE as follows: Observe that σ CE is uniform in its support.
The flattening of σ C can be realized in a unitary manner as follows. We define some registers and unitaries required for this process. Flattening is ensured via the following relation, which uses Claim 1.
(6) Given the flattening of a quantum state σ C , Definition 1 gives us |supp(σ CE ) is a prime power, Definition 2 gives us the collection of unitaries . This allows us to construct the quantum states Now we prove the following theorem, which is the analogue of Theorem 1 for a flattened quantum state.
Proof. From Fact 6, we have that the eigenvalues of σ C are integer multiples of γ |C| and Consider, where (a) uses Equation 6.
The equality (a) uses Lemma 1. The operator inequality (b) uses the fact that S(1,n) S(a,n) ≤ (1 + 15δ), as given in Claim 1. The rest of the argument is identical to Theorem 1, up to the factor of (1 + 15δ) induced by above operator inequality. This completes the proof.
For later application, we also state a smooth version of Theorem 3, which is similar to Corollary 1.
In a similar manner, we obtain an improved version of Theorem 2. We first construct the desired states to be used in the statement of the Theorem. For the flattening of a quantum state σ C as given in Definition 5, let H ′ CE def = supp(σ CE ) ⊂ H C ⊗ H E denote the support of σ CE . Introduce registers C 0 E 0 ≡ CE and C 1 E 1 ≡ CE. Let Q be a register such that |Q| = 2. Let F be a register such that |F | is a prime, This choice of F is guaranteed by Bertrand's postulate [45]. Introduce register We identify the pair (c, e) with an element in {0, 1, . . . |C| γ − 1} through some one to one mapping and let {U ℓ } |F |−1 ℓ=0 be the unitaries constructed in Definition 3, by setting C ← supp(σ CE ). Observe that U ℓ : H F 1 ⊗H F 2 → H F 1 ⊗H F 2 are 'classical' as long as choice of the preferred basis on H C is the eigenbasis of σ C . Define the quantum states where W is as given in Definition 6 and |D| ≥ n. We have the following theorem, proof of which is given in Appendix B.
Theorem 4. Fix ε, γ ∈ (0, 1), δ ∈ (0, 1 15 ) such that |C| γ is an integer and quantum states Ψ RC , ω C . Let k Let σ C be the quantum state as constructed in the first part of Fact 6 using ω C . For the quantum states τ ℓ as constructed in Equation 9, define
We state a smooth version of Theorem 4 which will be used later.
Corollary 3. Fix ε, γ ∈ (0, 1), δ ∈ (0, 1 15 ) such that |C| γ is an integer and a quantum state . Let σ C be the quantum state as constructed in the first part of Fact 6 using Ψ C . For the quantum states τ ℓ as constructed in Equation 9, define

Analogues of position-based decoding
We now show how to perform hypothesis testing as a dual to Theorem 2, in analogy with position-based decoding [37]. We note that similar construction can achieve a dual to Theorem 1, but we do not state it here as it will be constructed in details in Theorem 7. We have the following theorem.
Theorem 5. Let ε ∈ (0, 1) and Ψ BC be a quantum state. Let S ⊆ {0, 1, . . . |G| − 1} such that For each ℓ ∈ S, let τ ℓ be the quantum state defined in Theorem 2 with Ψ RC ← Ψ BC . There exists an POVM Proof. Let Ω BC be the operator such that We have Let {Λ −1 , Λ ℓ } ℓ∈S be the POVM as constructed in Fact 10 using the operators U ℓ Ω BC 0 U † ℓ . We have Tr Tr Above, (a) uses Fact 10. From Lemma 3, Thus choosing c = δ ε and using Equation 10, from the choice of |S|. This completes the proof.
Along the lines similar to Theorem 5, we have the following theorem for position-based decoding. We will directly use the registers and unitaries as introduced in Theorem 4. Theorem 6. Let ε ∈ (0, 1), δ ∈ (0, 1 15 ) and Ψ BC , ω C be quantum states.
Let σ C be the quantum state as constructed in the second part of Fact 6 using ω C . Let τ ℓ be the quantum states as defined in Equation 9, using the quantum states Ψ RC ← Ψ BC , σ CE and by choosing |D| ≤ 2n · |E| ≤ 2|E| 1+ 1 δ . There exists a collection of POVM {Λ −1 , Λ ℓ } ℓ∈S such that Proof. We will outline the main steps of the proof, which closely follow those of Theorem 5. Let Ω BC be the operator that satisfies From Fact 6, we have Let {Λ −1 , Λ ℓ } ℓ∈S be the POVM constructed in Fact 10 using the operators Rest of the calculation follows using Fact 10. The following claim is similar to Lemma 3 and is proved in Appendix C.
We require the following inequality for m, ℓ ∈ S with m = ℓ.
Above, (a) follows from Claim 4. Now, we use the fact that Thus, Finally, we use Claim 2 to conclude that where we use the fact that Ω BC only acts in the support of Ψ R ⊗ σ C 0 . This completes the proof.

Entanglement-assisted quantum channel coding
We show how exponential improvement in entanglement can be obtained for entanglement-assisted quantum channel coding, in comparison to the entanglement required in [37]. We begin by defining an entanglementassisted code. We have the following theorem, near-optimality of which is shown by the converse given in [76]. For the ease of presentation, we will represent the relation P(|ψ ψ|, |φ ) ≤ ε between two pure states |ψ , |φ as |ψ ε ≈ |φ .
. For any pure quantum state |Ψ AC and there exists a (R, ε + 4γ 1/4 + δ ′ + 20 √ δ) entanglement-assisted code for a quantum channel N A→B . The protocol uses 1 δ log |A| γ·δ qubits of shared entanglement and 4 log |A| bits of shared randomness. The latter can be fixed by standard derandomization argument.
Proof. Without loss of generality, we can assume that |Ψ AC is the canonical purification of Ψ A , by applying a local unitary on register C which does not change the hypothesis testing relative entropy. Let Ψ BC def = N A→B (Ψ AC ). From Fact 6, there exists a quantum state σ C such that the eigenvalues of σ C are integer multiples of γ |C| and σ C 1 Let |σ AC be the canonical purification of σ C and σ BC def = N A→B (σ AC ). Using Fact 8, and using Fact 2, Let Ω BC be the optimum operator in the definition of D ε H (Ψ BC Ψ B ⊗ Ψ C ). From Fact 7 (11) We expand |σ AC = c q(c)|c A |c C . Let E be the register and σ CE be the quantum state as obtained in Definition 5. It holds that |E| ≤ |A| γ . Consider the following purification of σ CE , which is maximally entangled.
Since V x acts in supp(σ CE ), Fact 11 ensures that there exists a unitary V T By triangle inequality for purified distance (Fact 1), these equations lead to Introduce registers X 1 , is a prime power, Definition 2 gives a family of functions {f m : X × X → X } and a collection of unitaries . Shared resources: Alice and Bob share the state |σ AC |ξ a:n D ′ D |0, 0 E ′ E . They also possess µ X 1 X 2 in shared registers X 1 X 2 . Thus, the number of qubits of shared entanglement is Encoding: To send the message m ∈ {1, 2, . . . 2 R }, Alice applies the unitary on her registers. She then sends the register A through the channel.
Error analysis: Let θ ′ m be the quantum state on Bob's registers just after Alice's transmission through the channel. Define the following quantum state: From Equation 12, we have P(θ m , θ ′ m ) ≤ 10 √ δ. Thus, from Fact 7, Applying Fact 10, we conclude Since

from Equation 11, we have
Tr For m ′ = m, consider Thus, where (a) uses the fact that Setting c = δ ′ ε+4γ 1/4 and from the choice of R, the proof concludes.

Consequences for quantum state merging and quantum state redistribution
Combining Corollary 3 (which is a smooth version of Theorem 4; alternatively we could use Corollary 2) and Theorem 6, we exponentially improve upon the entanglement cost of the protocol for quantum state redistribution given in [11]. Since the proof is similar to that given in [11], we give the statement of the result.
Corollary 4. Fix ε ∈ (0, 1), δ ∈ (0, 1 15 ) and a pure quantum state |Ψ RABC . There exists an entanglementassisted one-way protocol in which Alice (AC), Bob (B) and Reference (R) start with the quantum state |Ψ RABC and Alice communicates a message to Bob such that the final state Φ RABC between Alice (A), Bob (BC) and Reference (R) satisfies Φ RABC ∈ B 4ε+65δ (Ψ RABC ). Reference plays no role in the protocol. The number of qubits of shared entanglement required is at most 4 + 1 δ log |C| δ and the number of qubits communicated is By the argument in [6] that shows how a convex-split for Ψ RC can be used to obtain a protocol for the task of quantum state splitting, we obtain the following corollary using Theorem 4. Corollary 5. Fix ε, δ ∈ (0, 1 15 ) and a pure quantum state |Ψ RAC . There exists an entanglement-assisted one-way protocol in which Alice (AC) and Reference (R) start with the quantum state |Ψ RAC and Alice communicates a message to Bob such that the final state Φ RAC between Alice (A), Bob (C) and Reference (R) satisfies Φ RAC ∈ B 2ε+8 √ δ (Ψ RABC ). Reference plays no role in the protocol. The number of qubits communicated is 1 2 I ε max (R : C) Ψ + 2 + 2 log 1 δ .
The number of qubits of entanglement required is at most 4 + 1 δ log |C| δ .
Thus, the result improves upon the number of qubits communicated in [5] by an additive factor of log log |C| and at the same time achieves the number of qubits of entanglement required. It achieves the same communication as given in [6], but exponentially improves upon the number of qubits of entanglement.

Conclusion
In this work, we have studied the problem of decoupling quantum registers by means of efficient operations and reduction in the resource required in the applications of convex-split and position-based decoding. We have given an efficient operation that achieves the task and acts 'classically' on a preferred basis. Along with our second method, we exponentially improve the amount of entanglement required in the quantum communication protocols based on the convex-split and position-based decoding methods.
An important question is to see if the number of bits of additional randomness used in our decoupling protocol can further be reduced. It is known that seed size in randomness extraction in presence of quantum side information can be very small [35] (based on Trevisan's construction [36]). Since our construction treats classical side information and quantum side information in similar manner, we can hope to have similar results even in the case of quantum decoupling. Similarly, we would like to understand if the amount of entanglement can further be reduced in our applications to quantum communication tasks.
Using Claim 4 and Fact 9, we proceed similar to Theorem 2.
This completes the proof.

C Proof of Claim 4
Proof. We expand Ψ RC 0 = c,c ′ Ψ (c,c ′ ) R ⊗ |c c ′ | C 0 . For convenience, set b(c) = q(c)|C|/γ. Recall that Thus, As shown in Lemma 3, Hence, we conclude that where in the last operator inequality, we have used an argument similar to that used in Claim 1. Thus, This completes the proof.