Site- and bond-percolation thresholds in Kn,n -based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
Oliver Melchert, Helmut G. Katzgraber, M. A. Novotny
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.
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.
We theoretically investigate the quantum percolation problem on Lieb lattices in two and three dimensions. We study the statistics of the energy levels through random matrix theory and determine the level spacing distributions, which, with the aid of finite-size scaling theory, allows us to obtain accurate estimates for site- and bond-percolation thresholds and critical exponents. Our numerical investigation supports a localized-delocalized transition at finite threshold, which decreases as the average coordination number increases. The precise determination of the localization length exponent enables us to claim that quantum site- and bond-percolation problems on Lieb lattices belong to the same universality class, with ν decreasing with lattice dimensionality d, similarly to the classical percolation problem. In addition, we verify that, in three dimensions, quantum percolation on Lieb lattices belongs to the same universality class as the Anderson impurity model.
Abstract The site-percolation problem on simple cubic lattices has been studied by means of numerical simulation and analytical calculations based on exact counting of configurations on finite cells. Motivated by considerations of cluster connectivity, two distinct schemes (denoted as S ∩ B and S ∪ B ) have been considered. In S ∩ B ( S ∪ B ), two points are said to be connected if a sequence of occupied sites and ( or ) bonds joins them. Theoretical and numerical results, supplemented by analysis using finite-size scaling theory, were used to calculate the complete phase diagram of the system in the ( p s , p b ) space. Our study allowed us also to determine the critical exponents (and universality) characterizing the phase transition occurring in the system.
Quantum walks have been used as simple models of quantum transport phenomena, applicable to systems as diverse as spin chains [1] and bio-molecules [2]. Here we investigate the properties of quantum walks on percolation lattices, disordered structures appropriate for modelling biological and experimentally realistic systems. Both bond (edge) and site percolation have similar definitions: with independent randomly chosen probability p the bond or site is present in the lattice. In two and higher dimensions, percolation lattices exhibit a phase transition from a set of small disconnected regions to a more highly connected structure (“one giant cluster”). On 2D Cartesian lattices, the critical probability pc = 0.5 (bond) and pc = 0.5927... (site). Below pc, the quantum walk will not be able to spread. Approaching pc from above, the spreading slows down completely, as the number of long-distance connected paths reduces to zero. For p = 1, the lattice is fully connected, and the standard quantum walk spreading applies (linear in t). In between, we find the quantum walks show fractional scaling of the spreading, i.e., proportional to tα for (0.5 < α < 1). The numerically determined scaling exponents α are shown in fig.
We study site- and bond-percolation on a class of lattices referred to as Lieb lattices. In two dimensions the Lieb lattice (LL) is also known as the decorated square lattice, or as the CuO_{2} lattice; in three dimensions it can be generalized to a layered Lieb lattice or to a perovskite lattice. Emergent electronic phenomena, such as topological states and ferrimagnetism, have been predicted to occur in these systems, which may be realized in optical lattices as well as in solid state. Since the study of the interplay between quantum fluctuations and disorder in these systems requires the availability of accurate estimates of geometrical critical parameters, such as percolation thresholds and correlation length exponents, here we use Monte Carlo simulations to obtain these data for LLs when a site (or bond) is present with probability p. We have found that the thresholds satisfy a mean-field (Bethe lattice) trend, namely that the critical concentration, p_{c}, increases as the average coordination number decreases; our estimates for the correlation length exponent are in line with the expectation that there is no change in the universality class.
We investigate bond- and site-percolation models on several two-dimensional lattices numerically, by means of transfer-matrix calculations and Monte Carlo simulations. The lattices include the square, triangular, honeycomb kagome, and diced lattices with nearest-neighbor bonds, and the square lattice with nearest- and next-nearest-neighbor bonds. Results are presented for the bond-percolation thresholds of the kagome and diced lattices, and the site-percolation thresholds of the square, honeycomb, and diced lattices. We also include the bond- and site-percolation thresholds for the square lattice with nearest- and next-nearest-neighbor bonds. We find that corrections to scaling behave according to the second temperature dimension X_{t2}=4 predicted by the Coulomb gas theory and the theory of conformal invariance. In several cases there is evidence for an additional term with the same exponent, but modified by a logarithmic factor. Only for the site-percolation problem on the triangular lattice does such a logarithmic term appear to be small or absent. The amplitude of the power-law correction associated with X_{t2}=4 is found to be dependent on the orientation of the lattice with respect to the cylindrical geometry of the finite systems.
We simulate the bond and site percolation models on a simple-cubic lattice with linear sizes up to L=512, and estimate the percolation thresholds to be pc(bond)=0.24881182(10) and pc(site)=0.3116077(2). By performing extensive simulations at these estimated critical points, we then estimate the critical exponents $1/\ensuremath{\nu}=1.1410(15)$, $\ensuremath{\beta}/\ensuremath{\nu}=0.477\phantom{\rule{0.16em}{0ex}}05(15)$, the leading correction exponent ${y}_{i}=\ensuremath{-}1.2(2)$, and the shortest-path exponent dmin=1.3756(3). Various universal amplitudes are also obtained, including wrapping probabilities, ratios associated with the cluster-size distribution, and the excess cluster number. We observe that the leading finite-size corrections in certain wrapping probabilities are governed by an exponent $\ensuremath{\approx}$$\ensuremath{-}2$, rather than ${y}_{i}\ensuremath{\approx}\ensuremath{-}1.2$.