Homology-changing percolation transitions on finite graphs

Abstract

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}$. Namely, 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. 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_{\mathrm{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_{\mathrm{c}}(\mathcal{H})$ in several cases where this ratio remains bounded, which is necessarily the case if $\mathcal{H}$ is non-amenable.

References in corpus (12)

• Quantum cryptography: Public key distribution and coin tossing
• Secure Quantum Key Distribution
• Practical challenges in quantum key distribution
• Error Threshold for Color Codes and Random 3-Body Ising Models
• Periodic boundary conditions on the pseudosphere
• Three-dimensional color code thresholds via statistical-mechanical mapping
• Fault-Tolerant Postselected Quantum Computation: Threshold Analysis
• Homological Percolation and the Euler Characteristic
• New critical exponent inequalities for percolation and the random cluster model
• Percolation Thresholds in Hyperbolic Lattices
• Generalized surface codes and packing of logical qubits
• Duality and free energy analyticity bounds for few-body Ising models with extensive homology rank

Cited by in corpus (1)

• Fundamental thresholds for computational and erasure errors via the coherent information