• DocumentCode
    579986
  • Title

    Learning-Graph-Based Quantum Algorithm for k-Distinctness

  • Author

    Belovs, Aleksandrs

  • Author_Institution
    Fac. of Comput., Univ. of Latvia, Riga, Latvia
  • fYear
    2012
  • fDate
    20-23 Oct. 2012
  • Firstpage
    207
  • Lastpage
    216
  • Abstract
    We present a quantum algorithm solving the k-distinctness problem in a less number of queries than the previous algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee, the algorithm doesn´t require any prior information on the input, and the complexity analysis is much simpler.
  • Keywords
    computational complexity; graph theory; learning (artificial intelligence); quantum computing; complexity analysis; k-distinctness problem; learning-graph-based quantum algorithm; queries; Algorithm design and analysis; Complexity theory; Input variables; Learning systems; Loading; Quantum computing; Silicon; quantum computing; query complexity;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
  • Conference_Location
    New Brunswick, NJ
  • ISSN
    0272-5428
  • Print_ISBN
    978-1-4673-4383-1
  • Type

    conf

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