Transcription
[Music] my name is George and relax and I'll speak about optimality in quantum data compression using dynamical entropy. This is joint work with Duncan right.
So let's recall the best compression rate. For asymptotically invertible encodings, we have a quantum source that emits symbols, strings of quantum symbols. We have an encoding E that takes those strings of quantum symbols to a storage device, and the decoding D takes those compressed strings of symbols to a receiver. So the quantum source consists of a symbol set S of normalized, not necessarily orthogonal vectors of some D-dimensional Hilbert space H_S. And the sequence of random variables X_1, X_2 up to X_N with values in S. So the quantum source produces finite strings, tensor products of symbols X_1, X_2 up to X_N, and that belongs to S to the tensor N, which is a subset of the Hilbert space H_S to the tensor N. And each such string of symbols produced with certain probability. And if it, if the sequence X_N is i.i.d., then we say that the quantum source is i.i.d. The domain of the encoding E, as well as the range of the decoding D, contained tensor products S_1, S_N in S to the tensor N, which is a subset of H_S to the tensor N for every N. Or more generally, states on the Fock space generated by H_S. By the Fock space, I recall the definition of the Fock space generated by a Hilbert space. The encoding and the decoding are completely positive trace preserving maps.
The compression rate. How do we define the compression rate? We take a string of N symbols, we apply the encoding, and then we take the dimension of that state, where the dimension of a state is the number of its non-zero eigenvalues. We multiply it by the appropriate probability, we sum up for all strings of N symbols, and we divide by N because we want to find the number of qubits needed per symbol. And we take the limit as N goes to infinity. We call that our E. But we assume it's important that we assume that an efficient decoding D exists. So by that, I mean that if I composed the encoding with the decoding for any string of symbols, string of N many symbols, and I averaged with the appropriate probability, and I sum up for all strings of N symbols, and I take the limit as N goes to infinity, that average fidelity goes to 1. And the best compression rate is the infimum of R_E, where E is an efficient decoding D.
Summa here in 1995 proved that for an i.i.d. quantum source, the best compression rate is equal to the von Neumann entropy of the average state.
So now let's examine a different definition of the best compression rate. We are in determine length encodings. These indeterminate length encodings were defined by Schumacher Westmoreland in 2001. So we start with the Fock space generated by the two-dimensional Hilbert space. We take P_L, the projection to the L-th component of that Fock space. We multiply P_L by L and we sum up, and this defines the length observable. This is an unbounded self-adjoint operator on the Fock space generated by the two-dimensional Hilbert space. And using the length observable, we can define the indeterminate length of every state row on the Fock space generated by the two-dimensional Hilbert space.
So how do we define now the best compression rate using the indeterminate length encodings? So we consider not arbitrary encodings, but uniquely decodable encoding E. And we assume that this encoding takes values in the Fock space generated by the two-dimensional Hilbert space. By this formula, we define the average length of E of S_N for a uniquely decodable encoding E. And the best compression rate is then defined by taking the infimum over all uniquely decodable encodings E of the average length of E of S to the tensor N, and we divide by N because we want the number of qubits per symbol. And we take the limit as N goes to infinity. Okay, so that redefines the best compression rate using indeterminate length encodings.
So now how do we compute the best compression rate? We take the average state of S to the tensor N. We compute the von Neumann entropy of the average state of S to the tensor N. And this is close to the infimum of the average length of E of S to the tensor N, infimum over all uniquely decodable E. It's close to up to distance one. But that distance one, when we divide by N and take the limit as N goes to infinity, the distance that goes to zero. So for any quantum source, not necessarily i.i.d., the best compression rate is equal to sup_{1/N} of the von Neumann entropy of the average state S to the tensor N.
Practical considerations. How do we find the best encoding? If we know in advance how many symbols we are going to emit, then a quantum version of the Shannon-Fano encoding or Huffman encoding will actually give the best encoding. And this can be shown using a quantum version of the Kraft-McMillan inequality. There are several versions of the Kraft-McMillan inequality in the literature. Our version is an if and only if statement.
So let's recall now in the third part of my talk, the dynamical entropy of a quantum dynamical system. First, recall what is the quantum dynamical system and what is the transition expectation. A quantum dynamical system is a triplet of a phenomenon bra dynamical map from the phenomenon to itself and the state on the von Neumann algebra. Accardi defined the quantum Markov chain to be a couple of state and the transition expectation. A transition expectation is a linear bounded positive unital map on M_D tensor A to A. So how is the quantum Markov chain corresponding to a quantum dynamical system defined? So we have a quantum dynamical system and the positive operator measure gamma. And we define the quantum Markov chain phi. And phi is the same as the state of the of the quantum dynamical system. The transition expectation is defined via this formula, where we take the operators A_IJ which belong in the von Neumann algebra A, we sandwich them with the appropriate elements of the positive operator value and we sum them up, and then we compose with a dynamical map theta. We define the quantum Markov state C of the quantum Markov chain by iteratively applying the transition expectation to more and more elements of M_D. The joint correlations of the quantum Markov state is defined as the sequence of density matrices that defines that quantum Markov state. And the dynamical entropy of the dynamical system with respect to the positive operator measure is defined as the limit sup of the von Neumann entropy of the joint correlations divided by N, the lim sup of that.
So our theorem examines lossless quantum data compression of not necessarily i.i.d. quantum sources and relates the best compression rate to a dynamical c2 dynamical entropy of an appropriate quantum dynamical system. We, given any quantum source, not necessarily i.i.d., we construct a dynamical system, a quantum dynamical system, and the positive operator measure gamma such that the joint correlations are equal to the average state. Therefore, the best compression rate of that quantum source is equal to the quantum dynamical entropy of the quantum dynamical system that we construct. The construction is given in my slides. So you can see the construction. My slides will be available on my website and in the site of APS, and also at the end I give the link to the paper. Thank you.