論文の概要: Reachability Deficits in Quantum Approximate Optimization of Graph Problems

• arxiv url: http://arxiv.org/abs/2007.09148v2
• Date: Fri, 27 Aug 2021 11:56:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-09 04:52:02.809955
• Title: Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Title（参考訳）: グラフ問題の量子近似最適化における到達性欠陥
• Authors: V. Akshay and H. Philathong and I. Zacharov and J. Biamonte
• Abstract要約: 問題変数に対する問題制約の即時性は,性能指標として機能することを示す。 Googleが最近行ったQAOAの実験的実現によって、我々は理想的なノイズのない環境で再現されたレポートデータを再分析した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、現代の量子アプリケーション開発の基礎となっている。 ここで、問題制約と問題変数の \emph{density} がパフォーマンス指標として作用することを示す。 密度は、ランダムグラフ最小化問題に適用される固定深さqaoaの近似非効率と強く相関する。 さらに、グラフ問題インスタンスに対する正確なQAOAソリューションに必要な深さは、密度とともに決定的にスケールする。 Googleが最近行ったQAOAの実験的実現に触発されて、理想的なノイズのない環境で再現されたレポートデータの再分析をプリフォームする。 その結果、Googleが実験的に解決したインスタンスの能力は、中間密度を超えた近似品質で急速に低下する領域に近づいた。 本研究は,現代の量子最適化アルゴリズムの性能解析に新たな知見を与え,近年のqaoa性能向上に関する憶測と矛盾する。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
  QAOA anszeのエネルギー景観を様々なグラフでナビゲートするために、流域ホットなグローバルな手法を用いています。 対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
  論文  参考訳（メタデータ） (2024-01-09T19:17:01Z)
• Multiscale Quantum Approximate Optimization Algorithm [0.0]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題の近似解を見つけるために設計された標準アルゴリズムの1つである。 本稿では,QAOAの能力と実空間再正規化群変換を取り入れたQAOAの新バージョンを提案する。
  論文  参考訳（メタデータ） (2023-12-11T07:47:16Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Quantifying the Impact of Precision Errors on Quantum Approximate Optimization Algorithms [0.24629531282150877]
  本稿では,QAOA回路のアナログ実装における誤差が最適化アルゴリズムとしての性能を損なうことを示す。 この大幅な削減にもかかわらず、変動パラメータのデジタル化により、QAOAにおける精度誤差を軽減できることが示されている。
  論文  参考訳（メタデータ） (2021-09-09T18:00:03Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。 QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。 得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
  論文  参考訳（メタデータ） (2021-02-12T23:12:09Z)
• Bridging Classical and Quantum with SDP initialized warm-starts for QAOA [4.76507354067301]
  本稿では,QAOAをグラフ内のすべての可能なカットの偏重重ね合わせで初期化する,古典的な前処理ステップを紹介する。 我々は、QAOA-Warmと呼ばれるこのQAOAの変種が、トレーニング時間が少なく、低い回路深度で標準QAOAより優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-27T02:57:22Z)
• 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)

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

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