論文の概要: Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms

• arxiv url: http://arxiv.org/abs/2209.05164v1
• Date: Mon, 12 Sep 2022 11:46:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-26 22:21:09.622185
• Title: Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms
• Title（参考訳）: 3次元原子配列を用いた有界次数非局所グラフのmis問題への埋め込み
• Authors: Constantin Dalyac and Loic Henriet
• Abstract要約: 最大独立集合(英: Maximum Independent Set、MIS)は、リンドバーグ原子配列に自然に符号化できるNPハード問題である。 我々は3次元原子配列に非局所グラフの大きな族を埋め込む決定論的かつ効率的な構成を提案する。 この構成は、古典的な効率的なエプシロン近似スキームが存在しない量子コンピュータ上のタスクに取り組むための最初の重要なステップである。
• 参考スコア（独自算出の注目度）: 0.0
• 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. These algorithms, which have been studied in depth in complexity theory, are at the heart of many industrial applications. 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 node-to-atom on such devices are limited to Unit-Disk graphs. In this setting, the inherent locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an {\epsilon}-approximate solution. In this work, we present a deterministic and polynomial-time construction to embed a large family of non-local graphs in 3D atomic arrays. This construction is a first crucial step towards tackling combinatorial tasks on quantum computers for which no classical efficient {\epsilon}-approximation scheme exists.
• Abstract（参考訳）: 過去数年間、多くの量子アルゴリズムが難しい組合せ問題に取り組むために提案されてきた。 これらのアルゴリズムは、複雑性理論において深く研究されており、多くの産業応用の中心にある。 特に、最大独立集合 (MIS) は、Rydberg 原子配列に自然に符号化できる既知のNPハード問題である。 グラフを中性原子のアンサンブルで表すことで、ライドバーグ力学を利用して制約とMISの解を自然にエンコードすることができる。 しかし、そのようなデバイス上で直接ノードからアトムにマッピングできるグラフのクラスは単位円グラフに限られる。 この設定では、グラフの本質的な局所性は、古典多項式時間近似スキーム(PTAS)によって利用でき、これは {\epsilon}-近似解を保証する。 本研究では、3次元原子配列に非局所グラフの大きな族を埋め込む決定論的および多項式時間構成を提案する。 この構成は、古典的効率のよい近似スキームが存在しない量子コンピュータの組合せタスクに取り組むための最初の重要なステップである。

関連論文リスト

• 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)
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems [0.3562485774739681]
  本稿では,Rydbergatom グラフを用いて2次非制約二元最適化問題を効果的に解く方法を示す。 ライドバーグ-原子グラフ(英: Rydberg-atom graph)は、プログラム可能な光ツイーザーによって促進される数学的グラフへの中性原子の構成である。
  論文  参考訳（メタデータ） (2023-09-26T11:22:38Z)
• Exploring the impact of graph locality for the resolution of MIS with neutral atom devices [0.755972004983746]
  グラフのより複雑なクラスを埋め込むために3Dアレンジメントを用いた最近の進歩の上に構築する。 本稿では,量子コンピュータ上での難しい問題に対処するための重要なステップを示す実験的,理論的結果について報告する。
  論文  参考訳（メタデータ） (2023-06-23T08:53:16Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays [0.0]
  元の問題から明示的な写像を構築することにより、Rydberg配列に効率的にエンコードできる問題のクラスを拡張する。 任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解など、いくつかの例を分析する。
  論文  参考訳（メタデータ） (2022-09-08T18:00:00Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• 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)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)

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

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