論文の概要: Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and
Prospects for Quantum Speedups
- arxiv url: http://arxiv.org/abs/2307.09442v3
- Date: Tue, 9 Jan 2024 17:07:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 20:07:55.596861
- Title: Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and
Prospects for Quantum Speedups
- Title（参考訳）: 単位円グラフ上の最大独立集合問題の硬さと量子スピードアップの展望
- Authors: Ruben S. Andrist, Martin J. A. Schuetz, Pierre Minssen, Romina
Yalovetzky, Shouvanik Chakrabarti, Dylan Herman, Niraj Kumar, Grant Salton,
Ruslan Shaydulin, Yue Sun, Marco Pistoia, Helmut G. Katzgraber
- Abstract要約: ライドバーグ原子配列は量子スピードアップの実証において主要な候補の一つである。
古典的解法を幅広く含む単位ディスクグラフ上での最大独立集合問題について検討する。
Union-Jackのような接続性を持つ準平面インスタンスは、最大数千のノードを数分で最適に処理できる。
- 参考スコア（独自算出の注目度）: 9.927706464212168
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Rydberg atom arrays are among the leading contenders for the demonstration of
quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi
et al., Science 376, 1209 (2022)] we study the maximum independent set problem
on unit-disk graphs with a broader range of classical solvers beyond the scope
of the original paper. We carry out extensive numerical studies and assess
problem hardness, using both exact and heuristic algorithms. We find that
quasi-planar instances with Union-Jack-like connectivity can be solved to
optimality for up to thousands of nodes within minutes, with both custom and
generic commercial solvers on commodity hardware, without any instance-specific
fine-tuning. We also perform a scaling analysis, showing that by relaxing the
constraints on the classical simulated annealing algorithms considered in Ebadi
et al., our implementation is competitive with the quantum algorithms.
Conversely, instances with larger connectivity or less structure are shown to
display a time-to-solution potentially orders of magnitudes larger. Based on
these results we propose protocols to systematically tune problem hardness,
motivating experiments with Rydberg atom arrays on instances orders of
magnitude harder (for established classical solvers) than previously studied.
- Abstract（参考訳）: rydbergの原子配列は、量子スピードアップのデモンストレーションの有力候補の1つだ。
最大289 qubits (Ebadi et al., Science 376, 1209 (2022)) を用いた最近の実験により、原論文の範囲を超えて幅広い古典的解法を持つ単位ディスクグラフ上の最大独立集合問題について研究した。
我々は,厳密かつヒューリスティックなアルゴリズムを用いて,広範囲な数値研究を行い,問題の難易度を評価する。
共用ジャックのような接続性を持つ準平面インスタンスは、インスタンス固有の微調整をすることなく、コモディティハードウェア上でカスタムとジェネリックの両方の商用解法を用いて、数分で最大数千のノードで最適に解くことができる。
また,ebadiらによって検討された古典的なシミュレーションアニーリングアルゴリズムの制約を緩和することで,量子アルゴリズムとの競合性を示した。
逆に、より大きな接続性または少ない構造を持つインスタンスは、潜在的に桁違いに大きい時間から解法を示す。
これらの結果に基づき,従来より数桁難易度(確立された古典的解法)のインスタンス上で,rydberg原子配列を用いた実験をモチベーションとして,問題硬度を体系的に調整するプロトコルを提案する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - 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 speedup for combinatorial optimization with flat energy
landscapes [0.0]
我々は,最適化された量子断熱アルゴリズムと古典マルコフ連鎖モンテカルロアルゴリズムの相対的性能を解析するための理論的枠組みを開発する。
論文 参考訳（メタデータ） (2023-06-22T18:00:00Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum optimization with arbitrary connectivity using Rydberg atom
arrays [0.0]
元の問題から明示的な写像を構築することにより、Rydberg配列に効率的にエンコードできる問題のクラスを拡張する。
任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解など、いくつかの例を分析する。
論文 参考訳（メタデータ） (2022-09-08T18:00:00Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Optimization of Maximum Independent Set using Rydberg Atom
Arrays [39.76254807200083]
最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。
問題の難易度は解の縮退と局所ミニマの数によって制御される。
最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
論文 参考訳（メタデータ） (2022-02-18T19:00:01Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。