Journal of Quantum Information Science, 2012, 2, 5560 http://dx.doi.org/10.4236/jqis.2012.23010 Published Online September 2012 (http://www.SciRP.org/journal/jqis) Quantum Image Searching Based on Probability Distributions Fei Yan1, Abdullah M. Iliyasu1,2, Chastine Fatichah1, Martin L. Tangel1, Janet P. Betancourt1, Fangyan Dong1, Kaoru Hirota1 1Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama, Japan 2College of Engineering, Salman Bin AbdulAziz University, AlKharj, KSA Email: yan@hrt.dis.titech.ac.jp Received August 19, 2012; revised September 4, 2012; accepted September 10, 2012 ABSTRACT A quantum image searching method is proposed based on the probability distributions of the readouts from the quantum measurements. It is achieved by using low computational resources which are only a single Hadamard gate combined with m + 1 quantum measurement operations. To validate the proposed method, a simulation experiment is used where the image with the highest similarity value of 0.93 to the particular test image is retrieved as the search result from 4 × 4 binary image database. The proposal provides a basic step for designing a search engine on quantum computing devices where the image in the database is retrieved based on its similarity to the test image. Keywords: Quantum Computation; Image Processing; Quantum Image; Quantum Circuit; Image Searching; Probability Distribution 1. Introduction Research on quantum image processing has started from proposals on quantum image representations such as Qubit Lattice [1], Real Ket [2], and Flexible Representation of Quantum Image (FRQI) [3]. On the basis of these image representations, basic quantum operations can be realized by applying the elementary gates such as PauliX and Hadamard gates combined with appropriate quantum measurements [4,5]. For example, several processing transformations have been proposed based on the FRQI representation such as the geometric transformations, GTQI [6], and the CTQI [7], which focuses on the color information. In addition, a method to analyze the similar ity between two FRQI quantum images of the same size is suggested in [8], which advances a fundamental step to wards image searching on quantum mechanical systems. Inspired by the image searching on conventional com puters, the research on quantum image searching is also an indispensible field on quantum image processing. In order to improve the limitation of the traditional search ing, e.g. only text based and time consuming, the quan tum image searching on the strength of the content of the images can be executed in parallel to realize more effi cient computation. A quantum image searching method is proposed whe reby an image could be retrieved as a search result from a database based on the extent of its similarity in compari son with the particular test image. The searching result is provided by the probability distributions from two types of quantum measurements, the first of which, Zaxis measurement, represents the similarity between two cur rent images being compared; the second type, Saxis measurements, gives the position of the compare ing results in Zaxis measurement. Succinctly put, the main contributions of this work include the analysis of the si milarity between multiple pairs of images simulta neously and the proposal of the whole scheme for the image searching on quantum mechanical systems. The searching process is based on “parallel compare son”, where 2m pairs of quantum images are compared in parallel. In addition, the method is executed using low computational resources in comparison with performing the same task on traditional computing devices, since only a single Hadamard gate as well as m + 1 quantum measurement operations could transform the entire in formation encoding the quantum images in a strip simul taneously. The ZStrip is defined based on the flexible represent tation of quantum images (FRQI) in 2. The proposed scheme to realize image searching on quantum mechani cal systems is presented in 3. The simulation experiment and its discussion are shown in 4. 2. Representation of ZStrip to Indicate Multiple FRQI Images For the quantum image processing, a good deal of opera C opyright © 2012 SciRes. JQIS
F. YAN ET AL. 56 tions are done by relying on the corresponding applicai tons on classical image processing as reference [3,9]. The flexible representation for quantum images, FRQI [3], which is similar to the pixel representation for images on conventional computers, captures the essential information about the colors as well as the corresponding positions of every point in an image and integrates them into a quan tum state having its formula in (1), 2 21 0 1, 2 n ii n nc i (1) cos0 sin 1, ii i c (2) 2 0, π2,0,1,, 21, n ii (3) where 0 and 1 are 2D computational basis quan tum states, i, are 2nD computa tional basis quantum states and 2 01 21 n, is the vector of angles encoding colors. There are two parts in the FRQI representation of an image; 2 0,1,, 21 n i ,, , i c and i which encode information about the colors and corre sponding positions in the image, respectively. A dexterous property of Zstrip representation encod ing 2m+1ending FRQI images is its ability to utilize the parallelism inherent to quantum computation in order to transform multiple images using very few quantum re sources. The Zstrip representation is defined in Defini tion 1. Definition 1 A Zstrip, , mn , is a horizontal combination of two strips [10], which are located on the left and right side, respectively. The state of Zstrip is defined by 21 0 12 , 101 2 m ss s m Zmn Ln Rns , (4) where s Ln and s Rn are FRQI images as de fined in (5) and (6), 2 21 0,, 1, 2 n silsi n Lnc i (5) 2 21 0,, 1, 2 n sirsi n Rnc i (6) ,, ,,,, cos0sin1 , lsi lsilsi c (7) ,, ,,,, cos0sin1, rsi rsirsi c (8) ,, ,, ,0,π2, lsirsi (9) 2 0,1,, 21,0,1,, 21. n is m (10) As seen in Figure 1, the size of a Zstrip in the repre sentation captures the input state comprising 2m+1 quan tum images. The Zaxis differentiates the strip which is located on the left and the right position. Each image in the Zstrip is an FRQI state while the combination of such states in the Zstrip is best represented as a ZFRQI state. The ZFRQI state represents 2m + 1 quantum images us ing only m + 2n + 2 qubits since all of the images are of the same size on this Zstrip. A notation “○” for “0” or “●” for “1” controlcondition on Zaxis or Saxis, is suf ficient to specify any quantum image in the Zstrip. In addition, combining with the controlconditions from the position x to the color wire; every pixel in this strip can be accessed. The representation also facilitates the quantum operation to all the images in this strip. An example that has two 2 × 2 images on both the left and right side of the Zstrip, respectively, including its circuit structure and ZFRQI state is shown in Figure 2. 3. Image Searching on Quantum Mechanical Systems Inspired by the image searching on conventional com puter, quantum image searching from a database is also an indispensable field in quantum image processing [11, 12]. A first step towards realizing that would be to pro pose a scheme so as to evaluate the extent to which two or more images are similar to one another. The parallel computation on quantum computer leads us to find a way Figure 1. Circuit structure to encode the Zstrip input. Figure 2. An example of Zstrip, its circuit structure and ZFRQI st a te. Copyright © 2012 SciRes. JQIS
F. YAN ET AL. Copyright © 2012 SciRes. JQIS 57 10 ss PP that comparing many pairs of images in parallel. The proposal of the Zstrip comprising 2m+1 images in the Definition 1 provides us a crucial condition to make the parallel comparison of quantum images possible because the operation on the strip wires can transform the infor mation in every image simultaneously. The generalized circuit structure of comparing 2m pairs of FRQI quantum images in parallel is presented in Figure 3. 1 , as they should. Definition 2 Pixel difference in position i, , i , is de fined by ,,,,,, , 0,π2, silsirsisi (16) where ,,lsi and ,,rsi represent the color information at position i of the two images which are at the sth posi tion of the Zstrip, respectively. The input of this circuit is the ZFRQI state as defined in (4), a Hadamard gate, which maps the basis state 0 to 01 2 and 1 to 01 2, is applied on the Zaxis to obtain the new mathematical expressions between the two images being compared. The final step in the circuit consists of m + 1 measurements from which the similarity can be retrieved in each pair of images. It is apparent that, arising from (15) and (16), the pixel difference , i is related to the probability of getting readout of 1 from the Zaxis, 1 s P, in the measure ment and 1 s P will increase when pixel difference increases. Furthermore, the similarity between the two images, which is the function of the pixel differences at every position, depends on 1 s P as given by When n experiments are performed, the measurement results on the Zaxis follow a binomial distribution. The probability of obtaining k readouts of 1 in n experiments is given by the probability mass function 2 21 0, 2 1 ,121 cos 2, n ss i n sim LnRnPsi (17) where s Ln and s Rn are the two images being compared, ,1 nk kk n PrXkC pp (11) 1 s P is defined in (15), and ,0 where X is the incident that the result of measurement is 1, p is the probability of 1 when the results on the Zaxis are measured, . 0,1, ,kn ,1sim LnRn ss Two special cases of the similarity between two quan tum images are listed as follows: . a) ifi , ,π2 si , th en ,0 ss sim LnRn , two images are totally different; Meanwhile, the measurement results on the Saxis, 10 , mr ss , give the position of probabilities of the measurements on the Zaxis. Accord ing to the readouts on both the measurements, the similarity between each pair of images on the Zstrip can be assessed, from which the quantum image searching can be realized. 0,1 r s b) ifi , ,0 si , then ,1 ss sim LnRn , two images are exactly the same, where i = 0, 1, ···, 22n − 1, , i is the pixel difference at position i as defined in Definition 2. Corresponding to the circuit shown in Figure 3, the state of quantum system after applying the Hadamard gate on the strip wire can be shown in (12) and (13). Obviously, the result of the measurement depends on the disparities between s Ln and s Rn . The probability of state 0 on the Zaxis at position 12 0 ,,, mm s s is shown by 2 21 0,,, 21 11 cos 22 0. n , ilsir n P si (14) In the same manner, that of state 1 on the same wire is 2 21 0,,, 21 11 1cos , 22 n . ilsirsi n P (15) Figure 3. Generalized circuit structure for parallel com parison of quantum images. The probabilities of these two states sum up to 1, 2 21 2 21 0 2 0 12 01 01 1 ,222 1 01, 2 m m ziss m is ss s m HZmnLn Rns Ln RnLn Rns (12) where 2 21 0,,,, ,,,, 1coscos0 sinsin1. 2 n ssilsirsilsirsi n Ln Rni (13)
F. YAN ET AL. 58 Based on the comparison method and the probability distributions introduced above, the scheme to accomplish the image searching on quantum mechanical systems is presented in Figure 4. The quantum images are prepared from the classical images using FRQI representation [3,8,10,13]. The color information as well as the corresponding positions of every point in the classical image is integrated into the quantum state, and 2m+1 quantum images being com pared are combined as a Zstrip. Because of the superpo sition property of quantum computation, such a work can be realized using only a few quantum resources. The Zstrip prepared in the preceding period is trans formed using a gate array comprising of geometric, GTQI [6], and color, CTQI [7], transformations on all the images in the strip. For this particular application, the transformations are built in a way to allow the recovery of the pixel difference as defined in (16). This transfor mation unit combines with measurement operations that follow it to convert the quantum information into the classical form as probability distributions. The Zstrip is prepared n (n > 1) times to compare the similarity be tween two quantum images in parallel since a measure ment would destroy the superposition state in the quan tum system [5]. Extracting and analyzing the distribu tions gives information that the similarity values between the quantum images being compared, so that the image with the highest similarity to the particular test image could be retrieved as a result from the database. The operation to search image on quantum mechanical systems is realized by using only a single Hadamard gate and several measurements. Such an image searching scheme, however, can only be achieved on a classical computer by comparing one pair of images at a time. Hence, the proposed method offers a significant speedup compared to how it is performed using classical comput ing resources. Figure 4. Block diagram of scheme to realize image search ing on quantum mechanical systems. 4. A Simulation Experiment to Search Quantum Images from Database A conventional desktop computer with Intel Core i7, 2 Duo 2.80 GHz CPU, 4GB RAM and 64bit operating system is used to simulate the experiment. The simula tion experiment is based on linear algebra with complex vectors as quantum states and unitary matrices as unitary transformations using Matlab, and the program is en coded by means of equations as well as the definitions that are introduced in earlier sections of this paper. The purpose of this experiment is that to search the image from a database which has the highest similarity with the test image. An original database which includes sixtyfour (64) 4 × 4 binary image data is used, then the Zstrip comprising of 02D, 12D, , 63 2D, and sixtyfour (64) 2Ts is constituted as shown in Figure 5. The corresponding circuit structure to realize such an image searching is presented in Figure 6. There are three steps to achieve this comparison: Figure 5. Image searching from database . Figure 6. Circuit structure for realizing the image searching in Figure 5. Copyright © 2012 SciRes. JQIS
F. YAN ET AL. 59 Step 1. The test images 2T is prepared from the classical version using FRQI representation and inte graed to a Zstrip state with the images D in the da tabse. Step 2. A Hadamard operation is applied on the Zaxis in order to compare the test image 2T with 02D, 12D, , 63 2D. Step 3. The measurements which convert the quantum information to the classical form are used on the Saxis and Zaxis to distribute the readouts from which the his togram is built to reflect the similarity of the 64 pairs of images. The circuit comprises of 12 qubits of which 6 are used to address positions of the image, 1 qubit is reserved for storing the information about the colors, and the remain ing qubits are prepared for representing the Zstrip wire where the Hadamard gate and measurement MZ are ap plied. A simulation of a single Hadamard gate and 7 measurement operations are used to obtain the similari ties for these 64 pairs of images based on the probabili ties of getting the readouts on the Zaxis and Saxis in the measurements as shown in the Figure 7. From the histo gram, the image 37 2D, which manifests the highest similarity value of 0.93 to the test image 2T is re trieved as the search result. There is only one different grid between the test image and 37 2D, which are shown in Figure 8. It is testified from that the quantum image searching is based on the pixel difference between the test image and the images in the database. The foregoing experiment provides the foundation for the next step in quantum image processing based on the FRQI representation. The results as indicated in this sec tion show that the quantum image searching on quantum mechanical systems is feasible and practical. Further more, the target area to apply the proposed method is the development of the search engine on quantum computing devices. 5. Conclusions The simulation experiment is performed to search for a target image from an original database comprising of sixtyfour (64) binary images. There are 12 qubits which encodes each image in the Zstrip and 7 quantum meas urements which are for converting the quantum informa tion to the classical form as probability distributions in the circuit. According to the readouts from the measure ments, the similarity of each pair between the test image and the images in the database is calculated. For the simulationbased database used in this paper, the 38th image, 37 2D, with the highest similarity value of 0.93 is retrieved as search result. It is concluded that the more images in the database, the better the ability of the proposed method. This is because m qubits on the strip wires can represent 2m quantum images in the Zstrip,and Figure 7. Similarities among different pairs of images in Zstrip. Figure 8. The test image 2T and the retrieved image 37 2D. only one qubit on the Zaxis can represent the images on both the left and right side of Zstrip. This further dem onstrates the low computational resources of the pro posed method compared to performing the same task on traditional computing devices. As for future work, the proposal will be applied on de signing a search engine on such quantum computing de vices that the image in the database is retrieved based on its similarity to the test image. Most of the search engines recently are only based on the text to realize the search ing. Even some searching is developed based on the con tent of the images. It is, however, usually timeconsum ing. This work, which realizes the searching based on the content of the images and is executed in parallel, pro poses a basic step for the quantum image searching, es pecially when a database comprising of a huge amount of data is confronted. 6. Acknowledgements This work is sponsored by the ASPIRE League (Asian Science and Technology Pioneering Institutes of Re search and Education). The authors appreciate the kind comments and professional criticisms of the anonymous reviewer. The suggestions and advices received from Messrs Phuc Q. Le and Bo Sun are also appreciated. These various inputs have greatly enhanced the overall Copyright © 2012 SciRes. JQIS
F. YAN ET AL. Copyright © 2012 SciRes. JQIS 60 quality of the manuscript and opened numerous perspec tives geared toward improving the work in the future. REFERENCES [1] S. E. VenegasAndraca and S. Bose, “Storing, Processing and Retrieving an Image Using Quantum Mechanics,” Proceedings of SPIE Conference of Quantum Information and Computation, Vol. 5105, 2003, pp. 134147. [2] J. I. Latorre, “Image Compression and Entanglement,” 2005, in press. [3] P. Q. Le, A. M. Iliyasu, F. Dong and K. Hirota, “A Flexi ble Representation and Invertible Transformations for Images on Quantum Computers,” New Advances in Intel ligent Signal Processing, Book Series: Studies in Compu tational Intelligence, Vol. 372, 2011, pp. 179202. doi:10.1007/9783642117398_9 [4] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, et al., “Elementary Gates for Quantum Computation,” Physical Review A, Vol. 52, No. 5, 1995, pp. 34573467. doi:10.1103/PhysRevA.52.3457 [5] M. Nielsen and I. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press, New York, 2000. doi:10.2277/0521635039 [6] P. Q. Le, A. M. Iliyasu, F. Dong and K. Hirota, “Fast Geometric Transformations on Quantum Images,” IAENG International Journal of Applied Mathematics, Vol. 40, No. 3, 2010, pp. 113123. [7] P. Q. Le, A. M. Iliyasu, F. Dong and K. Hirota, “Efficient Color Transformations on Quantum Image,” Journal of formatics, Vol. 15, No. 6, 2011, pp. 698706. [8] F. Yan, P. Q. Le, A. M. Iliyasu, B. Sun, J. A. Garcia, F. Dong and K. Hirota, “Assessing the Similarity of Quan tum Images Based on Probability Measurements,” 2012 IEEE World Congress on Computational Intelligence, Brisbane, 1015 June 2012, pp. 16. doi:10.1109/CEC.2012.6256418 [9] R. S. Bennink, S. J. Bentley and R. W. Boyd, “Quantum and Classical Coincidence Imaging,” Physical Review Letters, Vol. 92, No. 6, 2004, pp. 14. doi:10.1103/PhysRevLett.92.069901 [10] A. M. Iliyasu, P. Q. Le, F. Dong and K. Hirota, “A Framework for Representing and Producing Movies on Quantum Computers,” International Journal of Quantum Information, Vol. 9, No. 6, 2011, pp. 14591497. doi:10.1142/S0219749911008015 [11] L. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack,” Physical Review Letters, Vol. 79, No. 2, 1997, pp. 325328. doi:10.1103/PhysRevLett.79.325 [12] M. Inoue, “On the Need for AnnotationBased Image Retrieval,” Proceedings of the ACMSIGIR Workshop on Information Retrieval in Context, Sheffield, 29 July 2004, pp. 4446. [13] A. M. Iliyasu, P. Q. Le, F. Dong and K. Hirota, “Water Marking and Authentication of Quantum Images Based Restricted Geometric Transformations,” Information Sci ences, Vol. 186, No. 1, 2012, pp. 126149. doi:10.1016/j.ins.2011.09.028
