論文の概要: Diversity measure for discrete optimization: Sampling rare solutions via
algorithmic quantum annealing
- arxiv url: http://arxiv.org/abs/2110.10560v2
- Date: Sat, 23 Oct 2021 00:50:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 00:00:21.610417
- Title: Diversity measure for discrete optimization: Sampling rare 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.5277024349608835
- 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. To test
this metric, we compare the sampling power of various quantum annealing
strategies. 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 Time-To-Solution (TTS) and
Time-To-Diversity (TTD) for finding rare solutions. Using Path-Integral Monte
Carlo simulations for up to 1600 qubits, we demonstrate that non-equilibrium
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最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
この測定値をテストするために、様々な量子アニーリング戦略のサンプリングパワーを比較する。
非均質な量子アニーリングスケジュールは、時空分離された臨界前線を制御することによって位相的欠陥の発生を再分配し抑制することができ、希少解を見つけるためのタイム・トゥ・ソリューション (tts) とタイム・トゥ・ダイバーシティ (ttd) の両方に関して標準量子アニーリングスケジュールよりも有利であることを示した。
1600 量子ビットまでのパス積分モンテカルロシミュレーションを用いて、量子ゆらぎの非平衡駆動は、効率的な近似テンソルネットワーク収縮によって導かれるが、局所場を持つランダムなフラストレーション2次元スピングラスのハードインスタンスの割合を著しく減少させることができることを実証する。
具体的には、アルゴリズムによる量子相転移のクラスを作成することによって、ハード・ツー・サムルインスタンスの割合を25%以上削減することで、ソリューションの多様性を最大40%向上させることができることを観察する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。