Cycle Basis Algorithms for Reducing Maximum Edge Participation

• URL: http://arxiv.org/abs/2511.10961v1
• Date: Fri, 14 Nov 2025 04:59:52 GMT
• Title: Cycle Basis Algorithms for Reducing Maximum Edge Participation
• Authors: Fan Wang, Sandy Irani,
• Abstract summary: We study the problem of constructing cycle bases of graphs with low maximum edge participation.<n>This quantity plays a critical role in quantum fault tolerance because it directly impacts the overhead of lattice surgery procedures.<n>We introduce a family of load-awares that adaptively select vertices and edges to minimize edge participation.
• Score: 5.635920304725715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of constructing cycle bases of graphs with low maximum edge participation, defined as the maximum number of basis cycles that share any single edge. This quantity, though less studied than total weight or length, plays a critical role in quantum fault tolerance because it directly impacts the overhead of lattice surgery procedures used to implement an almost universal quantum gate set. Building on a recursive algorithm of Freedman and Hastings, we introduce a family of load-aware heuristics that adaptively select vertices and edges to minimize edge participation throughout the cycle basis construction. Our approach improves empirical performance on random regular graphs and on graphs derived from small quantum codes. We further analyze a simplified balls-into-bins process to establish lower bounds on edge participation. While the model differs from the cycle basis algorithm on real graphs, it captures what can be proven for our heuristics without using complex graph theoretic properties related to the distribution of cycles in the graph. Our analysis suggests that the maximum load of our heuristics grows on the order of (log n)^2. Our results indicate that careful cycle basis construction can yield significant practical benefits in the design of fault-tolerant quantum systems. This question also carries theoretical interest, as it is essentially identical to the basis number of a graph, defined as the minimum possible maximum edge participation over all cycle bases.

Related papers

• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle problem [0.0]
  Hamiltonian cycle problem (HCP) consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once. In this paper we compare some algorithms to solve aHCP, using different models of computations and especially the probabilistic and quantum ones.
  arXiv  Detail & Related papers  (2023-11-18T02:36:10Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
  We develop a graph clustering framework textitPCon. We show that many existing solutions can be reduced to our framework. Based on our framework, we propose two novel algorithms textitPCon_core and emphPCon_de with linear time and space complexity.
  arXiv  Detail & Related papers  (2022-11-22T12:45:27Z)
• Variational quantum eigensolver for causal loop Feynman diagrams and directed acyclic graphs [0.0]
  We present a variational quantum eigensolver (VQE) algorithm for the efficient bootstrapping of the causal representation of multiloop Feynman diagrams. A loop Hamiltonian based on the adjacency matrix describing a multiloop topology, and whose different energy levels correspond to the number of cycles, is minimized by VQE to identify the causal or acyclic configurations.
  arXiv  Detail & Related papers  (2022-10-24T13:42:53Z)
• On constant-time quantum annealing and guaranteed approximations for graph optimization problems [0.0]
  Quantum Annealing (QA) is a computational framework where a quantum system's continuous evolution is used to find the global minimum of an objective function. In this paper we use a technique borrowed from theoretical physics, the Lieb-Robinson (LR) bound, and develop new tools proving that short, constant time quantum annealing guarantees constant factor approximations ratios. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework.
  arXiv  Detail & Related papers  (2022-02-03T15:23:18Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm [0.0]
  A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing. The good performance and time efficiency of CTGA are verified on the regular random and Erd"os-R'enyi random graph ensembles.
  arXiv  Detail & Related papers  (2021-10-12T12:28:05Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.