Site- and bond-percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies

We estimate the critical thresholds of bond and site percolation on nonplanar, effectively two-dimensional graphs with chimeralike topology. The building blocks of these graphs are complete and symmetric bipartite subgraphs of size $2n$, referred to as $K_{n,n}$ graphs. For the numerical simulations we use an efficient union-find-based algorithm and employ a finite-size scaling analysis to obtain the critical properties for both bond and site percolation. We report the respective percolation thresholds for different sizes of the bipartite subgraph and verify that the associated universality class is that of standard two-dimensional percolation. For the canonical chimera graph used in the D-Wave Systems Inc. quantum annealer ($n=4$), we discuss device failure in terms of network vulnerability, i.e., we determine the critical fraction of qubits and couplers that can be absent due to random failures prior to losing large-scale connectivity throughout the device.

Figure 1

Topological representation of a chimera graph with $N=128$ sites, based on a $4\times 4$ grid of $K_{4,4}$ subgraphs, which corresponds to the D-Wave One Rainier quantum annealer introduced in 2011.

Figure 2

Instances of bond percolation configurations on a chimera graph with $N=128$ sites. From left to right: $p=0.2, p=0.38\approx p_{\mathrm{c}}$, and, $p=0.42$. The vertices and edges belonging to the largest connected component are colored black and the remaining vertices and subsisting edges are colored gray.

Figure 3

Finite-size scaling analysis of the relative size $s_{\max }$ of the largest cluster of sites for the bond-percolation problem on chimera graphs. The main panels always show the scaled data according to Eq. (1), whereas the insets display the unscaled data in the vicinity of the critical point. (a) Binder ratio $b\left(p\right)$, (b) disorder-averaged order parameter $P_{\max }\left(p\right)$, and (c) fluctuation $\chi \left(p\right)=N\times \mathrm{var}\left(s_{\max }\right)$ of the order parameter. Note that the insets feature two additional data curves, illustrating the statistical properties of small chimera graphs of current quantum annealing machines with $N=512$ and 1152 qubits (sites).

Figure 4

Bond and site percolation thresholds for chimeralike graphs built from $K_{n,n}$ subgraphs. The percolation thresholds decrease with increasing average vertex degree and thus of $n$, the cell size. The dashed lines represent fits to functions of the form $f\left(n\right)=a{(n-\mathrm{\Delta }n)}^{-b}$ (see text for details).

Figure 5

Finite-size scaling analysis of the relative size $s_{\max }$ of the largest cluster of sites for the site-percolation problem on the small-world enhanced chimera graphs (see Sec. 4d). (a) Scaling of the effective system-size-dependent estimate of $p_{\mathrm{c}}\left(N\right)$. The inset shows a scaling of $\beta \left(N\right)$, as discussed in the text. (b) Fit of fifth-order polynomials to the finite-size fluctuations to estimate the system-size-dependent peak positions $p_{\max }\left(N\right)$. The inset shows the extrapolation to the asymptotic critical point $p_{\max }^{\infty }$, as discussed in the text.