論文の概要: Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy
- arxiv url: http://arxiv.org/abs/2211.03957v1
- Date: Tue, 8 Nov 2022 02:12:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 23:30:47.156345
- Title: Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy
- Title（参考訳）: 繰り返し改善戦略における量子アニール利用のための整数最適化問題の等式化
- Authors: Shuntaro Okada, Masayuki Ohzeki
- Abstract要約: 繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
- 参考スコア（独自算出の注目度）: 1.14219428942199
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing is a heuristic algorithm for searching the ground state of
an Ising model. Heuristic algorithms aim to obtain near-optimal solutions with
a reasonable computation time. Accordingly, many algorithms have so far been
proposed. In general, the performance of heuristic algorithms strongly depends
on the instance of the combinatorial optimization problem to be solved because
they escape the local minima in different ways. Therefore, combining several
algorithms to exploit their complementary strength is effective for obtaining
highly accurate solutions for a wide range of combinatorial optimization
problems. However, quantum annealing cannot be used to improve a candidate
solution obtained by other algorithms because it starts from an initial state
where all spin configurations are found with a uniform probability. In this
study, we propose an Ising formulation of integer optimization problems to
utilize quantum annealing in the iterative improvement strategy. Our
formulation exploits the biased sampling of degenerated ground states in
transverse magnetic field quantum annealing. We also analytically show that a
first-order phase transition is successfully avoided for a fully connected
ferromagnetic Potts model if the overlap between a ground state and a candidate
solution exceeds a threshold. The proposed formulation is applicable to a wide
range of integer optimization problems and enables us to hybridize quantum
annealing with other optimization algorithms.
- Abstract（参考訳）: 量子アニーリング(Quantum annealing)は、イジングモデルの基底状態を探索するヒューリスティックアルゴリズムである。
ヒューリスティックアルゴリズムは、妥当な計算時間で近似最適解を求める。
そのため、これまでに多くのアルゴリズムが提案されている。
一般に、ヒューリスティックアルゴリズムの性能は、局所的ミニマを異なる方法でエスケープするため、解決すべき組合せ最適化問題のインスタンスに強く依存する。
したがって,複数のアルゴリズムを組み合わせることで,多種多様な組合せ最適化問題に対して高精度な解を得ることができる。
しかし、量子アニールは、全てのスピン配置が均一な確率で見つかる初期状態から始まるため、他のアルゴリズムによって得られる候補解を改善するには使用できない。
本研究では,反復的改善戦略において量子アニーリングを利用する整数最適化問題のイジング定式化を提案する。
我々の定式化は、逆磁場量子アニールにおける劣化した基底状態のバイアスサンプリングを利用する。
また, 基底状態と候補溶液との重なりがしきい値を超える場合, 完全連結強磁性ポッツモデルにおいて, 1次相転移をうまく回避できることを解析的に示した。
提案手法は幅広い整数最適化問題に適用可能であり,量子アニーリングと他の最適化アルゴリズムのハイブリッド化を可能にする。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Quantum walk in a reinforced free-energy landscape: Quantum annealing
with reinforcement [0.0]
強化は、システムの指数的に小さなエネルギーギャップを回避できる戦略の1つである。
本研究では、強化のための構成空間における局所エントロピーを取り上げ、アルゴリズムを多くの容易かつ難しい最適化問題に適用する。
論文 参考訳（メタデータ） (2022-02-22T14:16:27Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳（メタデータ） (2020-11-10T22:17:50Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。