Site and bond percolation thresholds in -based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
arXiv:1511.07078 · doi:10.1103/PhysRevE.93.042128
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 , referred to as 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 (), 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.
arXiv comment9 pages, 5 figures
References in corpus (23)
- Error and attack tolerance of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Network robustness and fragility: Percolation on random graphs
- Quantum annealing with more than one hundred qubits
- A fast Monte Carlo algorithm for site or bond percolation
- Efficient Monte Carlo algorithm and high-precision results for percolation
- Recent advances in percolation theory and its applications
- Architectural considerations in the design of a superconducting quantum annealing processor
- Continuum Percolation Thresholds in Two Dimensions
- Exact solution of site and bond percolation on small-world networks
- Probing for quantum speedup in spin glass problems with planted solutions
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
- 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
- Synchronization Landscapes in Small-World-Connected Computer Networks
- Critical properties of loop percolation models with optimization constraints
- Superconductor-to-Normal Phase Transition in a Vortex Glass Model: Numerical Evidence for a New Percolation Universality Class
- 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