[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Geometric pictures for quantum search algorithms

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

In this paper, we give the geometric pictures for quantum search algorithms in decomposed form, namely in terms of a phase rotation of the marked state and a phase rotation about the average. We apply this formalism to various quantum search algorithms, and give explicit interpretations of the standard Grover algorithm, arbitrary phase rotations, phase matching and fixed-point search algorithm. The pictures straightforwardly show how state vectors evolve during the search process. These results are helpful in understanding how the quantum search algorithms work.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Grover L.K.: Quantum mechanics helps in searching for a Needle in a Haystack. Phys. Rev. Lett. 79, 325 (1997)

    Article  ADS  Google Scholar 

  2. Grover L.K.: Quantum computers can search rapidly by using almost any transformation. Phys. Rev. Lett. 80, 4329 (1998)

    Article  ADS  Google Scholar 

  3. Zalka C.: Grovers quantum searching algorithm is optimal. Phys. Rev. A 60, 2746 (1999)

    Article  ADS  Google Scholar 

  4. Long G.L., Zhang W.L., Li Y.S., Niu L.: Arbitrary phase rotation of the marked state cannot be used for Grover’s quantum search algorithm. Commun. Theor. Phys. 32, 335–338 (1999)

    Google Scholar 

  5. Long G.L., Li Y.S., Zhang W.L., Niu L.: Phase matching in quantum searching. Phys. Lett. A. 262, 27 (1999)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  6. Long G.L. et al.: Phase matching condition for quantum search with a generalized initial state. Phys. Lett. A. 294, 143 (2002)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  7. Long G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A. 64, 022307 (2001)

    Article  ADS  Google Scholar 

  8. Li S.S., Long G.L., Feng Feng-Shan Baii S.L., Feng Song-Lin, Zheng Hou-Zhi.: Quantum computing. PNAS 98, 11847 (2001)

    Article  ADS  Google Scholar 

  9. Long G.L., Liu Y.: Search an unsorted database with quantum mechanics. Front. Comput. Sci. China 1, 247–271 (2007)

    Article  Google Scholar 

  10. Bhattacharya N., van Linden van den Heuvell H.B., Spreeuw R.J.C.: Implementation of quantum Search algorithm using Classical Fourier Optics. Phys. Rev. Lett. 88, 137901 (2002)

    Article  ADS  Google Scholar 

  11. Long G.L. et al.: Experimental NMR realization of a generalized quantum search algorithm. Phys. Lett. A 286, 121–126 (2001)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  12. Puentes G., La Mela C., Ledesma S., Iemmi C., Paz Pablo J., Saraceno M.: Optical simulation of quantum algorithms using programmable liquid-crystal displays. Phys. Rev. A 69, 042319 (2004)

    Article  ADS  Google Scholar 

  13. Long G.L., Li Y.S., Zhang W.L., Tu C.C.: Dominant gate imperfection in Grovers quantum search algorithm. Phys. Rev. A 61, 042305 (2000)

    Article  ADS  Google Scholar 

  14. Feng M.: Grover search with pairs of trapped ions. Phys. Rev. A 63, 052308 (2001)

    Article  ADS  Google Scholar 

  15. Shapira D., Mozes S., Biham O.: Effect of unitary noise on Grovers quantum search algorithm. Phys. Rev. A 67, 042301 (2003)

    Article  ADS  Google Scholar 

  16. Fang Y., Kaszlikowski D., Chin C., Tay K., Kwek L.C., Oh C.H.: Entanglement in the Grover search algorithm. Phys. Lett. A 345, 265 (2005)

    Article  ADS  MATH  Google Scholar 

  17. Deng Z.J., Feng M., Gao K.L.: Simple scheme for the two-qubit Grover search in cavity QED. Phys. Rev. A 72, 034306 (2005)

    Article  ADS  Google Scholar 

  18. Choo Keng W.: Measuring peptide mass spectrum correlation using the quantum Grover algorithm. Phys. Rev. A 75, 031919 (2007)

    ADS  Google Scholar 

  19. Zheng X.-H., Dong P., Xue Z., Cao Z.: Implementation of the Grover search algorithm with Josephson charge qubits. Phys. C 453, 76 (2007)

    Article  ADS  Google Scholar 

  20. Hijmans Tom W., Huussen Tycho N., Spreeuw Robert J.C.: Time-and frequency-domain solutions in an optical analogue of Grover’s search algorithm. J. Opt. Soc. Am. B 24, 2 (2007)

    Google Scholar 

  21. Tulsi A.: Quantum computers can search rapidly by using almost any selective transformation. Phys. Rev. A 78, 022332 (2008)

    Article  ADS  Google Scholar 

  22. Linington I.E., Ivanov P.A., Vitanov N.V.: Quantum search in a nonclassical database of trapped ions. Phys. Rev. A 79, 012322 (2009)

    Article  MathSciNet  ADS  Google Scholar 

  23. Torosov Boyan T., Vitanov Nikolay V.: Phase shifts in nonresonant coherent excitation. Phys. Rev. A 79, 042108 (2009)

    Article  ADS  Google Scholar 

  24. Toyama F.M., van Dijk W., Nogami Y., Tabuchi M., Kimura Y.: Multiphase matching in the Grover algorithm. Phys. Rev. A 77, 042324 (2008)

    Article  ADS  Google Scholar 

  25. Grover L.K.: Fixed-Point quantum search. Phys. Rev. Lett. 95, 150501 (2005)

    Article  ADS  Google Scholar 

  26. Xiao L., Jones Jonathan A.: Error tolerance in an NMR implementation of Grovers fixed-point quantum search algorithm. Phys. Rev. A 72, 032326 (2005)

    Article  ADS  Google Scholar 

  27. Li D., Chen J.P., Li X., Huang H., Li X.: Performance of equal phase-shift search for one iteration. Eur. Phys. J.D 45, 335 (2007)

    Article  ADS  Google Scholar 

  28. Li D., Li X., Huang H., Li X.: Fixed-point quantum search for different phase shifts. Phys. Lett. A 362, 260 (2007)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  29. Long G.L., Liu Y.: Duality computing in Quantum computers. Comm. Theor. Phys. 50, 1303 (2008)

    Article  ADS  Google Scholar 

  30. Hao L., Liu D., Long G.: An N/4 fixed-point duality Quantum search algorithm. Sci. China-Phys. Mech. Astron. 53, 1765 (2010)

    Article  ADS  Google Scholar 

  31. Pèrez A., Romanelli A.: Nonadiabatic Quantum search algorithms. Phys. Rev. A 76, 052318 (2007)

    Article  MathSciNet  ADS  Google Scholar 

  32. Rezakhani A.T., Pimachev A.K., Lidar D.A.: Accuracy versus run time in an adiabatic quantum search. Phys. Rev. A 82, 052305 (2010)

    Article  ADS  Google Scholar 

  33. Wang H., Zhang S., Zhao Y.: Phase matching in fixed-point Quantum Search Algorithm. Int. J. Quan. Inform. 7, 1269 (2009)

    Article  MATH  Google Scholar 

  34. Wocjan P., Chiang C., Nagaj D., Abeyesinghe A.: Quantum algorithm for approximating partition functions. Phys. Rev. A 80, 022340 (2009)

    Article  ADS  Google Scholar 

  35. Iwai T., Hayashi N., Mizobe K.: The geometry of entanglement and Grovers algorithm. J. Phys. A: Math. Theor. 41, 105202 (2008)

    Article  MathSciNet  ADS  Google Scholar 

  36. Mizel Ari: Critically damped Quantum search. Phys. Rev. Lett. 102, 150501 (2009)

    Article  ADS  Google Scholar 

  37. Grover L.K.: Quantum computers can search arbitrarily large databases by a single query. Phys. Rev. Lett. 79, 4709 (1997)

    Article  ADS  Google Scholar 

  38. Yu S., Sun C.: Canonical quantum teleportation. Phys. Rev. A 61, 022310 (2000)

    Article  ADS  Google Scholar 

  39. Long G.L., Tu C.C., Li Y.S., Zhang W.L., Yan H.Y.: An SO(3) picture for quantum searching. J. Phys. A 34, 861 (2001)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  40. Braunstein Samuel L., Choi B., Ghosh S., Maitra S.: Exact quantum algorithm to distinguish Boolean functions of different weights. J. Phys. A: Math. Theor. 40, 8441 (2007)

    Article  ADS  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Key Laboratory for Atomic and Molecular Nanosciences and Department of Physics, Tsinghua University, Beijing, 100084, China

    Lian-Jie Zhao, Yan-Song Li, Liang Hao, Tao Zhou & Gui Lu Long

  2. Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, Beijing, 100084, China

    Gui Lu Long

Authors
  1. Lian-Jie Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yan-Song Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liang Hao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tao Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Gui Lu Long
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gui Lu Long.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhao, LJ., Li, YS., Hao, L. et al. Geometric pictures for quantum search algorithms. Quantum Inf Process 11, 325–340 (2012). https://doi.org/10.1007/s11128-011-0249-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11128-011-0249-7

Keywords

Search

Navigation