論文の概要: Quantum approximate algorithm for NP optimization problems with constraints

• arxiv url: http://arxiv.org/abs/2002.00943v1
• Date: Sat, 1 Feb 2020 04:45:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 00:18:32.640758
• Title: Quantum approximate algorithm for NP optimization problems with constraints
• Title（参考訳）: 制約付きnp最適化問題に対する量子近似アルゴリズム
• Authors: Yue Ruan, Samuel Marsh, Xilin Xue, Xi Li, Zhihao Liu, and Jingbo Wang
• Abstract要約: 本稿では,異なる制約型を等式,線形不等式,任意の形式に定式化する。 そこで本研究では,NP最適化問題の解法としてQAOAフレームワークに適合する制約符号化方式を提案する。 提案手法の有効性と有効性を示す。
• 参考スコア（独自算出の注目度）: 12.294570891467604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (quantum approximation optimization algorithm,qaoa) は、組合せ最適化問題の近似解を求めるアルゴリズムフレームワークであり、量子断熱アルゴリズム (quantum adiabatic algorithm,qaa) への近似から導かれる。 QAOA や QAA の文脈における制約を伴う組合せ最適化問題の解決には、問題の制約をスキームにエンコードする方法を見つける必要がある。 本稿では,異なる制約型を線形等式,線形不等式,任意の形式に形式化する。 そこで本研究では,NP組合せ最適化問題の解法としてQAOAフレームワークに適合する制約符号化方式を提案する。 実装されたアルゴリズムは、よく知られたNP最適化問題の様々な事例のテスト結果により提案手法の有効性と効率を示す。 我々の研究は、QAOAの文脈において、様々な種類の制約を伴う組合せ問題に対する高品質な近似解を見つけるための一般化された枠組みにつながると論じる。

関連論文リスト

• Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations [0.0]
  本稿では,QAOAの有効性を向上させるための簡単なアプローチであるTwo-Step QAOAを提案する。 問題を2段階に分けて,ソフト制約をハード制約に変換する。
  論文  参考訳（メタデータ） (2024-08-09T23:38:28Z)
• A two-phase-ACO algorithm for solving nonlinear optimization problems subjected to fuzzy relational equations [0.0]
  本稿では,制約をファジィリレーショナル方程式(FRE)と定義した非線形最適化問題について検討する。 アルゴリズム問題に対処するアリコロニー最適化アルゴリズム(ACORで記述)と連続アリコロニー最適化アルゴリズム(ACOで記述)の連続最適化問題の解法について論じる。
  論文  参考訳（メタデータ） (2024-05-17T09:24:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。 我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。 本研究は,本手法の有効性と応用の可能性を示すものである。
  論文  参考訳（メタデータ） (2022-03-29T05:44:07Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。 提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。 タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
  論文  参考訳（メタデータ） (2021-06-24T16:39:31Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。 学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。 また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
  論文  参考訳（メタデータ） (2021-05-14T11:31:14Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。