論文の概要: Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays

• arxiv url: http://arxiv.org/abs/2202.09372v1
• Date: Fri, 18 Feb 2022 19:00:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-24 17:24:53.358278
• Title: Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Title（参考訳）: Rydberg Atom Array を用いた最大独立集合の量子最適化
• Authors: Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T. Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, Jinguo Liu, Rhine Samajdar, Xiu-Zhe Luo, Beatrice Nash, Xun Gao, Boaz Barak, Edward Farhi, Subir Sachdev, Nathan Gemelke, Leo Zhou, Soonwon Choi, Hannes Pichler, Shengtao Wang, Markus Greiner, Vladan Vuletic, Mikhail D. Lukin
• Abstract要約: 最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
• 参考スコア（独自算出の注目度）: 39.76254807200083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find the problem hardness is controlled by the solution degeneracy and number of local minima, and experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
• Abstract（参考訳）: 量子スピードアップを実現することは、量子情報科学において重要な課題である。 2次元で最大289キュービットのRydberg原子配列を用いて、最大独立集合問題を解くための量子アルゴリズムを実験的に検討した。 我々はrydbergブロックに関連するハードウェア効率のよいエンコーディングを用いて、いくつかの変分アルゴリズムをテストするクローズドループ最適化を実現し、プログラム可能な接続性を持つグラフのクラスを体系的に探索する。 問題硬度は解縮率と局所極小数によって制御され、量子アルゴリズムの性能を古典的シミュレートアニーリングに対して実験的にベンチマークする。 最も難しいグラフでは、深部回路の正確な解を見つけるために超線形量子スピードアップを観察し、その起源を分析する。

関連論文リスト

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  半定値アプローチに着想を得たハイブリッド量子古典アルゴリズムの性能について検討した。 何千もの問題インスタンスのランダムアンサンブルに対して平均99%のパフォーマンスを達成した。 実行時解析により、大規模問題における量子解法は、グロビと競合するが、他の問題には劣ることを示した。
  論文  参考訳（メタデータ） (2024-04-26T17:59:22Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups [9.927706464212168]
  ライドバーグ原子配列は量子スピードアップの実証において主要な候補の一つである。 古典的解法を幅広く含む単位ディスクグラフ上での最大独立集合問題について検討する。 Union-Jackのような接続性を持つ準平面インスタンスは、最大数千のノードを数分で最適に処理できる。
  論文  参考訳（メタデータ） (2023-07-18T17:16:42Z)
• Quantum speedup for combinatorial optimization with flat energy landscapes [0.0]
  我々は,最適化された量子断熱アルゴリズムと古典マルコフ連鎖モンテカルロアルゴリズムの相対的性能を解析するための理論的枠組みを開発する。
  論文  参考訳（メタデータ） (2023-06-22T18:00:00Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。 我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。 この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
  論文  参考訳（メタデータ） (2023-06-10T23:28:13Z)
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays [0.0]
  元の問題から明示的な写像を構築することにより、Rydberg配列に効率的にエンコードできる問題のクラスを拡張する。 任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解など、いくつかの例を分析する。
  論文  参考訳（メタデータ） (2022-09-08T18:00:00Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。 一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。 幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
  論文  参考訳（メタデータ） (2021-04-01T19:06:00Z)

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

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