論文の概要: 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完全問題に対する近似アルゴリズムの設計において非常に有用なツールであることを示している。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Performance of Parity QAOA for the Signed Max-Cut Problem [0.0]
  パリティアーキテクチャにおける量子近似アルゴリズムの最適化性能(パリティQAOA)について検討する。 固定回路深さでのアルゴリズムの比較により、Parity QAOAはSWAPネットワークに基づく従来のQAOA実装よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-09-23T08:00:03Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
  量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。 我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。 提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
  論文  参考訳（メタデータ） (2024-03-27T18:17:23Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• 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)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

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

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