Open AccessArticle

Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation

Shumei Wang

Pengao Xu

Ruicheng Song

Peiyao Li

and

Hongyang Ma

Quantum Physics Laboratory, School of Sciences, Qingdao University of Technology, Qingdao 266520, China

Author to whom correspondence should be addressed.

Entropy 2020, 22(11), 1207; https://doi.org/10.3390/e22111207

Submission received: 18 August 2020 / Revised: 15 October 2020 / Accepted: 22 October 2020 / Published: 25 October 2020

(This article belongs to the Special Issue Methods and Applications of Quantum Data Processing)

Download

Browse Figures

Figure 1
Image degradation process. "> Figure 2
Realization of quantum circuits <math display="inline"><semantics> <msub> <mi>U</mi> <mi>L</mi> </msub> </semantics></math>. On the shifted image set, the gradient is calculated by addition, subtraction, and doubling. "> Figure 3
Quantum circuits of <math display="inline"><semantics> <mrow> <mi>C</mi> <mo>(</mo> <mi>x</mi> <mo>+</mo> <mo>)</mo> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>C</mi> <mo>(</mo> <mi>y</mi> <mo>−</mo> <mo>)</mo> </mrow> </semantics></math> for n-qubit sequence length. "> Figure 4
Realization of quantum circuit of adder and simplified model. (a) The concrete quantum circuit of adder; (b) Simplified model of adder. "> Figure 5
Realization of quantum circuit of subtracter and simplified model. (a) The concrete quantum circuit of the subtracter; (b) A simplified model of a subtracter. "> Figure 6
Double operation of the quantum circuit implementation and simplified model. (a) The concrete quantum circuit of doubling operations; (b) A simplified model of doubling operations. "> Figure 7
The original image. "> Figure 8
Motion blurred image. "> Figure 9
Motion blur and noise images. "> Figure 10
The restored image after filtering. ">

Versions Notes

Abstract

Recent development of computer technology may lead to the quantum image algorithms becoming a hotspot. Quantum information and computation give some advantages to our quantum image algorithms, which deal with the limited problems that cannot be solved by the original classical image algorithm. Image processing cry out for applications of quantum image. Most works on quantum images are theoretical or sometimes even unpolished, although real-world experiments in quantum computer have begun and are multiplying. However, just as the development of computer technology helped to drive the Technology Revolution, a new quantum image algorithm on constrained least squares filtering computation was proposed from quantum mechanics, quantum information, and extremely powerful computer. A quantum image representation model is introduced to construct an image model, which is then used for image processing. Prior knowledge is employed in order to reconstruct or estimate the point spread function, and a non-degenerate estimate is obtained based on the opposite processing. The fuzzy function against noises is solved using the optimal measure of smoothness. On the constraint condition, determine the minimum criterion function and estimate the original image function. For some motion blurs and some kinds of noise pollutions, such as Gaussian noises, the proposed algorithm is able to yield better recovery results. Additionally, it should be noted that, when there is a noise attack with very low noise intensity, the model based on the constrained least squares filtering can still deliver good recovery results, with strong robustness. Subsequently, discuss the simulation analysis of the complexity of implementing quantum circuits and image filtering, and demonstrate that the algorithm has a good effect on fuzzy recovery, when the noise density is small.

Keywords:

quanta image computation; quantum image algorithm; image restoration; algorithm analysis

1. Introduction

Just as Feynman first discussed quantum computing in 1982 [1] and Bennett and Brassard, who performed key distribution on the quantum channel, proposed BB84 protocol [2] with modern technology. This is a new burgeoning branch of quantum physics is updating 19th-century image processing algorithm for quantum information systems at present. Some quantum information algorithms have been extensively studied in the past few decades. The quantum prime factorization algorithm that was proposed by Shor [3] and the quantum search algorithm proposed by Grover [4] have proved the computing power of quantum computers. In these case, increasing amounts of researchers have began to explore the various applications of quantum computers [5,6,7,8,9]. In addition, interrelated disciplines are also emerging. Quantum image algorithm is an interdisciplinary field in its infancy.

Physicists nowadays who work at the intersection of two fields—quantum information theory and image processing—live it. The existing computing technology is inefficient for the demand of image processing. The development of classic image processing is limited by image resolution. Because of the properties of quantum superposition and entanglement, the efficiency of algorithm can be greatly improved. It is possible to use quantum computer to solve the problem of time and space consumption in this kind of complex image processing algorithm. At first, S. E. Venegas Andraca proposed the concept of a quantum matrix shown here, exists as a thought experiment [10]. Since then, other algorithms [11,12] have been constantly improved. In previous studies, researchers have proposed many quantum image models, which play a good role in representing image information in practice. These include qubit lattice [13], entangled image [14], real ket [15], flexible representation of quantum images(FRQI) [16], and the novel enhanced quantum representation of digital images (NEQR) [17]. The image processing function [18,19,20,21] in the classical field is very powerful, and the development of quantum image is also following the direction of classical image processing. However, due to the late start, most of the existing models can only be used for simple image processing. Yuan et al. [22] proposed two kinds of improved quantum dilation and erosion operations in order to reduce the time complexity of quantum morphology operations in 2016. In this algorithm, all operations are done via quantum circuits. They constructed a system for using qubits to code and process image information. In 2020, Ma et al. [23] improved the algorithm on the basis of Yuan et al. and proposed a more consistent algorithm for quantum dilation and erosion as well as its implementation in the IBM quantum simulator. This is a powerful step forward in quantum image processing. In many digital image processing algorithms, noise cancellation is one of the basic procedures that must be considered. However, not a lot of studies have considered the noise problem in the quantum image processing mode. In 2017, Liu et al. studied restoration to remove noise in quantum images [24]. Although the filtering model of quantum image works well, the problem of blurring should also be considered. In digital image processing, we should not only consider noise, but also the deblurring problem caused by external factors. It can be said that the quality of digital images plays a crucial role in the process of communication and visual perception. High quality images will bring richer content and information, and even give the viewer a beautiful enjoyment, while poor quality images will not only lose a lot of image information, but also sometimes bring uncomfortable feelings to the viewer.

The photos taken by the camera may appear blurred due to some environmental influence factors of distance and light intensity. Shaking during filming can cause this problem. Therefore, we need to analyze this point spread function to solve the impact that is caused by the blur and restore the image. Because of the increase of image resolution, the development of traditional digital image processing have been restricted. The merge of quantum computation and traditional digital image processing methods is considered to be a promising candidate to solve the problem. Because quantum image processing will use the superposition and entanglement properties of quantum mechanics to calculate all pixels of the image at the same time, it can achieve exponential acceleration compared to classical algorithms. Accordingly, this paper proposes a quantum image restoration model that is based on constrained least squares filtering. This model can not only solve the problem that the degradation function is sensitive to noise, but also eliminate the influence of some noise.

The remaining paper are organized, as follows: Section 2 describes the NEQR model and constrained least square filtering computation. The detailed quantum image process, including NEQR construction process and basic quantum circuits, is described in Section 3. Section 4 and Section 5 describe complexity analysis and simulation experiments. Finally, in Section 6, the conclusions and prospects of future work are introduced.

2. Preliminaries

2.1. NEQR Model

In the NEQR representation model, the position information and color information of grayscale images can be represented by two entangled quantum sequences. Quantum entanglement is a quantum mechanical phenomenon, in which entangled quantum sequences have a correlation. The model uses q quantum bits to represent color information. q is the image color depth and it can represent all colors in the grayscale range

[0, 2^{q} - 1]

. An image compiled through the NEQR description model can be expressed, as follows:

| I 〉 = \frac{1}{2^{n}} \sum_{i = 0}^{2^{2 n} - 1} | c_{i} 〉 \otimes | i 〉

(1)

| c_{i} 〉

and

| i 〉

respectively represents the color image color Information and the position information of the image:

\begin{matrix} |c_{i}〉 = |c_{i}^{q - 1} \dots c_{i}^{1} c_{i}^{0}〉, |c_{i}^{k}〉 \in {0, 1}, k = q - 1, \dots 1, 0 . \end{matrix}

(2)

\begin{matrix} | i 〉 = | y 〉 | x 〉 = |y_{n - 1} y_{n - 2} \dots y_{0}〉 |x_{n - 1} x_{n - 2} \dots x_{0}〉, |y_{i}〉 |x_{i}〉 \in {0, 1} . \end{matrix}

(3)

NEQR images can be measured in order to obtain images exactly the same as the original image color information. Therefore, NEQR images are more flexible in color processing.

2.2. Constrained Least Square Filtering Computation

The input-output relationship of image acquisition, in Figure 1:

g (x, y) = H [f (x, y)] + n (x, y)

(4)

As a significant part of digital image processing, image restoration is helpful to eliminate the distortion and deterioration in the process of image information transmission so as to obtain high-quality image information. Image restoration is an inverse process of image degradation, where H points to the diffusion function.

The constrained least square filtering model [25] only requires knowledge of the variance and mean of the noise signal, and the noise parameters can be inferred from the known degraded image.The key of constrained least square filtering is to overcome the relative sensitivity of noise to H. H is the entire degradation process. Image degradation can be obtained after the original image is convolved with the system. Therefore, the image restoration can achieve de-convolution operation on the output result in order to obtain the original image estimation. To obtain the degenerate image

g (x, y)

, one needs to superimpose the original image

f (x, y)

and noise

n (x, y)

under the degenerate operator

h (x, y)

. Accordingly, a constrained minimum criterion function C can be set up, as follows

C = \sum_{0}^{M - 1} \sum_{0}^{N - 1} {[\nabla^{2} f (x, y)]}^{2}

(5)

In the constrained minimum criterion function C, M and N, respectively, represent the value range of pixels,

\nabla^{2} f (x, y)

is the Laplace transform of the original image

f (x, y)

The constraint is

∥ G - H \hat{F} ∥_{2}^{2} = {∥ N ∥}_{2}^{2}

. Here, in the frequency domain, G is the degraded image,

\hat{F}

is the estimate of degraded image, N is additive noise, and Laplace operator

\nabla^{2}

is smoothness. To find the minimum value of the function, one needs to use the Lagrange multiplier method and convert the constraint term into the Lagrange multiplier term.

The matrix form of the Laplace operator can be expressed as:

\nabla^{2} = [\begin{matrix} 0 & - 1 & 0 \\ - 1 & 4 & - 1 \\ 0 & - 1 & 0 \end{matrix}]

(6)

The Laplace transform of a continuous function

f (x, y)

at x and y is defined as:

\nabla^{2} f = \frac{\partial^{2} f}{\partial x^{2}} + \frac{\partial^{2} f}{\partial y^{2}}

(7)

For digital images, it can be obtained by difference calculation

\begin{matrix} \frac{\partial^{2} f}{\partial x^{2}} & = \frac{\partial (f (i + 1, j) - f (i, j))}{\partial x} \\ = f (i + 1, j) - 2 f (i, j) + f (i - 1, j) \end{matrix}

Similarly,

\frac{\partial^{2} f}{\partial y^{2}} = f (i, j + 1) - 2 f (i, j) + f (i, j - 1)

(8)

Therefore, combining the second order difference of the horizontal and vertical directions of the image, the Laplace calculation method is as follows:

\nabla^{2} f = f (i + 1, j) + f (i - 1, j) + f (i, j + 1) + f (i, j - 1) - 4 f (i, j)

(9)

Additionally likewise, use the Laplace convolution model and convert the constraint term to the Lagrange multiplier term, so the Lagrangian function

L (\hat{F}, λ)

is:

L (\hat{F}, λ) = {∥ P \hat{F} ∥}_{2}^{2} - λ (∥ G - H \hat{F} ∥_{2}^{2} - {∥ N ∥}_{2}^{2})

(10)

where H represents the fuzzy matrix and P is the Fourier transform of the Laplace operator. Different point spread function are used to restore the image.

When one take the derivative of the function

L (\hat{F}, λ)

with respect to

\hat{F}

, one obtains

\begin{matrix} \frac{\partial L (\hat{F}, λ)}{\partial \hat{F}} & = \frac{2 [∥ P \hat{F} ∥_{2}^{2} + λ (114 - H \hat{E} ∥_{2}^{2} -∥ {N ∥}_{2}^{2})]}{2 \hat{F}} \\ = 2 p^{*} p \hat{F} + λ (- 2 H^{*} G + 2 H^{*} H \hat{F}) \end{matrix}

(11)

when

\frac{\partial L (\hat{F}, λ)}{\partial \hat{F}} = 0

, one get the minimum

\hat{F}

\hat{F} (u, v) = [\frac{H^{*} (u, v)}{{| H (u, v) |}^{2} + γ {| P (u, v) |}^{2}}] G (u, v)

(12)

where

γ = \frac{1}{λ}

H^{*}

is the complex conjugate of H.

3. Quantum Image Algorithm

3.1. Initialization

For a

2^{n} \times 2^{n}

classic image, NEQR requires a total of

2 n + q

qubits to save information. According to the initialization state, the quantum image can be constructed in two steps:

(1) The initial quantum state is converted to an equal weight superposition of all pixels in the image.

U_{1} = I^{\otimes q} \otimes H^{\otimes 2 n}

. Hence, when

U_{1}

applied to an initial quantum state

| ψ 〉

, the quantum state is converted to an intermediate quantum state. This quantum evolution process can be expressed as:

U_{1} {= (I | 0 〉)}^{\otimes q} {\otimes (H | 0 〉)}^{\otimes 2 n} = \frac{1}{2^{n}} {| 0 〉}^{\otimes q} \otimes \sum_{i = 0}^{2^{2 m - 1}} | i 〉 = |ψ_{1}〉

(13)

(2) Each pixel on the intermediate state is assigned a color bit. Since in the new quantum image, the pixels of the image are still processed in the superposition state, the operation in this step still needs to be divided into

2^{n} \times 2^{n}

sub-operations in order to assign color bits to each pixel of the image. Suppose that the sub operation of each pixel is

Ω_{Y X}

, so the sub operation of each pixel of the image can be expressed as:

U_{Y X} = (I \otimes \sum_{j = 0, j \neq Y}^{2^{n} - 1} \sum_{i = 0, i \neq X}^{2^{n} - 1} | j i 〉 〈 j i |) + Ω_{Y X} \otimes | Y X 〉 〈 Y X |

(14)

Subsequently, when the operation

U_{Y X}

is applied to the intermediate state

| ψ_{1} 〉

, the quantum evolution process of the whole system is:

\begin{matrix} U_{Y X} |ψ_{1}〉 & = U_{Y X} (\frac{1}{2^{n}} \sum_{j = 0}^{2^{n} - 1} \sum_{i = 0}^{2^{n} - 1} {| 0 〉}^{\otimes q} 〈 j i |) \\ = \frac{1}{2^{n}} (\sum_{j = 0}^{2^{n} - 1} \sum_{i = 0, j i \neq Y X}^{2^{n} - 1} {| 0 〉}^{\otimes q} 〈 j i | + | f (Y, X) 〉 | Y X 〉) \end{matrix}

(15)

In the classical digital image, the quantum image NEQR model is quantified and the translated data set is obtained through cyclic shift operation.

3.2. Quantum Circuit Implementation

We can obtain the gradient value of all pixels by quantum image cyclic shift operation. The original image

I_{x y}

, and

| I 〉 = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y X}〉 | Y 〉 | X 〉

, then

C_{y -}

, Shift

I_{x y}

one-unit downwards,

I_{x y - 1} = C_{y -} I_{x y} = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y - 1 X}〉 | Y 〉 | X 〉

(16)

The output

I_{x y - 1}

, then

C_{x +}

, shift

I_{x y}

one-unit rightwards,

I_{x + 1 y} = C_{x +} I_{x y} = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y X + 1}〉 | Y 〉 | X 〉

(17)

The output

I_{x + 1 y}

, then

C_{y +}

, shift

I_{x y}

one-unit upwards,

I_{x y + 1} = C_{y +} I_{x y} = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y + 1 X}〉 | Y 〉 | X 〉

(18)

The output

I_{x y + 1}

, then

C_{x -}

, shift

I_{x y}

one-unit leftwards,

I_{x - 1 y} = C_{x -} I_{x y} = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y X - 1}〉 | Y 〉 | X 〉

(19)

At last, the output

I_{x - 1 y}

. One obtains the pixel value of the neighborhood by cycle shift operation, and then calculate the gradient according to Laplace’s template, where a quantum black box

U_{L}

is designed to compute the gradient of the Laplace operator, in Figure 2.

3.3. Cycle Shift, Addition Subtraction and Double Operation

Cyclic shift transform can move the whole image at the same time, and each image will get the pixel information of its field, as in Figure 3.

C (x \pm) | I 〉 = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y X^{'}}〉 | Y 〉 | X 〉

(20)

C (y \pm) | I 〉 = \frac{1}{2^{n}} \sum_{Y = 0}^{2^{n} - 1} \sum_{X = 0}^{2^{n} - 1} |C_{Y^{'} X}〉 | Y 〉 | X 〉

(21)

For the image

I_{A}

and

I_{B}

, the sum of the images is

I_{C}

|I_{C}〉 = \frac{1}{2^{n}} \sum_{Y X = 0}^{2^{2 n} - 1} |C_{Y X}〉 | Y X 〉 = \frac{1}{2^{n}} \sum_{Y X = 0}^{2^{2 n} - 1} |A_{Y X} + B_{Y X}〉 | Y X 〉

(22)

The following is the addition operation of the quantum image, and the expression of the addition operation is:

| I_{c} 〉 = A D D (I_{A}, I_{B})

(23)

The realization process of the quantum circuit of adder is shown in the Figure 4.

Add the pixel value to the corresponding complement in order to obtain the difference of pixel subtraction between two quantum images

|C_{Y X}〉 = |A_{Y X}〉 - |B_{Y X}〉

The subtraction operation of the quantum image is deduced, as follows:

|I_{C}〉 = S U B (|I_{A}〉, |I_{B}〉)

(24)

The realization process of the quantum circuit of the subtracter is shown in the Figure 5.

If one wants to shift the binary sequence to the right by this, one obtains

| 2 \cdot C 〉 = |c_{q - 1} c_{q - 2} \dots c_{1} c_{0} 0〉

. In order to form a sequence of qubits, add an auxiliary qubit

| 0 〉

, then obtain

| 0 〉 \otimes | C 〉 = |0 c_{q - 1} c_{q - 2} \dots c_{1} c_{0}〉

. The realization process of the quantum circuit of double operation is shown in the Figure 6.

3.4. Restoration for Deblurring of Quantum Image

If the premise of prior knowledge of noise signal n is lacking, then the process of image restoration is an estimation

\hat{f}

of trying to find undegraded image f. This needs to make

H \hat{f}

and g mean square error as small as possible. In other words, in the sense of the least mean square error,

H \hat{f}

is closest to g. In order to solve this problem, Laplace operator is introduced, according to the previous discussion. The sensitivity to noise is reduced by means of smoothing measures.

If space domain recovery method is needed, then we need to solve the problem of estimating the least square of the original image f.

The quantum images can be obtained through the coordinate transformation. Through the cyclic shift operation of the original image

|I_{x y}〉

, we can obtain a set of quantum images:

|I_{x y - 1}〉, |I_{x - 1 y}〉, |I_{x y}〉 | I_{x + 1} y 〉, |I_{x y + 1}〉

. Next, we calculate the gradient based on the convolution template.

\begin{matrix} | μ_{1} 〉 & = q A D D (| I_{x y - 1} 〉 + | I_{x - 1 y} 〉) \\ | μ_{2} 〉 & = q A D D (| I_{x + 1 y} 〉 + | I_{x y + 1} 〉) \\ | μ_{3} 〉 & = q A D D (| μ_{1} 〉 + | μ_{2} 〉) \\ | ξ_{1} 〉 & = q A D D (| I_{x y} 〉 + | I_{x y} 〉) \\ | ξ_{2} 〉 & = q A D D (| ξ_{1} 〉 + | ξ_{1} 〉) \\ | ϖ 〉 & = q S U B (| μ_{3} 〉 - | ξ_{2} 〉) \end{matrix}

(25)

The processed image is stored in

| ϖ 〉

| I_{\hat{f}} 〉 = \frac{1}{2^{n}} \sum_{X = 0}^{2^{n} - 1} \sum_{Y = 0}^{2^{n} - 1} | f_{ϖ} (Y, X) 〉 | Y X 〉

(26)

Because solving the minimum value of the function consumes too many resources, so, according to Equations (11) and (12), we estimate the minimum of the function

\hat{F}

when the function

\frac{\partial L (\hat{F}, λ)}{\partial \hat{F}}

is equal to 0. According to the frequency domain filtering [26], an estimated expression for an image:

| I_{\hat{F}} 〉 = [\frac{H^{*}}{H^{*} H + γ {| P |}^{2}}] | I_{G} 〉

(27)

| I_{\hat{F}} 〉

is the Fourier transform of the estimation of degraded image.

| I_{G} 〉

is the Fourier transform of fuzzy image. Where

γ

is a parameter that can be adjusted.

H^{*}

is the complex conjugate of H and it represents the Fourier transform of fuzzy matrix. It is worth noting that, if

γ = 0

, the constrained least square filtering can be reduced to inverse filtering.

4. Complexity Analysis

We discuss the simulation analysis of the complexity of implementing quantum circuits and image filtering in this section. In quantum image processing, it is known that the complexity depends on the number of elementary gates in quantum image processing. Consider a digital image with a size of

2^{n}

2^{n}

as an example. The complexity of the basic quantum gate includes NOT gates and controlled NOT gates, which is considered to refer to a n-controlled NOT (n-CNOT) gate that equal to 2(n-1) Toffoli gates and one CNOT gate, and one Toffoli gate can be simulated by six CNOT gates.

From the introduction of Reference [17], we know that the computation complexity of this stage does not exceed

O (q n 2^{2 n})

, because some operations will be performed for each pixel individually. The quantum circuit will construct the NEQR quantum image

| I 〉

When an image is filtered by Laplace operator, the circuit design mainly involves two parts: shift transformation and gradient calculation of pixel points. In total, we use the 4 shift operations to get the pixel values in other locations. In addition, each shift conversion will cost

O (n^{2})

the time complexity by the article [12]. In the light of the Laplace operator template, the complexity of quantum circuit mainly includes 5 addition operations and 1 subtraction operation, which are

8 q - 4

and

3 q^{2}

. The cost of quantum black boxes

U_{L}

module is

2^{q + 3} - 2

Therefore, the quantum cost of image filtering for a

2^{n}

2^{n}

digital image is:

\begin{matrix} q n 2^{2 n} + 4 n^{2} + 5 (8 q - 4) + 3 q^{2} + 2^{q + 3} - 2 \\ = q n 2^{2 n} + 4 n^{2} + 3 q^{2} + 40 q + 2^{q + 3} - 22 \\ = O (q n 2^{2 n} + n^{2} + 2^{q + 3}) \end{matrix}

(28)

Hence, if the quantum image has been constructed, our proposed scheme can restore the quantum image that is based on NEQR, and its computational complexity of around

O (n^{2} + 2^{q + 3})

5. Simulation Experiment

In our simulation, the experiments were conducted on the classic computer with an Intel(R) Core(TM) i5-7500 CPU processor. The environment for the Windows 7 operating system and Matlab(2016a).

The peak signal-to-noise ratio (PSNR) is an objective criterion for evaluating images. It works by using the mean square error (MSE) between the undegraded original image I and the processed image G. In the Formula (30), MAXI is the maximum value in the pixel range.

M S E = \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n - 1} (\frac{{(I (i, j) - G (i, j))}^{2}}{m * n})

(29)

P S N R = 10 \cdot {log}_{10} (\frac{M A X_{I}^{2}}{M S E}) = 20 \cdot {log}_{10} (\frac{M A X_{I}}{\sqrt{M S E}})

(30)

The original input image is shown in the Figure 7. In motion blur functions, offset Angle is 11 and the offset length is 21 (see Figure 8). Gaussian noise can be added to the fuzzy image, as well as the noise density is

0.0001

(see Figure 9). We can calculate PSNR from the Formula (30). The PSNR of the motion blur image and noise-added image are 23.1184 dB and 23.1112dB, respectively. After the model processing (Figure 10), the PSNR of the restored image is 31.6785 dB. Different restoration effects can be seen according to different parameters. When the noise density is small, the algorithm has a good effect on fuzzy restoration, as shown in the Table 1.

6. Conclusions and Prospects

In this paper, quantum image-deblurring algorithm for quantum image with size

2^{n} \times 2^{n}

that is based on constrained least squares filtering is proposed and studied. The quantum circuit we designed based on Laplace operator solves the problem of image blur very well. In terms of the computational complexity, for the NEQR quantum image of size

2^{n} \times 2^{n}

, the quantum circuit that we constructed can recover the image whose computational complexity does not exceed

O (n^{2} + 2^{q + 3})

In fact, under the influence of the surrounding environment, image blurring is a problem that needs to be studied. When compared with classical computers, quantum computers have great advantages. This method can not only effectively remove the fuzzy problem, but also filter out a variety of noise. Image deblurring is always an important research direction in image processing. In the future, we will also study various deblurring problems.

Author Contributions

Conceptualization, S.W.; methodology, H.M. and S.W.; validation, P.X. and S.W.; investigation, S.W. and R.S.; writing—original draft preparation, S.W. and H.M.; writing—review and editing, P.L. and H.M.; visualization, R.S. and P.L. All authors have read and agreed to the published version of the manuscript.

Funding

The work is supported by was supported by the Shandong Province Higher Educational Science and Technology Program (Grant No. J18KZ012), and the National Natural Science Foundation of China (Grant No.11975132,61772295), and the Shandong Provincial Natural Science Foundation, China (Grant No. ZR2019YQ01).

Conflicts of Interest

The authors declare no conflict of interest.

References

Feynman, R.P. Simulating physics with computers. Int. J. Theor. Phys. 1982, 21, 467–488. [Google Scholar] [CrossRef]
Bennett, C.H.; Brassard, G. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, 9–12 December 1984; pp. 175–179. [Google Scholar]
Shor, P.W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November 1994; pp. 124–134. [Google Scholar]
Grover, L. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 22–24 May 1996; pp. 212–219. [Google Scholar]
Ma, H.; Teng, J.; Hu, T.; Shi, P.; Wang, S. Co-communication Protocol of Underwater Sensor Networks with Quantum and Acoustic Communication Capabilities. Wirel. Pers. Commun. 2020, 113, 337–347. [Google Scholar] [CrossRef]
Ma, H.-Y.; Xu, P.-A.; Shao, C.-H.; Chen, L.; Li, J.-X.; Pan, Q. Quantum Private Query Based on Stable Error Correcting Code in the Case of Noise. Int. J. Theor. Phys. 2019, 58, 4241–4248. [Google Scholar] [CrossRef]
Shi, P.; Li, N.; Wang, S.; Liu, Z.; Ren, M.; Ma, H. Quantum Multi-User Broadcast Protocol for the “Platform as a Service” Model. Sensors 2019, 19, 5257. [Google Scholar] [CrossRef] [Green Version]
Teng, J.; Ma, H. Dynamic asymmetric group key agreement protocol with traitor traceability. IET Inf. Secur. 2019, 13, 703–710. [Google Scholar] [CrossRef]
Ma, H.; Zhang, X.; Xu, P.; Liu, F. Quantum Secure Primary Communication Based on Quantum Information Compression. Wirel. Pers. Commun. 2020, 113, 2203–2214. [Google Scholar] [CrossRef]
Venegas-Andraca, S.E.; Ball, J.L. Storing images in engtangled quantum. arXiv 2004, arXiv:quant-ph/0402085. [Google Scholar]
Venegas-Andraca, S.E.; Bose, S. Quantum Computation and Image Processing: New Trends in Artificial Intelligence. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 9–15 August 2003; pp. 1563–1564. [Google Scholar]
Le, P.Q.; Iliyasu, A.M.; Dong, F.; Hirota, K. Fast Geometric Transformations on Quantum Images. Int. J. Appl. Math. 2010, 40, 113–123. [Google Scholar]
Venegas-Andraca, S.E.; Bose, S. Storing, processing, and retrieving an image using quantum mechanics. Int. Soc. Opt. Photonics 2003, 5105, 137–147. [Google Scholar]
Venegas-Andraca, S.E.; Ball, J.L. Processing images in entangled quantum systems. Quantum Inf. Process. 2010, 9, 1–11. [Google Scholar] [CrossRef]
Latorre, J.I. Image compression and entanglement. arXiv 2005, arXiv:quant-ph/0510031. [Google Scholar]
Le, P.Q.; Dong, F.; Hirota, K. A flexible representation of quantum images for polynomial preparation, image compression, and processing operations. Quantum Inf. Process. 2011, 10, 63–84. [Google Scholar] [CrossRef]
Zhang, Y.; Lu, K.; Gao, Y.; Zhang, Y.; Lu, K.; Gao, Y.; Wang, M. NEQR: A novel enhanced quantum representation of digital images. Quantum Inf. Process. 2013, 12, 2833–2860. [Google Scholar] [CrossRef]
Le, P.Q.; Iliyasu, A.M.; Dong, F.; Hirota, K. Strategies for designing geometric transformations on quantum images. Theor. Comput. Sci. 2011, 412, 1406–1418. [Google Scholar] [CrossRef] [Green Version]
Sang, J.; Wang, S.; Li, Q. A novel quantum representation of color digital images. Quantum Inf. Process. 2017, 16, 42. [Google Scholar] [CrossRef]
Li, P.; Liu, X.; Xiao, H. Quantum image median filtering in the spatial domain. Quantum Inf. Process. 2018, 17, 49. [Google Scholar] [CrossRef]
Zhang, Y.; Lu, K.; Xu, K.; Gao, Y.; Wilson, R. Local feature point extraction for quantum images. Quantum Inf. Process. 2015, 14, 1573–1588. [Google Scholar] [CrossRef]
Yuan, S.; Mao, X.; Chen, L.; Wang, X. Improved quantum dilation and erosion operations. Quantum Inf. Process. 2016, 14, 1650036. [Google Scholar] [CrossRef]
Ma, S.Y.; Khalil, A.; Hajjdiab, H.; Eleuch, H. Quantum Dilation and Erosion. Appl. Sci. 2020, 10, 4040. [Google Scholar] [CrossRef]
Liu, K.; Zhang, Y.; Lu, K.; Wang, X. Restoration for noise removal in quantum images. Int. J. Theor. Phys. 2017, 56, 2867–2886. [Google Scholar] [CrossRef]
Song, Q.; Ma, L.; Cao, J.; Han, X. Image Denoising Based on Mean Filter and Wavelet Transform. In Proceedings of the 2015 4th International Conference on Advanced Information Technology and Sensor Application (AITS), Harbin, China, 21–23 August 2015. [Google Scholar]
Caraiman, S.; Manta, V.I. Quantum image filtering in the frequency domain. Adv. Electr. Comput. Eng. 2013, 13, 77–85. [Google Scholar] [CrossRef]

Figure 1. Image degradation process.

Figure 2. Realization of quantum circuits

U_{L}

. On the shifted image set, the gradient is calculated by addition, subtraction, and doubling.

Figure 2. Realization of quantum circuits

U_{L}

. On the shifted image set, the gradient is calculated by addition, subtraction, and doubling.

Figure 3. Quantum circuits of

C (x +)

and

C (y -)

for n-qubit sequence length.

Figure 3. Quantum circuits of

C (x +)

and

C (y -)

for n-qubit sequence length.

Figure 4. Realization of quantum circuit of adder and simplified model. (a) The concrete quantum circuit of adder; (b) Simplified model of adder.

Figure 5. Realization of quantum circuit of subtracter and simplified model. (a) The concrete quantum circuit of the subtracter; (b) A simplified model of a subtracter.

Figure 6. Double operation of the quantum circuit implementation and simplified model. (a) The concrete quantum circuit of doubling operations; (b) A simplified model of doubling operations.

Figure 7. The original image.

Figure 8. Motion blurred image.

Figure 9. Motion blur and noise images.

Figure 10. The restored image after filtering.

Table 1. Average peak signal-to-noise ratio (PSNR) on 100 images by different parameters for image restoration.

Fuzzy Factor (Angle:Length)	PSNR (Fuzzy)	Noise Density	PSNR (Noise)	PSNR (Recovery)
11:21	23.1184	0.0001	23.1112	31.6785
20:22	21.6673	0.008	18.3736	21.5656
10:20	21.8055	0.08	11.8724	21.4558
11:23	21.3195	0.1	11.1295	21.9005

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, S.; Xu, P.; Song, R.; Li, P.; Ma, H. Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation. Entropy 2020, 22, 1207. https://doi.org/10.3390/e22111207

AMA Style

Wang S, Xu P, Song R, Li P, Ma H. Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation. Entropy. 2020; 22(11):1207. https://doi.org/10.3390/e22111207

Chicago/Turabian Style

Wang, Shumei, Pengao Xu, Ruicheng Song, Peiyao Li, and Hongyang Ma. 2020. "Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation" Entropy 22, no. 11: 1207. https://doi.org/10.3390/e22111207

APA Style

Wang, S., Xu, P., Song, R., Li, P., & Ma, H. (2020). Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation. Entropy, 22(11), 1207. https://doi.org/10.3390/e22111207

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Development of High Performance Quantum Image Algorithm on Constrained Least Squares Filtering Computation

Abstract

1. Introduction

2. Preliminaries

2.1. NEQR Model

2.2. Constrained Least Square Filtering Computation

3. Quantum Image Algorithm

3.1. Initialization

3.2. Quantum Circuit Implementation

3.3. Cycle Shift, Addition Subtraction and Double Operation

3.4. Restoration for Deblurring of Quantum Image

4. Complexity Analysis

5. Simulation Experiment

6. Conclusions and Prospects

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI