Power law scaling for the adiabatic algorithm for search engine ranking

ORAL

Abstract

An important method for search engine result ranking works by finding the principal eigenvector of the ``Google matrix." Recently, a quantum algorithm for this problem and evidence of an exponential speedup for some scale-free networks were presented. Here, we show that the run-time depends on features of the graphs other than the degree distribution, and can be altered sufficiently to rule out a general exponential speedup. For a sample of graphs with degree distributions that more closely resemble the Web than in the previous work, the proposed algorithm does not appear to run exponentially faster than the classical one.

*This work was supported in part by ARO, DOD (W911NF-09-1-0439) and NSF (CCR-0635355, DMR 0906951). A.F. acknowledges support from the NSF REU program (PHY-PIF-1104660)

–

Authors

  • Adam Frees

    • Department of Physics, Brown University, Providence, RI 02912

  • John King Gamble

    • Department of Physics, University of Wisconsin-Madison, Madison, WI 53706

  • Kenneth Rudinger

    • Department of Physics, University of Wisconsin-Madison, Madison, WI 53706

  • Eric Bach

    • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706

  • Mark Friesen

    • Department of Physics, University of Wisconsin-Madison, Madison, WI 53706

  • Robert Joynt

    • Department of Physics, University of Wisconsin-Madison, Madison, WI 53706

  • S. N. Coppersmith

    • Department of Physics, University of Wisconsin-Madison, Madison, WI 53706