- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

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

O. Melchert1, Helmut G. Katzgraber1,2,3, and M. A. Novotny4,5

  • 1Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
  • 2Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
  • 3Applied Mathematics Research Centre, Coventry University, Coventry, CV1 5FB, England
  • 4Department of Physics and Astronomy, Mississippi State University, Mississippi State, Mississippi 39762-5167, USA
  • 5HPC2 Center for Computational Sciences, Mississippi State University, Mississippi State, Mississippi 39762-5167, USA

PDF

Phys. Rev. E 93, 042128 – Published 25 April, 2016

DOI: https://doi.org/10.1103/PhysRevE.93.042128

Abstract

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 Kn,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.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (56)

  1. S. R. Broadbent and J. M. Hammersley, Percolation processes. I. Crystals and Mazes, Proc. Cambridge Philos. Soc. 53, 629 (1957).
  2. J. M. Hammersley, Percolation processes: Lower bounds for the critical probability, Ann. Math. Statist. 28, 790 (1957).
  3. J. M. Hammersley, Percolation processes. II. The connective constant, Proc. Cambridge Philos. Soc. 53, 642 (1957).
  4. M. E. Fisher, Critical probabilities for cluster size and percolation problems, J. Math. Phys. 2, 620 (1961).
  5. A. Bunde, P. Maass, and M. D. Ingram, Diffusion limited percolation: A model for transport in ionic glasses, Berichte der Bunsengesellschaft für physikalische Chemie 95, 977 (1991).
  6. F. O. Pfeiffer and H. Rieger, Superconductor-to-normal phase transition in a vortex glass model: Numerical evidence for a new percolation universality class, J. Phys.: Condens. Matter 14, 2361 (2002).
  7. F. O. Pfeiffer and H. Rieger, Critical properties of loop percolation models with optimization constraints, Phys. Rev. E 67, 056113 (2003).
  8. D. Stauffer, Scaling theory of percolation clusters, Phys. Rep. 54, 1 (1979).
  9. D. Stauffer and A. Aharony, Introduction to Percolation Theory (Taylor and Francis, London, 1994).
  10. J. W. Essam and M. E. Fisher, Some basic definitions in graph theory, Rev. Mod. Phys. 42, 271 (1970).
  11. J. M. Yeomans, Statistical Mechanics of Phase Transitions (Oxford University Press, Oxford, 1992).
  12. A. M. Becker and R. M. Ziff, Percolation thresholds on two-dimensional Voronoi networks and Delaunay triangulations, Phys. Rev. E 80, 041101 (2009).
  13. A. A. Saberi, Recent advances in percolation theory and its applications, Phys. Rep. 578, 1 (2015).
  14. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, 026118 (2001).
  15. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Network Robustness and Fragility: Percolation on Random Graphs, Phys. Rev. Lett. 85, 5468 (2000).
  16. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, Cambridge, MA, 2001).
  17. M. E. J. Newman and R. M. Ziff, Efficient Monte Carlo Algorithm and High-Precision Results for Percolation, Phys. Rev. Lett. 85, 4104 (2000).
  18. M. E. J. Newman and R. M. Ziff, Fast Monte Carlo algorithm for site or bond percolation, Phys. Rev. E 64, 016706 (2001).
  19. S. Mertens and C. Moore, Continuum percolation thresholds in two dimensions, Phys. Rev. E 86, 061109 (2012).
  20. P. Bunyk, E. Hoskinson, M. W. Johnson, E. Tolkacheva, F. Altomare, A. J. Berkley, R. Harris, J. P. Hilton, T. Lanting, and J. Whittaker, Architectural Considerations in the Design of a Superconducting Quantum Annealing Processor, IEEE Trans. Appl. Supercond. 24, 1 (2014).
  21. See http://www.dwavesys.com.
  22. Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, and A. Roy, Discrete optimization using quantum annealing on sparse Ising models, Front. Phys. 2 (2014).
  23. C. Klymko, B. D. Sullivan, and T. S. Humble, Adiabatic quantum programming: Minor embedding with hard faults, Quant. Inf. Proc. 13, 709 (2014).
  24. R. Albert, H. Jeong, and A. Barabási, Error and attack tolerance of complex networks, Nature (Lodnon) 406, 378 (2000).
  25. Note that in Ref. [53] the percolation properties of a two-level-grid minor embedded into chimera were studied within the context of quantum annealing corrections.
  26. Within this context, native refers to a problem that uses all physical qubits on the chip as logical qubits. An embedded problem, for example, might require multiple physical qubits to encode one logical qubit or interaction between two qubits that are not nearest neighbors on the lattice.
  27. K. Binder and A. P. Young, Spin glasses: Experimental facts, theoretical concepts and open questions, Rev. Mod. Phys. 58, 801 (1986).
  28. D. L. Stein and C. M. Newman, Spin Glasses and Complexity, Primers in Complex Systems (Princeton University Press, Princeton, NJ, 2013).
  29. H. G. Katzgraber, F. Hamze, and R. S. Andrist, Glassy Chimeras Could Be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines, Phys. Rev. X 4, 021008 (2014).
  30. H. G. Katzgraber, F. Hamze, Z. Zhu, A. J. Ochoa, and H. Munoz-Bauza, Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly, Phys. Rev. X 5, 031026 (2015).
  31. Z. Zhu, A. J. Ochoa, and H. G. Katzgraber, Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension, Phys. Rev. Lett. 115, 077201 (2015).
  32. I. Hen, J. Job, T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar, Probing for quantum speedup in spin-glass problems with planted solutions, Phys. Rev. A 92, 042325 (2015).
  33. A. D. King, Performance of a quantum annealer on range-limited constraint satisfaction problems, arXiv:1502.02098.
  34. J. S. Hall, M. A. Novotny, T. Neuhaus, and K. Michielsen, A study of spanning trees on a D-Wave quantum computer, Phys. Proc. 68, 56 (2015).
  35. S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, Evidence for quantum annealing with more than one hundred qubits, Nat. Phys. 10, 218 (2014).
  36. K. Binder, Critical Properties from Monte Carlo Coarse Graining and Renormalization, Phys. Rev. Lett. 47, 693 (1981).
  37. Note that in Ref. [10] these bipartite graphs are referred to as “bichromatic.”
  38. Needless to mention, the expectation that the current chip topology will scale to hundreds of thousands of qubits requires an unhealthily large amount of wishful thinking. This estimate does not take into account, for example, fabrication limitations, or the effects of qubit noise that are amplified the more qubits are added to the system [54, 55, 56].
  39. K. Binder and D. W. Heermann, Monte Carlo Simulation in Statistical Physics: An Introduction, 4th ed., Springer Series in Solid-State Science (Springer, New York, 2002).
  40. O. Melchert, autoScale.py—A program for automatic finite-size scaling analyses: A user's guide, arXiv:0910.5403v1; the source code of autoScale.py and the raw data for an illustrative example can be downloaded toghether with the source files of the preprint at http://arxiv.org/abs/0910.5403 by choosing the download-option “Other formats.”
  41. A. Sorge, pyfssa: v0.2.0 (2015); pyfssa is a scientific Python package for algorithmic finite-size scaling analysis at phase transitions.
  42. J. Houdayer and A. K. Hartmann, Low temperature behavior of two-dimensional Gaussian Ising spin glasses, Phys. Rev. B 70, 014418 (2004).
  43. K. Binder, Finite size scaling analysis of Ising model block distribution functions, Z. Phys. B 43, 119 (1981).
  44. The numerical value of S measures the mean-square distance of the data points to the master scaling curve described by the scaling function, in units of the standard error [42].
  45. J. C. Wierman, Percolation threshold is not a decreasing function of the average coordination number, Phys. Rev. E 66, 046125 (2002).
  46. R. Ziff (private communication) drew our attention to his independent estimates of pc,2≈0.42776 (bond percolation) and pc,2≈0.51298 (site percolation) on the K2,2 chimera lattice, consistent with the values quoted in Table 2.
  47. H. Guclu, G. Korniss, M. A. Novotny, Z. Toroczkai, and Z. Rácz, Synchronization landscapes in small-world-connected computer networks, Phys. Rev. E 73, 066115 (2006).
  48. If N is odd, one qubit does not have a small-world bond.
  49. A. Nachmias, Mean-field conditions for percolation on finite graphs, Geom. Funct. Anal. 19, 1171 (2009).
  50. C. Moore and M. E. J. Newman, Exact solution of site and bond percolation on small-world networks, Phys. Rev. E 62, 7059 (2000).
  51. A. K. Hartmann and H. Rieger, Optimization Algorithms in Physics (Wiley-VCH, Berlin, 2001).
  52. Octomore Collaboration, M. Weigel, H. G. Katzgraber, J. Machta, F. Hamze, and R. S. Andrist, Erratum: Glassy Chimeras Could Be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines [Phys. Rev. X 4, 021008 (2014)], Phys. Rev. X 5, 019901(E) (2015).
  53. W. Vinci, T. Albash, G. Paz-Silva, I. Hen, and D. A. Lidar, Quantum annealing correction with minor embedding, Phys. Rev. A 92, 042310 (2015).
  54. Z. Zhu, A. J. Ochoa, F. Hamze, S. Schnabel, and H. G. Katzgraber, Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities, Phys. Rev. A 93, 012317 (2016).
  55. A. Perdomo-Ortiz, B. O'Gorman, J. Fluegemann, R. Biswas, and V. N. Smelyanskiy, Determination and correction of persistent biases in quantum annealers, arXiv:1503.05679 [quant-ph].
  56. A. Perdomo-Ortiz, J. Fluegemann, R. Biswas, and V. N. Smelyanskiy, A performance estimator for quantum annealers: Gauge selection and parameter setting, arXiv:1503.01083 [quant-ph].

Outline

Information

Phys. Rev. E 93, 042128– Published 25 April, 2016
  • Received 22 November 2015
Article part of CHORUS

©2016 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation