論文の概要: Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach

• arxiv url: http://arxiv.org/abs/2508.06130v1
• Date: Fri, 08 Aug 2025 08:50:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.151759
• Title: Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
• Title（参考訳）: 任意接続性を持つRydberg原子配列の量子最適化:ガジェット制限とヒューリスティックアプローチ
• Authors: Pierre Cazals, Amalia Sorondo, Victor Onofre, Constantin Dalyac, Wesley da Silva Coelho, Vittorio Vitale,
• Abstract要約: 任意のグラフから単位ディスクインスタンスへの還元の複雑性-理論的限界について論じる。 このような減少は幾何数で爆発的に起こり、解近似の保証を低下させる。 現実的な代替手段として,プリド原子配置を利用する線形オーバーヘッドのみを持つ分割・分散器を提案する。
• 参考スコア（独自算出の注目度）: 0.5497663232622965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Programmable quantum systems based on Rydberg atom arrays have recently emerged as a promising testbed for combinatorial optimization. Indeed, the Maximum Weighted Independent Set problem on unit-disk graphs can be efficiently mapped to such systems due to their geometric constraints. However, extending this capability to arbitrary graph instances typically necessitates the use of reduction gadgets, which introduce additional experimental overhead and complexity. Here, we analyze the complexity-theoretic limits of polynomial reductions from arbitrary graphs to unit-disk instances. We prove any such reduction incurs a quadratic blow-up in vertex count and degrades solution approximation guarantees. As a practical alternative, we propose a divide-and-conquer heuristic with only linear overhead which leverages precalibrated atomic layouts. We benchmark it on Erd\"os-R\'enyi graphs, and demonstrate feasibility on the Orion Alpha processor.
• Abstract（参考訳）: Rydberg 原子配列に基づくプログラム可能な量子システムは、最近、組合せ最適化のための有望なテストベッドとして登場した。 実際、単位ディスクグラフ上の最大重み付き独立集合問題は、幾何学的制約のため、そのような系に効率的にマッピングすることができる。 しかし、この機能を任意のグラフインスタンスに拡張するには、通常、リダクションガジェットを使用する必要がある。 ここでは、任意のグラフから単位ディスクインスタンスへの多項式還元の複雑性-理論的限界を分析する。 このような減少は頂点数において2次的爆発を生じさせ、解近似の保証を低下させる。 現実的な代替手段として,プリカリブレーションされた原子配置を利用する線形オーバーヘッドのみを持つ分割・対数ヒューリスティックを提案する。 Erd\"os-R'enyiグラフ上でベンチマークを行い、Orion Alphaプロセッサで実現可能であることを示す。

関連論文リスト

• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  量子断熱最適化(Quantum adiabatic optimization)は、量子力学を用いて問題を解決する。 ハミルトニアンはしばしば量子ハードウェアのネイティブな制約とは相容れない。 符号化された問題は指数関数的に閉じた最小のギャップを示す。
  論文  参考訳（メタデータ） (2024-11-07T12:10:01Z)
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts [0.0]
  Rydberg 原子アレイ上での最大重み付き独立集合問題の解法を示す。 重み付きグラフを1次元および2次元配列で作成する能力を検証する。
  論文  参考訳（メタデータ） (2024-04-03T11:42:38Z)
• Exploring the impact of graph locality for the resolution of MIS with neutral atom devices [0.755972004983746]
  グラフのより複雑なクラスを埋め込むために3Dアレンジメントを用いた最近の進歩の上に構築する。 本稿では,量子コンピュータ上での難しい問題に対処するための重要なステップを示す実験的,理論的結果について報告する。
  論文  参考訳（メタデータ） (2023-06-23T08:53:16Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Efficient algorithms to solve atom reconfiguration problems. I. The redistribution-reconfiguration (red-rec) algorithm [35.300779480388705]
  Red-recはグリッド上の原子再構成問題を解決するためにシンプルで正確なサブルーチンを利用する。 Red-recは、平均的な成功確率の高い原子の大規模な構成を組み立てることができる。
  論文  参考訳（メタデータ） (2022-12-07T19:00:01Z)
• 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)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)

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

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