論文の概要: Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability

• arxiv url: http://arxiv.org/abs/2507.22761v1
• Date: Wed, 30 Jul 2025 15:22:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 16:14:18.282696
• Title: Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Title（参考訳）: Rydberg原子による近似組合せ最適化--解釈可能性の障壁
• Authors: Christian de Correc, Thomas Ayral, Corentin Bertrand,
• Abstract要約: 最近導入されたCrossing Lattice埋め込みにおいて,2つの解釈戦略が誤りを訂正する能力を評価する。 Rydbergプラットフォームで、スケーラブルで汎用的な品質改善が達成できる可能性は低い。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Analog quantum computing with Rydberg atoms is seen as an avenue to solve hard graph optimization problems, because they naturally encode the Maximum Independent Set (MIS) problem on Unit-Disk (UD) graphs, a problem that admits rather efficient approximation schemes on classical computers. Going beyond UD-MIS to address generic graphs requires embedding schemes, typically with chains of ancilla atoms, and an interpretation algorithm to map results back to the original problem. However, interpreting approximate solutions obtained with realistic quantum computers proves to be a difficult problem. As a case study, we evaluate the ability of two interpretation strategies to correct errors in the recently introduced Crossing Lattice embedding. We find that one strategy, based on finding the closest embedding solution, leads to very high qualities, albeit at an exponential cost. The second strategy, based on ignoring defective regions of the embedding graph, is polynomial in the graph size, but it leads to a degradation of the solution quality which is prohibitive under realistic assumptions on the defect generation. Moreover, more favorable defect scalings lead to a contradiction with well-known approximability conjectures. Therefore, it is unlikely that a scalable and generic improvement in solution quality can be achieved with Rydberg platforms -- thus moving the focus to heuristic algorithms.
• Abstract（参考訳）: ライドバーグ原子を用いたアナログ量子コンピューティングは、古典的コンピュータ上でかなり効率的な近似スキームを許容する問題であるユニットディスク(UD)グラフ上の最大独立集合(MIS)問題を自然に符号化するため、ハードグラフ最適化問題を解くための手段と見なされている。 UD-MISを超えて汎用グラフに対処するには、典型的にはアンシラ原子の連鎖を含む埋め込みスキームと、結果を元の問題にマッピングする解釈アルゴリズムが必要である。 しかし、現実的な量子コンピュータで得られた近似解を解釈することは難しい問題である。 ケーススタディとして,最近導入されたCrossing Lattice埋め込みにおいて,2つの解釈戦略が誤りを訂正する能力を評価する。 1つの戦略は、最も近い埋め込みソリューションを見つけることに基づくもので、指数的なコストではあるものの、非常に高い品質をもたらす。 埋め込みグラフの欠陥領域を無視した第2の戦略は、グラフサイズにおける多項式であるが、欠陥生成に関する現実的な仮定で禁止される解の質の低下につながる。 さらに、より好ましい欠陥スケーリングは、よく知られた近似可能性予想と矛盾する。 したがって、Rydbergプラットフォームで、スケーラブルで汎用的なソリューション品質の改善が達成される可能性は低い。

関連論文リスト

• Minor Embedding for Quantum Annealing with Reinforcement Learning [10.787328610467801]
  強化学習(RL)は、小さな埋め込みをシーケンシャルな意思決定問題として扱うことで、有望な代替手段を提供する。 提案手法は, 完全連結問題とランダムに生成した問題の両方を埋め込む能力をテストする。 提案手法は,よりフレキシブルで汎用的なフレームワークとしてのRLの可能性を強調し,問題のサイズを適度に拡大し,異なるグラフ構造に順応することができる。
  論文  参考訳（メタデータ） (2025-07-21T18:54:15Z)
• A Scalable and Robust Compilation Framework for Emitter-Photonic Graph State [1.3624495460189865]
  決定論的スキームの文脈におけるGraphState-to-Circuitコンパイル問題について検討する。 本稿では,対象のグラフ状態をサブグラフに分割し,個別にコンパイルし,その後回路を結合してエミッタ資源利用を最大化する,新たなコンパイルフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-03-20T17:01:33Z)
• 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)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  量子断熱最適化(Quantum adiabatic optimization)は、量子力学を用いて問題を解決する。 ハミルトニアンはしばしば量子ハードウェアのネイティブな制約とは相容れない。 符号化された問題は指数関数的に閉じた最小のギャップを示す。
  論文  参考訳（メタデータ） (2024-11-07T12:10:01Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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