論文の概要: Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum
Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2105.05698v1
- Date: Wed, 12 May 2021 14:33:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 08:42:01.832368
- Title: Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum
Approximation Algorithms
- Title(参考訳): 量子近似アルゴリズムにおけるレベル-$2$量子ラッサーレ階層の適用
- Authors: Ojas Parekh and Kevin Thompson
- Abstract要約: 我々はQMA完全問題に対する近似アルゴリズムの2$階層を初めて使用し、量子マックスカット(Quantum Max Cut)と呼ぶ。
我々は、この問題に対する最先端の近似係数の質素な改善と、レベル$2$階層が多くの物理的動機付けられた制約を満たすことを示す。
この観測は我々の分析の中心であり、量子ラッサール階層の上位レベルがQMA完全問題に対する近似アルゴリズムの設計において非常に有用なツールであることを示している。
- 参考スコア(独自算出の注目度): 3.553493344868414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Lasserre Hierarchy is a set of semidefinite programs which yield
increasingly tight bounds on optimal solutions to many NP-hard optimization
problems. The hierarchy is parameterized by levels, with a higher level
corresponding to a more accurate relaxation. High level programs have proven to
be invaluable components of approximation algorithms for many NP-hard
optimization problems. There is a natural analogous quantum hierarchy, which is
also parameterized by level and provides a relaxation of many (QMA-hard)
quantum problems of interest. In contrast to the classical case, however, there
is only one approximation algorithm which makes use of higher levels of the
hierarchy. Here we provide the first ever use of the level-$2$ hierarchy in an
approximation algorithm for a particular QMA-complete problem, so-called
Quantum Max Cut. We obtain modest improvements on state-of-the-art
approximation factors for this problem, as well as demonstrate that the
level-$2$ hierarchy satisfies many physically-motivated constraints that the
level-$1$ does not satisfy. Indeed, this observation is at the heart of our
analysis and indicates that higher levels of the quantum Lasserre Hierarchy may
be very useful tools in the design of approximation algorithms for QMA-complete
problems.
- Abstract(参考訳): ラッサール階層(英: Lasserre Hierarchy)は、NP-ハード最適化問題に対する最適解の厳密な境界を求める半定値プログラムの集合である。
階層はレベルによってパラメータ化され、より高いレベルはより正確な緩和に対応する。
高レベルプログラムは多くのnpハード最適化問題に対する近似アルゴリズムの貴重なコンポーネントであることが証明されている。
自然に類似した量子階層が存在し、これはレベルによってパラメータ化され、興味を持つ多くの(QMA-ハード)量子問題を緩和する。
しかし、古典的な場合とは対照的に、階層の上位レベルを利用する近似アルゴリズムは1つしかない。
ここでは、特定のQMA完全問題に対する近似アルゴリズム(いわゆる量子マックスカット)において、レベル2$階層を初めて利用する。
我々は,この問題に対する最先端の近似因子について緩やかに改善するとともに,レベル-$2$階層が,レベル-$$が満たさない多くの物理的動機付け制約を満たすことを実証する。
実際、この観測は我々の分析の中心であり、量子ラッサール階層の上位レベルがQMA完全問題に対する近似アルゴリズムの設計において非常に有用なツールであることを示している。
関連論文リスト
- Stochastic Multi-Level Compositional Optimization Algorithms over
Networks with Level-Independent Convergence Rate [22.988563731766586]
マルチレベル関数を扱うために,2つの新しい分散アルゴリズムを開発した。
両アルゴリズムが非レベル依存問題に対する収束率を達成可能であることを示す。
最良の知識のために、これは、分散された設定の設定の下で、レベル非依存の収束率を達成する最初の研究である。
論文 参考訳(メタデータ) (2023-06-06T00:23:28Z) - Iteration Complexity of Variational Quantum Algorithms [5.684122393859336]
雑音は量子回路のバイアスによる目的関数の評価を行う。
我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
論文 参考訳(メタデータ) (2022-09-21T19:18:41Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳(メタデータ) (2022-03-01T18:20:01Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳(メタデータ) (2021-05-14T11:31:14Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-11-26T18:22:21Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z) - Decomposition algorithms for solving NP-hard problems on a quantum
annealer [0.0]
NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。
Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。
本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
論文 参考訳(メタデータ) (2020-09-10T15:59:06Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳(メタデータ) (2020-06-16T10:49:27Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳(メタデータ) (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。