1 Introduction

Quantum computing [1] which has the unique computing performance of quantum coherence, entanglement, superposition of quantum states and other inherent characteristics quickly becomes an international research focus. In fact, utilizing the unique properties, Shor’s discrete logarithms and integer factoring algorithms in polynomial time [2], Deutsh’s parallel computing algorithm with quantum parallelism and coherence [3] and Grover’s quadratic speedup for unordered database search algorithm [4] are insurmountable so far by any known classical algorithms.

Since the amplitude or phase of a quantum state can be used to store information [16], a quantum system is superior to a classical computer for information storage (e.g., we may consider a system of n qubits which can store \({2^n}\) complex numbers. For \(n=500,\,{2^{500}}\), this number is lager than the estimated number of atoms in the Universe! Trying to store all these complex numbers would not possible on any conceivable computer [12]). In a quantum system, frequency of the physical nature of color could represent a color instead of the RGB model or the HIS model, so a color was represented by only a 1-qubit quantum state [5] and an image was stored in a quantum array [5, 6]. A quantum composite state (FRQI state) stored the colors and the coordinates of a 2D gray image of \({2^n}\) pixels with (\(n+1\)) qubits [7]. A set of quantum states (QSMC) was proposed to represent \(M\) colors in an image and discussed how to retrieve images stored in a quantum system [8]. The phase-space distribution functions (Wigner and Husimi functions) were used to store an image in a quantum system [10].

Quantum computing can be realized by quantum gate operations. A finite set of basic gate operations was used to construct any quantum gate operation [11]. Universal quantum gates were expressed as the combination of one-bit gate and two-bit gates [12, 13], and two-bit gates were universal for quantum computing [14]. An efficient scheme was proposed for initializing a quantum register with an arbitrary superposed state, and application of the scheme in three special cases was discussed [15].

Many scholars have studied Grover search algorithms. Grover’s algorithm was generalized to deal with an arbitrary initial amplitude distribution, and a bound of the success probability of searching a marked state was derived [17]. For the known number of solutions, the rotation phase \(\pi \) in Grover’s algorithm was replaced with an arbitrary phase of the rotation and modified algorithm’s properties were analyzed by recursion equations [18]. In order to search out marked states with the maximum success probability, rotational phases of Grover algorithm must satisfy certain matching conditions [9, 19, 20].

Content-based image search is an emerging technology [21], and the image segmentation is a key technology. Significant progress had been made in field of image segmentation, for example, snake- and region growing were combined with a principled framework [21]. But for content-based image search, the accuracy or efficiency of image segmentation is not high enough for some images by employing classical segmentation algorithms. Such as, snake [22], region growing [23], clustering [24], these algorithms search out a coordinate of a target object in \(o(N)\) where \(N\) is the number of pixels. For some special images (e.g., overlapping target objects [6], the target object and the background whose colors are similar [25]), classical algorithms are difficult to segment target objects. In order to improve the efficiency and accuracy of content-based image search, image segmentation information is extracted from an original image by using classic segmentation algorithms in advance. For some special images (e.g., overlapping target objects), we can get segmentation information of target objects from the image with human–computer interaction (e.g., using Photoshop software). And then, we store the colors, coordinates and segmentation information of an image in a quantum system. It is a motivation to propose that a (\(n+1\))-qubit normal arbitrary quantum superposition state (NAQSS) represents a multi-dimensional color image (including segmentation information) in this paper. On the basis of the color treatment strategy in the paper [8], we design a generic quantum circuit to transform a simple initial state \({\left| 0 \right\rangle ^{ \otimes (n + 1)}}\) into a NAQSS state to realize an image storage. And the generic quantum circuit is optimized by a quantum circuit simplification (QCS) algorithm. For the purpose of retrieving the entire image from a quantum system, we measure directly the NAQSS state with a set of projection measurement operators and calculate the maximum number of measurements (namely, Monte Carlo sampling). We adopt an improved Grover search algorithm with arbitrary rotation phases and an arbitrary initial state to efficiently retrieve a target sub-image of an image (e.g., search out a coordinate of a target sub-image only running in \(O(\sqrt{N/r})\)).

The paper is organized as follows: An image representation are presented in Sect. 2. The realizations of image storage and quantum circuit optimization are discussed in Sect. 3. Multi-dimensional color image retrievals are described in detail in Sect. 4. Conclusion is shown in Sect. 5.

2 Basic quantum gates and representation of a quantum image

2.1 Representation of a quantum image

We describe briefly an angle how to represent a color [8] as follows.

A bijective function \({F_1}\) which sets up a one-to-one relationship between color and angle is created

$$\begin{aligned} {F_1}:Color \leftrightarrow \phi \end{aligned}$$
(1)

where \(Color = \{ colo{r_1}, colo{r_2}, \cdots ,colo{r_M}\},\,colo{r_i}\) corresponds to the \(ith\) color in ordered \(M\) colors, \(\phi = \{ {\phi _1},{\phi _2}, \ldots ,{\phi _M}\},\,{\phi _i} = \frac{{\pi (i - 1)}}{{2(M - 1)}},\,i \in \{ 1,2, \ldots ,M\}\). For grayscale images, \(M = 256\), colors are sorted in ascending order by the grayscale values. For example, \(colo{r_1}\) and \(colo{r_{256}}\) correspond to grayscale values 0 and 255, respectively. For color images, \(M = {2^{24}}\), we make \(x, y, z\) be the values of \(R, G, B\) in 24-bit RGB true color, and let \(i = x \times 256 \times 256 + y \times 256 + z + 1\), thus, \(colo{r_i}\) corresponds to the value \((x,y,z)\) of \(RGB\). For instance, \(colo{r_1}\) and \(colo{r_{16777216}}\) correspond to RGB values (0,0,0) and (255,255,255).

If \(V\) is a k-dimensional Euclidean space spanned by the orthogonal basis vectors \({b_1},{b_2}, \ldots {b_k}\), a k-dimensional digital image is represented as the function \(f:V \rightarrow R\) where \(V\) notates the position information of an image and \(f\left( V \right) \) is a color set of pixels corresponding to the position \(V\). Let \(f\left( V \right) \subset color\) in this paper, we obtain that the angle set \(\phi \) represents colors of a k-dimensional digital image by (1).

A quantum superposition state in \({2^n}\) dimensional Hilbert space may be expressed as \(\left| {{\psi _a}} \right\rangle = \sum \nolimits _{i = 0}^{{2^n} - 1} {{a_{i}}\left| i \right\rangle } \) where \(\left| i \right\rangle ,\,i = 0,1, \cdots {2^n} - 1\), is a set of orthogonal basis and \({a_i}\) is an arbitrary real.

In order to represent a k-dimensional color digital image, \(\left| {{\psi _a}} \right\rangle = \sum \nolimits _{i = 0}^{{2^n} - 1} {{a_{i}}\left| i \right\rangle } \) is changed

$$\begin{aligned} \left| {{\psi _\phi }} \right\rangle = \sum \limits _{i = 0}^{{2^n} - 1} {{a_i}\left| {{v_1}} \right\rangle } \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle \end{aligned}$$
(2)

where \(i = {i_1} \cdots {i_j}{i_{j + 1}} \cdots {i_l} \cdots {i_m} \cdots {i_n},\,{v_1} = {i_1} \cdots {i_j},\,{v_{2}} = {i_{j + 1}} \cdots {i_l}\) and \({v_k} = {i_m} \cdots {i_n}\) are the binary expansions for \(i,\ {v_1},\ {v_2}\) and \({v_k}\), respectively; \(\left| i \right\rangle = \left| {{v_1}} \right\rangle \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle \) is a coordinate \(\left( {{v_1},{v_2}, \ldots ,{v_k}} \right) \) in the k-dimensional space \(V\) and \({a_i} \in \phi \) (see (1)) notates the color of pixel corresponding to the coordinate.

To normalize the state \(\left| {{\psi _\phi }} \right\rangle \) in (2), we set

$$\begin{aligned} {\theta _{i}} = \frac{a_i}{{\sqrt{\sum \limits _{y = 0}^{{2^n} - 1} {a_y^2}}}} \end{aligned}$$
(3)

Substituting (3) for \({a_i}\) in (2), we obtain a state \(\left| {{\psi _N}} \right\rangle \)

$$\begin{aligned} \left| {{\psi _N}} \right\rangle = \sum \limits _{i = 0}^{{2^n} - 1} {{\theta _i}\left| {{v_1}} \right\rangle } \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle \end{aligned}$$
(4)

where \((\sum \nolimits _{i = 0}^{{2^n} - 1} {\theta _{i}^2} ) = 1\) and \(i = {v_1}{v_2} \cdots {v_k}\).

Thus, the state \(\left| {{\psi _N}} \right\rangle \) can represent a k-dimensional color image. For the sake of storing image segmentation information in a quantum state, we create a bijective function \({F_2}\) which sets up a one-to-one relationship between an angle and an integer

$$\begin{aligned} {F_2}:\textit{Number} \leftrightarrow \textit{Angle} \end{aligned}$$
(5)

where \(Angle = \{ {\beta _0},{\beta _2}, \ldots ,{\beta _{m - 1}}\}\) is an angle set, and \(Number = \{ 1,2, \ldots ,m\}\) is a set of integers, \({\beta _i} = \frac{{i\pi }}{{2(m - 1)}},\,i \in \{ 0,1, \ldots ,m - 1\}\); if \(m = 1\), let \({\beta _0} = 0\).

Assuming that an image is divided into \(m\) sub-images numbered as \(1,2, \ldots m\), we define a quantum state \(\left| \psi \right\rangle \) by changing (4) to represent the whole image (including segmentation information)

$$\begin{aligned} \left| \psi \right\rangle = \sum \limits _{i = 0}^{{2^n} - 1} {{\theta _{i}}\left| {{v_1}} \right\rangle } \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle \left| {{\chi _i}} \right\rangle \end{aligned}$$
(6)

where \(\left| {{\chi _i}} \right\rangle = \cos {\gamma _i}\left| 0 \right\rangle + \sin {\gamma _i}\left| 1 \right\rangle ,\,{\gamma _i} \in Angle\) corresponding to an integer from (5), represents the serial number of the sub-image which contains the pixel corresponding to the coordinate \(\left| {{v_1}} \right\rangle \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle \).

Since \(\left\| {\left| \psi \right\rangle } \right\| = \sqrt{\sum \nolimits _{i = 0}^{{2^n} - 1} {\theta _i^2(\cos ^{2}{\gamma _i} + \sin ^{2}{\gamma _i})}} = 1,\,\left| \psi \right\rangle \) is called a normal arbitrary quantum superposition state (NAQSS).

3 Realizations of image storage and circuit optimization

Two unitary matrixes are defined as

$$\begin{aligned} {R_x}(\theta )&= \left[ {\begin{array}{ll} {\cos \theta }&{}{\sin \theta }\\ {\sin \theta }&{}{- \cos \theta } \end{array}} \right] , \theta \in \left[ {0,2\pi }\right] \end{aligned}$$
(7)
$$\begin{aligned} {R_y}(\theta )&= \left[ {\begin{array}{ll} {\cos \theta }&{}{-\sin \theta }\\ {\sin \theta }&{}{\cos \theta } \end{array}} \right] , \theta \in \left[ {0,2\pi }\right] \end{aligned}$$
(8)

\({R_x}(\theta )\) and \({R_y}(\theta )\) have the following properties

$$\begin{aligned} {R_y}(\theta ) \cdot {R_y}( - \theta )&= {R_y}( - \theta ) \cdot {R_y}(\theta ) = I\nonumber \\ {R_y}(\theta )\left| 0 \right\rangle&= \cos \theta \left| 0 \right\rangle + \sin \theta \left| 1 \right\rangle \nonumber \\ {R_y}(0)&= I,\ {R_y}\left( \frac{\pi }{2}\right) \left| 0 \right\rangle = \left| 1 \right\rangle \nonumber \\ {R_x}(\theta ) \cdot {R_x}(\theta )&= I,\ {R_x}\left( \frac{\pi }{4}\right) = H,\ and \ {R_x}\left( \frac{\pi }{2}\right) = X \end{aligned}$$
(9)

where \(I,H,X\) are an identity matrix, a Hadamard matrix and a pauli-x matric, respectively.

A sequence of angles is given as follows

$$\begin{aligned} {\alpha _{ 1}}&= \hbox {arctan} \sqrt{\frac{{\sum \nolimits _{{i_2} \cdots {i_n}} {{{\left| {{\theta _{1{i_2} \cdots {i_n}}}} \right| }^2}} }}{{\sum \nolimits _{{i_2} \cdots {i_n}} {{{\left| {{\theta _{0{i_2} \cdots {i_n}}}} \right| }^2}} }}} \end{aligned}$$
(10)
$$\begin{aligned} {\alpha _{j, {i_1} \cdots {i_{j - 1}}}}&= \arctan \sqrt{\frac{{\sum \nolimits _{{i_{j + 1}} \cdots {i_n}} {{{\left| {{\theta _{{i_1} \cdots {i_{j - 1}}1{i_{j + 1}} \cdots {i_n}}}} \right| }^2}} }}{{\sum \nolimits _{{i_{j + 1}} \cdots {i_n}} {{{\left| {{\theta _{{i_1} \cdots {i_{j - 1}}0{i_{j + 1}} \cdots {i_n}}}} \right| }^2}} }}} \end{aligned}$$
(11)

where \(j = 2,3, \ldots n\) and \({i_1}{i_2} \cdots {i_{j - 1}}\) is the binary expansion of an integer. For instance, when \(j = 2\), (11) is rewritten

$$\begin{aligned} {\alpha _{2,0}}&= \hbox {arctan} \sqrt{\frac{{\sum \nolimits _{{i_3} \cdots {i_n}} {{{\left| {{\theta _{01{i_3} \cdots {i_n}}}} \right| }^2}} }}{{\sum \nolimits _{{i_3} \cdots {i_n}} {{{\left| {{\theta _{00{i_3} \cdots {i_n}}}} \right| }^2}} }}} \end{aligned}$$
(12)
$$\begin{aligned} {\alpha _{2,1}}&= \arctan \sqrt{\frac{{\sum \nolimits _{{i_3} \cdots {i_n}} {{{\left| {{\theta _{11{i_3} \cdots {i_n}}}} \right| }^2}} }}{{\sum \nolimits _{{i_3} \cdots {i_n}} {{{\left| {{\theta _{10{i_3} \cdots {i_n}}}} \right| }^2}}}}} \end{aligned}$$
(13)

A controlled-\({R_{xyi}}\) operation is defined

$$\begin{aligned} {R_{xji}} = \left( \sum \limits _{k = 0,k \ne i}^{{2^{j - 1}} - 1} {\left| k \right\rangle \left\langle k \right| }\right) \otimes I + \left| i \right\rangle \left\langle i \right| \otimes {R_x}({\alpha _{j,i}}),j \ge 2 \end{aligned}$$
(14)

The controlled-\({R_{xyi}}\) operation is a unitary matrix, since \({R_{xyi}}R_{xyi}^ + = {I^{ \otimes j}}\). A unitary matrix \({R_{xj}}\) is given for \(j = 1\) and \(j \ge 2\)

$$\begin{aligned} {R_{xj}} = {R_x}({\alpha _1}) \otimes {I^{ \otimes (n - 1)}},j = 1 \end{aligned}$$
(15)

and

$$\begin{aligned} {R_{xj}} = \prod \limits _{i = 0}^{{2^{j-1}}}-1 {\left( {R_{xji}}\otimes {I^{\otimes (n-j)}}\right) ,}j\ge 2 \end{aligned}$$
(16)

Applying successively the unitary matrix \({R_{xj}}\) on the initial state \({\left| 0 \right\rangle ^{ \otimes n}}\), we acquire that \(\left| {{\psi _N}} \right\rangle = (\prod \nolimits _{j = 1}^n {{R_{xj}}} ){\left| 0 \right\rangle ^{ \otimes n}} = \sum \nolimits _{i = 0}^{{2^n} - 1} {{\theta _{i}}\left| {{v_1}} \right\rangle \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle }\).

A controlled-\({R_{yi}}\) operation is defined

$$\begin{aligned} {R_{yi}} = \left( \sum \limits _{j = 0,j \ne i}^{{2^n} - 1} {\left| j \right\rangle \left\langle j \right| } \right) \otimes I + \left| i \right\rangle \left\langle i \right| \otimes {R_y}({\gamma _i}) \end{aligned}$$
(17)

Applying successively the unitary matrix \({R_{yi}}\) on the initial state \(\left| {{\psi _N}} \right\rangle \otimes \left| 0 \right\rangle \), we achieve a NAQSS state \(\left| \psi \right\rangle \)

$$\begin{aligned} \left| \psi \right\rangle = \left( {\prod \limits _{i = 0}^{{2^n} - 1} {{R_{yi}}} } \right) (\left| {{\psi _N}} \right\rangle \otimes \left| 0 \right\rangle ) = \sum \limits _{i = 0}^{N - 1} {{\theta _{i}}\left| {{v_1}} \right\rangle } \left| {{v_2}} \right\rangle \cdots \left| {{v_k}} \right\rangle (\cos {\gamma _i}\left| 0 \right\rangle + \sin {\gamma _i}\left| 1 \right\rangle )\nonumber \\ \end{aligned}$$
(18)

\(\left| \psi \right\rangle \) is realized by the quantum circuit shown in Fig. 1. The circuit is built with (\({{2}^{{n + 1}}}-1\)) quantum gates which can be constructed by one-bit and two-bit gates whose total number is \(o(Nlo{g^2}N)\) where \(N = {2^n}\) is the pixel’s number of an image. Usually, an image may have many same colors or be locally symmetric, and a large number of pixels belong to a sub-image, so we design QCS algorithm (see Algorithm 1) to reduce the quantum gates in Fig. 1. The computational complexity of this algorithm is \(o({N^2}\log N)\).

Fig. 1
figure 1

The realization of a normal arbitrary quantum superposition state. Dashed box \(i(i = 1,2,n)\) corresponds to \({R_{xj}}(j = 1,2,n)\), Dashed box \(n+1\) corresponds to \(\prod \nolimits _{i = 0}^{{2^n} - 1} {{R_{yi}}}\). \({\gamma _0},{\gamma _1}, \ldots {\gamma _{{2^n} - 1}} \in \left\{ {{\beta _1},{\beta _2}, \ldots {\beta _m}} \right\} \) (see (5))

Full size image
figure a

In order to make the above algorithm explicit, let us consider a \(4 \times 4 \times 2\) image shown in Fig. 2 as an example. From formulas (7)–(18) and Fig. 2, values of \({\alpha _{j,{i_1} \cdots {i_{j - 1}}}}\) are given and QCS algorithm implementation is shown in Table 1. The optimized quantum circuit for the image is shown in Fig. 3.

Fig. 2
figure 2

Left a \(4 \times 4 \times 2\) image which is divided into two sub-images (numbered 0 and 1) and on the right for lower sub-image. The image is represented as \(\left| \psi \right\rangle = \sum \nolimits _{i = 0}^{31} {{\theta _{i}}\left| {{v_1}} \right\rangle \left| {{v_2}} \right\rangle \left| {{v_3}} \right\rangle (\cos {\beta _i}\left| 0 \right\rangle + \sin {\beta _i}\left| 1 \right\rangle )}\) where \(\left| {{v_1}} \right\rangle \left| {{v_2}} \right\rangle \left| {{v_{3}}} \right\rangle = \left| x \right\rangle \left| y \right\rangle \left| z \right\rangle = \left| {{x_1}{x_2}} \right\rangle \left| {{y_1}{y_2}} \right\rangle \left| {{z_1}} \right\rangle ,\,{x_i},{y_i},{z_i} \in \left\{ {0,1} \right\} \)

Full size image
Fig. 3
figure 3

The optimized quantum circuit for the \(4 \times 4 \times 2\) image. Dashed box \(i (i = 1,2, \cdots ,6)\) corresponds, respectively, to \({\alpha _{1}} = \frac{\pi }{4} ({R_x}(\frac{\pi }{4}) = H),\,{\alpha _{2,x}} = \frac{\pi }{4},\,{\alpha _{{3,xx}}},\,{\alpha _{{4,xxx}}} = \frac{\pi }{4},\,{\alpha _{{5,xxxx}}} = \frac{\pi }{4},\,{\gamma _{{xx0xx}}} = 0 ({R_y}(0) = I), {\gamma _{{xx1xx}}} = \frac{\pi }{2} ({R_y}(\frac{\pi }{2}))\)

Full size image
Table 1 QCS algorithm implementation
Full size table

4 Image retrieval

In order to retrieve images from a quantum system, we adopt two strategies: direct measurement (namely retrieve a whole image by Monte Carlo sampling), retrieve target sub-images whose amplitudes are amplified by applying improved improved Grover’s algorithm. To be simply, we substitute \(\left| i \right\rangle \) for \(\left| {{v_1}} \right\rangle \cdots \left| {{v_k}} \right\rangle \) in (6) in the section, i.e., the NAQSS state is expressed as

$$\begin{aligned} \left| {\psi } \right\rangle = \sum \limits _{i = 0}^{{2^n} - 1} {{\theta _{i}}\left| i \right\rangle \left| {{\chi _i}} \right\rangle } \end{aligned}$$
(19)

We define \(\dim (\left| {{v_i}} \right\rangle )\) as the dimensions of the subspace \(\left| {{v_i}} \right\rangle \), i.e., \(\left| {{v_i}} \right\rangle \) is expressed with \(\dim (\left| {{v_i}} \right\rangle )\) 1-qubit states. To successfully retrieve images, suppose we have a documentation, including the following known information: the values of \(k\) and \(\dim (\left| {{v_i}} \right\rangle )\) of \(\left| i \right\rangle = \left| {{v_1}} \right\rangle \cdots \left| {{v_k}} \right\rangle \), the value of \(\sqrt{\sum \nolimits _{{i}=0}^{{2^n} - 1} {a_i^2} } \), the number of sub-images, the number of pixels of each sub-image, average and variance of color values of each sub-image, projection measurement operator.

4.1 Retrieving a whole image from a quantum system

We define the observable operator \(M = \sum \nolimits _{j = 0}^{{2^{n + 1}} - 1} {{m_j}{P_j}} \) where \({P_j} = \left| j \right\rangle \left\langle j \right| \), apply \(M\) to measure the quantum state \(\left| {\psi } \right\rangle \) in Eq. (19), and obtain result \({m_j}\) with probability \(p({m_j}) = \left\langle {\psi } \right. \left| {{P_j}} \right| \left. {\psi } \right\rangle = \theta _j^2\) , i.e.,

$$\begin{aligned} {\theta _j} = \sqrt{p({m_j})} \end{aligned}$$
(20)

Define \({n_s}\) as the number of samples and suppose that the results of \({n_s}\) measurements are \({n_j}\) times of \({m_j}\), set \(\hat{p}(m_j) = n_j {\big /} n_s \), so we know that \(\hat{p}({m_j}),\,{\widehat{\theta }_j}\) are the estimates of \(p({m_j})\) and \({\theta _j}\), i.e.,

$$\begin{aligned} {\widehat{\theta }_j} = \sqrt{\hat{p}({m_j})} \end{aligned}$$
(21)

Assuming that a quantum state is detected with the probability of \(1 - \alpha \) in \({n_{\max }}\) measurements, now, we describe how to solve the value of \({n_{\max }}\) (i.e., how many measurements are necessary to acquire the correct value of \({\theta _j}\)) by appropriately changing the method in Sect. 2.2 of paper [8].

Set

$$\begin{aligned} Z = \left\{ \begin{array}{ll} 0, &{} \hbox {result of measurment is not}\, m_j\\ 1, &{} \hbox {result of measurment is}\, m_j \end{array} \right. \end{aligned}$$
(22)

Since \(Z\) is either 1 or 0, \(Z\) is a Bernoulli random variable. The probability mass function of random variable \(Z\) is given by

$$\begin{aligned} \left\{ \begin{array}{l} p({\widetilde{m_j}}) = P\{ Z = 0\} = 1 - p\\ p(m_j) = P\{Z = 1\} = p \end{array} \right. \end{aligned}$$
(23)

where \(\widetilde{{m_j}}\) notates result of measurement is not \({m_j}\).

The expectation \(\mu \) and variance \(\sigma \) of \(Z\) are \(\mu = p\) and \({\sigma ^2} = p(1 - p)\), respectively. Suppose that \({Z_1},{Z_2}, \cdots {Z_{{n_s}}}\) are \({n_s}\) samples of \(Z\) and \({n_s}\) is sufficiently large, then \({{{(\sum \nolimits _{i = 1}^{{n_s}} {{Z_i} - {n_s}p)}}{\big /} {\sqrt{{n_s}p(1 - p)} }}} = {{{({n_s}\overline{Z} - {n_s}p)}{\big /}{\sqrt{{n_s}p(1 - p)}}}}\) has approximately a standard normal distribution by the Central Limit Theorem. Thus, \(P\{\left| ({n_s}\overline{Z} - {n_s}p) {\big /} {\sqrt{{n_s}p(1 - p)}} \right| < Z_{\alpha /2}^{2}\}\approx 1 - \alpha \) where \(1 - \alpha \) is a confidence level (the value of \(Z_{\alpha {\big /}2}\) can be found in standard normal distribution lookup tables: e.g., when \(\alpha = 0.05\), we can obtain \(Z_{\alpha /2}= 1.96\)). Solving the inequality \(\left| ({n_s}\overline{Z} - {n_s}p) {\big /} {\sqrt{{n_s}p(1 - p)}} \right| < Z_{\alpha /2}^{2}\), we obtain that the confidence interval of \(p\) is \([{p_{\min }},{p_{\max }}]\) with approximate confidence level \(1 - \alpha \). \({p_{\min }}\) and \({p_{\max }}\) are expressed as follows

$$\begin{aligned} {p_{\min }} = \frac{{2{n_s}\overline{Z} + \lambda - \sqrt{{{(2{n_s}\overline{Z} + \lambda )}^2} - 4({n_s} + \lambda )n{{\overline{_sZ} }^2}} }}{{2{n_s} + 2\lambda }} \end{aligned}$$
(24)

and

$$\begin{aligned} {p_{\max }} = \frac{{2{n_s}\overline{Z} + \lambda + \sqrt{{{(2{n_s}\overline{Z} + \lambda )}^2} - 4({n_s} + \lambda )n{{\overline{_sZ}}^2}}}}{{2{n_s} + 2\lambda }} \end{aligned}$$
(25)

where \(\lambda = Z_{\alpha /2}^2\).

The size of the confidence interval \([{p_{\min }},{p_{\max }}]\) is

$$\begin{aligned} \varDelta p = {p_{\max }} - {p_{\min }} = \frac{{\sqrt{4{n_s}\lambda \overline{Z} - 4{n_s}\lambda {{\overline{Z}}^2} + {\lambda ^2}}}}{{{n_s} + \lambda }} \end{aligned}$$
(26)

Define

$$\begin{aligned} {\theta _{\max }} = \sqrt{{p_{\max }}}, {\theta _{\min }} = \sqrt{{p_{\min }}} \end{aligned}$$
(27)

From (26) and (27), we infer

$$\begin{aligned} \varDelta \theta = \sqrt{{p_{\max }}} - \sqrt{{p_{\min }}} \le \sqrt{{p_{\max }} - {p_{\min }}} = \sqrt{\varDelta p} \end{aligned}$$
(28)

where \(\varDelta \theta = {\theta _{\max }} - {\theta _{\min }}\).

Since \(\overline{Z} = {\sum \nolimits _{i = 1}^{{n_s}} {{Z_i}}}{\big /}n_s\) and \(\hat{p}({m_j}) = \overline{Z} \), we know that \({\widehat{\theta }_j} = \sqrt{\overline{Z} }\) and \(\overline{Z} \approx p\) by Law of Large Numbers. The confidence interval of \(p\) is \([{p_{\min }},{p_{\max }}]\); therefore, \(\overline{Z} \in [{p_{\min }},{p_{\max }}]\) and \(p \in [{p_{\min }},{p_{\max }}]\) are with the approximate probability of \(1 - \alpha \). Thus

$$\begin{aligned} {\theta _j} \in [{\theta _{\min }},{\theta _{\max }}], {\widehat{\theta }_j} \in [{\theta _{\min }},{\theta _{\max }}] \end{aligned}$$
(29)

By (29), we find

$$\begin{aligned} \left| {{{\widehat{\theta }}_j}-{\theta _j}}\right| \le \varDelta \theta \end{aligned}$$
(30)

Since \({a_j} = {\theta _j}\sqrt{\sum \nolimits _{i = 0}^{{2^n} - 1} {a_i^2} }\) (see (3)), from (29) and (30), we yield

$$\begin{aligned} \frac{{\left| {{{\widehat{a}}_j} - {a_j}} \right| }}{{{G_\phi }}} \le \varDelta \theta \end{aligned}$$
(31)

and

$$\begin{aligned} {a_j},{\widehat{a}_j} \in \left[ {{G_\phi }{\theta _{\min }},{G_\phi }{\theta _{\max }}}\right] \end{aligned}$$
(32)

where \({G_\phi } = \sqrt{\sum \nolimits _{i = 0}^{{2^n} - 1} {a_i^2}}\) and \({\widehat{a}}_j = {\widehat{\theta }}_j\sqrt{\sum \nolimits _{i = 0}^{{2^n} - 1} {a_i^2}}\).

According to (1), we calculate

$$\begin{aligned} \varDelta \phi = \left| {{\phi _{i + 1}} - {\phi _i}} \right| = \frac{\pi }{{2(M - 1)}} \end{aligned}$$
(33)

where \(i \in \{ 1,2, \cdots (M - 1)\},\,M = {2^{24}}\) or \(M = 256\).

Suppose

$$\begin{aligned} \sqrt{\varDelta p} < \frac{{\varDelta \phi }}{{{G_\phi }}} \end{aligned}$$
(34)

Let \(\varDelta \widehat{\phi }= \left| {{a_j} - {{\widehat{a} }_j}} \right| \), from (28), (31), (32) and (34), we see

$$\begin{aligned} \varDelta \widehat{\phi }\le {G_\phi }\varDelta \theta < \varDelta \phi \end{aligned}$$
(35)

\(\varDelta \widehat{\phi },\,\varDelta \phi ,\,{a_j},\,{\hat{a}_j},\,{G_\phi }{\theta _{\min }},\,{G_\phi }{\theta _{\max }}\) and \({G_\phi }\varDelta \theta \) are shown in Fig. 4.

Fig. 4
figure 4

The relation of \(\varDelta \widehat{\phi },\,\varDelta \phi ,\,{a_j},\,{\hat{a}_j},\,{G_\phi }{\theta _{\min }},\,{G_\phi }{\theta _{\max }}\) and \({G_\phi }\varDelta \theta \). When \(\widehat{{\theta _j}} \in \varDelta \theta \) (i.e., \(\widehat{{a_j}} \in {G_\phi }\varDelta \theta )\), we derive that \({a_j} = {\phi _i}\) from the figure

Full size image

Formula (34) is equivalent to

$$\begin{aligned} {y^4}{n_s}^2 + \left[ {2\lambda {y^4} - 4\lambda \left( \overline{Z} - {{\overline{Z} }^2}\right) } \right] {n_s} + {y^4}{\lambda ^2} - {\lambda ^2} > 0 \end{aligned}$$
(36)

where \(y = \frac{{\varDelta \phi }}{{{G_\phi }}}\).

Solving (36), two solutions are

$$\begin{aligned} {n_-}&= \lambda \left[ {\frac{{2(\overline{Z} - {{\overline{Z} }^2})}}{{{y^4}}} - 1 - \sqrt{{{\left( \frac{{2\left( \overline{Z} - {{\overline{Z}}^2}\right) }}{{{y^4}}} - 1\right) }^2} + (1 - {y^8})} }\,\, \right] \end{aligned}$$
(37)
$$\begin{aligned} {n_+}&= \lambda \left[ {\frac{{2\left( \overline{Z} - {{\overline{Z} }^2}\right) }}{{{y^4}}} - 1 + \sqrt{{{\left( \frac{{2(\overline{Z} - {{\overline{Z} }^2})}}{{{y^4}}} - 1\right) }^2} + (1 - {y^8})} }\,\, \right] < \frac{{4\lambda (\overline{Z} - {{\overline{Z} }^2})}}{{{y^4}}}\nonumber \\ \end{aligned}$$
(38)

where \(\lambda \!=\! Z_{{\alpha {\big /}2}}^2,\,y \!=\! \frac{{\varDelta \phi }}{{{G_\phi }}},\,\varDelta \phi \!=\! \frac{\pi }{{2(M - 1)}},\,{G_\phi } \!=\! \sqrt{\sum \nolimits _{i = 0}^{{2^n} - 1} {a_i^2} } \) and \(\overline{Z} \!=\! {{{\sum \nolimits _{i = 1}^{{n_s}} {{Z_i}} }{\big /} n}_s}\).

Let

$$\begin{aligned} {n_{\max }} = \left\lceil {\frac{{4\lambda (\overline{Z} - {{\overline{Z} }^2})}}{{{y^4}}}} \right\rceil \end{aligned}$$
(39)

where \(\left\lceil \cdot \right\rceil \) means rounding up.

Since \({n_ -} \le 0\) in (37), \({n_ - }\) is not selected. Thus, we can acquire the correct quantum state after at most \({n_{\max }}\) (see Eq. (39)) measurements with the approximate probability of \(1 - \alpha \).

Defining \(\overline{a} = \frac{{\sum \nolimits _{i = 0}^{{2^n} - 1} {a_i^2} }}{{{2^n}}}\), we have

$$\begin{aligned} {G_\phi } = \sqrt{{2^n}} \sqrt{\overline{a}} \end{aligned}$$
(40)

Since \({a_i} \in [0,\frac{\pi }{2}]\) (see (2)), we yield that \(\sqrt{\overline{a} } \in [0,\frac{\pi }{2}]\) and \(\sqrt{\overline{a} } \) can be seen as a number which is irrelevant to the size of the number \(n\). From (22), (23) and (40), we infer

$$\begin{aligned} \overline{z} \approx p = \theta _j^2 = {\left( \frac{{{a_j}}}{{{G_\phi }}}\right) ^2} = \frac{{a_j^2}}{{{2^n}\overline{a}}} \end{aligned}$$
(41)

Substitute \(\varDelta \phi = \frac{\pi }{{2(M - 1)}},\,{G_\phi } = \sqrt{2^n} \sqrt{\overline{a}}\) and \(\overline{z} \approx \frac{{a_j^2}}{{{2^n}\overline{a}}}\) into (39), so that

$$\begin{aligned} {n_{\max }}&= \left\lceil {{N^{2}}{{(M - 1)}^4}\frac{{{2^6}\lambda (\overline{Z} - {{\overline{Z} }^2}){{\overline{a} }^2}}}{{{\pi ^4}}}} \right\rceil \nonumber \\&\approx N{(M - 1)^4}\frac{{{2^6}\lambda a_j^2\left( \overline{a} - \frac{{a_j^2}}{N}\right) }}{{{\pi ^4}}}\nonumber \\&\approx N{(M - 1)^4}\frac{{{2^6}\lambda a_j^2\overline{a} }}{{{\pi ^4}}} \end{aligned}$$
(42)

where \(N = {2^n}\) (suppose \(N \gg 1\)) is the number of pixels and \(M\) is the number of colors (\(M = {2^{24}}\) for color images and \(M = 256\) for grayscale images).

We can conclude that \({n_{\max }}\) is proportional to \(N{(M - 1)^4}\) by (42).

4.2 Retrieving a target sub-image from a quantum system

Suppose an image is only divided into two sub-images (i.e., target and background), in the case, \(Angle = \left\{ {{\beta _0} = 0,{\beta _1} = {\pi /2}} \right\} \) in (5), let \({\gamma _i} = {\beta _0}\) for \(i \in B\) and \({\gamma _i} = {\beta _1}\) for \(i \in A\), the NAQSS state \(\left| {\psi } \right\rangle \) in (19) is rewritten

$$\begin{aligned} \left| {\psi (r)} \right\rangle = \sum \limits _{i = 0,i \in B}^{{2^n} - 1} {{\theta _i}\left| i \right\rangle } \otimes \left| 0 \right\rangle + \sum \limits _{i = 0,i \in A}^{{2^n} - 1} {{\theta _i}\left| i \right\rangle } \otimes \left| 1 \right\rangle \end{aligned}$$
(43)

where \(A\) and \(B\) are defined as sets contain coordinates of the target and background in an image, respectively. That is to say, \(A\) is a set of marked states and \(B\) is a set of unmarked states. We employ Grover search algorithm to efficiently search out the target sub-image corresponding to marked states. Synthesizing papers [9] and [17–20], we propose an improved Grover’s algorithm which is suitable for the NAQSS state \(\left| {\psi (r)} \right\rangle \) in (43) and describe in detail the Grover search algorithm how to search out the marked states with the minimum number of iterations and the largest success probability.

We assume : \(N = {2^n}\) is a total of states, and \(r\) is a number of marked states; \(A\) and \(B\) are sets of marked and unmarked states, respectively; \({I_r}\) is the rotation operator of marked states, and \({I_0}\) is the rotation operator of the initial state \(\left| {\psi (r)} \right\rangle \) in (43). So Grover search operator is expressed as \({G_\psi } = G \otimes I = - {H^{ \otimes n}}{I_0}{({H^{ \otimes n}})^{ - 1}}{I_r} \otimes I\) where \(H\) and \(I\) are Hadamard and identity matrixes, respectively. \(A,\,B\) , \({I_0}\) and \({I_r}\) are listed as follows

$$\begin{aligned} A = \{ i|f({i_1}{i_2} \cdots {i_n}j) = 1\} ,B = \{ i|f({i_1}{i_2} \cdots {i_n}j) = 0\} \end{aligned}$$
(44)

where \(f( \cdot )\) is a quantum oracle (a blank box) of Grover’s algorithm , \(f({i_1}{i_2} \cdots {i_n}1) = 1,\,f({i_1}{i_2} \cdots {i_n}0) = 0,\,i = {i_1}{i_2} \cdots {i_n}\) and \({i_1},{i_2}, \ldots {i_n},j \in \left\{ {0,1} \right\} \).

$$\begin{aligned} {I_r}&= {I^{ \otimes n}} - (1 - {e^{i\alpha }})\sum \limits _{\tau \in A} {\left| \tau \right\rangle \left\langle \tau \right| } \end{aligned}$$
(45)
$$\begin{aligned} {I_0}&= {I^{ \otimes n}} - (1 - {e^{i\alpha }})\left| 0 \right\rangle \left\langle 0 \right| \end{aligned}$$
(46)

where \(\alpha \) is a rotation angle of marked and initial states in (45) and (46).

Applying Grover search operator \({G_\psi }\) on \(\left| \psi (r) \right\rangle \)

$$\begin{aligned} {G_\psi }\left| {\psi (r)} \right\rangle&= (G \otimes I)\left( \sum \limits _{i = 0,i \in B}^{{2^n} - 1} {{\theta _i}\left| i \right\rangle } \otimes \left| 0 \right\rangle + \sum \limits _{i = 0,i \in A}^{{2^n} - 1} {{\theta _i}\left| i \right\rangle } \otimes \left| 1 \right\rangle \right) \nonumber \\&= \sum \limits _{i = 0,i \in B}^N {G({\theta _i}\left| i \right\rangle } ) \otimes \left| 0 \right\rangle + \sum \limits _{i = 0,i \in A}^N {(G{\theta _i}\left| i \right\rangle )} \otimes \left| 1 \right\rangle ) \end{aligned}$$
(47)

The state \(\left| \psi (r) \right\rangle \) after \(t\) iterations of \({G_\psi }\) is changed into

$$\begin{aligned} \left| {\psi (t)} \right\rangle = \sum \limits _{i \in B} {{l_i}(t)} \left| i \right\rangle \left| 0 \right\rangle + \sum \limits _{i \in A} {{k_i}(t)} \left| i \right\rangle \left| 1 \right\rangle \end{aligned}$$
(48)

We denote the averages of the amplitudes as follows

$$\begin{aligned} \overline{l} (t)&= \frac{1}{{N - r}}\sum \limits _{i \in B} {{l_i}(t)} \end{aligned}$$
(49)
$$\begin{aligned} \overline{k} (t)&= \frac{1}{r}\sum \limits _{i \in A} {{k_i}(t)} \end{aligned}$$
(50)
$$\begin{aligned} C(t)&= \frac{{r(1 - {e^{i\alpha }}){e^{i\alpha }}}}{N}\overline{k} (t) + \frac{{(1 - {e^{i\alpha }})(N - r)}}{N}\overline{l} (t) \end{aligned}$$
(51)

The recursion equations of the amplitudes take

$$\begin{aligned} {k_i}(t + 1) = C(t) - {e^{i\alpha }}{k_i}(t) \end{aligned}$$
(52)

and

$$\begin{aligned} {l_i}(t + 1) = C(t) - {l_i}(t) \end{aligned}$$
(53)

Accumulating (52) and (53) from \(i = 0\) to \(i = N - 1\) , we gain another recursion equations

$$\begin{aligned} \overline{k} (t + 1) = C(t) - {e^{i\alpha }}\overline{k} (t) \end{aligned}$$
(54)

and

$$\begin{aligned} \overline{l} (t + 1) = C(t) - \overline{l} (t) \end{aligned}$$
(55)

Solving the recurrence Eqs. (54) and (55) to give

$$\begin{aligned} \overline{k} (t)&= {\left( {{ - 1}} \right) ^{t}}{e^{i\alpha t}}\left[ \frac{{d\sin (t\beta ) - \sin (t\beta - \beta )}}{{\sin \beta }}\overline{k} (0)\right. \nonumber \\&\left. +\, \frac{{(1 - {e^{ - i\alpha }})\cos ^{2}\theta \sin (t\beta )}}{{\sin \beta }}\overline{l} (0)\right] \end{aligned}$$
(56)

and

$$\begin{aligned} \overline{l} (t)&= {\left( {{ - 1}} \right) ^{t}}{e^{i\alpha t}}\left[ \frac{{\sin (t\beta + \beta ) - d\sin (t\beta )}}{{\sin \beta }}\overline{l} (0)\right. \nonumber \\&\left. -\, \frac{{\left( {{d^2} + 1} \right) \sin (t\beta ) - 2d\cos \beta \sin (t\beta )}}{{(1 - {e^{ - i\alpha }})\cos ^{2}\theta \sin \beta }}\overline{k} (0)\right] \end{aligned}$$
(57)

where \(d = {e^{i\alpha }}{\sin ^2}\theta + {\cos ^2}\theta ,\,\sin \theta = \sqrt{\frac{r}{N}} ,\cos \theta = \sqrt{\frac{{N - r}}{N}} \) ( \(0 \le \theta \le \pi /2\)), and \(\cos \beta = 1 - 2{\sin ^2}\theta {\sin ^2}(\alpha {\big /}2)\) ( \(0 \le \beta \le 2\pi ,0 < \alpha < 2\pi \)).

Subtracting (52) from (54) and subtracting (53) from (55), we find

$$\begin{aligned} {k_i}(t) - \overline{k} (t) = {k_i}(t - 1) - \overline{k} (t - 1) = \cdots = {k_i}(0) - \overline{k} (0) \end{aligned}$$
(58)

and

$$\begin{aligned} {l_i}(t) - \overline{l} (t) = - \left[ {{l_i}(t - 1) - \overline{l} (t - 1)} \right] = \cdots = {( - 1)^t}\left[ {{l_i}(0) - \overline{l} (0)} \right] \end{aligned}$$
(59)

So, we acquire the solutions of (52) and (53) from (58) and (59)

$$\begin{aligned} {k_i}(t) = \overline{k} (t) + {k_i}(0) - \overline{k} (0) \end{aligned}$$
(60)

and

$$\begin{aligned} {l_i}(t) = \overline{l} (t) + {( - 1)^t}\left[ {{l_i}(0) - \overline{l} (0)} \right] \end{aligned}$$
(61)

From (58) and (59), we can denote the variances of the amplitudes as follows

$$\begin{aligned} \sigma _k^2(t) = \frac{1}{r}{\sum \limits _{i \in A} {\left| {{k_i}(t) - \overline{k} (t)} \right| }^2} = \sigma _k^2(0) \end{aligned}$$
(62)

and

$$\begin{aligned} \sigma _l^2(t) = \frac{1}{{N - r}}{\sum \limits _{i \in B} {\left| {{l_i}(t) - \overline{l} (t)} \right| }^2} = \sigma _l^2(0) \end{aligned}$$
(63)

Set \({P_t}\) is the probability of success after \(t\) iterations to search out marked states

$$\begin{aligned} {P_t} = {\sum \limits _{i \in A} {\left| {{k_i}(t)} \right| }^2} = 1 - {\sum \limits _{i \in B} {\left| {{l_i}(t)} \right| }^2} = 1 - (N - r)\sigma _l^2(t) - (N - r){\left| {\overline{l} (t)} \right| ^2} \end{aligned}$$
(64)

Since \({\sigma _l}(t) = {\sigma _l}(0)\), (64) can be rewritten as

$$\begin{aligned} {P_t} = 1 - (N - r)\sigma _l^2(0) - (N - r){\left| {\overline{l} (t)} \right| ^2} \end{aligned}$$
(65)

When \(\overline{l} (t) = 0\), we define

$$\begin{aligned} {P_{\max }} = {P_t} = 1 - (N - r)\sigma _l^2(0) \end{aligned}$$
(66)

Simplifying the equation \(\overline{l} (t) = 0\), results are

$$\begin{aligned}&\sin (t\beta )\left[ (1 + \cos \alpha )(1 - \cos \beta )(\cos ^{2}\theta )\overline{l} (0) - 2\cos ^{2}\theta (1 - \cos \beta )\overline{k} (0)\right] \nonumber \\&\quad + \cos (t\beta )\sin \beta (1 - \cos \alpha )({\cos ^2}\theta )\overline{l} (0) = 0 \end{aligned}$$
(67)

and

$$\begin{aligned} \sin (t\beta )(\cos \beta - 1)\sin \alpha (\cos ^{2}\theta )\overline{l} (0) + \cos (t\beta )\sin \beta \sin \alpha (\cos ^{2}\theta )\overline{l} (0) \end{aligned}$$
(68)

Since \(0 < \alpha < 2\pi \) and \(\cos \theta \ne 0\) (otherwise, the search space is composed by the marked states), we rewrite (67) as

$$\begin{aligned} \frac{{\sin (t\beta )(1 + \cos \alpha )\sin ^{2}\theta + \cos (t\beta )\sin \beta }}{{2{{\sin }^2}\theta \sin (t\beta )}} = \frac{{\overline{k} (0)}}{{\overline{l} (0)}} \end{aligned}$$
(69)

Solving (69), the optimal iterations of Grover is

$$\begin{aligned} t = \left\lfloor {\frac{{\frac{\pi }{2} - \arctan \left[ {\left( {\frac{{\overline{k} (0)}}{{\overline{l} (0)}} - \frac{{1 + \cos \alpha }}{2}} \right) \frac{{2{{\sin }^2}\theta }}{{\sin \beta }}} \right] }}{\beta }} \right\rfloor \end{aligned}$$
(70)

Where \(\lfloor \rfloor \) means rounding down.

Substitute \(t = 1\) in (69), we derive that the rotation angle \(\alpha \) satisfies

$$\begin{aligned} \cos \alpha = \frac{{\overline{k} (0)}}{{\overline{l} (0)}} - \frac{1}{{2{{\sin }^2}\theta }} \end{aligned}$$
(71)

Thus, \({P_t} = {P_{\max }}\) after applying just one iteration when \( - 1 \le \cos \alpha < 1\), i.e.,

$$\begin{aligned} {- 1} \le \frac{{\overline{k} (0)}}{{\overline{l} (0)}} - \frac{1}{{2{{\sin }^2}\theta }} < 1 \end{aligned}$$
(72)

Substitute \(t = 2\) in (69), we derive that the rotation angle \(\alpha \) satisfies

$$\begin{aligned} \cos \alpha = \frac{1}{2}\left( 1 + \frac{{\overline{k} (0)}}{{\overline{l} (0)}}\right) - \frac{{3 \pm \sqrt{{{\left[ {2\sin ^{2}\theta (1 - \frac{{\overline{k} (0)}}{{\overline{l} (0)}}) - 1} \right] }^2} + 4}}}{{4{{\sin }^2}\theta }} \end{aligned}$$
(73)

Thus, \({P_t} = {P_{\max }}\) after applying just two iterations when

$$\begin{aligned} {- 1} \le \frac{1}{2}\left( 1 + \frac{{\overline{k} (0)}}{{\overline{l} (0)}}\right) - \frac{{3 \pm \sqrt{{{\left[ {2\sin ^{2}\theta \left( 1 - \frac{{\overline{k} (0)}}{{\overline{l} (0)}}\right) - 1}\right] }^2} + 4}}}{{4{{\sin }^2}\theta }} < 1 \end{aligned}$$
(74)

If (72) or (74) are not satisfied, we take \(\alpha = \pi \) in (70) and \({P_t} \approx {P_{\max }}\) after

$$\begin{aligned} t = \left\lfloor {\frac{{\frac{\pi }{2} - \hbox { arctan } \left[ {\frac{{\overline{k} (0)}}{{\overline{l} (0)}}\sqrt{\frac{r}{{{N} - r}}}}\right] }}{{\hbox {arccos }(1 - 2\frac{r}{N})}}}\right\rfloor \end{aligned}$$
(75)

iterations.

When \({r}\ll N,\,t\) is in maximum. Setting \({r} \ll N\) , from (75), we infer

$$\begin{aligned} t < \frac{\pi }{2}\frac{1}{{\hbox { arccos } (1 - 2\frac{r}{N})}} < \frac{{\frac{\pi }{4}\sqrt{N/r} }}{{\sqrt{1 - \frac{r}{N}} }} \approx \frac{\pi }{4}\sqrt{N/r} \end{aligned}$$
(76)

Therefore, the minimum number of iterations \(t\) is in \(O(\sqrt{N/r} )\) from (71), (73) and (76).

Suppose that

$$\begin{aligned} {\left| {{k_i}(t)} \right| ^{2}} = P_t^i, \ {\left| {{k_i}(0)} \right| ^{2}} = P_0^i \end{aligned}$$
(77)

So \(\sum \nolimits _{i \in A} {{P}_t^i} = {{P}_t}\) , \(\sum \nolimits _{i \in A} {{P}_0^i} = {{P}_0}\) from (64). We rewrite (60) as

$$\begin{aligned} {k_i}(0) = {k_i}(t) - \overline{k} (t) + \overline{k} (0) \end{aligned}$$
(78)

By (72), (74) or (75), taking appropriate \(t\) and \(\alpha \) in (56), we calculate \(\overline{k} (t)\). Since \({k_i}(0)\) and \(\overline{k} (0)\) are real , by (78), we can suppose

$$\begin{aligned} \overline{k} (t) = a + bi, \ {k_i}(t) = {c_i} + bi \end{aligned}$$
(79)

For \({k_i}(0) > 0 (i = 0,1, \ldots (N - 1))\), Grover search algorithm increases the total probability of the marked states and keeps the relative amplitude among the marked states, so \({a} \times {{c}_i} > 0\) (i.e., the signs of \(a\) and \({{c}_i}\) are the same). Hence, from (77) and (79), we yield

$$\begin{aligned} {c_i}&= \sqrt{{P}_t^i - {b^2}}, when \quad a > 0 \end{aligned}$$
(80)
$$\begin{aligned} {c_i}&= - \sqrt{{P}_t^i - {b^2}}, when \quad a < 0 \end{aligned}$$
(81)

From (78) and (79), we obtain

$$\begin{aligned} {k_i}(0) = {c_i} - a + \overline{k} (0) \end{aligned}$$
(82)

Therefore, select \(\alpha \), after \(t\) iterations, \({P_t} = {P_{\max }}\) or \({P_t} \approx {P_{\max }}\). We detect the state \({({G_\phi })^t}(\left| \psi \right\rangle )\) to acquire values of \({\left| {{k_i}(t)} \right| ^2} (i = 0,1, \ldots (N - 1))\) by the method shown in Sect. 4.1 in this paper, and further get values of \({k_i}(0)\) (i.e., amplitudes of the initial state \(\left| \psi (r) \right\rangle \)) from (80), (81) and (82). When \(\sigma _l^2(0) \approx 0\) (colors of the background sub-image are similar), \({P_t} \approx 1\) , in this case, measuring \({({G_\phi })^t}(\left| \psi \right\rangle ) \approx \sum \limits _{i \in A} {{k_i}(t)} \left| i \right\rangle \left| 1 \right\rangle \), we retrieve a coordinate of the marked sub-image with approximate probability 100 % every time.

In order to make the above description explicit, let us consider a \(512 \times 512\) image shown on the left of Fig. 5 as an example. We consider two cases: Only retrieve the coordinates of the edge of the airplane (see the middle of Fig. 5) and retrieve the whole airplane including colors and coordinates (see the right of Fig. 5). The process of the example consists of the following steps.

  1. (1)

    Store the original image on the left of Fig. 5 in quantum systems as a quantum state \(\left| {\psi (1)} \right\rangle \) or \(\left| {\psi (2)} \right\rangle \).

  2. (2)

    Apply improved Grover’s algorithm on a quantum state \(\left| {\psi (1)} \right\rangle \) or \(\left| {\psi (2)} \right\rangle \).

  3. (3)

    Measure the quantum state after \(t\) iterations of Grover and retrieve the target sub-image.

    Fig. 5
    figure 5

    (left) The original image is segmented into two sub-images, one of which is marked ’0’ as a background sub-image and the other one is marked ’1’ as a target sub-image. (middle) The target sub-image is the edge of the airplane, and the background sub-image is the original image except the edge of the airplane. (right) The target sub-image is the whole airplane, and the background sub-image is the original image except the airplane

    Full size image

In (1) step, first, we represent colors of the original image by using angles \(\left\{ {{a_i}} \right\} \) (see Eq. (2)). Second, calculating \({\theta _{i}} = \frac{{{a_i}}}{{{G_\phi }}}\) where \({G_\phi } = \sqrt{\sum \nolimits _{y = 0}^{N - 1} {a_y^2} } \) and \(N = 262144\) , we acquire a quantum state (\(\left| {\psi (1)} \right\rangle \) or \(\left| {\psi (2)} \right\rangle \)) as the representation of the original image for No. 1 (the edge of an airplane) or No. 2 (the whole airplane) case.

$$\begin{aligned} \left| {\psi (1)} \right\rangle = \sum \limits _{i = 0,i \in B}^{262143} {{\theta _i}\left| i \right\rangle } \otimes \left| 0 \right\rangle + \sum \limits _{i = 0,i \in A}^{262143} {{\theta _i}\left| i \right\rangle } \otimes \left| 1 \right\rangle \end{aligned}$$
(83)

where \(B\) and \(A\) are defined as two sets containing coordinates of the background sub-image and the edge of the airplane (see the middle of Fig. 5), respectively.

$$\begin{aligned} \left| {\psi (2)} \right\rangle = \sum \limits _{i = 0,i \in B}^{262143} {{\theta _i}\left| i \right\rangle } \otimes \left| 0 \right\rangle + \sum \limits _{i = 0,i \in A}^{262143} {{\theta _i}\left| i \right\rangle } \otimes \left| 1 \right\rangle \end{aligned}$$
(84)

where \(B\) and \(A\) are defined as two sets contain coordinates of the background sub-image and the whole airplane (see the right of Fig. 5), respectively. Third, we create the quantum state (\(\left| {\psi (1)} \right\rangle \) or \(\left| {\psi (2)} \right\rangle \)) by the quantum circuit in Fig. 1. Finally, we store some priori data in quantum systems shown in Table 2.

Table 2 \({G_\phi },\,N\) (number of pixels of the original image), \(r\) (number of pixels of the target sub-image), \(\overline{k} (0) = \frac{1}{r}\sum \nolimits _{i \in A}^{} {{\theta _i}} ,\,\overline{l} (0) = \frac{1}{{N - r}}\sum \nolimits _{i \in B}^{} {{\theta _i}} \) and \(\sigma _l^2(0) = \frac{1}{{N - r}}{\sum \nolimits _{i \in B} {\left| {{\theta _i} - \overline{l} (0)} \right| }^2}\) are some priori data
Full size table

In (2) step, \(\alpha \) (a rotation angle of marked and unmarked states corresponding to the target sub-image and the background sub-image), \(t\) (the number of iterations of Grover), \({P_{\max }}\) (the max probability of success after t iterations to search out marked states) are calculated by Eqs. (71–75), (66) and shown in Table 3. And then, we design the quantum circuit of the improved Grover’s algorithm shown in Fig. 6.

Table 3 Some calculated data
Full size table
Fig. 6
figure 6

The quantum circuit of the improved Grover’s algorithm. a for No. 1 case and b for No. 2 case, dashed box is an oracle (i.e., \({I_r}\) in Eq. (48)) and solid box is \( - {H^{ \otimes 18}}({I^{ \otimes 18}} - (1 - {e^{i\alpha }})\left| 0 \right\rangle \left\langle 0 \right| ){H^{ \otimes 18}}\) where \(\alpha = \pi \) and \(\alpha = 2.545259554463482\), respectively. Note \(\left| {{\chi _i}} \right\rangle \) is a state \(\left| 0 \right\rangle \) or \(\left| 1 \right\rangle \), \(R(\alpha ) = \left[ {\begin{array}{*{20}{c}} {{{e}^{i\alpha }}}&{}0\\ 0&{}{{{e}^{i\alpha }}} \end{array}} \right] \) in Fig. 6

Full size image

In (3) step, for No. 1 case, we retrieve a coordinate of the edge of the airplane with probability 94.13 % by measuring the first 19 qubits in (a) of Fig. 6 every time. For No. 2 case, we know that \(\left| {\psi (t)} \right\rangle = \sum \nolimits _{i \in B} {{l_i}(t)} \left| i \right\rangle \left| 0 \right\rangle + \sum \nolimits _{i \in A} {{k_i}(t)} \left| i \right\rangle \left| 1 \right\rangle \) after \(t\) Grover iterations where \({k_i}(t)\) and \({l_i}(t)\) are amplitudes of the marked and unmarked states, and obtain \({\left| {{k_i}(t)} \right| ^2}\) by measuring the first 19 qubits in (b) of Fig. 6. Then, we get \({k_i}(0)\) (i.e., \({\theta _i}\)) by Eqs. (77–82) and calculate \({a_i} = {\theta _{i}} \times {G_\phi }\) which represents a color. We can retrieve a coordinate of the airplane with probability 95.59 % by measuring (b) of Fig. 6 every time, but we retrieve a coordinate of the airplane with probability 8.63 % (\(\sum \nolimits _{i \in A}^{} {{{({\theta _i})}^2}} = 0.0863\)) by measuring directly the original image in Fig. 5.

If the number of sub-images \(2 < m \le 8\), the NAQSS state \(\left| \psi (r) \right\rangle \) in (43) is small changed into

$$\begin{aligned} \left| {{\psi _m}} \right\rangle = \sum \limits _{i = 0}^{N - 1} {{\theta _i}\left| i \right\rangle } \otimes \left| j \right\rangle ,j \in \left\{ {0,1, \cdots ({2^{\left\lceil {\log (m)} \right\rceil }} - 1)} \right\} \end{aligned}$$
(85)

For example, suppose \(m = 4\), let us consider a \(4 \times 4 \times 2\) image shown in Fig. 7 as an example. Grover search algorithm for state \(\left| {{\psi _m}} \right\rangle \) in (85) just needs to redefine the quantum Oracles as following: \(f({i_1}{i_2} \cdots {i_n}00) = 1,\,f({i_1}{i_2} \cdots {i_n}01) = 1,\,f({i_1}{i_2} \cdots {i_n}10) = 1\) and \(f({i_1}{i_2} \cdots {i_n}11) = 1\) correspond, respectively, to No. 0, 1, 2, 3 sub-images in Fig. 7. For example, we retrieve No. 0 sub-image using Grover search algorithm by redefined \(A\) and \(B\)

$$\begin{aligned} A = \{ i|f({i_1}{i_2} \cdots {i_n}{j_1}{j_2}) = 1\} ,B = \{ i|f({i_1}{i_2} \cdots {i_n}{j_1}{j_2}) = 0\} \end{aligned}$$
(86)

where \(f({i_1}{i_2} \cdots {i_n}00) = 1, f({i_1}{i_2} \cdots {i_n}{j_1}{j_2}) = 0\) for \({j_1}{j_2} \ne 00,\,i = {i_1}{i_2} \cdots {i_n}\) and \({i_1},{i_2}, \ldots {i_n},{j_1},{j_2} \in \left\{ {0,1} \right\} \).

Fig. 7
figure 7

A \(4 \times 4 \times 2\) image which is divided into four sub-images (numbered as 0, 1, 2, 3), and on the right for lower sub-image

Full size image

5 Conclusion

In this paper, a (\(n+1\))-qubit NAQSS state can represent a k-dimensional color image, where \(n\) qubits represent colors and coordinates of \({2^n}\) pixels and 1 qubit represents an image segmentation information to improve the accuracy of image segmentation, while only the image (not including additional segmentation information) is represented by (\(n+1\))-qubits in paper [7]. And we design a general quantum circuit to store an image in quantum systems and study the different strategies to retrieve images from quantum systems. So, the NAQSS provides a foundation not only to represent images but also to explore theoretical and practical aspects of image processing on quantum computers.