Fugu-MT 論文翻訳(概要): The role of quantum and classical correlations in shrinking algorithms for optimization

論文の概要: The role of quantum and classical correlations in shrinking algorithms for optimization

arxiv url: http://arxiv.org/abs/2404.17242v1
Date: Fri, 26 Apr 2024 08:29:04 GMT
ステータス: 処理完了
システム内更新日: 2024-04-29 13:44:15.334431
Title: The role of quantum and classical correlations in shrinking algorithms for optimization
Title（参考訳）: 最適化のための縮小アルゴリズムにおける量子および古典的相関の役割
Authors: Victor Fischer, Maximilian Passek, Friedrich Wagner, Jernej Rudi Finžgar, Lilly Palackal, Christian B. Mendl,
Abstract要約: 最適化問題(COP)における縮小アルゴリズムの性能について検討する。量子近似最適化アルゴリズム (QAOA) と古典線形計画法 (LP) と半定値計画法 (SDP) の相関によるアルゴリズムの性能の比較を行った。その結果、LPは低密度のインスタンスに対して他の全てのアプローチよりも優れており、SDPは高密度の問題に対して優れていた。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The benefit of quantum computing for solving combinatorial optimization problems (COPs) constitutes an open research question. In this work, we study the performance of a shrinking algorithm for COPs. The algorithm leverages correlations extracted from quantum or classical subroutines to recursively simplify the problem. We compare the performance of the algorithm equipped with correlations from the quantum approximate optimization algorithm (QAOA) as well as the classical linear programming (LP) and semi-definite programming (SDP) relaxations. This allows us to benchmark the utility of QAOA correlations against established classical relaxation algorithms. We apply the recursive algorithm to MaxCut problem instances with up to a hundred vertices at different graph densities. Our results indicate that LP outperforms all other approaches for low-density instances, while SDP excels for high-density problems. Moreover, the shrinking algorithm proves to be a viable alternative to established methods of rounding LP and SDP relaxations. In addition, the recursive shrinking algorithm outperforms its bare counterparts for all three types of correlations, i.e., LP with spanning tree rounding, the Goemans-Williamson algorithm, and conventional QAOA. While the lowest depth QAOA consistently yields worse results than the SDP, our tensor network experiments show that the performance increases significantly for deeper QAOA circuits.
Abstract（参考訳）: 組合せ最適化問題(COP)を解決するための量子コンピューティングの利点は、オープンな研究課題である。本研究では,COPのための縮小アルゴリズムの性能について検討する。このアルゴリズムは、量子または古典的なサブルーチンから抽出された相関を利用して問題を再帰的に単純化する。量子近似最適化アルゴリズム (QAOA) と古典線形計画法 (LP) と半定値計画法 (SDP) の相関によるアルゴリズムの性能の比較を行った。これにより、確立された古典的緩和アルゴリズムに対するQAOA相関の有用性をベンチマークすることができる。グラフ密度の異なる最大100個の頂点を持つMaxCut問題インスタンスに対して再帰的アルゴリズムを適用する。その結果、LPは低密度のインスタンスに対して他の全てのアプローチよりも優れており、SDPは高密度の問題に対して優れていた。さらに、縮小アルゴリズムは、LPおよびSDP緩和の確立された方法の代替となることが証明された。さらに、再帰的縮小アルゴリズムは3種類の相関関係、すなわち木の丸みを分散したLP、ゴーマンス・ウィリアムソンアルゴリズム、および従来のQAOAにおいて、その素数よりも優れる。低深さQAOAはSDPよりも常に悪い結果をもたらすが、このテンソルネットワーク実験により、より深いQAOA回路では性能が著しく向上することが示された。

関連論文リスト

Performance of Parity QAOA for the Signed Max-Cut Problem [0.0]
パリティアーキテクチャにおける量子近似アルゴリズムの最適化性能(パリティQAOA)について検討する。固定回路深さでのアルゴリズムの比較により、Parity QAOAはSWAPネットワークに基づく従来のQAOA実装よりも優れていることを示す。
論文参考訳（メタデータ） (2024-09-23T08:00:03Z)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
論文参考訳（メタデータ） (2023-07-11T22:02:01Z)
COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文参考訳（メタデータ） (2021-07-27T08:48:01Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative [0.0]
最適化のための3つの量子アルゴリズムの性能スケーリングについて検討する。 MFB-CIM、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズム
論文参考訳（メタデータ） (2021-05-07T22:35:02Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文参考訳（メタデータ） (2020-05-05T08:34:58Z)
Algorithms for Tensor Network Contraction Ordering [0.0]
十分に設計された収縮シーケンスは、収縮コストを劇的に削減することができる。この順序付け問題に対して、2つの一般的な離散最適化手法をベンチマークする。検討するアルゴリズムは、同等の計算資源を与えられた欲求探索を一貫して上回っていることがわかった。
論文参考訳（メタデータ） (2020-01-15T19:00:07Z)

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

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