論文の概要: Cycle Basis Algorithms for Reducing Maximum Edge Participation
- arxiv url: http://arxiv.org/abs/2511.10961v1
- Date: Fri, 14 Nov 2025 04:59:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-17 22:42:18.436197
- Title: Cycle Basis Algorithms for Reducing Maximum Edge Participation
- Title（参考訳）: 最大エッジ参加率削減のためのサイクルバスアルゴリズム
- Authors: Fan Wang, Sandy Irani,
- Abstract要約: 最大エッジ参加率の低いグラフのサイクルベース構築の問題について検討する。
この量は格子手術のオーバーヘッドに直接影響するため、量子フォールトトレランスにおいて重要な役割を果たす。
我々は、エッジ参加を最小限に抑えるために、頂点とエッジを適応的に選択する負荷認識のファミリーを導入する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 本研究では,任意のエッジを共有するベースサイクルの最大数として定義される,エッジの最大参加度が低いグラフのサイクルベースを構築する問題について検討する。
この量は、総重量や長さよりも研究されていないが、ほぼ普遍的な量子ゲートセットを実装するために使用される格子手術手順のオーバーヘッドに直接影響するため、量子フォールトトレランスにおいて重要な役割を果たす。
フリードマンとヘイスティングスの再帰的アルゴリズムに基づいて、サイクルベース構築におけるエッジ参加を最小限に抑えるために、頂点とエッジを適応的に選択する負荷認識ヒューリスティックのファミリーを導入する。
提案手法は、ランダムな正則グラフや小さな量子符号から導出したグラフに対する経験的性能を向上させる。
さらに,簡易なボール・イン・イン・ビン・プロセスを分析し,エッジ参加の下位境界を確立する。
このモデルは実グラフ上のサイクルベースアルゴリズムと異なるが、グラフ内のサイクルの分布に関連する複雑なグラフ理論特性を使わずに、我々のヒューリスティックスで証明できることをキャプチャする。
解析の結果, ヒューリスティックスの最大負荷は (log n)^2 の順に増加することが示唆された。
この結果から, 耐故障性量子系の設計において, 注意深いサイクルベース構築が重要な実用的利益をもたらす可能性が示唆された。
この問題は、本質的にはグラフの基底数と同一であり、すべてのサイクル基底に対する最小限の最大エッジ参加として定義されるため、理論的な関心も持たせる。
関連論文リスト
- A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。
完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。
ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文 参考訳（メタデータ） (2025-01-02T05:06:16Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文 参考訳（メタデータ） (2023-11-18T02:36:10Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Variational quantum eigensolver for causal loop Feynman diagrams and
directed acyclic graphs [0.0]
マルチループファインマン図の因果表現の効率的なブートストラップのための変分量子固有解法(VQE)アルゴリズムを提案する。
マルチループトポロジーを記述する隣接行列に基づくループハミルトニアン(英語版)は、異なるエネルギーレベルがサイクルの数に対応する)はVQEによって最小化され、因果的あるいは非巡回的な構成が特定される。
論文 参考訳（メタデータ） (2022-10-24T13:42:53Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Cycle-tree guided attack of random K-core: Spin glass model and
efficient message-passing algorithm [0.0]
最小攻撃セットは、Kコアの完全な崩壊を引き起こす最小数の頂点を含む。
ここでは、この最適初期条件問題に、サイクルツリー最大パッキングのスピングラスの観点から取り組む。
CTGAの性能と時間効率は、正規ランダムおよびエルド・オス・レニイランダムグラフアンサンブルで検証される。
論文 参考訳（メタデータ） (2021-10-12T12:28:05Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。