論文の概要: Sampling diverse near-optimal solutions via algorithmic quantum
annealing
- arxiv url: http://arxiv.org/abs/2110.10560v3
- Date: Thu, 11 Jan 2024 22:08:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-16 00:37:45.272285
- Title: Sampling diverse near-optimal solutions via algorithmic quantum
annealing
- Title（参考訳）: アルゴリズム量子アニールによる多様な準最適解のサンプリング
- Authors: Masoud Mohseni, Marek M. Rams, Sergei V. Isakov, Daniel Eppens,
Susanne Pielawa, Johan Strumpfer, Sergio Boixo, Hartmut Neven
- Abstract要約: 主要な開問題の1つは、典型的なモンテカルロ解法に対するエルゴディディティの欠如、あるいはモード崩壊である。
本稿ではNP-hard最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
- 参考スコア（独自算出の注目度）: 0.3506539188356145
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sampling a diverse set of high-quality solutions for hard optimization
problems is of great practical relevance in many scientific disciplines and
applications, such as artificial intelligence and operations research. One of
the main open problems is the lack of ergodicity, or mode collapse, for typical
stochastic solvers based on Monte Carlo techniques leading to poor
generalization or lack of robustness to uncertainties. Currently, there is no
universal metric to quantify such performance deficiencies across various
solvers. Here, we introduce a new diversity measure for quantifying the number
of independent approximate solutions for NP-hard optimization problems. Among
others, it allows benchmarking solver performance by a required
time-to-diversity (TTD), a generalization of often used time-to-solution (TTS).
We illustrate this metric by comparing the sampling power of various quantum
annealing strategies. In particular, we show that the inhomogeneous quantum
annealing schedules can redistribute and suppress the emergence of topological
defects by controlling space-time separated critical fronts, leading to an
advantage over standard quantum annealing schedules with respect to both TTS
and TTD for finding rare solutions. Using path-integral Monte Carlo simulations
for up to 1600 qubits, we demonstrate that nonequilibrium driving of quantum
fluctuations, guided by efficient approximate tensor network contractions, can
significantly reduce the fraction of hard instances for random frustrated 2D
spin-glasses with local fields. Specifically, we observe that by creating a
class of algorithmic quantum phase transitions, the diversity of solutions can
be enhanced by up to 40% with the fraction of hard-to-sample instances reducing
by more than 25%.
- Abstract（参考訳）: ハード最適化問題に対する様々な高品質なソリューションをサンプリングすることは、人工知能や運用研究のような多くの科学分野や応用において、非常に実用的な意味を持つ。
主要なオープンな問題の1つは、モンテカルロ法に基づく典型的な確率的解法に対するエルゴディディティの欠如またはモード崩壊であり、不確実性に対する一般化や堅牢性の欠如につながる。
現在、様々な解法においてそのような性能欠陥を定量化する普遍的な計量は存在しない。
本稿ではNP-hard最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
中でもTTD(Time-to-diversity)は,よく使用されるTTS(Time-to-solution)の一般化である。
種々の量子アニーリング戦略のサンプリングパワーを比較することで、この指標を説明する。
特に,不均質な量子アニーリングスケジュールは,時空分離された臨界前線を制御することによって位相的欠陥の発生を再分配し抑制することができ,ttsとttdの両方について標準量子アニーリングスケジュールよりも稀な解を求めることができることを示した。
1600 量子ビットまでのパス積分モンテカルロシミュレーションを用いて、量子ゆらぎの非平衡駆動は、効率的な近似テンソルネットワーク収縮によって導かれるが、局所場を持つランダムなフラストレーション2次元スピングラスのハードインスタンスの分数を大幅に削減できることを示した。
具体的には、アルゴリズムによる量子相転移のクラスを作成することにより、解の多様性を最大40%向上させ、サンプルインスタンスの分画を25%以上減少させることができる。
関連論文リスト
- Observation of disorder-free localization and efficient disorder averaging on a quantum processor [117.33878347943316]
我々は、量子並列性を利用して、量子プロセッサ上で効率的な手順を実装し、すべての障害実現を効率的にサンプリングする。
1次元と2次元の量子多体ダイナミクスにおいて、乱れのない局所化を観察する。
論文 参考訳（メタデータ） (2024-10-09T05:28:14Z) - Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。
私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。
基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
論文 参考訳（メタデータ） (2024-05-22T18:11:42Z) - Investigation into the Potential of Parallel Quantum Annealing for
Simultaneous Optimization of Multiple Problems: A Comprehensive Study [0.0]
アナリング(Annealing)は、複数の最適化問題を同時に解く手法である。
アニーリング法はアイドル量子ビットを最小化し、かなりのスピードアップを約束する。
論文 参考訳（メタデータ） (2024-03-09T02:18:48Z) - A self-consistent field approach for the variational quantum
eigensolver: orbital optimization goes adaptive [52.77024349608834]
適応微分組立問題集合型アンザッツ変分固有解法(ADAPTVQE)における自己一貫したフィールドアプローチ(SCF)を提案する。
このフレームワークは、短期量子コンピュータ上の化学系の効率的な量子シミュレーションに使用される。
論文 参考訳（メタデータ） (2022-12-21T23:15:17Z) - 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Nonequilibrium Monte Carlo for unfreezing variables in hard
combinatorial optimization [1.1783108699768]
適応的勾配自由戦略を開発することにより,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入する。
我々は、特殊解法と汎用解法の両方に対して、大幅な高速化と堅牢性を観察する。
論文 参考訳（メタデータ） (2021-11-26T17:45:32Z) - Diversity metric for evaluation of quantum annealing [1.0499611180329802]
量子解法が古典的手法と比較して構成空間をいかによくサンプリングするかは分かっていない。
メタヒューリスティックス・ソルバの評価のための指標として,時間と多様性を用いる。
このことは、量子と古典的な解を組み合わせたポートフォリオソルバが全ての解法に勝っていることを示唆している。
論文 参考訳（メタデータ） (2021-10-19T18:37:01Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。