Abstract
A quantum algorithm with certainty is introduced in order to find a marked pre-image of an element which is known to be in the image domain of an orthogonal projection operator. The analysis of our algorithm is made by using properties of the Moebius transformations acting on the complex projective line. This new algorithm closely resembles the quantum amplitude amplification algorithm, however it is proven that our algorithm is a proper generalization of the latter (with generalized phases), in such a way that the quantum search engine of the main operator of quantum amplification is included as a particular case. In order to show that there exist search problems that can be solved by our proposal but cannot be by applying the quantum amplitude amplification algorithm, we modify our algorithm as a cryptographic authentification protocol. This protocol results to be robust enough against attacks based on the quantum amplitude amplification algorithm. As a byproduct, we show a condition where it is impossible to find exactly a pre-image of an orthoghonal projection. This result generalizes the fact that, it is impossible to find a target state exactly by using quantum amplification on a three dimensional invariant subspace.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Goguen J.A.: A categorical manifesto. Math. Struct. Comput. Sci. 1, 49–67 (1991)
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lomonaco, J. S. J., Brandt, H.E. (eds.) Quantum Computation and Quantum Information: A Millennium Volume. AMS Contemporary Mathematics Series, vol. 305, pp. 53–74 (2002)
Grover L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997)
Grover L.K.: Quantum computers can search rapidly by using almost any transformation. Phys. Rev. Lett. 80, 4329–4332 (1998)
Long G.L., Zhang W.L., Li Y.S., Niu L.: Arbitrary phase rotation can not be used in Grover’s quantum search algorithm. Commun. Theor. Phys. 32, 335–338 (1999)
Long G.L., Li X., Sun Y.: Phase matching condition for quantum search with a generalized initial state. Phys. Lett. A 294, 143–152 (2002)
Høyer P.: Arbitrary phases in quantum amplitude amplification. Phys. Rev. A 62, 052,304 (2000)
Long G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64, 022,307 (2001)
Biham E., Biham O., Biron D., Grassl M., Lidar D.A.: Grover’s quantum search algorithm for an arbitrary initial amplitude distribution. Phys. Rev. A 60, 2742–2745 (1999)
Carlini A., Hosoya A.: Quantum computers and unstructured search: finding and counting items with an arbitrarily entangled initial state. Phys. Lett. A 280, 114–120 (2001)
Jin W.L., Chen X.D.: A desired state can not be found with certainty for Grover’s algorithm in a possible three-dimensional complex subspace. Quantum Inf. Process. 10, 419–429 (2011)
Jin, W.: Quantum search in a possible three-dimensional complex subspace. Quantum Inf. Process. (2011). doi:10.1007/s11128-011-0230-5
Li D.F., Li X.X.: More general quantum search algorithm Q = −I γ VI τ U and the precise formula for the amplitude and the non-symmetric effects of different rotating angles. Phys. Lett. A 287, 304–316 (2001)
Long G.L., Yang L.: Search an unsorted database with quantum mechanics. Front. Comput. Sci. China 1(3), 247–271 (2007)
Ahlfors L.V.: Complex Analysis. 3rd edn. McGraw-Hill, Tokyo (1979)
Conway J.B.: Functions of One Complex Variable I. 2nd edn. Springer, New York (1995)
Needham T.: Visual Complex Analysis. Oxford University Press, Oxford (2002)
Lee J., Kim C.H., Lee E., Kim J., Lee S.: Qubit geometry and conformal mapping. Quantum Inf. Process. 1(1/2), 129–134 (2002)
Bautista-Ramos C., Castillo-Tepox N.: Möbius transformations in quantum amplitude amplification with generalized phases. Int. J. Quantum Inf. 8(6), 923–935 (2010)
Codd E.F.: A relational model of data for large shared data banks. Commun. ACM 13, 377–387 (1970)
Codd E.F.: The Relational Model for Database Management: Version 2. Addison-Wesley, Reading Mass (1990)
Abiteboul S., Hull R., Vianu V.: Foundations of Databases. Addison-Wesley, Reading Mass (1995)
Agoston M.K.: Computer Graphics and Geometrical Modeling. Springer, London (2005)
Hartley R., Zisserman A.: Multiple View Geometry in Computer Vision. Cambrigde University Press, Cambridge (2003)
Xie M.: Fundamentals of Robotics: linking perception to action. World Scientific, Singapore (2003)
Menezes A., van Oorschot P., Vanstone S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Schwerdtfeger H.: Geometry of Complex Numbers. Dover, New York (1979)
Schwerdtfeger H.: Moebius transformations and continued fractions. Bull. Amer. Math. Soc. 52, 307–309 (1946)
Lane R.: The convergence and the values of periodic continued fractions. Bull. Amer. Math. Soc. 51, 246–250 (1945)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bautista-Ramos, C., Guillén-Galván, C. & Rangel-Huerta, A. From orthogonal projections to a generalized quantum search. Quantum Inf Process 12, 1–20 (2013). https://doi.org/10.1007/s11128-011-0355-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-011-0355-6