Compressed Sensing Based on Tensor Network Machine Learning

Introduction

Compressed sensing [1] is a significant scheme for classical data compression by sampling. Consider the following scenario. Alice wants to send a piece of classical information $\{x\}$, e.g., an image of hand-written digit "3" consisting of N pixels, to Bob. She intends to send only very little M ($M < N$) pixels, denoted by $\{x\text{sent}\}$, to Bob by classical communication. They need to find a protocol so that, after receiving the M pixels, Bob can reproduce the hand-written image "3" as perfect as possible.

The tensor-network (TN) [2, 3, 4, 5, 6] is a powerful quantum-inspired computational tool for machine learning [7]. The idea is first to map an image to a quantum state, by associating the n-th pixel $x_n$ ($0 \leq x_n \leq 1$) of the image to a qubit state,

$$x_n \rightarrow |s(x_n)\rangle = \cos(x_n \pi/2)|0\rangle + \sin(x_n \pi/2)|1\rangle.$$

In this way, an image with pixels $\{x\} = (x_1, x_2, \cdots)$ is mapped to a separable quantum state $|\varphi\rangle = \Pi_n |s(x_n)\rangle$.

TN Machine Learning based Compressed Sensing

Now consider that we have a set of images in the training set. We would like to get a tensor network state $|\Psi\rangle$ to represent this class of images, say, the hand-written images "3". Let $|\varphi\rangle = \Pi_n |s(x_n)\rangle$, where $|s(x_n)\rangle = \cos(x_n \pi/2)|0\rangle + \sin(x_n \pi/2)|1\rangle$.

Be the state with respect to the $i^{th}$ image in the training set. In the generative tensor network machine learning algorithm proposed in [7], the quantum state $|\Psi\rangle$ is obtained by minimizing the negative log-likelihood defined by

$$f = \ln \left| \langle \Psi | \Psi \rangle \right|^2 - \frac{\sum_i \ln \left| \langle \Psi | \varphi_i \rangle \right|^2}{N},$$

where the summation $\sum_i$ goes over all the training images.

The idea of compressed sensing based on tensor-network machine learning is to encode and communicate the information by implementing designed projections on the state $|\Psi\rangle$ obtained by the unsupervised tensor-network machine learning algorithm [7]. Instead of sending all the pixels of a hand-written image "3", Alice sends only the pixels $x^{sent}$ to Bob by classical communication. Although Bob does not have the information about the rest pixels, he knows that the image sent by Alice is a hand-written "3", namely, it is characterized by the quantum state $|\Psi\rangle$. In other words, the rest information of $x^{rest}$ ($\{x\} = x^{sent}\} \cup \{x^{rest}\}$ is encoded in $|\Psi\rangle$.

To recover $x^{rest}$, Bob projects $|\Psi\rangle$ according to $x^{sent}$, $|\Phi\rangle = \prod_{x_i \in x^{sent}} \langle s(x_n)|\Psi\rangle / C$ with $C$ a normalization constant. Here, $x^{sent}$ should be selected so that Bob can reconstruct the rest of the pixels $x^{rest}$ from $|\Phi\rangle$ as perfect as possible by sampling on $|\Phi\rangle$ in terms of tensor network machine learning.

Therefore, to send a given image, Alice first trains $|\Psi\rangle$ by the unsupervised tensor network machine learning algorithm [7], so that $|\Psi\rangle$ represents the probability distribution of a huge amount of information about the training set of images. $|\Psi\rangle$ is called a Born machine since the probability of each piece of information is the square of the corresponding coefficient in $|\Psi\rangle$ [8]. Then to send a specific piece of information (image), she chooses to send Bob the pixels, with which the uncertainty of the rest of the pixels in the probability distribution will be minimized. The full information $x$ is efficiently compressed to a small part of the image $x^{rest}$ and the Born machine $|\Psi\rangle$.

The key problem here is how to select the pixels $x^{sent}$ for given M. In the standard compressed sensing scheme, one may randomly choose M pixels from the N pixels of the image. The sampling can be compressed since the randomly selected pixels approximately lead to averaged distributed frequencies, while an image in the frequency space is normally sparse.

However, based on the tensor network machine learning, one can do better compressed sensing. The main idea is that, since the state $|\Psi\rangle$ contains the information about the correlations (quantum entanglement) among the pixels, one may simply select only the representative pixels that are strongly correlated with the other ones, thus giving rise to a quantum inspired sampling protocol based on entanglement and the post-selections of measurements.

Based on the entanglement of $|\Psi\rangle$, $x^{sent}$ should be selected such that the uncertainty of $x^{rest}$ will be minimized from the probability distribution given by the Born machine. Given $x^{sent}$, the conditional probability distribution of $x^{rest}$ is

$$P\left(\{x^{rest}\}|x^{sent}\right) = \prod_{x_i \in x^{sent}} \langle s(x_n)|\Phi\rangle|^2$$

The task is to find the M pixels $x^{sent}$ that minimize the Shannon entropy,

$$S^{Shan} = -\sum_{x_i \in x^{sent}} P\left(\{x^{rest}\}|x^{sent}\right) \ln P\left(\{x^{rest}\}|x^{sent}\right)$$

Consider the single-site entanglement entropy with respect to the $n$-the qubit state

$$S_{n}^{ent} = -Tr\hat{\rho}_n \ln \hat{\rho}_n$$

$S_{n}^{ent}$ quantifies the information of the rest of the system that will be gained if one has the information of the $n$th qubit. Now Alice chooses the $\hat{n}$th pixel, where $\hat{n} = \arg \max_n S_{n}^{ent}$ so that Bob will gain as much information as possible from one sent pixel. In this way, one has the so-called entanglement-ordered sampling protocol in selecting $x^{sent}$ [9]: i) calculate the single-site entanglement entropy $S_{n}^{ent}$ of all qubits from the $N$-qubit state $|\Psi(N)\rangle$ and find the qubit that has the maximal $S_{n}^{ent}$, i.e., $\hat{n} = \arg \max_n S_{n}^{ent}$, ii) calculate its dominant eigenstate $|s_n\rangle$ from the reduced density matrix of the $\hat{n}$th qubit, $\hat{\rho}_n$; iii) project the $\hat{n}$th qubit of $|\Psi(N)\rangle$ to obtain the $(N-1)$-qubit state, $|\Psi(N-1)\rangle = \langle s_n|\Psi(N)\rangle / C$ with $C$ the normalized constant; iv) record the positions of these qubits if M qubits have been projected, and transfer the pixels at these positions of the image to Bob. Note that $|\Psi(N-M)\rangle = |\Phi\rangle$. Otherwise, go back to Step i) with $|\Psi(N-1)\rangle$.

In short, one selects the pixels in the order of entanglement. To obtain better accuracy for reconstructing gray-scale images, the pixels $x^{rest}$ are generated by locating the separable state with maximal probability,

$$\{x^{rest}\} = \arg \max_{x_i} \left| \prod_n \langle s(x_n)|\Phi\rangle \right|^2,$$

i.e., each projective basis $|s(x_n)\rangle$ is the dominant eigenstate of the corresponding single-site reduced density matrix of $|\Phi\rangle$. Here, it should be emphasized that the order of projections in such entanglement-ordered sampling protocol is solely determined by the entanglement properties of the generative matrix product states. It does not depend on the specific images to be sent.

As a simple example of such entanglement-ordered sampling protocol, let us consider the following four-qubit state,

$$|\Psi\rangle = \left( \frac{\sqrt{2}}{2} |01\rangle + \frac{\sqrt{2}}{2} |10\rangle \right) \otimes \left( \frac{1}{2} |01\rangle + \frac{\sqrt{3}}{2} |10\rangle \right) = \frac{\sqrt{2}}{4} |0101\rangle + \frac{\sqrt{6}}{4} |0110\rangle + \frac{\sqrt{2}}{4} |1001\rangle + \frac{\sqrt{6}}{4} |1010\rangle.$$

Such a state can describe a dataset of four images $(0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1)$ and $(1, 0, 1, 0)$, with the probabilities $P = 1/8, 3/8, 1/8$ and $3/8$, respectively. If Alice wants to send two pixels and encode the rest two in the state, the pixel that Alice should firstly choose is obviously the first (or the second) pixel, since the first two qubits are maximally entangled, namely, one of the pixels can be determined by knowing the other pixel. The second pixel Alice chooses should be the third or the forth one. These two qubits are entangled but not maximally entangled. Hence, knowing one of them will gain certain, but not the full, information of the other. Any way, the best choice for Alice is to send the first (or second) and the third (or the forth) pixels to Bob.

From the view of entanglement-ordered sampling protocol, one has that Sent $S_1^{ent} = S_2^{ent} = \ln 2 \approx 0.693$, and $S_3^{ent} = S_4^{ent} = -\frac{1}{4} \ln \frac{1}{4} - \frac{3}{4} \ln \frac{3}{4} \approx 0.562$. Therefore, Alice chooses the first or the second pixel. Since the reduced density matrices $\hat{\rho}_1 = \hat{\rho}_2 = I/2$ with $I$ the $2 \times 2$ identity, Alice decides to measure the first qubit by the measurement operators $|0\rangle$ or $|1\rangle\langle1\rangle$. In either case, the resulting three-qubit state will be $|\Psi(3)\rangle = |x\rangle \otimes \left( \frac{1}{2} |01\rangle + \frac{\sqrt{3}}{2} |10\rangle \right)$ with $x = 0$ or $1$. In the second iteration, Alice has $S_2^{ent} = 0$ and $S_3^{ent} = S_4^{ent} \approx 0.562$.

Hence, she decides to send the third (or forth) pixel.

Conclusions

We have introduced a novel compressed sensing approach by combining the ideas of compressed sensing, quantum communication and unsupervised tensor network machine learning. One key step is to train the state $|\Psi\rangle$ by the unsupervised tensor network machine learning algorithm, so that the targeted piece of information can be encoded with minimal distance to the state $|\Phi\rangle$ obtained by projecting $|\Psi\rangle$ in a designed way. Another key step is to select the pixels in the order of entanglement from $|\Psi\rangle$. These results provide new possibilities for processing real-life data by secure quantum communications.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant No. 12075159, Beijing Natural Science Foundation (Z190005), the Academician Innovation Platform of Hainan Province, and Academy for Multidisciplinary Studies, Capital Normal University.