Homology-changing percolation transitions on finite graphs. (English) Zbl 1507.60137
Summary: We consider homological edge percolation on a sequence \((\mathcal{G}_t)_t\) of finite graphs covered by an infinite (quasi)transitive graph \(\mathcal{H}\) and weakly convergent to \(\mathcal{H} \). In particular, we use the covering maps to classify 1-cycles on graphs \(\mathcal{G}_t\) as homologically trivial or non-trivial and define several thresholds associated with the rank of thus defined first homology group on the open subgraphs generated by the Bernoulli (edge) percolation process. We identify the growth of the homological distance \(d_t \), the smallest size of a non-trivial cycle on \(\mathcal{G}_t\), as the main factor determining the location of homology-changing thresholds. In particular, we show that the giant cycle erasure threshold \(p_E^0\) (related to the conventional erasure threshold for the corresponding sequence of generalized toric codes) coincides with the edge percolation threshold \(p_{\operatorname{c}}(\mathcal{H})\) if the ratio \(d_t \)/ln \(n_t\) diverges, where \(n_t\) is the number of edges of \(\mathcal{G}_t\), and we give evidence that \(p_E^0 < p_{\operatorname{c}}(\mathcal{H})\) in several cases where this ratio remains bounded, which is necessarily the case if \(\mathcal{H}\) is non-amenable.
©2022 American Institute of Physics
©2022 American Institute of Physics
MSC:
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 82B43 | Percolation |
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
| 94B60 | Other types of codes |
| 05C80 | Random graphs (graph-theoretic aspects) |
Software:
GAPReferences:
| [1] | Shor, P. W., Fault-tolerant quantum computation, 56-65 (1996), IEEE Computer Society Press: IEEE Computer Society Press, Los Alamitos |
| [2] | Steane, A. M., Active stabilization, quantum computation, and quantum state synthesis, Phys. Rev. Lett., 78, 2252-2255 (1997) · doi:10.1103/physrevlett.78.2252 |
| [3] | Gottesman, D., Theory of fault-tolerant quantum computation, Phys. Rev. A, 57, 127-137 (1998) · doi:10.1103/physreva.57.127 |
| [4] | Dennis, E.; Kitaev, A.; Landahl, A.; Preskill, J., Topological quantum memory, J. Math. Phys., 43, 4452 (2002) · Zbl 1060.94045 · doi:10.1063/1.1499754 |
| [5] | Knill, E., Scalable quantum computing in the presence of large detected-error rates, Phys. Rev. A, 71, 042322 (2005), 10.1103/physreva.71.042322; Knill, E., Scalable quantum computing in the presence of large detected-error rates, Phys. Rev. A, 71, 042322 (2005), 10.1103/physreva.71.042322; Knill, E., Scalable quantum computing in the presence of large detected-error rates, Phys. Rev. A, 71, 042322 (2005), 10.5555/2011665.2011666; Knill, E., Scalable quantum computing in the presence of large detected-error rates, Phys. Rev. A, 71, 042322 (2005), 10.1007/s00453-007-9069-7; · Zbl 0949.28011 |
| [6] | Katzgraber, H. G.; Bombin, H.; Martin-Delgado, M. A., Error threshold for color codes and random three-body Ising models, Phys. Rev. Lett., 103, 090501 (2009) · doi:10.1103/PhysRevLett.103.090501 |
| [7] | Bennett, C. H.; DiVincenzo, D. P.; Smolin, J. A., Capacities of quantum erasure channels, Phys. Rev. Lett., 78, 3217-3220 (1997) · Zbl 0944.81008 · doi:10.1103/physrevlett.78.3217 |
| [8] | Kubica, A.; Beverland, M. E.; Brandao, F.; Preskill, J.; Svore, K. M., Three-dimensional color code thresholds via statistical-mechanical mapping, Phys. Rev. Lett., 120, 180501 (2018) · doi:10.1103/PhysRevLett.120.180501 |
| [9] | Jiang, Y.; Dumer, I.; Kovalev, A. A.; Pryadko, L. P., Duality and free energy analyticity bounds for few-body Ising models with extensive homology rank, J. Math. Phys., 60, 083302 (2019) · Zbl 1426.82008 · doi:10.1063/1.5039735 |
| [10] | Delfosse, N.; Zémor, G., Quantum erasure-correcting codes and percolation on regular tilings of the hyperbolic plane, 1-5 (2010), IEEE |
| [11] | Delfosse, N.; Zémor, G., Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel, Quantum Inf. Comput., 13, 793-826 (2013) · doi:10.26421/qic13.9-10-4 |
| [12] | Delfosse, N.; Zémor, G., A homological upper bound on critical probabilities for hyperbolic percolation, Ann. Inst. Henri Poincare, 3, 139-161 (2016) · Zbl 1342.82075 · doi:10.4171/aihpd/27 |
| [13] | Calderbank, A. R.; Shor, P. W., Good quantum error-correcting codes exist, Phys. Rev. A, 54, 1098-1105 (1996) · Zbl 07918813 · doi:10.1103/physreva.54.1098 |
| [14] | Steane, A. M., Simple quantum error-correcting codes, Phys. Rev. A, 54, 4741-4751 (1996) · Zbl 07918814 · doi:10.1103/physreva.54.4741 |
| [15] | Kitaev, A. Y., Fault-tolerant quantum computation by anyons, Ann. Phys., 303, 2 (2003) · Zbl 1012.81006 · doi:10.1016/s0003-4916(02)00018-0 |
| [16] | Bravyi, S. B.; Kitaev, A. Y., Quantum codes on a lattice with boundary (1998) |
| [17] | Freedman, M. H.; Meyer, D. A., Projective plane and planar quantum codes, Found. Comput. Math., 1, 325-332 (2001) · Zbl 0995.94037 · doi:10.1007/s102080010013 |
| [18] | Delfosse, N.; Iyer, P.; Poulin, D., Generalized surface codes and packing of logical qubits (2016) |
| [19] | Zémor, G.; Chee, Y. M.; Li, C.; Ling, S.; Wang, H.; Xing, C., On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction, Coding and Cryptology: Second International Workshop, IWCC 2009, 259-273 (2009), Springer: Springer, Berlin, Heidelberg · Zbl 1248.94128 |
| [20] | Bobrowski, O.; Skraba, P., Homological percolation and the Euler characteristic, Phys. Rev. E, 101, 032304 (2020) · doi:10.1103/PhysRevE.101.032304 |
| [21] | Bobrowski, O.; Skraba, P., Homological percolation: The formation of giant k-cycles, International Mathematics Research Notices (2020) · Zbl 07510518 · doi:10.1093/imrn/rnaa305 |
| [22] | Stace, T. M.; Barrett, S. D.; Doherty, A. C., Thresholds for topological codes in the presence of loss, Phys. Rev. Lett., 102, 200501 (2009) · doi:10.1103/physrevlett.102.200501 |
| [23] | Fujii, K.; Tokunaga, Y., Error and loss tolerances of surface codes with general lattice structures, Phys. Rev. A, 86, 020303 (2012) · doi:10.1103/physreva.86.020303 |
| [24] | Grimmett, G. R., Percolation, Grundlehren der Mathematischen Wissenschaften (1999), Springer-Verlag: Springer-Verlag, Berlin, Heidelberg · Zbl 0926.60004 |
| [25] | Menshikov, M. V., Coincidence of critical points in percolation problems, Dokl. Akad. Nauk SSSR, 33, 856-859 (1986) · Zbl 0615.60096 |
| [26] | Men’shikov, M. V.; Sidorenko, A. F., The coincidence of critical points in Poisson percolation models, Theory Probab. Appl., 32, 547-550 (1988) · Zbl 0661.60122 · doi:10.1137/1132083 |
| [27] | Aizenman, M.; Barsky, D. J., Sharpness of the phase transition in percolation models, Commun. Math. Phys., 108, 489-526 (1987) · Zbl 0618.60098 · doi:10.1007/bf01212322 |
| [28] | Antunović, T.; Veselić, I., Sharpness of the phase transition and exponential decay of the subcritical cluster size for percolation on quasi-transitive graphs, J. Stat. Phys., 130, 983-1009 (2008) · Zbl 1214.82028 · doi:10.1007/s10955-007-9459-x |
| [29] | Duminil-Copin, H.; Tassion, V., A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model, Commun. Math. Phys., 343, 725-745 (2016) · Zbl 1342.82026 · doi:10.1007/s00220-015-2480-z |
| [30] | Benjamini, I.; Schramm, O., Percolation beyond Z^d, many questions and a few answers, Electron. Commun. Probab., 1, 71-82 (1996) · Zbl 0890.60091 · doi:10.1214/ecp.v1-978 |
| [31] | Häggström, O.; Jonasson, J., Uniqueness and non-uniqueness in percolation theory, Probab. Surv., 3, 289-344 (2006) · Zbl 1189.60175 · doi:10.1214/154957806000000096 |
| [32] | van der Hofstad, R.; Molchanov, I.; Kendall, W., Percolation and random graphs, New Perspectives on Stochastic Geometry, 173-247 (2010), Oxford University Press · Zbl 1193.82017 |
| [33] | Aizenman, M.; Kesten, H.; Newman, C. M., Uniqueness of the infinite cluster and continuity of connectivity functions for short and long range percolation, Commun. Math. Phys., 111, 505-531 (1987) · Zbl 0642.60102 · doi:10.1007/bf01219071 |
| [34] | Burton, R. M.; Keane, M., Density and uniqueness in percolation, Commun. Math. Phys., 121, 501-505 (1989) · Zbl 0662.60113 · doi:10.1007/bf01217735 |
| [35] | Kesten, H., Some highlights of percolation, 345-365 (2002), Higher Education Press: Higher Education Press, Beijing, China · Zbl 1042.60066 |
| [36] | Hutchcroft, T., Percolation on hyperbolic graphs, Geom. Funct. Anal., 29, 766-810 (2019) · Zbl 1474.60230 · doi:10.1007/s00039-019-00498-0 |
| [37] | Lyons, R.; Schramm, O., Indistinguishability of percolation clusters, Ann. Probab., 27, 1809-1836 (1999) · Zbl 0960.60013 · doi:10.1214/aop/1022874816 |
| [38] | Tang, P., Heavy Bernoulli-percolation clusters are indistinguishable, Ann. Probab., 47, 4077-4115 (2019) · Zbl 1453.60161 · doi:10.1214/19-aop1354 |
| [39] | Benjamini, I.; Schramm, O., Percolation in the hyperbolic plane, J. Am. Math. Soc., 14, 487-507 (2001) · Zbl 1037.82018 · doi:10.1090/S0894-0347-00-00362-3 |
| [40] | Häggström, O.; Jonasson, J.; Lyons, R., Explicit isoperimetric constants and phase transitions in the random-cluster model, Ann. Probab., 30, 443-473 (2002) · Zbl 1025.60044 · doi:10.1214/aop/1020107775 |
| [41] | Teplyaev, A., Spectral analysis on infinite Sierpiński gaskets, J. Funct. Anal., 159, 537-567 (1998) · Zbl 0924.58104 · doi:10.1006/jfan.1998.3297 |
| [42] | Breuckmann, N. P., Homological quantum codes beyond the toric code (2017), RWTH Aachen University |
| [43] | Dumer, I.; Kovalev, A. A.; Pryadko, L. P., Thresholds for correcting errors, erasures, and faulty syndrome measurements in degenerate quantum codes, Phys. Rev. Lett., 115, 050502 (2015) · doi:10.1103/PhysRevLett.115.050502 |
| [44] | Kahn, J.; Kalai, G.; Linial, N., The influence of variables on Boolean functions, 68-80 (1988), IEEE |
| [45] | Hermon, J.; Hutchcroft, T., Supercritical percolation on nonamenable graphs: Isoperimetry, analyticity, and exponential decay of the cluster size distribution, Inventiones mathematicae, 224, 445-486 (2021) · Zbl 1516.60057 · doi:10.1007/s00222-020-01011-3 |
| [46] | Delfosse, N., Tradeoffs for reliable quantum information storage in surface codes and color codes, 917-921 (2013), IEEE |
| [47] | Breuckmann, N. P.; Terhal, B. M., Constructions and noise threshold of hyperbolic surface codes, IEEE Trans. Inf. Theory, 62, 3731-3744 (2016) · Zbl 1359.94882 · doi:10.1109/tit.2016.2555700 |
| [48] | Bennett, C. H.; Brassard, G., Quantum cryptography: Public key distribution and coin tossing, 175-179 (1984), IEEE: IEEE, Bangalore |
| [49] | Lo, H.-K.; Curty, M.; Tamaki, K., Secure quantum key distribution, Nat. Photonics, 8, 595-604 (2014) · doi:10.1038/nphoton.2014.149 |
| [50] | Diamanti, E.; Lo, H.-K.; Qi, B.; Yuan, Z., Practical challenges in quantum key distribution, npj Quantum Inf., 2, 16025 (2016) · doi:10.1038/npjqi.2016.25 |
| [51] | Širáň, J., Triangle group representations and constructions of regular maps, Proc. London Math. Soc., 82, 513-532 (2001) · Zbl 1015.05033 · doi:10.1112/plms/82.3.513 |
| [52] | Sausset, F.; Tarjus, G., Periodic boundary conditions on the pseudosphere, J. Phys. A: Math. Theor., 40, 12873 (2007) · Zbl 1149.82004 · doi:10.1088/1751-8113/40/43/004 |
| [53] | GAP, GAP Groups, Algorithms, and Programming—A System for Computational Discrete Algebra, The GAP Group, 2020. |
| [54] | Dumer, I.; Kovalev, A. A.; Pryadko, L. P., Numerical techniques for finding the distances of quantum codes, 1086-1090 (2014), IEEE: IEEE, Honolulu, HI |
| [55] | Dumer, I.; Kovalev, A. A.; Pryadko, L. P., Distance verification for classical and quantum LDPC codes, IEEE Trans. Inf. Theory, 63, 4675-4686 (2017) · Zbl 1368.94158 · doi:10.1109/tit.2017.2690381 |
| [56] | Newman, M. E.; Ziff, R. M., Fast Monte Carlo algorithm for site or bond percolation, Phys. Rev. E, 64, 016706 (2001) · doi:10.1103/PhysRevE.64.016706 |
| [57] | Benjamini, I.; Nachmias, A.; Peres, Y., Is the critical percolation probability local?, Probab. Theory Relat. Fields, 149, 261-269 (2011) · Zbl 1230.60099 · doi:10.1007/s00440-009-0251-5 |
| [58] | Margolina, A.; Herrmann, H. J.; Stauffer, D., Size of largest and second largest cluster in random percolation, Phys. Lett. A, 93, 73-75 (1982) · doi:10.1016/0375-9601(82)90219-5 |
| [59] | da Silva, C. R.; Lyra, M. L.; Viswanathan, G. M., Largest and second largest cluster statistics at the percolation threshold of hypercubic lattices, Phys. Rev. E, 66, 056107 (2002) · doi:10.1103/PhysRevE.66.056107 |
| [60] | Mertens, S.; Moore, C., Percolation thresholds in hyperbolic lattices, Phys. Rev. E, 96, 042116 (2017) · doi:10.1103/PhysRevE.96.042116 |
| [61] | Kozma, G.; Nachmias, A., A note about critical percolation on finite graphs, J. Theoretical Probability, 24, 1087-1096 (2011) · Zbl 1235.60138 · doi:10.1007/s10959-010-0283-x |
| [62] | Heydenreich, M.; van der Hofstad, R., Progress in High-Dimensional Percolation and Random Graphs, CRM Short Courses (2017), Springer International Publishing: Springer International Publishing, Switzerland · Zbl 1445.60003 |
| [63] | Kovalev, A. A.; Pryadko, L. P., Spin glass reflection of the decoding transition for quantum error-correcting codes, Quantum Inf. Comput., 15, 0825 (2015) · doi:10.26421/qic15.9-10-5 |
| [64] | Hutchcroft, T., New critical exponent inequalities for percolation and the random cluster model, Probability and Mathematical Physics, 1, 147-165 (2020) · Zbl 1487.60184 · doi:10.2140/pmp.2020.1.147 |
| [65] | Wilkinson, D.; Willemsen, J. F., Invasion percolation: A new form of percolation theory, J. Phys. A: Math. Gen., 16, 3365-3376 (1983) · doi:10.1088/0305-4470/16/14/028 |
| [66] | Sykes, M. F.; Essam, J. W., Exact critical percolation probabilities for site and bond problems in two dimensions, J. Math. Phys., 5, 1117-1127 (1964) · doi:10.1063/1.1704215 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
