42
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: not found
      • Article: not found

      A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

      , , , , ,
      Science
      American Association for the Advancement of Science (AAAS)

      Read this article at

      ScienceOpenPublisherPubMed
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Related collections

          Most cited references2

          • Record: found
          • Abstract: not found
          • Article: not found

          Quantum annealing in the transverse Ising model

            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            Critical behavior in the satisfiability of random boolean expressions.

            Determining the satisfiability of randomly generated Boolean expressions with k variables per clause is a popular test for the performance of search algorithms in artificial intelligence and computer science. It is known that for k = 2, formulas are almost always satisfiable when the ratio of clauses to variables is less than 1; for ratios larger than 1, the formulas are almost never satisfiable. Similar sharp threshold behavior is observed for higher values of k. Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold. A relationship can be drawn between thresholds and computational complexity.
              Bookmark

              Author and article information

              Journal
              Science
              Science
              American Association for the Advancement of Science (AAAS)
              0036-8075
              1095-9203
              April 20 2001
              April 20 2001
              : 292
              : 5516
              : 472-475
              Article
              10.1126/science.1057726
              11313487
              87ee8114-88e9-422a-b1cb-41a9fae05795
              © 2001
              History

              Comments

              Comment on this article