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

Abstract

We estimate the critical thresholds of bond and site percolation on nonplanar, effectively two-dimensional graphs with chimera like 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.

9 pages, 5 figures

References in corpus (10)

• Recent advances in percolation theory and its applications
• Continuum Percolation Thresholds in Two Dimensions
• Probing for quantum speedup in spin glass problems with planted solutions
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Quantum Annealing Correction with Minor Embedding
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Percolation thresholds on 2D Voronoi networks and Delaunay triangulations
• autoScale.py - A program for automatic finite-size scaling analyses: A user's guide
• Erratum: Glassy Chimeras Could Be Blind to Quantum Speedup. . . [Phys. Rev. X 4, 021008 (2014)]

Cited by in corpus (4)

• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Measurement-induced phase transitions in sparse nonlocal scramblers
• borealis - A generalized global update algorithm for Boolean optimization problems
• Heat percolation in many-body flatband localizing systems