論文の概要: Exploring the impact of graph locality for the resolution of MIS with neutral atom devices

• arxiv url: http://arxiv.org/abs/2306.13373v1
• Date: Fri, 23 Jun 2023 08:53:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-26 13:16:10.664130
• Title: Exploring the impact of graph locality for the resolution of MIS with neutral atom devices
• Title（参考訳）: 中性原子デバイスを用いたMISの分解能に対するグラフ局所性の影響の探索
• Authors: Constantin Dalyac, Louis-Paul Henry, Minhyuk Kim, Jaewook Ahn, Lo\"ic Henriet
• Abstract要約: グラフのより複雑なクラスを埋め込むために3Dアレンジメントを用いた最近の進歩の上に構築する。 本稿では,量子コンピュータ上での難しい問題に対処するための重要なステップを示す実験的,理論的結果について報告する。
• 参考スコア（独自算出の注目度）: 0.755972004983746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. In particular, the Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped ``vertex-to-atom" on standard devices with 2D capabilities are currently limited to Unit-Disk graphs. In this setting, the inherent spatial locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an $\epsilon$-approximate solution. In this work, we build upon recent progress made for using 3D arrangements of atoms to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling combinatorial tasks on quantum computers for which no classical efficient $\varepsilon$-approximation scheme exists.
• Abstract（参考訳）: 過去数年間、多くの量子アルゴリズムが難しい組合せ問題に取り組むために提案されてきた。 特に、最大独立集合 (MIS) は、Rydberg 原子配列に自然に符号化できる既知のNPハード問題である。 グラフを中性原子のアンサンブルで表すことで、ライドバーグ力学を利用して制約とMISの解を自然にエンコードすることができる。 しかし、2d機能を持つ標準デバイス上で直接 ``vertex-to-atom" をマッピングできるグラフのクラスは、現時点では単位円グラフに限られている。 この設定では、グラフの本質的な空間的局所性は、$\epsilon$-approximate解を保証する古典多項式時間近似スキーム(PTAS)によって利用することができる。 本研究では,より複雑なグラフのクラスを埋め込むために,原子の3次元配置を用いた最近の進歩について述べる。 古典的効率のよい$\varepsilon$近似スキームが存在しない量子コンピュータにおける組合せタスクに取り組むための重要なステップを示す実験的および理論的結果を報告する。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms [4.619601221994331]
  本稿では,Rydberg 励起を用いた単位ディスクグラフの最大重み付き独立集合の問題について検討する。 相互作用する原子の量子系を多体基底状態に駆動し,非線形準断熱プロファイルを用いてライドバーグデチューニングを網羅する。 また、原子配列の1次元および2次元空間配置において、コンメニュレートおよび非コンメニュレート相を実現する物質の量子相についても検討する。
  論文  参考訳（メタデータ） (2024-05-16T04:23:17Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  フービニ・スタディ計量に基づく絡み合い尺度は、Cocchiarellaと同僚によって最近導入された。 本稿では,多モードガウス状態に対する幾何絡み合いの一般化であるガウスエンタングルメント尺度(GEM)を提案する。 自由度の高い系に対する計算可能な多部絡み合わせ測度を提供することにより、自由なボゾン場理論の洞察を得るために、我々の定義が利用できることを示す。
  論文  参考訳（メタデータ） (2024-01-31T15:50:50Z)
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems [0.3562485774739681]
  本稿では,Rydbergatom グラフを用いて2次非制約二元最適化問題を効果的に解く方法を示す。 ライドバーグ-原子グラフ(英: Rydberg-atom graph)は、プログラム可能な光ツイーザーによって促進される数学的グラフへの中性原子の構成である。
  論文  参考訳（メタデータ） (2023-09-26T11:22:38Z)
• Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms [0.0]
  最大独立集合(英: Maximum Independent Set、MIS)は、リンドバーグ原子配列に自然に符号化できるNPハード問題である。 我々は3次元原子配列に非局所グラフの大きな族を埋め込む決定論的かつ効率的な構成を提案する。 この構成は、古典的な効率的なエプシロン近似スキームが存在しない量子コンピュータ上のタスクに取り組むための最初の重要なステップである。
  論文  参考訳（メタデータ） (2022-09-12T11:46:10Z)
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays [0.0]
  元の問題から明示的な写像を構築することにより、Rydberg配列に効率的にエンコードできる問題のクラスを拡張する。 任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解など、いくつかの例を分析する。
  論文  参考訳（メタデータ） (2022-09-08T18:00:00Z)
• Rydberg Quantum Wires for Maximum Independent Set Problems with Nonplanar and High-Degree Graphs [0.7046417074932257]
  我々は、非決定論的時間ハード(NP-hard)問題を解くために、Rydberg原子を用いて実験を行った。 補助原子を用いたRydberg量子ワイヤスキームを導入し、量子ビット原子の長距離ネットワークを設計する。 3次元(3次元)リードバーグ原子配列は、2次元アレイの本質的な限界を克服して構築される。
  論文  参考訳（メタデータ） (2021-09-08T09:37:18Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  我々は中性原子量子コンピュータにおいてエラー源の完全な特徴付けを行う。 計算部分空間外の状態への原子量子ビットの崩壊に伴う最も重要なエラーに対処する,新しい,明らかに効率的な手法を開発した。 我々のプロトコルは、アルカリ原子とアルカリ原子の両方にエンコードされた量子ビットを持つ最先端の中性原子プラットフォームを用いて、近い将来に実装できる。
  論文  参考訳（メタデータ） (2021-05-27T23:29:53Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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