論文の概要: Reducibility of native weighted graphs on Rydberg Arrays

• arxiv url: http://arxiv.org/abs/2605.07952v1
• Date: Fri, 08 May 2026 16:18:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.194736
• Title: Reducibility of native weighted graphs on Rydberg Arrays
• Title（参考訳）: Rydberg配列上のネイティブ重み付きグラフの低減性
• Authors: J. Kombe, J. D. Pritchard,
• Abstract要約: 最大独立集合 (MIS) と最大重み付き独立集合 (MWIS) のランダム単位ディスクグラフ (UDG) の古典的再現性について検討した。 残りの有限個のカーネルでは、量子実行はリソースオーバーヘッドがかなり大きい非ネイティブな埋め込みを必要とする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.
• Abstract（参考訳）: 我々は、Rydberg原子量子プロセッサでネイティブに実現可能な、最大独立集合 (MIS) と最大重み付き独立集合 (MWIS) 問題のランダム単位ディスクグラフ (UDG) インスタンスの古典的再現性について検討する。 最先端のカーネル化技術を用いて,従来のプリプロセッシングが,サイズや接続性の異なるネイティブな最適化問題をいかに単純化できるかを体系的に検討する。 多くの小さな、あるいはスパースなインスタンスは、完全に還元できるが、高密度グラフは、広範囲に還元された後も、有限既約核を保持することが多い。 頂点重みの導入は再現性を高める傾向にあるが、基礎となるUDG接続における相互作用範囲の拡張は還元効率を抑制する。 古典的な削減が効果的に行われなくなる場所を探索することによって、計算的に要求される問題インスタンス - 短期的な量子最適化ハードウェアのテストとベンチマークに最も関係のあるもの - の体制を明確にすることを目指している。 残りの有限個のカーネルでは、量子実行はリソースオーバーヘッドがかなり大きい非ネイティブな埋め込みを必要としているため、直接実行されたネイティブインスタンスは、削減されたカーネルを埋め込むよりも実用的である可能性が示唆されている。

関連論文リスト

• Quantum Optimization Methods for the Generalized Traveling Salesman Problem [2.4029307306254513]
  本稿では,汎用トラベリングセールスマン問題(GTSP)の量子最適化ベースラインについて検討する。 本稿では,量子アニールにおける実現可能な解の維持に焦点をあてた新しいGTSP QUBO の定式化を提案する。 我々は、理想回路モデルにおいて段階的にハミング重みを保持するXYミキサーを用いた制約付きQAOA変種を実装した。
  論文  参考訳（メタデータ） (2026-04-28T11:58:35Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。 等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。 完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
  論文  参考訳（メタデータ） (2026-04-20T13:57:49Z)
• A quantum feasibility preserving modeling for the min cut problem [1.3701366534590498]
  変分量子アルゴリズムを用いた重み付き無向グラフにおける最小カット問題について検討する。 我々は、量子進化を有効なカット構成の部分空間に制限するリング構造XYミキサーを用いる。
  論文  参考訳（メタデータ） (2026-02-26T12:34:59Z)
• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach [0.5497663232622965]
  任意のグラフから単位ディスクインスタンスへの還元の複雑性-理論的限界について論じる。 このような減少は幾何数で爆発的に起こり、解近似の保証を低下させる。 現実的な代替手段として,プリド原子配置を利用する線形オーバーヘッドのみを持つ分割・分散器を提案する。
  論文  参考訳（メタデータ） (2025-08-08T08:50:29Z)
• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  制約処理は、量子最適化における重要なボトルネックである。 量子シミュレータやハードウェア上での制約問題を解くために,ラグランジアンに基づく一連の最適化手法について検討する。 この結果は,QUBOのペナライゼーションに代わるスケーラブルな代替手段として,ラグランジアン定式化の柔軟性を強調した。
  論文  参考訳（メタデータ） (2025-07-16T11:39:47Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  我々は,textbfMixed textbfPrecision textbfQuantizationフレームワークを改良したMPQ-DMv2を提案する。
  論文  参考訳（メタデータ） (2025-07-06T08:16:50Z)
• A quantum wire approach to weighted combinatorial graph optimisation problems [0.0]
  本稿では,Rydberg-blockaded 原子の連鎖に基づく効率的な符号化方式を実験的に提案する。 中性原子アーキテクチャに最大重み付き独立集合(MWIS)と2次非制約二元最適化(QUBO)問題を埋め込む。
  論文  参考訳（メタデータ） (2025-03-21T13:00:51Z)
• QT-DoG: Quantization-aware Training for Domain Generalization [58.439816306817306]
  領域一般化のための量子化アウェアトレーニング(QT-DoG)を提案する。 我々は、減量量化が損失景観におけるより平坦なミニマムを効果的に導くことを実証した。 QT-DoGは、モデル重みのノイズを誘導することで暗黙の正則化器として量子化を利用する。
  論文  参考訳（メタデータ） (2024-10-08T13:21:48Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  ディープニューラルネットワーク(DNN)モデルは、特にリソース制限されたデバイスにおいて、実用的なアプリケーションに不可欠である。 既往の非構造的あるいは構造化された重量刈り法は、推論を真に加速することはほとんど不可能である。 ハードウェア互換のマイクロ構造レベルでの一般化された重み統一フレームワークを提案し,高い圧縮と加速度を実現する。
  論文  参考訳（メタデータ） (2021-06-15T17:22:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。