{'fraction_non_alphanumeric': 0.053517034537700924, 'fraction_numerical': 0.007123107924457566, 'mean_word_length': 4.067679886012823, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum Data Compression and Relative Entropy Revisited

B. Schumacher and M. Westmoreland have established a quantum analog of a well-known classical information theory result on a role of relative entropy as a measure of non-optimality in (classical) data compression. In this paper, we provide an alternative, simple and constructive proof of this result by constructing quantum compression codes (schemes) from classical data compression codes. Moreover, as the quantum data compression/coding task can be effectively reduced to a (quasi-)classical one, we show that relevant results from classical information theory and data compression become applicable and therefore can be extended to the quantum domain.


I. INTRODUCTION
Quantum relative entropy, defined as S(ρ||σ) tr(ρ log ρ) − tr(ρ log σ), is always non-negative and is equal to zero if and only if ρ = σ, where ρ and σ are density operators defined on the same finite-dimensional Hilbert space. For a review of the properties of quantum relative entropy as well as the properties of quantum (von Neumann) entropy, defined as S(ρ) = tr(ρ log ρ), see, for instance, [10].
Both quantum (von Neumann) entropy and quantum relative entropy can be viewed as quantum extensions of their respective classical counter-parts and inherit many of their properties and applications. Such inheritance however is often neither automatic, nor obvious. For example, classical information theory [4,Chap. 5] provides the following natural interpretations of Shannon entropy and relative entropy. A compression code (scheme), for example, Huffman code, which is made optimal for an information source with a given probability distribution p of characters, would require H(p) bits per input letter to encode a sequence emitted by the source, where H(p) stands for the Shannon entropy of the probability distribution p and is defined by Thus, if using a compression code 1 (scheme) made optimal for an information source with probability distribution q, also called as "q-source", one could compress such a source with H(q) bits per input character. If, to compress the same q-source, one uses a different compression code (scheme) optimal for a source with a different probability distribution p (i.e. p-source), it will require H(q) + D(q||p) bits per input character, where D(q||p) stands for the relative entropy function for the probability distribution q and p and is defined by Accordingly, the quantity D(q||p) represents an additional encoding cost which arises from encoding a q-source with a code optimal for a p-source. This (classical) data compression interpretation of (classical) Shannon and relative entropies extends [8,9] to the quantum domain if one replaces classical information sources having probability distributions p and q with quantum information sources having density matrices ρ and σ, respectively, as well as (classical) Shannon and relative entropies with (quantum) von Neumann and relative entropies, respectively. In this paper, we provide an alternative, simple and constructive proof of this result. We build quantum compression codes (schemes) from classical compression codes. As the original source density matrix ρ can simply be replaced withρ, a so-called "effective" source matrix [5] with respect to our computational basis, our quantum compression/coding task is effectively reduced to a (quasi-)classical one, with classical information sources having probability distributions pρ and p σ , which are formed by the eigenvalues ofρ and σ, respectively. Thus, relevant results from classical information theory and data compression become applicable and therefore can be extended to the quantum domain.
Our paper is organized as follows. In Section II, we briefly review some classical data compression definitions and results, including information sources and source codes (also known as "data compression codes"). In Section III, we introduce quantum information sources, quantum data compression and discuss how classical data compression codes can be "turned" into quantum data compression codes. In Section IV, we introduce an "effective" density matrix for a quantum information source. In Section V, we state our main results: Lemma V.1 and Theorem 3 followed by a discussion. We conclude the paper with a brief conclusion section.

II. CLASSICAL DATA COMPRESSION
A. Classical Information Sources, Compression Codes, and Optimal Data Compression Let A = a 1 , a 2 , . . . , a |A| be a data sequence alphabet, where the notation |A| stands for the cardinality of A. Binary alphabet {0, 1} and Latin alphabet {a, b, c, d, . . . , x, y, z} are widely-used alphabet examples. We will also use the notation |sequence name| to denote the sequence length. Let A * , A + , and A ∞ be respectively the set of all finite sequences, including the empty sequence, the set of all finite sequences of positive length, and the set of all infinite sequences, where all the sequences are drawn from A. For any positive integer n, A n denotes the set of all sequences of length n from A. A sequence from A is sometimes called an A-sequence. To save space, we denote an A-sequence x 1 , x 2 , . . . , x n by x n for every integer n > 0.

Definition II.1 An alphabet A independently and identically distributed (i.i.d.) information source is an i.i.d. discreet stochastic process, which is defined by a single-letter (marginal) probability distribution of characters from A.
We extend the single-letter probability distribution to a probability measure on the probability space constructed for the set A + of all A-sequences. We say "A-source" or "p-source" to emphasize that the source has a certain alphabet A or a probability distribution p.
Thus, we assume that every A-sequence is generated by an i.i.d. information source.
Definition II.2 An alphabet A source code C is a mapping from A + into {0, 1} + , where, according to our notation, A + is the set of all A-strings and {0, 1} + is the set of all binary strings.
We restrict our attention to uniquely decidable codes that is, for every n and every x 1 , x 2 , . . . , x n , we have C −1 (C(x 1 , x 2 , . . . , x n )) = x 1 , x 2 , . . . , x n For every n and every x 1 , x 2 , . . . , x n , we call a sequence C(x 1 , x 2 , . . . , x n ) a codeword. We often call a source code a compression code and use the terms "source code" and "compression code" interchangeably.

Definition II.3 For any given source and an alphabet
A source code C, we define the compression rate of C in bits per input character by 1 n |C(x 1 , x 2 , . . . , x n )| p , where the length of a compressed sequence (codeword) C(x 1 , x 2 , . . . , x n ) is divided by n and averaged with respect to information source's probability measure p.

Theorem 1 (Optimal Data Compression) For an i.i.d. information source with probability measure p and any compression code, the best achievable compression rate is given by Shannon entropy H(p), which is defined by
Definition II.4 For any probability distribution p, we call a source code optimal for an i.i.d. source with probability distribution p if the compression rate for this code is equal to Shannon entropy H(p). We denote such a code by C p .

B. Classical Data Compression and Relative Entropy
Suppose we have a compression code C p , that is C p is optimal for an A-source with a probability distribution p. What happens to the compression rate if we use C p to compress another A-source with a different distribution q?
It is not difficult to infer that the compression rate will generally increase, but by how much? The increase in the compression rate will be equal to relative entropy function D(q||p), which is defined by where relative entropy function D(q||p) is always non-negaitive [4] and equal to zero if and only if q ≡ p. More precisely, if using a code C q (i.e. optimal for a distribution q), one could encode a q-source with H(q) bits per input character. If, instead, one uses a code C p (i.e. optimal for p) to encode a q-source, it will require H(q) + D(q||p) bits per input character.

III. TURNING CLASSICAL SOURCE CODES INTO QUANTUM TRANSFORMATIONS
In this section we review how a classical one-to-one mapping (code) can be naturally extended 2 to a unitary quantum transformation. But first, we need to define quantum information sources.

A. Quantum Information Sources
Informally, a quantum identically and independently distributed (i.i.d.) information source is an infinite sequence of identically and independently generated quantum states (say, photons, where each photon can have one of two fixed polarizations). Each such state "lives" in its "own" copy of the same Hilbert space and is characterized by its "own" copy of the same density operator acting on the Hilbert space. We denote the Hilbert space and the density operator by H and ρ, respectively. Then, the sequence of n states "lives" in the space H ⊗n and is characterized by the density operator ρ ⊗n acting on H ⊗n . For example, in case of a photon sequence, we have dim H = 2. Thus, to define a quantum source, we just need to specify ρ and H. In this paper, we restrict our attention to quantum sources defined on two-dimensional Hilbert spaces. Often, just ρ is given and H is not explicitly specified as all Hilbert spaces of the same dimensionality are isomorphic.

B. Turning Classical Source Codes into Quantum Transformations
Now we ready to explain how a classical source code can be turned into a quantum transformation. For the rest of the paper, we will only be considering binary classical sources with alphabet A = {0, 1} and quantum information sources defined on a 2-dimensional Hilbert space.
Let B |0 , |1 be an arbitrary, but fixed orthonormal basis in the quantum information source space H. We call B a computational basis. Then, for a sequence of n quantum states, the orthonormal basis will have 2 n vectors of the form where, for every integer 1 i n, |e i ∈ B |0 , |1 . To emphasize the symbolic correspondence between binary strings of length n and the basis vectors in H ⊗n , we can rewrite (5) as where, for every integer 1 i n, e i ∈ {0, 1}. In other words, if we add the Dirac's "ket" notation at the beginning and the end of any binary string of length n, then we will get a basis vector in H ⊗n . Thus, for any computational basis B ∈ H, positive integer n, and a classical fully reversible function (mapping) for n-bit binary strings, we can define a unitary transformation on H ⊗n as follows. Let ϕ : {0, 1} n → {0, 1} n be a classical fully reversible function for n-bit binary strings. For every ϕ and n, we define a unitary operator U n B,ϕ : H in = H ⊗n → H out by the bases vectors mapping U n B,ϕ |e 1 . . . e n = |ϕ(e 1 . . . e n ) , where, for every integer 1 i n, e i ∈ {0, 1} and |e i ∈ B |0 , |1 . We point out that H out denotes an output space which is an isomorphic copy of the input space H in = H ⊗n , and H out may sometimes coincide with H in .
An elegant way of designing quantum circuits to implement U n B,ϕ was given by Langford in [7], where U n B,ϕ was computed by the following two consecutive operations defined on H in ⊗ H out : where e i , e out i ∈ {0, 1}, |e out 1 . . . e out n ∈ H out , and the notation ⊕ stands for bit-wise modulo-2 addition. In the above, Relation (7)  Another interesting approach for computing U n B,ϕ was suggested in [5], where Jozsa and Presnell used a so-called "digitalization procedure".

Remark 2
We reiterate that, given a quantum source's Hilbert space H, the quantum transformation U n B,ϕ entirely depends on-and determined by the selection of the computational basis B ∈ H and a classical fully reversible function ϕ (mapping) for n-bit binary strings. We also point out that as long as ϕ(·) and ϕ −1 (·) can be classically computed in linear time and space, then, U n B,ϕ can be computed [1,2,3] in (log-)linear time and space, too.

C. Quantum Data Compression Overview
We wish to compress a sequence of quantum states so that at a later stage the compressed sequence can be decompressed . We also want that the decompressed sequence will be the same as-or "close" to the original sequence. The measure of "closeness" is called quantum fidelity. There are a few different definitions of fidelity. One widely used is the fidelity between any pure state |ψ and mixed state ρ, defined by F (|ψ ψ|, ρ) = ψ|ρ|ψ We now introduce a new notation U n B,C for a unitary transformation defined as U n B,C := U n B,ϕ ϕ=C . Thus, the unitary transformation U n B,C acts on a product space H ⊗n × H ⊗n and can be viewed as a quantum extension of the classical compression code C. So to call U n B,C , we will use terms "unitary transformation" and "(quantum) compression code" interchangeably.
Definition III.1 Given a quantum i.i.d. source with density operator ρ, we define a compression rate of U n B,C by 1 n U n B,C |z 1 z 2 z 3 . . . z n , where |z 1 z 2 z 3 . . . z n ∈ H ⊗n is a sequence emitted by the quantum source, and the length of compressed quantum sequence U n B,C |z 1 z 2 z 3 . . . z n is divided by n and averaged in the sense of a quantum-mechanical observable 3 . If we "cut" the compressed sequence U n B,C |z 1 z 2 z 3 . . . z n at the length "slightly more" than U n B,C |z 1 z 2 z 3 . . . z n , then it can be de-compressed with high fidelity. Thus, U n B,C |z 1 z 2 z 3 . . . z n is the average number of qubits needed to faithfully represent an uncompressed sequence of length n. See [9] for a detailed treatment.

Theorem 2 (Schumacher's Optimal Quantum Data Compression[8]) For a quantum i.i.d. source with a density operator ρ and any compression scheme, the best achievable compression rate with a high expected fidelity is given by the von Neumann entropy, which is defined by
Definition III.2 A compression code, for which the above rate is achieved, is called optimal.
Lemma III.1 For a density operator ρ, we choose the eigenbasis of ρ to be our computational basis B. Let C pρ be a classical compression code, which is optimal for a probability distribution formed my the set of the eigenvalues of ρ. Then, a unitary transformation U n B,Cp ρ is an optimal quantum compression code for a quantum information source with the density operator ρ.

IV. "EFFECTIVE" SOURCE DENSITY MATRIX
We recall a quantum (binary) identically and independently distributed (i.i.d.) information source is defined by a density operator acting on a two-dimensional Hilbert space.
Let B = {|b i } be our computational basis and suppose we have a quantum i.i.d. source with density operator ρ acting on our two-dimensional computational Hilbert space. Let i λ i |λ i λ i | be an orthonormal decompositions of ρ.
For every ρ and {|b i }, Jozsa and Presnell defined [5] a so-called "effective" source density matrixρ with respect to a (computational) orthonormal basis {|b i } as follows where η j i P ij λ i and [P ij ] is a doubly stochastic matrix defined by We observe the following obvious fact. If the source eigenbasis coincides with the computation basis, i.e. {|λ i } = {|b i }, then effective source density matrix coincides with the actual source density matrix, i.e.ρ = ρ.

V. MAIN RESULT
Definition V.1 With any density matrix ρ, we associate a probability distribution formed by the density matrix's eigenvalues and denote it by putting the density matrix notation as a subscript: p ρ . That is p ρ = λ 0 , λ 1 , where λ 0 , λ 1 are the eigenvalues of ρ.
Lemma V.1 Let ρ and σ be density matrices defined on the same Hilbert space, with orthonormal decompositions ρ = i λ i |λ i λ i | and σ = j χ j |χ j χ j |.
Letρ be the effective density matrix of ρ with respect to the basis {|χ i }, and let {η j } be the eigenvalues ofρ. Then, we have the following relation between quantum and classical entropies: where D(·||·) is classical relative entropy, H(·) is classical (Shannon) entropy, pρ and p σ are the probability distributions formed by eigenvalues sets ofρ and σ, respectively. That is we have pρ = {η j } and p σ = {χ i }.
Proof 1 By the definition of effective density matrix, we have where [P ij ] is a doubly stochastic matrix, defined by By the definition of quantum relative entropy, we have S(ρ||σ) tr(ρ log ρ) − tr(ρ log σ).
First, we look at the quantity tr(ρ log σ): Substituting the identity λ i |ρ = λ i λ i | into the above equation, we get On the other hand, we have the following identity for the log function: and, therefore, substituting the right-hand-side of (13) into λ i | log σ|λ i , we get Combining equations (12) and (14), we obtain Substituting the right-hand-side of the quantum entropy identity S(ρ||σ) = i λ i log λ i and that of (15) into the definition of quantum relative entropy, we have where D(η j ||χ j ) is the (classical) relative entropy of the probability distributions η j and χ j ; H(η j ) is the (classical) entropy of the distribution η j . We can rewrite (17) as (11) which completes the proof.
In Subsection II A, we have introduced a notation C p to denote a classical data compression code (mapping) optimal for a source probability distribution p. Then, according to our notation, the code C pσ will be optimal for a (classical) i.i.d. source with probability distribution formed by the eigenvalues of a density matrix σ.
Lemma V.2 (Classical data compression and relative entropy) Let z n z 1 , . . . , z n be a sequence emitted by a classical i.i.d. source with a marginal probability distribution formed by the eigenvalues ofρ. Then, from classical data compression theory, we have where the notation in the left-hand-side stands for the length of compressed sequence (codeword) divided by n and averaged with respect to the probability measure pρ.
Combining Lemma V.1, Lemma V.2, and the results of Section III, we obtain the following theorem: where the notation in the right-hand-side stands for the length of compressed quantum sequence divided by n and averaged in the sense of a quantum-mechanical observable.
Remark 3 Quantum relative entropy S(ρ||σ) has the following operational meaning. If a quantum compression code, optimal for one quantum information source with a density operator σ, is applied to another source with a density operator ρ, then the increase of the compression rate is equal to S(ρ||σ).
Remark 4 By fixing ρ and the computational basis B (i.e. the eigenbasis of σ), we will also fixρ. Then, for a fixedρ, D(pρ||p σ ) is minimized (and is therefore equal to zero) when σ =ρ. Then, as it follows from Theorem 3, for an arbitrary computational basis B, the best possible compression rate is equal to H(pρ) = S(ρ) and is achieved with transformation U n B,Cp . In [5], such setup is called "mismatched bases" compression. If we choose the eigenbasis of ρ to be our computational basis B, then we haveρ = ρ, and optimal quantum compression is achieved with U n B,Cp ρ , with compression rate H(p ρ ) = S(ρ).
Discussion 1 As long as U n B,Cp σ is computed in a computational basis B, we can simply replace the original source density matrix ρ withρ, the effective one with respect to the computational basis. Then, our quantum compression/coding task is effectively reduced to a classical one, with classical information sources having probability distributions pρ and p σ . Therefore, all relevant results from classical information theory and data compression become applicable. We have already seen one such result, the statement of data compression (non-)optimality D(pρ||p σ ) + H(pρ).
To give another example, we consider the following task of quantum relative entropy estimation. Suppose we have two quantum i.i.d. sources with unknown density matrices ρ and σ, where ρ and σ defined on the same Hilbert space. We want to estimate quantum relative entropy S(ρ||σ).
Let |z 1 z 2 z 3 . . . z n and |x 1 x 2 x 3 . . . x n be emitted by the sources with density matrices ρ and σ, respectively. From Theorem 3, one could (hope) to estimate the quantity S(ρ||σ) + S(ρ) by simply measuring the average length of codeword U n B,Cp σ |z 1 z 2 z 3 . . . z n , then estimate S(ρ) by measuring the average length of codeword U n B,Cp ρ |z 1 z 2 z 3 . . . z n , and then subtract the latter from the former. For such straightforward approach to work, one should have quantum compression codes U n B,Cp σ and U n B,Cp ρ , which are optimal for sources with density matrices ρ and σ, respectively. But as ρ and σ are unknown, so are U n B,Cp σ and U n B,Cp ρ . Fortunately, in classical data compression, there exist so-called "universal compression codes" [11], which will let estimate (classical) quantities D(pρ||p σ ) + H(pρ) and H(pρ) even without knowing probability distributions pρ and p σ . So, based on these classical codes, we can construct quantum codes [6] (unitary transformations) to estimate S(ρ||σ).

VI. CONCLUSION
We have provided a simple and constructive proof of a quantum analog of a well-known classical information theory result on a role of relative entropy as a measure of non-optimality in data compression. We have constructed quantum compression codes (schemes) from classical data compression codes. Moreover, as the quantum data compression/coding task can be effectively reduced to a (quasi-)classical one, we show that relevant results from classical information theory and data compression become applicable and therefore can be extended to the quantum domain.