論文の概要: Finding trail covers: near-optimal decompositions of graph states as linear fusion networks
- arxiv url: http://arxiv.org/abs/2508.18375v1
- Date: Mon, 25 Aug 2025 18:06:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-27 17:42:38.540981
- Title: Finding trail covers: near-optimal decompositions of graph states as linear fusion networks
- Title（参考訳）: 経路被覆を見つける:線状融合ネットワークとしてのグラフ状態の準最適分解
- Authors: William Cashman, Giovanni de Felice, Aleks Kissinger,
- Abstract要約: ユーレアン経路問題とハミルトン経路問題の一般化とみなすことができる3つのグラフ理論問題について検討する。
これらは測定ベースの量子コンピューティングのフォトニックな実装に現れる。
グラフ構築に必要な融合数を削減できるグラフ状態の新しい書き直し戦略を提案する。
- 参考スコア（独自算出の注目度）: 1.7842332554022695
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum compilation requires the development of new algorithms that optimise the cost of implementing quantum computations on physical hardware. Often this gives rise to problems which are asymptotically hard to solve classically, and for which heuristics and reductions to known problems are of great practical use. In this paper, we study three graph-theoretic problems which can be seen as generalisations of the Eulerian and Hamiltonian path problems. These arise in photonic implementations of measurement-based quantum computing, where graph states are constructed by fusing bounded-length linear resource states. Since the fusion operation succeeds with probability smaller than one, we wish to minimise the number of fusions required to build a particular graph state and this corresponds to finding a minimal path or trail cover of the graph. We show that these covering problems are NP-hard in most cases and give heuristic algorithms for finding trail covers in graphs including a reduction to the travelling salesman problem. We propose new rewrite strategies for graph states that reduce the number of fusions required to build a given graph. Finally, we apply these algorithms to the compilation of photonic fusion networks and provide a series of benchmarks showing the performance of our algorithms on common error-correcting codes and circuits from the QASMBench set.
- Abstract（参考訳）: 量子コンパイルは、物理ハードウェア上で量子計算を実装するコストを最適化する新しいアルゴリズムの開発を必要とする。
これはしばしば、漸近的に古典的解決が難しい問題を引き起こし、既知の問題に対するヒューリスティックと縮小が非常に実用的である。
本稿では、ユーレアン経路問題とハミルトン経路問題の一般化とみなすことができる3つのグラフ理論問題について検討する。
これらは測定ベースの量子コンピューティングのフォトニックな実装で発生し、グラフ状態は有界長線形資源状態と融合して構築される。
融合演算は1より小さい確率で成功するので、特定のグラフ状態を構築するのに必要な融合の数を最小化したい。
これらの被覆問題は、ほとんどの場合NPハードであり、トラベリングセールスマン問題への還元を含むグラフの軌跡被覆を見つけるためのヒューリスティックアルゴリズムを提供する。
グラフ構築に必要な融合数を削減できるグラフ状態の新しい書き直し戦略を提案する。
最後に、これらのアルゴリズムをフォトニックフュージョンネットワークのコンパイルに適用し、QASMBench集合の一般的な誤り訂正符号および回路上でのアルゴリズムの性能を示す一連のベンチマークを提供する。
関連論文リスト
- A Scalable and Robust Compilation Framework for Emitter-Photonic Graph State [1.3624495460189865]
決定論的スキームの文脈におけるGraphState-to-Circuitコンパイル問題について検討する。
本稿では,対象のグラフ状態をサブグラフに分割し,個別にコンパイルし,その後回路を結合してエミッタ資源利用を最大化する,新たなコンパイルフレームワークを提案する。
論文 参考訳（メタデータ） (2025-03-20T17:01:33Z) - Parallel Token Swapping for Qubit Routing [2.280359339174839]
現代の量子コンピュータでよく見られるグラフトポロジ上の並列トークンスワップ問題に対する最初の定数係数近似アルゴリズムを提供する。
また、量子ビットルーティング問題に対する再構成を設計する際に有用であることが示されている自然下界のいわゆる伸張係数についても検討した。
論文 参考訳（メタデータ） (2024-11-27T18:26:16Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳（メタデータ） (2022-08-22T22:07:27Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。