1 Introduction

Quantum computing is a combination of quantum mechanics and computer science, which could be used to solve the failure of Moore’s law. In 1982, Feynman proposed the quantum computer, whose arithmetic speed much faster than classic ones [1]. Then, Shor designed a quantum integer factoring algorithm in 1994 [2] and Grover explored a database searching algorithm in 1996 [3], quantum computer has been demonstrated a bright prospect over the classic computer.

Quantum image processing (QImP) is a branch of quantum information processing, which developed relatively late. Recent years, various quantum representation models have been proposed. The first quantum image representation model of qubit lattice was proposed in 2003, which using one qubit to hold one pixel [4]. Then, entangled images [5] and Real Kat [6] were proposed consecutively. In 2011, Le et al. [7] proposed a flexible representation of quantum images (FRQI), which using a normalized state to capture information about colors and their corresponding positions in the images. The FRQI representation requires 2n + 1 qubits for representing a 2n × 2n image. In 2013, a novel enhance quantum representation (NEQR) was proposed by Zhang et al. [8], which used q qubits encoding the color information. Following years, more quantum image representations were proposed, such as normal arbitrary quantum superposition state (NAQSS) [9], improved novel enhanced quantum representation (INEQR) [10] and generalized quantum image representation (GQIR) [11]. The GQIR can represent quantum images having H × W pixels where H and W can be any arbitrary integer number by modifying the position information of NEQR. QImPs are increasingly moving toward more and more convenient to manipulate and restore images, despite there are various representation models.

Edge extraction is an essential task in digital image processing. In an image, the edges are the pixels where the gray level changes rapidly [12]. Based on features of edges, there are some famous edge extraction algorithms were proposed such as Sobel [13], Prewitt [14], Kirsch [15] and Canny [16]. Recent years, several quantum edge extraction algorithms were proposed based on above quantum image representation models. In 2015, Zhang et al. [17] proposed QSobel algorithm based on FRQI, which could resolve the real-time problem of image edge extraction. Then, Fan et al. [18] proposed a quantum image edge extraction based on classical sobel operator for NEQR, they provided an integrated quantum circuit realization to implement quantum image edge extraction for a 2n × 2n quantum image based on a series of quantum computation modules.

This paper is organized as follows. In Section 2, the generalized quantum image representation (GQIR) and improved classical sobel operator are reviewed and quantum modules used in circuit are stated. The quantum image edge extraction based on improved sobel operator for GQIR is designed in Section 3. Experimental results and analysis are given in Section 4. Finally, we draw conclusions in Section 5.

2 Related Works

2.1 The Generalized Quantum Image Representation (GQIR)

GQIR model [11] was improved by NEQR, and it used to store arbitrary integer numbers H × W quantum images. ⌈log2H⌉ + ⌈log2W⌉ + q qubits are needed to represent a H × W image.

A H × W image can be written as blew

$$ {\displaystyle \begin{array}{l}\mid I\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}{\otimes}_{i=0}^{q-1}\mid {C}_{YX}^i\right\rangle \mid YX\Big\rangle \\ {}\mid YX\left\rangle =\mid Y\right\rangle \mid X\left\rangle =\mid {y}_0{y}_1\cdots {y}_{h-1}\right\rangle \mid {x}_0{x}_1\cdots {x}_{w-1}\Big\rangle, {y}_i,{x}_i\in \left\{0,1\right\}\\ {}\mid {C}_{YX}\left\rangle =\mid {C}_{YX}^0{C}_{YX}^1\cdots {C}_{YX}^{q-1}\right\rangle, {C}_{YX}^i\in \left\{0,1\right\}\end{array}} $$
(1)

where

$$ h=\left\{{\displaystyle \begin{array}{l}\left\lceil {\log}_2H\right\rceil, H>1\\ {}1,\kern3.25em H=1\end{array}},w=\right\{{\displaystyle \begin{array}{l}\left\lceil {\log}_2W\right\rceil, W>1\\ {}1,\kern3.25em \mathrm{W}=1\end{array}} $$
(2)

∣YX⟩ is the location information and ∣CYX⟩ is the color information.

Figure 1 shows a 1 × 3 gray-scale image and its representation expression in GQIR. The 1 × 3 gray-scale image put into a 2 × 4 box.

Fig. 1
figure 1

An example image and its GQIR

Full size image

2.2 Improved Classic Sobel Algorithm

Sobel operator [13] is one of the most widely used image edge extraction, which is an essential issue of digital image processing. Sobel operator utilizes the pixel neighborhood window to calculate approximations of the gradient of the image intensity. The pixel neighborhood window is shown in Fig. 2a. Classic sobel operator contains two 3 × 3 masks, which are shown in Fig. 2b and Fig. 2c, to calculate the two approximations of the derivatives.

Fig. 2
figure 2

(a) The pixel neighborhood window. (b), (c), (d) and (e) are four masks of improved sobel algorithm

Full size image

However, sobel operator only responds well to the vertical and horizontal edges, it is difficult to detect the edges along the diagonal directions. Improved sobel algorithm increases two masks to detect the diagonal edges. Figure 2b, c, d, e show the vertical, horizontal, +45∘ and −45∘ masks respectively.

The approximations of the gradient of four directions can be calculate by following formulas.

$$ {\displaystyle \begin{array}{l}{G}_x=\left[\begin{array}{ccc}-1& -2& -1\\ {}0& 0& 0\\ {}1& 2& 1\end{array}\right]\ast p,{G}_y=\left[\begin{array}{ccc}-1& 0& 1\\ {}-2& 0& 2\\ {}-1& 0& 1\end{array}\right]\ast p\\ {}{G}_{45}=\left[\begin{array}{ccc}0& 1& 2\\ {}-1& 0& 1\\ {}-2& -1& 0\end{array}\right]\ast p,{G}_{-45}=\left[\begin{array}{ccc}-2& -1& 0\\ {}-1& 0& 1\\ {}0& 1& 2\end{array}\right]\ast p\end{array}} $$
(3)

therein, Gx, Gy, G45 and G−45 represent the image gradient value detected by the vertical, horizontal, +45∘ and −45∘ diagonal edges, respectively; p represents the pixel neighborhood window.

The specific calculation of Eq.(3) can be denoted by Eq.(4)-Eq.(7).

$$ {\displaystyle \begin{array}{c}{G}_x=p\left(Y-1,X+1\right)+2p\left(Y,X+1\right)+p\left(Y+1,X+1\right)\\ {}-p\left(Y-1,X-1\right)-2p\left(Y,X-1\right)-p\left(Y+1,X-1\right)\end{array}} $$
(4)
$$ {\displaystyle \begin{array}{c}{G}_y=p\left(Y+1,X-1\right)+2p\left(Y+1,X\right)+p\left(Y+1,X+1\right)\\ {}-p\left(Y-1,X-1\right)-2p\left(Y-1,X\right)-p\left(Y-1,X+1\right)\end{array}} $$
(5)
$$ {\displaystyle \begin{array}{c}{G}_{45}=p\left(Y-1,X\right)+2p\left(Y-1,X+1\right)+p\left(Y,X+1\right)\\ {}-p\left(Y,X-1\right)-2p\left(Y+1,X-1\right)-p\left(Y+1,X\right)\end{array}} $$
(6)
$$ {\displaystyle \begin{array}{c}{G}_{-45}=p\left(Y,X+1\right)+2p\left(Y+1,X+1\right)+p\left(Y+1,X\right)\\ {}-p\left(Y-1,X\right)-2p\left(Y-1,X-1\right)-p\left(Y,X-1\right)\end{array}} $$
(7)

The gradient of each pixel is the maximum value of absolute value of its four directions gradient values, it is shown in Eq.(8).

$$ G=\max \left\{|{G}_x|,|{G}_y|,|{G}_{45}|,|{G}_{-45}|\right\} $$
(8)

By comparing with a gradient threshold T, a pixel will be considered as a part of edge when G ≥ T.

2.3 Quantum Modules

In this subsection, a series of specific quantum modules used in the quantum image edge extraction are introduced, which include the parallel full adder (PA), the parallel full subtractor (PS), X-Shift transformation C(x±), Y-shift transformation C(y±), quantum duplicate operation Ud, quantum comparison operation and threshold operation UT.

2.3.1 Reversible Parallel Adder (PA)

The reversible parallel adder [19] implements the addition of n qubits Y = yn − 1yn − 2⋯y0 and n qubits X = xn − 1xn − 2⋯x0. As shown in Figure 3, it is composed by one reversible half adder (RHA) module and n-1 reversible full adder (RFA) modules. More details about RHA module and RFA module are described in Ref. 15.

Fig. 3
figure 3

(a) Reversible parallel adder. (b) The simplified graph of PA

Full size image

2.3.2 Reversible Parallel Subtractor (PS)

The reversible parallel subtractor [20, 21] implements the subtraction of n qubits Y = yn − 1yn − 2⋯y0 and n qubits X = xn − 1xn − 2⋯x0. As shown in Figure 4, it is composed by one reversible half subtractor (RHS) module and n-1 reversible full subtractor (RFS) modules. More details about RHS module and RFS module are described in Ref. 16.

Fig. 4
figure 4

(a) Reversible parallel subtractor. (b) The simplified graph of PS

Full size image

It should be noted that the difference dndn − 1⋯d1d0 shown in Figure 4 is a complement code form of X − Y. Therein, dn is the sign bit of the difference. In other words, if dn = 0, X − Y ≥ 0; Otherwise, X − Y < 0.

As shown in Figure 5, a quantum black box UR was designed by Fan et al. [18] to calculate the absolute value of X − Y.

Fig. 5
figure 5

(a) The quantum circuit of UR. (b) The simplified graph of UR

Full size image

2.3.3 X-Shift and Y-Shift Transformations

For the model of GQIR, every pixel is represented as a basis state of the quantum superposition. The position transformation will be computed simultaneously for all pixels in the image. Le et al. [22] defined the cyclic shift transformation. Every pixel will access the information of its neighborhood simultaneously by shifting the whole image. The X-Shift and Y-Shift transformations based on the cyclic shift transformation for a GQIR image with a size of H × W is described as follows.

The two transformations are defined in Eq.(9).

$$ {\displaystyle \begin{array}{l}T\left(x\pm \right)\mid I\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}\mid {C}_{YX}\right\rangle \mid Y\left\rangle \mid \left(X\pm 1\right)\operatorname{mod}{2}^{\left\lceil {\log}_2W\right\rceil}\right\rangle \\ {}T\left(y\pm \right)\mid I\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}\mid {C}_{YX}\right\rangle \mid \left(Y\pm 1\right)\operatorname{mod}{2}^{\left\lceil {\log}_2H\right\rceil}\left\rangle \mid X\right\rangle \end{array}} $$
(9)

By using X to replace X ± 1 and Y to replace Y ± 1, we can gain the relationships as Eq.(10).

$$ {\displaystyle \begin{array}{l}T\left(x\pm \right)\mid I\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}\mid {C}_{YX\hbox{'}}\right\rangle \mid Y\left\rangle \mid X\right\rangle \\ {}T\left(y\pm \right)\mid I\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}\mid {C}_{Y\hbox{'}X}\right\rangle \mid Y\left\rangle \mid X\right\rangle \end{array}} $$
(10)

where \( {X}^{\prime }=\left(X\mp 1\right)\ \mathit{\operatorname{mod}}\ {2}^{\left\lceil {\log}_2W\right\rceil } \) and \( {Y}^{\prime }=\left(Y\mp 1\right)\ \mathit{\operatorname{mod}}\ {2}^{\left\lceil {\log}_2H\right\rceil } \).

Figure 6 give the quantum circuit diagram of T(x+) and T(x−). T(y+) and T(y−) are similar with T(x+) and T(x−).

Fig. 6
figure 6

Quantum circuit of T(x+) and T(x-)

Full size image

2.3.4 Quantum Duplicate Operator U d

Eq.(11) defines the quantum duplicate operator, which can copy a q-length qubit sequence information of ∣C⟩ =  ∣ cq − 1cq − 2⋯c0⟩ into a q ancillary qubits ∣0⟩⊗q. The quantum duplicate operator Ud is shown in Fig. 7.

Fig. 7
figure 7

(a) Quantum circuit of Ud. (b) The simplified graph of Ud

Full size image
$$ {U}_d\left(|C\Big\rangle |0\Big\rangle {}^{\otimes n}\right)=\mid C\left\rangle \mid C\right\rangle $$
(11)

2.3.5 Quantum Comparison Operation

Quantum comparison operation can compare two number and output the larger one. Firstly, the quantum bit string comparator(QBSC) [23] was introduced.

Given two n-partite of qubits quantum states ∣a⟩ ∣ b⟩, the quantum bit string comparator is shown in Eq.(12).

$$ {U}_C=\mid a\left\rangle \mid b\right\rangle \mid 0\left\rangle {}^{\otimes l}\mid 0\right\rangle \mid 0\left\rangle =\mid a\right\rangle \mid b\left\rangle \mid \varphi \right\rangle \mid x\left\rangle \mid y\right\rangle $$
(12)

In above equation, there are l + 2 ancillary qubits initialized as state of ∣0⟩, ∣φ⟩ is a l qubits output state with unimportant information and the last two qubits carry the result of comparison. If a = b, then x = y = 0; if a < b, then x = 1,  y = 0; if a > b, then x = 0,  y = 1. The comparative result can be obtained by measuring the last two qubits ∣X⟩ ∣ Y⟩. The quantum circuit of QBSC for two 3-qubits strings is shown in Fig. 8.

Fig. 8
figure 8

(a) Quantum circuit of QBSC for two 3-qubits strings. (b) Quantum circuit of UC

Full size image

As shown in Fig. 9, quantum comparison(QC) module is designed based on QBSC, which can compare two q qubits strings and output the larger one. The simplified graph of QC is shown in Fig. 10.

Fig. 9
figure 9

Quantum circuit of QC

Full size image
Fig. 10
figure 10

Simplified graph of QC

Full size image

2.3.6 Quantum Threshold Operator U T

Fan et al. [18] proposed the quantum threshold operator to make the classification for the (q + 3)-length qubit sequence. All the (q + 3)-length qubit sequence value less than T belong to one group and left are in the other group by setting a threshold value T. As shown in Eq.(13), this scheme needs an auxiliary qubit to store the result of the classification. Generally, the highest few qubits are used to be controllers. Figure 11 shows the quantum circuit of the quantum threshold operator UT.

Fig. 11
figure 11

(a) The quantum circuit of UT. (b) The simplified graph of UT

Full size image
$$ \mid {C}_{q+2}{C}_{q+1}\cdots {C}_1{C}_0\left\rangle \mid 0\right\rangle $$
(13)

3 Quantum Image Edge Extraction Based on Improved Sobel Operator for GQIR

In this section, the concrete quantum circuit realization of quantum image edge extraction based on improved sobel operator for GQIR will be introduced.

3.1 Mask Computation of Improved Sobel

In this subsection, we will utilize the quantum modules introduced in Sec.2.3 to calculate the intensity gradients of the pixels in a quantum image simultaneously on the basis of improved sobel masks and the 3 × 3 neighborhood window of every pixel.

Firstly, the color information of every pixel of its 3 × 3 neighborhood window can be obtained simultaneously by ranging the X-Shift and Y-Shift transformations in a serious of certain operations. Extra eight identical quantum images ∣Iyx⟩ are prepared before the operations. The computation prepared operators as shown in Table 1 can do this task.

Table 1 Computation prepared operators
Full size table

Then, we utilize the improved sobel mask to calculate the approximately gradient according to Eq.(4)–(7). Figure 2b–e show the improved sobel mask on four directions, respectively. A quantum black box UG is designed to calculate the absolute value of approximate gradient of four directions for every pixels as defined Eq.(14) based on improved sobel operator, which utilizes the color information qubits of the neighborhood pixels obtained in computation prepared algorithm. Figure 12 shows the function of the quantum black box UG. The concrete quantum circuit realization of UG is shown in Fig. 13.

$$ {\displaystyle \begin{array}{l}\mid \mid {G}_x\Big\rangle \mid =\mid \begin{array}{l}\left(2|{C}_{Y,X+1}\Big\rangle +|{C}_{Y-1,X+1}\Big\rangle +|{C}_{Y+1,X+1}\Big\rangle \right)\\ {}-\left(2|{C}_{Y,X-1}\Big\rangle +|{C}_{Y-1,X-1}\Big\rangle +|{C}_{Y+1,X-1}\Big\rangle \right)\end{array}\mid \\ {}\mid \mid {G}_y\Big\rangle \mid =\mid \begin{array}{l}\left(2|{C}_{Y+1,X}\Big\rangle +|{C}_{Y+1,X-1}\Big\rangle +|{C}_{Y+1,X+1}\Big\rangle \right)\\ {}-\left(2|{C}_{Y-1,X}\Big\rangle +|{C}_{Y-1,X-1}\Big\rangle +|{C}_{Y-1,X+1}\Big\rangle \right)\end{array}\mid \\ {}\mid \mid {G}_{45}\Big\rangle \mid =\mid \begin{array}{l}\left(2|{C}_{Y-1,X+1}\Big\rangle +|{C}_{Y-1,X}\Big\rangle +|{C}_{Y,X+1}\Big\rangle \right)\\ {}-\left(2|{C}_{Y+1,X-1}\Big\rangle +|{C}_{Y,X-1}\Big\rangle +|{C}_{Y+1,X}\Big\rangle \right)\end{array}\mid \\ {}\mid \mid {G}_{-45}\Big\rangle \mid =\mid \begin{array}{l}\left(2|{C}_{Y+1,X+1}\Big\rangle +|{C}_{Y,X+1}\Big\rangle +|{C}_{Y+1,X}\Big\rangle \right)\\ {}-\left(2|{C}_{Y-1,X-1}\Big\rangle +|{C}_{Y-1,X}\Big\rangle +|{C}_{Y,X-1}\Big\rangle \right)\end{array}\mid \end{array}} $$
(14)
Fig. 12
figure 12

The quantum black box UG

Full size image
Fig. 13
figure 13

Quantum circuit of quantum edge extraction

Full size image

At last, we can get the intensity gradient of every pixel based on Eq.(8). Figure 14 shows the quantum circuit realization of it.

Fig. 14
figure 14

Quantum circuit of intensity gradient of image

Full size image

3.2 Circuit Realization for Quantum Image Edge Extraction

In this subsection, based on the X-Shift transformation, Y-Shift transformation, quantum black box UG, quantum comparison operation and threshold operator UT, we designed the quantum circuit realization of quantum image edge extraction. The concrete quantum circuit can be sectionalized to 3 steps. As shown in Fig. 15, it realizes the quantum image edge extraction for an image with size of H × W.

Fig. 15
figure 15

Quantum circuit of improved sobel edge extraction for GQIR

Full size image
  1. Step 1:

    Obtain the color information of every pixel of its 3 × 3 neighborhood window. Firstly, the digital image should be quantized into a GQIR quantum image with size of H × W as Eq.(1). We need a (⌈log2H⌉ + ⌈log2W⌉ + q)-qubits sequence to store the quantum image. At the same time, 8 extra (⌈log2H⌉ + ⌈log2W⌉ + q)-qubits sequences are needed to store the identical quantum images. After performing the computation prepared operations, we can obtain the neighborhood pixels of every pixels except the outermost pixels of the quantum image. After this step, we can obtain the quantum image set as defined in Eq.(15).

$$ \left\{\begin{array}{c}\mid {I}_{YX}\left\rangle, \mid {I}_{Y+1X}\right\rangle, \mid {I}_{YX-1}\left\rangle, \mid {I}_{Y-1X}\right\rangle, \mid {I}_{YX+1}\Big\rangle, \\ {}\mid {I}_{Y-1X-1}\left\rangle, \mid {I}_{Y-1X+1}\right\rangle, \mid {I}_{Y+1X-1}\left\rangle, \mid {I}_{Y+1X+1}\right\rangle \end{array}\right\} $$
(15)
  1. Step 2:

    Calculate the image intensity gradient. The image intensity gradient can be calculated using the quantum image sets obtained in step 1 through the quantum black box UG. After the operator UG, the calculated intensity gradient ∣G⟩ ∈ [0, 2q + 3 − 1] in the abstract, so we need a (q + 3)-qubits sequence to store the image intensity gradient information. It is worth noting that the outermost pixels of the image will be set to 0 because of the lack of neighbor pixels.

  2. Step 3:

    Perform the threshold operator. In the resulting quantum image, the color qubit state will be ∣1⟩ if the pixel in the edges, which represent white. On the contrary, it will be ∣0⟩ if the pixels not in the edges, which mean black. In this step, a certain threshold value T will be set to make the classification for the ∣G⟩ through the quantum threshold operator UT. As shown in Eq.(16), all the gradient values of pixels less than T belong to one group, the others pixels belong to the other group.

$$ {U}_T\left(\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}|{G}_{YX}\Big\rangle |0\Big\rangle \right)=\frac{1}{{\sqrt{2}}^{h+w}}\left(\sum \limits_{G_{YX}\ge T}|{G}_{YX}\Big\rangle |1\Big\rangle +\sum \limits_{G_{YX}<T}|{G}_{YX}\Big\rangle |0\Big\rangle \right) $$
(16)

Therefore, the result of quantum image edge extraction based on improved sobel operator can be obtained through the above steps, which is defined as Eq.(17).

$$ \mid result\left\rangle =\frac{1}{{\sqrt{2}}^{h+w}}\sum \limits_{Y=0}^{H-1}\sum \limits_{X=0}^{W-1}\mid {r}_{YX}\right\rangle \mid 0\Big\rangle, {r}_{YX}\in \left\{0,1\right\} $$
(17)

4 Circuit Complexity and Simulation Experiment

In this section, the circuit complexity of our scheme is given. Then, the simulation experiment is performed to show effect of the quantum edge extraction.

4.1 Circuit Complexity

In quantum information processing, the circuit complexity depends on the number of elementary gates used. Firstly, the complexity of a series of quantum operators used in the quantum circuit shown in Fig. 15 are analyzed as follows.

A reversible parallel adder(PA) is composed of 1 RHA and q − 1 RFA, which realizes the addition of two q qubits sequences. The quantum cost of RHA and RFA is 4 and 8, respectively. Hence, the quantum cost of single PA is 8q − 4.

A reversible parallel subtractor(PS) is composed of 1 RHS and q − 1 RFS, which realizes the subtraction of two q qubits sequences. The quantum cost of RHS and RFS is 5 and 7, respectively. Hence, the quantum cost of single PA is 7q − 1.

The quantum black box UR is used to calculate the absolute value of a q + 3 qubits sequence. It is composed of q + 3 CNOT gates and q + 1 multi-Control-Not gates. According to Ref. [24], the quantum cost of quantum black box UR is 2q + 3 − 2.

The quantum shift transformation is used to shift the whole image. According to the discussion of complexity of quantum shift transformations in Ref. [22], a single X-Shift or Y-Shift cost no more than O(n2) for n qubits sequence.

Every quantum duplicate operator costs O(q).

Quantum comparison operation(QC) is composed of q UC modules, 2q Toffoli gates, q 2-CNOT gates(all the control qubits’ state are ∣0⟩), q 2-CNOT gates(a control qubit’s state is ∣0⟩) and q 3-CNOT gates(a control qubit’s state is ∣0⟩). The UC module is composed of 4 NOT gates and 2 Toffoli gates. Hence, the cost of a QC is 69q.

The quantum threshold operator UT is composed of at most q CNOT gates to make classification for a q qubits sequence. According to the discussion of Ref. [22], the cost of a quantum threshold operator no more than O(q2).

To sum up, the complexity of the whole framework shown in Fig. 15 consisting of 12 quantum shift transformation models, 16 PA modules, 4 PS modules, 4 quantum black box UR, 2 quantum duplicate operators, 3 QC modules and 1 quantum threshold operator UT is shown in Eq.(18).

$$ {\displaystyle \begin{array}{c}12{n}^2+16\left(8q-4\right)+4\left(7q-1\right)+4\left({2}^{q+3}-2\right)+2q+3\times 69q+{q}^2\\ {}=12{n}^2+{2}^{q+5}+{q}^2+363q-76\\ {}=O\left({n}^2+{2}^{q+5}+{q}^2\right)\end{array}} $$
(18)

The circuit complexity comparisons between our scheme and other edge extraction algorithms including two classic algorithm and two existing quantum edge extraction algorithm are shown in Table 2. Our scheme has a lower circuit complexity than classical edge extraction algorithms and quantum edge extraction algorithm based on qubit lattice [25], and near to quantum edge extraction algorithm based on FRQI [17].

Table 2 The complexity comparisons between our scheme and other edge extraction algorithms
Full size table

4.2 Simulation Experiment

Our proposed quantum image edge extraction is simulated by MATLAB 2017 in a classical computer. As is shown in Figs. 16 and 17, we chose two images to test our scheme. In the two images, (a) represents the original image, (b), (c), (d) and (e) represent the vertical, horizontal, +45∘ and −45∘ diagonal edges respectively, (f) represent the result image of our proposed quantum edge extraction algorithm.

Fig. 16
figure 16

The result images of quantum edge extraction for Lena image

Full size image
Fig. 17
figure 17

The result images of quantum edge extraction for House image

Full size image

The results show that our proposed scheme can detect image edge successfully. And it has a better performance to detect image edges than other exist edge extraction algorithm, especially to detect diagonal edges. In foreseeable future, our proposed scheme will show its excellent performance in a real quantum computer.

5 Conclusion

In this paper, a new quantum image edge extraction based on classical sobel edge extraction and its improved mask for GQIR model is proposed. Through the quantum circuit, our scheme can extract four directional edges for a GQIR image with the size of H × W. Compared with classical edge extraction algorithm, our scheme can reach an exponential speedup. And it has a better effect compared with other existing quantum image edge extraction algorithms especially for diagonal edges. Our future work will focus on designing more efficient and practical edge extraction algorithm for quantum image.