Quantum Algorithm for Signal Denoising

Denoising a signal is an essential and long-standing challenge in number of applications, including medical science, geophysics, remote sensing, etc. Despite a large number of existing approaches, denoising is still the subject of active research nowadays.

Furthermore, with the development of quantum computing in recent years, such problems are bound to arise in a quantum setting as well. In this context, denoising is a different but complementary approach to error-correcting codes, which have been the subject of extensive research in the quantum computing community e.g, [1, 2, 3]. In particular, one could envision to use quantum computers to denoise a classical signal, as well as to deal directly with a quantum signal produced as the result of a quantum algorithm, or more generally as the output of a quantum process to be treated by quantum means.

With the advancement of quantum computing, many signal or image processing problems have been attempted to be solved using quantum algorithms in the last decade, with promising performance achieved in image compression [4], encryption [5], watermarking [6, 7, 8], color translation [9], resolution enhancement [10], feature extraction [11], edge detection [12, 13], quantum image representation [14, 15], quantum machine learning [16], and so on. Quantum denoising algorithms for removing standard classical noise (e.g., Gaussian, salt & pepper, etc.) have also emerged in recent years. In particular, spatial filtering methods such as quantum median filtering [17, 18] or weighted average filtering [19, 20] have been reported in the literature. Likewise, transform domain thresholding methods based on Quantum Fourier Transforms (QFT) [21, 22] and Quantum Wavelet Transforms (QWT) [23] have also been proposed.

However, in the literature on classical denoising, it has been seen that such classical transform methods are usually less powerful and efficient than methods which use tailored transforms adapted to the properties of the signal to be processed. Among recent works, we have developed a method based on adaptive transforms built from solutions of the Schroedinger equation [24]. The main advantage of such methods is that the thresholding is automatically modified according to the local properties of the underlying signal. Direct implementation of the method of [24] on a quantum computer or device is not an easy problem. Therefore, in the present work, we propose a modified algorithm which still takes advantage of the local properties of the signal while being efficiently implementable on a quantum computer. The main idea is to locally threshold a noisy quantum state (in quantum computation, a signal is represented by a quantum state) in the frequency domain, using combinations of QFT and amplitude amplification, a process derived from Grover’s quantum search algorithm [25, 26]. We show how to apply our method to a classical signal transformed into a quantum state by a specific process, as well as to a quantum state produced by a purely quantum process such as a quantum algorithm. We evaluate the complexity of our algorithm and show its efficiency compared to previous algorithms. Finally, we present numerical results demonstrating that our algorithm can denoise both classical and quantum signals, and more efficiently than previously proposed algorithms.

Our algorithm can be applied to denoise an initially noisy quantum state on a N-dimensional Hilbert space, which can be the end-product of a quantum algorithm running on a quantum computer such as algorithms simulating quantum physical systems. It can also apply to a classical numerical signal ${\boldsymbol{y}}\in\mathbb{R}^{N}$. In the latter case, the classical signal should be first implemented in a quantum state. In both cases, to use our denoising algorithm, we will need to additionally store in a quantum register the local mean value of the signal in sliding windows, as well as the value of a local threshold. To learn more about the standard tools of quantum computing, we refer the reader to good introductions to the field such as [27, 28].

In the case of a noisy classical signal ${\boldsymbol{y}}\in\mathbb{R}^{N}$, for simplicity and without loss of generality, we consider $N$ as a power of two such that $N=2^{n}$. Our procedure requires to divide ${\boldsymbol{y}}$ into $P=2^{p}$ signal windows of size $M=2^{m}$, such that $N=PM$. In order to store the values of ${\boldsymbol{y}}$ we need a $n$-qubit register split into a $m$-qubit register denoted $\ket{i}^{\mbox{\scriptsize{I}}}$ which stores the position inside a signal segment and a $p$-qubit register denoted $\ket{j}^{\mbox{\scriptsize{J}}}$ which holds the segment number. We also need two additional registers initially in the state $\ket{0}$. The first one of $a$ qubits will hold the mean values inside a segment as a binary sequence for each segment number. The second one of $b$ qubits will hold the local threshold which will be used for this segment. The mean value of a local window $A_{j}$ should be precomputed classically, as well as the thresholding function $\tau(A_{j})$ which depends on the mean value $A_{j}$, giving a sample-dependent adaptive threshold; assigning precise values to the function $\tau(A_{j})$ can be done classically before running the algorithm following methods in the line of the one explained in [29]. ${\boldsymbol{y}}$ is encoded into a quantum state which contains at the same time the values of the signal as amplitudes and its sliding windows mean values in a register, using a modification of a known method (see e.g. [14, 15]) that we detail below.

Starting from the quantum signal (4), the gate operations needed to perform the proposed algorithm correspond to the QFT, the amplitude amplification algorithm, and finally the IQFT. The $m$-qubits QFT and IQFT require $O(\mbox{log}^{2}M)$ operations, and the amplitude amplification algorithm needs $O(\sqrt{N/\sum_{j}M_{j}})$, where $M_{j}$ is the number of states below threshold in the $j$-th segment (with $M_{j}\leq M$ for all $j$). Classically the whole process starting from the same premises would be dominated by the Fourier transforms and would cost $O(PM\mbox{log}M)$ operations, i.e., $P$ Fourier transforms should be performed, for each window of size $M$. The gain of the proposed algorithm compared to the classical one depends on the size of the patches $M$ and the number of states selected by the threshold. The smaller the patch, the more efficient becomes the proposed algorithm; at worse, for extremely low threshold, the amplitude amplification will cost $O(\sqrt{N})$ and will dominate the computational cost, with still a quadratic gain compared to classical algorithms. For large or intermediate threshold, the QFT dominates and the cost is $O(\mbox{log}^{2}M)$ compared to $O(PM\mbox{log}M)$. Furthermore, $O(\mbox{log}N)$ qubits of storage space is sufficient for our proposed quantum computation in contrast with the classical process with $O(N)$ bits storage. To be fair, it should be noted that in the case of a purely classical signal, this comparison is done without counting the cost of transforming the classical signal into the quantum initial signal (4), which using the procedures of [14, 15] would cost $O(N^{2})$ operations; however using more refined implementations of the controlled operations [31], this could be reduced to $O(N\mbox{log}^{2}N)$ operations.

We also note that compared to other quantum algorithms for denoising based on simple transforms and direct thresholding (e.g. through measurements) the proposed algorithm leads to a gain on two distinct parts of the algorithm; indeed, previous quantum algorithms using QFT [21] or QWT [23] require $O(\mbox{log}^{2}N)$ operations for the transform and $O(N/\sum_{j}M_{j})$ operations for the thresholding. For $M\ll N$ or $\sum_{j}M_{j}\ll N$, these two parts are significantly accelerated by our algorithm.

In this section, we assess the performance of our proposed quantum denoising algorithm in presence of: (i) classical noise, (ii) quantum phase noise, and (iii) mixed classical and quantum noise. The simulations were executed on a classical computer using MATLAB implantation based on linear algebra, where quantum states and the unitary transformations are represented by complex vectors and unitary matrices respectively.

(i) Classical noise: Conventional additive white Gaussian noise (AWGN) with signal-to-noise-ratio (SNR) 15dB is considered as the classical noise that contaminates the classical signal. Following the quantum signal representation scheme proposed in Sec. II, the noisy quantum state $\ket{\psi}$ is prepared before implementing our proposed quantum algorithm. Fig. 1(a) depicts the respective denoising performance.

(ii) Quantum phase noise: Unitary transformations in a quantum computer are performed by some quantum circuits, basically made of one-qubit or two-qubit unitary operations or gates. To implement this kind of noise, which can correspond to, e.g., noise in the experimental implementation of the gates, we perform a QFT followed by an IQFT, and rotate each of the basic unitary operations with a small random angle of amplitude $\epsilon=10^{-1}$. These random $\epsilon$ rotations vary in time, generating a phase noise in the unitary transformations [32, 33]. The circuit implementation of our proposed quantum denoising algorithm is then implemented free of noise. The denoising performance in presence of such quantum noise is shown in Fig. 1(b).

(iii) Mixed noise: Finally, AWGN and quantum phase noise are combined to generate the effect of a mixed noise. A classical noisy signal contaminated with AWGN is used to prepare the quantum state $\ket{\psi}$ in eq. (3) following the strategy proposed in Sec. II and then quantum phase noise $\epsilon=10^{-1}$ is added as in (ii). Fig. 1(c) illustrates the denoising ability of our proposed algorithm in presence of mixed noise.

Rigorous comparisons²²2In the context of classical signal denoising, a vast literature with sophisticated algorithms is available, e.g., [34, 35, 36, 37, 38, 39]. Since our main focus in this letter is quantum computation, we only consider for comparison algorithms that have been proposed for a quantum computer. with existing quantum algorithms based on QFT [21] and QWT [23] are reported under the three noise scenarios. Visual and quantitative results in terms of SNR and peak-SNR (PSNR) in Fig. 1 indicate that the proposed quantum algorithm significantly outperforms other methods in all scenarios. We observe that in presence of quantum phase noise and mixed noise the proposed quantum denoising algorithm respectively presents a gain of more than 3.5 dB and 2 dB PSNRs compared to the second best performing method using QWT. This is particularly visible on the extreme left of the signal, where the proposed algorithm reproduces the global shape which is lost in the denoising by QFT and QWT alone. Our results thus indicate that simpler QFT and QWT based algorithms are less efficient, and in particular less adapted to the quantum phase noise than the proposed one; a result we attribute to the locally adaptive nature of our method. Other types of noise are possible, and in particular the quantum signal and quantum registers can be subject to decoherence. In order to test our algorithm in presence of another type of quantum noise which appears in decoherence processes, we added to the process bit-flip errors on the registers. On average, our proposed method produces denoised outputs with 19.77 dB PSNR, while QFT and QWT algorithms yield 17.98 dB and 17.46 dB PSNRs respectively (more details and an explicit example can be found in the Supp. Mat.). This suggests that our method is efficient in presence of other quantum noise and in particular quantum decoherence noises. Denoising results on classical Poisson and mixed (Poisson + quantum) noise scenarios are also reported in the Supp. Mat., showing that our method is equally effective in the presence of signal dependent noise models such as Poissonian noise.

This letter introduced a novel quantum algorithm for signal denoising. Our proposed algorithm uses a local thresholding in the frequency domain depending on the local mean value of the signal, which provides an adaptive way of thresholding a noisy signal. To illustrate the feasibility of our proposed method, we conducted experiments in presence of classical Gaussian noise, quantum phase noise in quantum gates, bit-flip noise and mixed noises (combined Gaussian and quantum phase noise). Our results suggest that our quantum algorithm is able to provide better denoising performances than the previously proposed quantum algorithms, especially in the presence of quantum phase noise, while being parametrically faster than existing classical and quantum algorithms. We note that such denoising performed a posteriori may be important to harness noisy quantum computers, and can be substituted or combined with standard quantum error correction, performed during the quantum computation. It should be noted that due to the efficiency of the algorithm and its ability to self-correct the noise produced, the signal size that could be handled should grow exponentially with the inverse of the level of noise deemed acceptable. In this letter, we empirically choose a simple thresholding operation based on the mean value, whereas the proposed method provides a general thresholding framework. Thus it would be interesting to study other advanced thresholding schemes, such as Wiener filtering incorporating mean and variance in the thresholding process. A promising future work could also be to extend our algorithm to other imaging applications, such as deconvolution.

Sayantan Dutta³³3Corresponding author: Sayantan Dutta (e-mail: [email protected]; [email protected]), Adrian Basarab, Denis Kouamé, and Bertrand Georgeot

In this Supplementary Material, we define precisely the proposed unitary operation ${\boldsymbol{\mathcal{T}}}$ to encode a classical signal into a quantum state, and present additional signal denoising results in presence of signal dependent Poissonian noise and mixed noise in Fig. 2, as well as analyze the effect of bit-flip errors which appear in quantum decoherence processes in Fig. 3 using our proposed quantum algorithm and compared with standard Quantum Fourier Transforms (QFT) and Quantum Wavelet Transforms (QWT).

where $\bigotimes$ represents the tensor product, ${\boldsymbol{I}}$ is the identity transform, ${\boldsymbol{\mathcal{R}}}_{y}(\theta_{ji})$ are the controlled rotation operations about the $y$-axis with angle $\theta_{ji}$, and, ${\boldsymbol{\mathbf{\Omega}}}_{j}$ and ${\boldsymbol{C}}_{{\boldsymbol{\mathbf{\Omega}}}_{j}}$ are the controlled value setting operations.

To implement quantum decoherence noises, we performed bit-flip operations randomly after each 1-qubit Hadamard gate in the quantum Fourier and inverse Fourier transforms together with quantum phase noise (by rotating each of the basic unitary operations with a small random angle of amplitude $\epsilon=10^{-1}$, as explained in the main text Sec.IV). Fig. 3 exemplifies the robustness of our proposed method against quantum decoherence noises. On average, our proposed method produces denoised signals with 19.77 dB PSNR, whereas standard QFT and QWT algorithms yield 17.98 dB and 17.46 dB PSNRs, respectively. Therefore, the proposed method significantly outperforms previously proposed algorithms.