論文の概要: Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
- arxiv url: http://arxiv.org/abs/2502.04291v1
- Date: Thu, 06 Feb 2025 18:34:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-07 14:32:13.027993
- Title: Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
- Title（参考訳）: 中性原子量子プロセッサ上の最大独立集合問題に対するハードネイティブインスタンスの同定
- Authors: Pierre Cazals, Aymeric François, Loïc Henriet, Lucas Leclerc, Malory Marin, Yassine Naghmouchi, Wesley da Silva Coelho, Florian Sikora, Vittorio Vitale, Rémi Watrigant, Monique Witt Garzillo, Constantin Dalyac,
- Abstract要約: 最大独立集合問題(英: Maximum Independent Set、MIS)は、中性原子量子プロセッサのイジング・ハミルトニアンに自然にマッピングできる基本的な最適化課題である。
NPハード問題と実世界の応用との関係を考えると、MISの量子的優位性を探究する実験的な関心がある。
我々は、複雑性理論結果と密度や木幅などの鍵硬度パラメータの変化を利用して、単位ディスクグラフのハードインスタンスを生成する。
- 参考スコア（独自算出の注目度）: 0.48520567143062737
- License:
- Abstract: The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.
- Abstract（参考訳）: 最大独立集合問題(英: Maximum Independent Set、MIS)は、中性原子量子プロセッサのイジング・ハミルトニアンに自然にマッピングできる基本的な組合せ最適化タスクである。
NPハード問題と実世界の応用との関係を考えると、MISの量子的優位性を探究する実験的な関心がある。
King's Lattice グラフのパイオニアリング実験では、シミュレートされたアニーリングよりも2次的なスピードアップが示唆されたが、最近のベンチマークでは、テストされたインスタンスの構造上、明確な利点は見つからなかった。
本研究では、複雑性理論結果と密度や木幅などの鍵硬度パラメータの変化を利用して、単位ディスクグラフのハードインスタンスを生成する。
固定グラフサイズの場合、これらのパラメータの増大は古典的実行を禁止的に数桁増加させる可能性があることを示す。
その後、我々は、小さなインスタンスにおける古典的および量子的アプローチを比較し、このスケールでは、量子的解は、正確な解を見つけるための古典的方法よりも遅いことを発見した。
1kHzの繰り返し速度で最大1000個の原子をスケーリングすることが、量子的手法による計算上の優位性を示すための必要なステップであると推定する。
関連論文リスト
- Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
3つの正則グラフに対する量子アニールは1000量子ビットと5000000量子ビットゲートのスケールでも古典的にシミュレートできることを示す。
非退化インスタンスの場合、一意解は最後の縮小された単一量子状態から読み出すことができる。
MaxCutのような退化問題に対して、グラフテンソル-ネットワーク状態に対する近似的な測定シミュレーションアルゴリズムを導入する。
論文 参考訳（メタデータ） (2024-09-18T18:00:08Z) - Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
超伝導量子コンピュータは、ハイブリッド量子古典アルゴリズムの性能を調べるために用いられる。
同様に高い性能の古典に対して量子解法をベンチマークする。
実行時解析により、大規模問題における量子解法は、グロビと競合するが、100量子ビットの量子コンピュータでは他より小さいことが示されている。
論文 参考訳（メタデータ） (2024-04-26T17:59:22Z) - 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 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) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
量子計算を古典的な結果によって補う手法を提案する。
予測の利点を生かして、新しいタイプの量子測度がもたらされる。
予測量子測定では、古典計算と量子計算の結果の組み合わせは最後にのみ起こる。
論文 参考訳（メタデータ） (2022-09-12T15:47:44Z) - 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) - Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer [0.4893345190925178]
多電子問題は計算科学における最大の課題のいくつかを浮き彫りにする。
フェルミオン量子モンテカルロ法(英語版)(QMC)はこれらの問題に対する最も強力なアプローチの一つである。
本稿では,制約付きQMCと量子コンピューティングツールを組み合わせることで,バイアスを低減する手法を提案する。
論文 参考訳（メタデータ） (2021-06-30T17:43:47Z) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。
ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。
この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
論文 参考訳（メタデータ） (2020-08-03T18:00:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。