Similarity assessment of quantum images

Abstract

Similarity assessment of quantum images is important in the area of quantum image processing. In this paper, quantum counting is applied to five algorithms for similarity assessment of quantum images, which brings an advantage to the number of quantum measurement. Among these algorithms, one algorithm is suitable for quantum binary image, two algorithms are suitable for quantum gray image and two algorithms are suitable for quantum color images. Moreover, the similarity assessment of quantum gray and color images involves two quantum image binarization algorithms. At the end of the paper, the quantum circuit complexity of these algorithms is analyzed and then an example is given to demonstrate the functionality of the algorithm.

1 Introduction

Quantum image processing (QIP) is the fusion of quantum computation and digital image processing. It has some advantages in the aspects of storage and processing compared with classical image processing (CIP), which attracts attention from many researchers with different backgrounds.

Two important areas of research for quantum image processing are quantum image representation and quantum image processing algorithms. The former researches how to store an image on a quantum computer and the latter is concerned with the development of algorithms to perform quantum image processing tasks. Le et al. [1] proposed the flexible representation for quantum images (FRQI) in 2010, then it was revised in 2011 [2]. Due to the inconvenience in color processing and retrieval of quantum image in FRQI, Zhang et al. [3] introduced a novel-enhanced quantum representation of digital image model (NEQR) in 2013. Sang et al. [4] presented a novel quantum representation of color digital images (NCQI) in 2016. Li et al. [5] proposed an (n + 1)-qubit normal arbitrary quantum superposition state (NAQSS) to represent a multidimensional color image. Other quantum image representations have been also proposed and they are summarized in Ref. [6]. Based on these quantum image representations, many quantum image processing algorithms have been developed, e.g., image geometric transformations [7,8,9,10], image watermarking [11,12,13,14,15], image scaling [16,17,18,19,20], image matching [21,22,23,24] and image edge detection [25, 26].

To the best of our knowledge, the researches on similarity comparison of quantum images are relatively subtle. Yan et al. [27] introduced a method to analyze the similarity of two quantum images of the same size based on FRQI in 2012. The similarity value is estimated according to the probability distribution of the results from quantum measurements. However, to assess the similarity of quantum images, many copies of the quantum states must be prepared and measured to construct a histogram. Zhou et al. [28] introduced a scheme for quantum multidimensional color images in 2014. The scheme is similar to Yan F et al.’s scheme. Yang et al. [21] presented a quantum grayscale image matching scheme in which a quantum template image is directly mapped with a quantum reference image, i.e., the quantum register representing each corresponding pixel of the quantum template image is subtracted from that of the quantum reference image by a quantum subtractor. According to the quantum measurement results, the difference is saved and all the differences are summed. Then, the sum is compared with a tolerance value. If the sum is smaller than the tolerance value, then the quantum image matching succeeds. The scheme is based on NEQR and determines whether the two quantum images under consideration are similar. Nevertheless, it has several shortcomings: (1) using quantum subtractor to determine whether the gray value of the pixels of two quantum images is equal is inefficient. (2) to acquire all the differences, processing and measurements based on NEQR are performed many times.

Based on quantum counting, we propose five algorithms in this paper for similarity assessment of quantum images. In addition, two quantum image binarization algorithms are involved in the similarity assessment of quantum gray and color images.

The contributions of this paper include:

• Apply quantum amplitude amplification and estimation to quantum image processing;

• Design the quantum implementation circuit of quantum gray and color images binarization;

• Design the quantum implementation circuit of similarity assessment of quantum images.

This paper is organized as follows. Two quantum image representations (NEQR, NCQI), quantum counting and quantum arithmetic operation are introduced in Sect. 2. An algorithm of similarity assessment of quantum binary images is proposed in Sect. 3. Two algorithms of assessing the similarity of two quantum gray images and two algorithms of assessing the similarity of two quantum color images are proposed in Sect. 4. In Sect. 5, quantum circuit complexity of these algorithms is analyzed and an example is given. In Sect. 6, these algorithms are compared with the other quantum algorithms. In Sect. 7, the conclusion and future works are given.

2 Theoretical background

Some theoretical background, two quantum image representations (NEQR, NCQI), quantum amplitude amplification and estimation and quantum arithmetic operation are reviewed in this section.

2.1 A novel-enhanced quantum representation of digital image model (NEQR)

Zhang et al. [3] proposed a novel-enhanced quantum representation of digital image (NEQR) to store a gray image of size $2^{n} \times 2^{n}$ and gray range $2^{q}$. Its modularized reversible circuit is illustrated in Fig. 1 and quantum representation can be written as

$$ \begin{aligned} \left| {\psi_{g} } \right\rangle & = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| y \right\rangle \left| x \right\rangle \left| {c_{yx} } \right\rangle } } \\ & { = }\frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| y \right\rangle \left| x \right\rangle \left| {c_{q - 1} c_{q - 2} \cdots c_{0} } \right\rangle } } \\ \end{aligned} $$

(1)

where $\left. {|y} \right\rangle |\left. x \right\rangle$ represents a pixel’s coordinate information and $\left. {|c_{yx} } \right\rangle$ represents a pixel’s color information.

Fig. 1

Modularized reversible circuit of NEQR

2.2 A novel quantum representation of color digital images (NCQI)

Sang et al. [4] proposed a novel quantum representation of color digital images (NCQI) to store a color image of size $2^{n} \times 2^{n}$. Its modularized reversible circuit is illustrated in Fig. 2 and quantum representation can be written as

$$ \begin{aligned} \left| {\psi_{c} } \right\rangle & = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| y \right\rangle \left| x \right\rangle \left| {c_{yx} } \right\rangle } } \\ {\kern 1pt} & = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| y \right\rangle \left| x \right\rangle \left| {\underbrace {{R_{q - 1} \cdots R_{0} }}_{\text{Red}}\underbrace {{G_{q - 1} \cdots G_{0} }}_{\text{Green}}\underbrace {{B_{q - 1} \cdots B_{0} }}_{\text{Blue}}} \right\rangle } } \\ \end{aligned} $$

(2)

where $\left. {|y} \right\rangle \left. {|x} \right\rangle$ represents a pixel’s coordinate information and $\left| {c_{yx} } \right\rangle$ represents a pixel’s color information.

Fig. 2

Modularized reversible circuit of NCQI

2.3 Quantum amplitude amplification and estimation

Brassard et al. [29] introduced quantum amplitude amplification and estimation, which can realize quantum counting.

Quantum amplitude amplification is a process that allows finding a good solution. It can be realized by repeatedly applying a unitary transformation $Q = - \varsigma S_{0} \varsigma^{ - 1} S_{\chi }$, where $\chi$ represents a Boolean function that partitions the set $X$ into good and bad solutions, $S_{\chi }$ is a unitary transformation that changes the sign of the amplitudes of the good solutions, $S_{0}$ is a unitary transformation that changes the sign of the amplitude if and only if quantum states are the zero state, $\varsigma$ is any quantum algorithm that acts on the initial zero states and uses no measurements and $\varsigma^{ - 1}$ is the reverse transformation. Figures 3 and 4, respectively, illustrate the framework of quantum implementation circuit of the unitary transformation $Q$ and quantum amplitude amplification.

Fig. 3

Framework of quantum implementation circuit of the unitary transformation $Q$. a The implementation circuit. b The abbreviation notation of the circuit in a

Fig. 4

Framework of quantum implementation circuit of quantum amplitude amplification. a The implementation circuit. b The abbreviation notation of the circuit in a

Algorithm 1 Est_Amp ( $\varvec{\varsigma },\varvec{\chi},\varvec{M}$ )

• 1. Initialize two registers of appropriate sizes to the state $\left| 0 \right\rangle^{ \otimes m} \varsigma \left| 0 \right\rangle^{ \otimes n}$;

• 2. Apply $F_{M}$ to the first register;

• 3. Apply $\varLambda_{M} \left( Q \right)$ where $Q = - \varsigma S_{0} \varsigma^{ - 1} S_{\chi }$;

• 4. Apply $F_{M}^{ - 1 }$ to the first register;

• 5. Measure the first register and denote the outcome $res$;

• 6. Output $\tilde{a} = \sin^{2} \left( {\pi *res/M} \right)$.

  where $M = 2^{m}$, $F_{M}$ represents quantum Fourier transformation, $F_{M}^{ - 1}$ represents the inverse transformation and the unitary transformation $\varLambda_{M} \left( Q \right)$ is defined as

$$ \varLambda_{M} \left( Q \right):\left| j \right\rangle \left| y \right\rangle \to \left| j \right\rangle \left( {Q^{j} \left| y \right\rangle } \right),\;\left( {0 \le j < M} \right). $$

(3)

Quantum amplitude estimation is a process that allows estimating amplitude. It can be realized by Algorithm 1. As illustrated in Fig. 5, there are two registers in the framework of quantum implementation circuit of quantum amplitude estimation. The first register contains $t = m + { \lceil }\log \left( {2 + 1/2\varepsilon } \right){ \rceil }$ qubits where m qubits represent the accuracy and the probability of success is at least $1 - \varepsilon$. The second register contains $n + 1$ qubits, enough to implement quantum amplitude amplification on the augmented search space.

Fig. 5

Framework of quantum implementation circuit of quantum amplitude estimation, which contains the first step to the fifth step. a The implementation circuit. b The abbreviation notation of the circuit in a

A straightforward application of quantum amplitude amplification and estimation is to approximately count the number of solutions $tg$. An estimate for $tg$, $tg'$ can be calculated by $tg^{'} = 2^{n} *Est\_Amp\left( {\varsigma ,\chi ,M} \right)$.

2.4 Quantum arithmetic operation

Quantum arithmetic operation includes addition, subtraction, multiplication and division. Here, quantum adder and quantum divider are simply introduced. More detailed information can refer to [30, 31].

Quantum adder [30] can add an n-qubit sequence to another n-qubit sequence. Figure 6 illustrates the modularized reversible circuit of a quantum adder, where $\left| a \right\rangle$, $\left| b \right\rangle$ are the inputs and $\left| a \right\rangle$, $\left| {a + b} \right\rangle$ are the outputs.

Fig. 6

Modularized reversible circuit of a quantum adder

Quantum divider [31] is based on the restoring division algorithm. Through using quantum Fourier transform, quantum divider could be easily generalized for the case of any arbitrary values of dividend and divisor. Figure 7 illustrates the modularized reversible circuit of a quantum divider, where some ancillary inputs and garbage outputs are omitted.

Fig. 7

Modularized reversible circuit of a quantum divider

3 Similarity assessment of quantum binary images

Algorithm 2 Similarity assessment of quantum binary images based on pixel value comparison (SAB_PV)

• 1. Store two binary images in a quantum system by using a unitary transformation ${\text{BTB}}$;

• 2. Compare the pixel values of two quantum binary images one by one;

• 3. Apply Algorithm Est_Amp where the output is represented by $\tilde{a}$;

• 4. Calculate the number of same pixels $\tilde{t} = 2^{2n} \times \tilde{a}$ where $2^{2n}$ is the size of the image;

• 5. Calculate the similarity $p = \tilde{t}/2^{2n}$.

Algorithm 2 assesses the similarity of quantum binary images by pixel value comparison. Next, its quantum implementation process is described as follows.

Define the unitary transformation ${\text{BTB}}$ as

$$ \left| 0 \right\rangle^{ \otimes 2n + 2} \mathop \to \limits^{BTB} \left| {\psi_{b} } \right\rangle = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| {yx} \right\rangle \left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} } \right\rangle } } . $$

(4)

As illustrated in Fig. 8, $2n + 2$ qubits and two unitary transformations NEQR are used in the quantum implementation circuit. The first $2n$ qubits are used to store two binary images’ coordinate information and the next two qubits are used to store two binary images’ color information. After applying ${\text{BTB}}$, two binary images can be stored in a quantum system.

Fig. 8

Quantum implementation circuit of the unitary transformation ${\text{BTB}}$. a The implementation circuit. b The abbreviation notation of the circuit in a

Define the unitary transformation ${\text{CP}}$ as

$$ \left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} } \right\rangle \mathop \to \limits^{CP} \left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} \oplus c_{0,yx} } \right\rangle . $$

(5)

It can be inferred that the unitary transformation ${\text{CP}}$ is a controlled NOT gate (CNOT). After using ${\text{CP}}$, the quantum state $\left| {\psi_{b} } \right\rangle$ in Eq. (4) is evolved to

$$ \left| {\psi_{b1} } \right\rangle = CP\left( {\left| {\psi_{b} } \right\rangle } \right) = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} \oplus c_{0,yx} } \right\rangle \left| {yx} \right\rangle } } . $$

(6)

Two corresponding pixel values are the same when $\left| {c_{0,yx} \oplus c_{1,yx} } \right\rangle = \left| 0 \right\rangle$, otherwise different.

The unitary transformations $\varsigma$ and $Q$ are important components of Algorithm Est_Amp. According to Sect. 2.3, the quantum implementation circuit of the unitary transformation $\varsigma$ and $Q$ can be illustrated in Figs. 9 and 10, respectively. In Fig. 10, the second register is initialized to $\left| 0 \right\rangle$, and then a NOT gate (NOT or X) and a Hadamard gate (H) are applied to it.

Fig. 9

Quantum implementation circuit of the unitary transformation $\varsigma$. a The implementation circuit. b The abbreviation notation of the circuit in a

Fig. 10

Quantum implementation circuit of the unitary transformation $Q$. a The implementation circuit. b The abbreviation notation of the circuit in a

Figure 11 illustrates the quantum implementation circuit of Algorithm 2, where the output outcome res can be obtained by one measurement of the first register. As described in Algorithm Est_Amp, the probability that two corresponding pixel values are the same is calculated by $\tilde{a} = \sin^{2} \left( {\pi *res/M} \right)$. According to Algorithm 2, the number of pixels that two corresponding pixel values are the same is calculated by $\tilde{t} = 2^{2n} \times \tilde{a}$. The similarity of two images is defined as $p = \tilde{t}/2^{2n}$.

Fig. 11

Quantum implementation circuit of Algorithm 2

4 Similarity assessment of quantum gray and color images

Gray and color images are more common than binary images. In this section, similarity assessments between quantum gray or color images and quantum gray or color image binarization are considered. It should be noted that quantum gray or color images binarization is complementary to this paper and it is not the primary focus of this paper, so it is kept simple.

4.1 Similarity assessment of quantum gray images

Algorithm 3 Similarity assessment of quantum gray images based on pixel value comparison (SAG_PV)

• 1. Store two gray images in a quantum system by using a unitary transformation ${\text{GTG}}$;

• 2. Compare the pixel values of two quantum gray images one by one;

• 3. Apply Algorithm Est_Amp where the output is represented by $\tilde{a}$;

• 4. Calculate the number of same pixels $\tilde{t} = 2^{2n} \times \tilde{a}$ where $2^{2n}$ is the size of the image;

• 5. Calculate the similarity $p = \tilde{t}/2^{2n}$.

Similar with Algorithm 2, Algorithm 3 also compares the pixel values of two quantum images one by one. This algorithm works fast and simply but may have a poor effect in some cases. It has the possibility that the similarity value of two gray images is small when the pixel values are slightly different.

Algorithm 4 Similarity assessment of quantum gray images based on Algorithm SAB_PV (SAG_SAB_PV)

• 1. Store two gray images in a quantum system by using a unitary transformation ${\text{GTG}}$;

• 2. Binarize two quantum gray images (or Extract the features of two quantum gray images) by using a unitary transformation ${\text{GTB}}$;

• 3. Apply Algorithm SAB_PV.

Algorithm 4 solves the poor effect mentioned in Algorithm 3 by using quantum image binarization or quantum image feature extraction that are important research in the area of quantum image processing. Algorithm SAB_PV has been described in Sect. 3. Next, unitary transformations, ${\text{GTG}}$ and ${\text{GTB}}$, are described as follows.

The unitary transformation ${\text{GTG}}$ is defined as

$$ \left| 0 \right\rangle^{ \otimes 2n + 2q} \mathop \to \limits^{GTG} \left| {\psi_{g} } \right\rangle = \frac{1}{{2^{2n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| {yx} \right\rangle \left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} } \right\rangle } } . $$

(7)

As illustrated in Fig. 12, there are $2n + 2q$ qubits and two unitary transformations NEQR in the quantum implementation circuit. The first $2n$ qubits are used to store two gray images’ coordinate information, and the next $2q$ qubits are used to store two gray images’ color information. After applying it, two gray images are stored to a quantum system.

Fig. 12

Quantum implementation circuit of the unitary transformation ${\text{GTG}}$. a The implementation circuit. b The abbreviation notation of the circuit in a

The unitary transformation ${\text{GTB}}$ is defined as

$$ c^{\prime}_{i,yx} \mathop{\longrightarrow}\limits{\text{GTB}}\left\{ \begin{aligned} \begin{array}{*{20}c} {1,} & {c_{i,yx} > s} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {0,} & {c_{i,yx} \le s} \\ \end{array} \hfill \\ \end{aligned} \right., $$

(8)

where $i = 0,1$, and s represents the preset threshold. Apply it to quantum state $\left| {\psi_{g} } \right\rangle$ in Eq. (7) to realize quantum gray image binarization, and then quantum state $\left| {\psi_{g} } \right\rangle$ is evolved to

$$ \begin{aligned} \left| {\psi_{gb} } \right\rangle & = {\text{GTB}}\left( {\left| {\psi_{g} } \right\rangle \left| 0 \right\rangle \left| 0 \right\rangle } \right) \\ & = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| y \right\rangle \left| x \right\rangle \left| {c_{0,yx} } \right\rangle \left| {c_{1,yx} } \right\rangle \left| {c^{\prime}_{0,yx} } \right\rangle \left| {c^{\prime}_{1.yx} } \right\rangle } } . \\ \end{aligned} $$

(9)

The quantum implementation circuit of it is illustrated in Fig. 13, where the modularized unitary transformation ${\text{COMP}}$ represents quantum comparator [32, 33]. If $e_{1} e_{0} = 10$, then $c_{i,yx} > s$; if $e_{1} e_{0} = 01$, then $c_{i,yx} < s$; and if $e_{1} e_{0} = 00$, then $c_{i,yx} = s$.

Fig. 13

Quantum implementation circuit of the unitary transformation ${\text{GTB}}$. a The implementation circuit. b The abbreviation notation of the circuit in a

4.2 Similarity assessment of quantum color images

Algorithm 5 Similarity assessment of quantum color images based on pixel value comparison (SAC_PV)

• 1. Store two color images in a quantum system by using a unitary transformation ${\text{CTC}}$;

• 2. Compare the pixel values of two quantum color images one by one;

• 3. Apply Algorithm Est_Amp where the output is represented by $\tilde{a}$;

• 4. Calculate the number of same pixels $\tilde{t} = 2^{2n} \times \tilde{a}$ where $2^{2n}$ is the size of the image;

• 5. Calculate the similarity $p = \tilde{t}/2^{2n}$.

Similar with Algorithm 2, Algorithm 5 also compares the pixel values of two quantum images one by one. This algorithm works fast and simply but may have a poor effect in some cases. It has the possibility that the similarity value of two color images is small when the pixel values are slightly different.

Algorithm 6 Similarity assessment of quantum color images based on Algorithm SAB_PV (SAC_SAB_PV)

• 1. Store two color images in a quantum system by using a unitary transformation ${\text{CTC}}$;

• 2. Binarize two quantum color images (or Extract the features of two quantum color images) by using unitary transformations ${\text{CTG}}$ and ${\text{GTB}}$;

• 3. Apply Algorithm SAB_PV.

Algorithm 6 solves the poor effect mentioned in Algorithm 5 by using quantum image binarization and quantum image feature extraction. Algorithm SAB_PV has been described in Sect. 3. Next, unitary transformations, ${\text{CTC}}$ and ${\text{CTG}}$, are described as follows.

The unitary transformation ${\text{CTC}}$ is defined as

$$ \left| 0 \right\rangle^{ \otimes 2n + 6q} \mathop \to \limits^{CTC} \left| {\psi_{c} } \right\rangle = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| {yx} \right\rangle \left| {R_{0,yx} G_{0,yx} B_{0,yx} } \right\rangle } } \left| {R_{1,yx} G_{1,yx} B_{1,yx} } \right\rangle . $$

(10)

As illustrated in Fig. 14, there are $2n + 6q$ qubits and two unitary transformations NCQI in the quantum implementation circuit. The first $2n$ qubits are used to store two color images’ coordinate information, and the next $6q$ qubits are used to store two color images’ color information. After applying it, two color images are stored to a quantum system.

Fig. 14

Quantum implementation circuit of the unitary transformation ${\text{CTC}}$. a The implementation circuit. b The abbreviation notation of the circuit in a

The unitary transformation ${\text{CTG}}$ is defined as

$$ \left| {c_{i,yx} } \right\rangle \mathop{\longrightarrow}\limits{\text{CTG}}\left| {\frac{{R_{i,yx} + G_{i,yx} + B_{i,yx} }}{3}} \right\rangle . $$

(11)

where $i = 1,2$. Apply it to quantum state $\left| {\psi_{c} } \right\rangle$ in Eq. (10) to transform two quantum color images into two quantum gray images, and then quantum state $\left| {\psi_{c} } \right\rangle$ is evolved to

$$ \begin{aligned} \left| {\psi_{cg} } \right\rangle & = {\text{CTG}}\left( {\left| {\psi_{c} } \right\rangle \left| 3 \right\rangle^{ \otimes q} \left| 3 \right\rangle^{ \otimes q} } \right) \\ & = \frac{1}{{2^{n} }}\sum\limits_{y = 0}^{{2^{n} - 1}} {\sum\limits_{x = 0}^{{2^{n} - 1}} {\left| {yx} \right\rangle } } \left| {R_{0,yx} G_{0,yx} B_{0,yx} } \right\rangle^{\prime } \left| {R_{1,yx} G_{1,yx} B_{1,yx} } \right\rangle^{\prime } \left| {c^{\prime}_{0.yx} } \right\rangle \left| {c^{\prime}_{1,yx} } \right\rangle \\ \end{aligned} $$

(12)

Figure 15 illustrates the quantum implementation circuit of it.

Fig. 15

Quantum implementation circuit of the unitary transformation ${\text{CTG}}$. a The implementation circuit. b The abbreviation notation of the circuit in a

Two quantum binary images are generated after applying the unitary transformation ${\text{GTB}}$ introduced in Sect. 4.1 to $\left| {\psi_{cg} } \right\rangle$ in Eq. (12).

As illustrated in Fig. 16, unitary transformations, ${\text{CTC}}$, ${\text{CTG}}$ and ${\text{GTB}}$, can realize the quantum implementation circuit of two quantum color image binarization.

Fig. 16

Quantum implementation circuit of two quantum color images binarization

5 Algorithm analyses

The proposed algorithms are analyzed in this section in terms of quantum circuit complexity and example experiment.

5.1 Quantum circuit complexity analyses

Quantum circuit complexity can be defined as the number of these universal gates that consists of all one-bit quantum states and two-bit controlled NOT gate (CNOT) gate make up universal gates [34]. All unitary transformations on arbitrarily many bits can be expressed as compositions of these universal gates. One Toffoli gate is equivalent to six CNOT gate. An n-controlled NOT (n-CNOT) gate ($n \ge 3$) is equivalent to $2\left( {n - 1} \right)$ Toffoli gates and one CNOT gate with adequate ancillary qubits. Thus, the quantum circuit complexity of n-CNOT gate (whether the control qubits state is in $\left| 1 \right\rangle$ or $\left| 0 \right\rangle$) is not more than $14n - 11$ [35].

The whole preparation of NEQR costs not more than $O\left( {qn2^{2n} } \right)$ for a $2^{n} \times 2^{n}$ gray image of gray range $2^{q}$ [3]. When $q = 1$, the whole preparation of NEQR costs not more than $O\left( {n2^{2n} } \right)$ for a $2^{n} \times 2^{n}$ binary image. The whole preparation of NCQI costs not more than $O\left( {3q + 2n + 6qn2^{2n} } \right)$ for a $2^{n} \times 2^{n}$ color image with every channel (R, G, B) ranged $\left[ {0, 2^{q} - 1} \right]$ [4].

Quantum Fourier transform and its inverse can be efficiently implemented by employing Hadamard gates (H) and controlled-phase gates [5] so that the quantum circuit complexity of quantum Fourier transform $F_{M}$, $F_{M}^{ - 1}$ in Fig. 11 is not more than $O\left( {t^{2} } \right)$.

Quantum circuit complexity of quantum comparator in Fig. 13 is $24q^{2} + 6q$ [9]. Quantum circuit complexity of quantum adder in Fig. 6 is not more than $O\left( {28n} \right)$ [9]. Quantum circuit complexity of quantum divider in Fig. 7 is $3n^{3} + 6n^{2} + n$ [18].

Let $\alpha = 2n2^{2n}$. Quantum circuit complexity of the unitary transformation ${\text{BTB}}$ in Fig. 8 is not more than $O\left( \alpha \right)$. Quantum circuit complexity of the unitary transformation $\varsigma$ in Fig. 9 is not more than $O\left( \alpha \right)$. Quantum circuit complexity of the unitary transformation $Q$ in Fig. 10 is not more than $O\left( {2\alpha } \right)$. Quantum circuit complexity of the unitary transformation ${\text{controlled}} - Q^{{2^{0} }}$, ${\text{controlled}} - Q^{{2^{1} }}$, …, ${\text{controlled}} - Q^{{2^{t - 1} }}$ in Fig. 11 is not more than $O\left( {2\alpha } \right)$, $O\left( {4\alpha } \right)$, …, $O\left( {2^{t - 1} 2\alpha } \right)$, respectively. Thus, quantum circuit complexity of Algorithm 2 (illustrated in Fig. 11) is

$$ O\left( {2t^{2} } \right) + O\left( \alpha \right) + O\left( {2\alpha } \right) + O\left( {4\alpha } \right) + \cdots + O\left( {2^{t - 1} 2\alpha } \right) + O\left( 1 \right) = O\left( {2t^{2} } \right) + O\left( {2^{t} \alpha } \right) $$

(13)

Let $\beta = 2qn2^{2n}$. Quantum circuit complexity of the unitary transformation ${\text{GTG}}$ in Fig. 12 is not more than $O\left( \beta \right)$. Quantum circuit complexity of the unitary transformation $\varsigma$ in Fig. 9 is not more than $O\left( \beta \right)$. Quantum circuit complexity of the unitary transformation $Q$ in Fig. 10 is not more than $O\left( {2\beta } \right)$. Quantum circuit complexity of the unitary transformation ${\text{controlled}} - Q^{{2^{0} }}$, ${\text{controlled}} - Q^{{2^{1} }}$, …, ${\text{controlled}} - Q^{{2^{t - 1} }}$ in Fig. 11 is not more than $O\left( {2\beta } \right)$, $O\left( {4\beta } \right)$, …, $O\left( {2^{t - 1} 2\beta } \right)$, respectively. Thus, quantum circuit complexity of Algorithm 3 is

$$ O\left( {2t^{2} } \right) + O\left( \beta \right) + O\left( {2\beta } \right) + O\left( {4\beta } \right) + \cdots + O\left( {2^{t - 1} 2\beta } \right) + O\left( 1 \right) = O\left( {2t^{2} } \right) + O\left( {2^{t} \beta } \right) $$

(14)

Quantum circuit complexity of the unitary transformation ${\text{GTG}}$ in Fig. 12 is not more than $O\left( {2qn2^{2n} } \right)$. Quantum circuit complexity of the unitary transformation ${\text{GTB}}$ in Fig. 13 is not more than $O\left( {24q^{2} } \right)$. Thus, quantum circuit complexity of Algorithm 4 is not more than

$$ O\left( {2qn2^{2n} } \right) + O\left( {48q^{2} } \right) + O\left( {2t^{2} } \right) + O\left( {2^{t} \alpha } \right) $$

(15)

Let $\gamma = 6q + 4n + 12qn2^{2n}$. Quantum circuit complexity of the unitary transformation ${\text{CTC}}$ in Fig. 14 is not more than $O\left( \gamma \right)$. Quantum circuit complexity of the unitary transformation $\varsigma$ in Fig. 9 is not more than $O\left( \gamma \right)$. Quantum circuit complexity of the unitary transformation Q in Fig. 10 is not more than $O\left( {2\gamma } \right)$. Quantum circuit complexity of the unitary transformation ${\text{controlled}} - Q^{{2^{0} }}$, ${\text{controlled}} - Q^{{2^{1} }}$, …, ${\text{controlled}} - Q^{{2^{t - 1} }}$ in Fig. 11 is not more than $O\left( {2\gamma } \right)$, $O\left( {4\gamma } \right)$, …, $O\left( {2^{t - 1} 2\gamma } \right)$, respectively. Thus, quantum circuit complexity of Algorithm 5 is

$$ O\left( {2t^{2} } \right) + O\left( \gamma \right) + O\left( {2\gamma } \right) + O\left( {4\gamma } \right) + \cdots + O\left( {2^{t - 1} 2\gamma } \right) + O\left( 1 \right) = O\left( {2t^{2} } \right) + O\left( {2^{t} \gamma } \right) $$

(16)

Quantum circuit complexity of the unitary transformation ${\text{CTC}}$ in Fig. 14 is not more than $O\left( {12qn2^{2n} } \right)$. Quantum circuit complexity of the unitary transformation ${\text{CTG}}$ is not more than $O\left( {3q^{3} } \right)$. Thus, quantum circuit complexity of Algorithm 6 is not more than

$$ O\left( {12qn2^{2n} } \right) + O\left( {6q^{3} } \right) + O\left( {2t^{2} } \right) + O\left( {2^{t} \alpha } \right) $$

(17)

5.2 Example analyses

There are two methods of simulation of quantum circuits. The first method uses real quantum computers such as IBMQ. But, these existing real quantum computers have limited qubits so that complex quantum circuits cannot be simulated. The second method uses classical computers. Theoretically, classical computers can simulate quantum systems. Vectors $v_{1} = \left[ {0 1} \right]^{\text{T}}$ and $v_{2} = \left[ {1 0} \right]^{\text{T}}$ simulate quantum computational basis states $\left| 1 \right\rangle$ and $\left| 0 \right\rangle$, respectively. Unitary matrices simulate unitary transformation that evolves the quantum system. Similarly, it is hard for the commonly used classical computers to simulate complex quantum systems.

This subsection gives an experiment assessing the similarity of two binary images. Figure 17 illustrates a template image, and Fig. 18 illustrates six reference images. Based on Algorithm 2, Fig. 19 illustrates the corresponding quantum circuit. However, as mentioned above, it is hard for the commonly used classical computers and existing real quantum computers to simulate it. Alternatively, we need to simplify Algorithm 2. That is to say, instead of Steps 3 and 4, the number of the superposition components with the 16th qubit being $\left| 0 \right\rangle$ is directly computed by statistical analysis. Thus, we here only classically simulate quantum circuit for Steps 1 and 2, and then obtain the similarity values by statistical analysis and Step 5.

Fig. 17

A template image

Fig. 18

Six reference images

Fig. 19

Quantum circuit for the experiment

Table 1 displays six similarity values. The similarity value between the template image and reference image is bigger when they are visually more like. Figure 18a–c is visually similar with the template image so that the similarity value more than 0.5. Figure 18d–f is visually different from the template image so that the similarity values are less than 0.5.

Table 1 Similarity values of two binary images

6 Discussion

Table 2 compares the proposed algorithms with the existing quantum algorithms in Ref. [21, 27, 28]. In terms of $t = m + { \lceil }\log \left( {2 + 1/2\varepsilon } \right) { \rceil } = n + 5$ where $m = { \lceil }\left( {2n + 3/2} \right){ \rceil } + 1 = n + 3$ and $\varepsilon = 1/6$, quantum complexity of Algorithms SAB_PV, SAG_PV, SAG_SAB_PV, SAC_PV, SAC_SAB_PV, respectively, is $O\left( {64n2^{3n} } \right)$, $O\left( {64qn2^{3n} } \right)$, $O\left( {2qn2^{2n} } \right) + O\left( {48q^{2} } \right) + O\left( {64n2^{3n} } \right)$, $O\left( {384qn2^{3n} } \right)$, $O\left( {12qn2^{2n} } \right) + O\left( {6q^{3} } \right) + O\left( {64n2^{3n} } \right)$.

Table 2 Compare the proposed algorithms with other algorithms

These algorithms are based on pixel value comparison but are different in quantum image representations, quantum implementation circuit and the number of measurement. When not considering the number of quantum measurement, quantum circuit complexity of some existing algorithms is less than that of the proposed algorithm. When considering the number of quantum measurement, quantum circuit complexity of existing algorithms is more than the proposed algorithms.

Different algorithms use different quantum image representations to store images. NEQR, FRQI can store quantum binary or gray images, and NCQI and NAQSS can store quantum color images. Moreover, different quantum image representations differently represent the color information, which causes quantum implementation circuits of assessing similarity that are different so that quantum circuit complexity is different. NEQR, NCQI represent the color information by quantum states so that the similarity of two images can be obtained by quantum subtractor or some CNOT gates. FRQI represent the color information by angles so that the similarity of two images is obtained by a Hadamard gate. NAQSS represent the color information by quantum amplitudes so that the similarity of two images is obtained by a Hadamard gate.

The algorithm in Ref. [21] estimates the similarity value by making quantum measurements on the quantum register and save it as a difference, then add up all the difference and compare the sum with the tolerance value. In this process, at least $2^{2n}$ same quantum states have to be prepared and measured to get all the difference. That is, the number of measurements is at least $2^{2n}$ times.

As illustrated in Fig. 20, the algorithm in Ref. [27] estimates the similarity value according to the probability distribution of the results from quantum measurements so that $2^{2n}$ same quantum states have to be prepared and are measured to summarize some sort of histogram. That is, the number of quantum measurement is at least $2^{2n}$ times.

Fig. 20

(figure adapted from [27])

Probability distribution of measure.

The algorithm in Ref. [28] is similar with Ref. [27] and points out that when measuring $2^{2n}$ same states prepared in advance, the measurement output with $pr(\left| 0 \right\rangle )$ and $pr(\left| 1 \right\rangle )$ obeys a binomial distribution. Only if the probability distribution value of a specific measurement result such as $\left| {00 \cdots 0} \right.$ becomes steady, i.e., its difference between two adjacent outcomes is less than a small number like $0.00001$, and the measurement can be stopped. In other words, the number of quantum measurement is at least $2^{2n}$.

In contrast, the proposed algorithms have an advantage in quantum measurement process. Based on quantum counting, the quantum state is only measured once and then the similarity value of quantum images can be estimated according to the measurement result.

7 Conclusion

Five algorithms are proposed to assess the similarity between two quantum images. They are suitable for binary or gray or color images, respectively. Their advantages lie in less number of measurements, only one measurement, compared with other quantum schemes. However, some things in the algorithms are not perfect, such as color image binarization. Any color has three basic characteristics, hue, purity and brightness, and sometimes purity is as important for color images as brightness. The color image binarization method used in Algorithm 6 only considers brightness but ignores purity. Perhaps, ingenious color image binarization methods or color image feature extraction can balance chromatic purity and brightness well. It would be a good research direction in future work.