• DocumentCode
    2074011
  • Title

    Quantum walk algorithm for element distinctness

  • Author

    Ambainis, Andris

  • Author_Institution
    Sch. of Math., Inst. for Adv. Study, Princeton, NJ, USA
  • fYear
    2004
  • fDate
    17-19 Oct. 2004
  • Firstpage
    22
  • Lastpage
    31
  • Abstract
    We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N23/) query quantum algorithm. This improves the previous O(N34/) quantum algorithm of Buhrman et al. and matches the lower bound by Shi. We also give an O(Nk(k+1)/) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.
  • Keywords
    quantum computing; element distinctness; quantum walk algorithm; query quantum algorithm; Algorithm design and analysis; Costs; Laboratories; Mathematics; Quantum computing; Sorting;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
  • ISSN
    0272-5428
  • Print_ISBN
    0-7695-2228-9
  • Type

    conf

  • DOI
    10.1109/FOCS.2004.54
  • Filename
    1366221
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2074011