Power-law scaling for the adiabatic algorithm for search-engine ranking

An important method for search engine result ranking works by finding the principal eigenvector of the “Google matrix.” Recently, a quantum algorithm for generating this eigenvector as a quantum state was presented, with evidence of an exponential speedup of this process for some scale-free networks. 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. According to our simulations, for a sample of graphs with degree distributions that are scale-free, with parameters thought to closely resemble the Web, the proposed algorithm for eigenvector preparation does not appear to run exponentially faster than the classical case.

Figure 1

Illustrations of the three network generation models used. (a) GZL [6] preferential attachment, (b) GZL copying, and (c) $\alpha$-preferential attachment [12, 14]. In all three models, a network is constructed by adding vertices and edges sequentially. (a) At each time step a new vertex $i$ is added with $m$ outgoing edges. The probability that one of these edges connects to a node $j$ is proportional to the total degree of $j$. (b) At each time step there are two possible actions. With probability $(1-p)$, the new vertex points to all of the same vertices as the “star vertex,” which is a pre-existing vertex chosen uniformly at random at each time step. With probability $p$, $m$ outgoing edges are added to the new vertex, each pointing to vertices chosen uniformly at random. (c) There are three possible actions at each time step. With probability $p_1$, a new vertex is added with a single outgoing edge, pointing to a node $j$ with probability proportional to the in degree of $j$ plus a parameter $\alpha$. With probability $p_2$, a new vertex is added with a single incoming edge, pointing from a node $j$ with probability proportional to the out degree of $j$ plus $\alpha$. With probability $(1-p_1-p_2)$, no vertex, only an edge, is added. Its ending and starting points are determined as in cases 1 and 2, respectively. In all panels, the newly added edges are indicated by dashed lines.

Figure 2

Comparison of the scaling of the inverse energy gap ${\delta }^{-1}$ for the GZL [6] preferential attachment model (triangles, horizontal hatching), GZL copying model (diamonds, upward-sloping hatching), and $\alpha$-preferential attachment model [12] (circles, downward-sloping hatching), shown on (a) semilog and (b) log-log scales, demonstrating that ${\delta }^{-1}$ is not proportional to $\log \left(n\right)$ for these models. Results are averaged over 1000 random instances for $n<8192$, and over 500 random instances at $n=8192$. The fitting lines showed in (a) are $72.2\ln \left(n\right)-363$ for the copying model and $10.1\ln \left(n\right)-48.8$ for the $\alpha$-preferential attachment model. In (b), the fits shown are $8.0n^{0.4}$ for the copying model and $1.7n^{0.4}$ for the $\alpha$-preferential attachment model. If we fit the data instead to a power of a logarithm (not shown), we obtain $0.56{\ln }^{2.9}\left(n\right)$ for the copying model and $0.18{\ln }^{2.5}\left(n\right)$ for the $\alpha$-preferential attachment model. (c) Histogram of the inverse energy gaps for the data shown in (a) and (b) at $n=8192$. (d) Histogram showing the distribution of number of vertices with in degree $d_{\mathrm{in}}=8$ for $n=8192$. (e) and (f) Degree distributions of the three models, demonstrating scale-free behavior and indicating that ${\gamma }_{\mathrm{in}}={\gamma }_{\mathrm{out}}=3$. Adaptive binning was used, as described in Appendix . In all cases, both the mean in and out degree of each graph are two edges per node. These results demonstrate that ${\delta }^{-1}$ differs significantly for the different graph construction methods, while the degree distributions are very similar.

Figure 3

Inverse energy gap scaling for GZL [6] copying model (diamonds), and $\alpha$-preferential attachment model [12] (circles) of WWW-like networks, shown on (a) semilog and (b) log-log scales. Results are averaged over 1000 random instances for $n<8192$, and over 500 random instances at $n=8192$. In (a) the line fit shown is $730\ln \left(n\right)-5300$, while in (b) the line fit is $0.2n^{0.97}$. If we fit the data to a power of a logarithm (not shown), for the copying model we obtain $3\times {10}^{-5}{\ln }^{8.0}\left(n\right)$. Because of the large power of the logarithm required for the polylogarithmic fit, the power-law dependence on $n$ appears more natural and plausible. (c) and (d) Degree distributions of the two models, histogrammed using adaptive binning (see Appendix ), indicating that ${\gamma }_{\mathrm{in}}=2.1$ and ${\gamma }_{\mathrm{out}}=2.72$, corresponding to the estimates for the degree distribution of the World Wide Web [13]. In all cases, the mean in and out degree of each network were each two edges per node.

Figure 4

Degree distributions for the GZL preferential attachment model with $m_X=1$ and $m_Y=15$, taken at graph size $n=8196$ and averaged over approximately 1000 random graph realizations. Both the in-degree (blue circles) and out-degree (red squares) distributions are shown. For reference, the in-degree distribution for $m_X=1$ and $m_Y=1$ [duplicated from Fig. 2 is shown (black diamonds)]. The dashed line is the expected power law scaling of $d^{-3}$, which is applicable for large $d$. As predicted by Eq. (A2), shown as fitting curves, the $m_X=1$ and $m_Y=15$ distributions exhibit non-scale-free behavior over a wide region of $d$.