論文の概要: Improving Quantum Optimization to Achieve Quadratic Time Complexity

• arxiv url: http://arxiv.org/abs/2501.13469v1
• Date: Thu, 23 Jan 2025 08:33:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-24 15:57:56.055401
• Title: Improving Quantum Optimization to Achieve Quadratic Time Complexity
• Title（参考訳）: 量子最適化の改良による2次時間複雑性の実現
• Authors: Ji Jiang, Peisheng Huang, Zhiyi Wu, Xuandong Sun, Zechen Guo, Wenhui Huang, Libo Zhang, Yuxuan Zhou, Jiawei Zhang, Weijie Guo, Xiayu Linpeng, Song Liu, Wenhui Ren, Ziyu Tao, Ji Chu, Jingjing Niu, Youpeng Zhong, Dapeng Yu,
• Abstract要約: 我々はPenta-Oを導入する。Penta-Oは、古典的な外ループを排除し、サンプリングオーバーヘッドを最小限に抑え、非遅延性能を確保する。 p$レベルのQAOAの場合、 Penta-O は $mathcalO(p2)$ という前例のない時間の複雑さを達成し、サンプリングオーバーヘッドは 5p+1$ に比例する。
• 参考スコア（独自算出の注目度）: 13.190476985206043
• License:
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage in combinatorial optimization. However, its variational framework presents a long-standing challenge in selecting circuit parameters. In this work, we prove that the energy expectation produced by QAOA can be expressed as a trigonometric function of the final-level mixer parameter. Leveraging this insight, we introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance. This method is broadly applicable to the generic quadratic unconstrained binary optimization formulated as the Ising model. For a $p$-level QAOA, Penta-O achieves an unprecedented quadratic time complexity of $\mathcal{O}(p^2)$ and a sampling overhead proportional to $5p+1$. Through experiments and simulations, we demonstrate that QAOA enhanced by Penta-O achieves near-optimal performance with exceptional circuit depth efficiency. Our work provides a versatile tool for advancing variational quantum algorithms.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、組合せ最適化において量子優位性を達成するための有望な候補である。 しかし,回路パラメータの選択には長期にわたる課題がある。 本研究では,QAOAが生成するエネルギー期待値が,最終レベルのミキサーパラメータの三角関数として表現できることを証明する。 この知見を生かしたPenta-Oは、古典的な外ループを排除し、サンプリングオーバーヘッドを最小限に抑え、非遅延性能を確保するための、レベルワイドなパラメータセット戦略である。 この方法は、Isingモデルとして定式化された2次非制約バイナリ最適化に広く適用できる。 p$レベルのQAOAの場合、Penta-Oは$\mathcal{O}(p^2)$という前例のない二次時間複雑性を達成し、サンプリングオーバーヘッドは5p+1$に比例する。 実験とシミュレーションにより、Penta-Oにより強化されたQAOAが、例外的な回路深さ効率でほぼ最適性能を達成することを示した。 我々の研究は、変分量子アルゴリズムを進化させるための多用途ツールを提供する。

関連論文リスト

• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Efficient and Robust Parameter Optimization of the Unitary Coupled-Cluster Ansatz [4.607081302947026]
  本稿では、量子コンピュータ上でのユニタリ結合クラスタ・アンサッツのパラメータ最適化のために、近似パラボラ(SOAP)を用いた逐次最適化を提案する。 分子システムに関する数値的なベンチマークでは、SOAPはより高速な収束とノイズに対する堅牢性を達成することが示されている。 SOAPは、2量子ビットモデルシステムを用いた超伝導量子コンピュータの実験によりさらに検証される。
  論文  参考訳（メタデータ） (2024-01-10T03:30:39Z)
• Quantum approximate optimization via learning-based adaptive optimization [5.399532145408153]
  量子近似最適化アルゴリズム(QAOA)は、目的最適化問題の解法として設計されている。 その結果,アルゴリズムは速度,精度,効率,安定性の点で従来の近似よりも大幅に優れていた。 この研究はQAOAの全パワーを解き放つのに役立ち、実践的な古典的なタスクにおいて量子的優位性を達成するための道を開く。
  論文  参考訳（メタデータ） (2023-03-27T02:14:56Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。 我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
  論文  参考訳（メタデータ） (2021-08-11T15:44:16Z)
• Mixer-Phaser Ans\"atze for Quantum Optimization with Hard Constraints [1.011960004698409]
  パラメタライズド・サーキット・アンス・アットーを導入し,その性能を標準的な量子交互演算子・アンザッツ法と比較した数値実験の結果を示す。 アンスアッツはQAOAの混合と相分離にインスパイアされ、また高温超伝導量子プロセッサ上での動作を目的としたコンパイルの考慮によって動機付けられる。
  論文  参考訳（メタデータ） (2021-07-13T04:50:56Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)
• Accelerating Quantum Approximate Optimization Algorithm using Machine Learning [6.735657356113614]
  本稿では,量子近似最適化アルゴリズム(QAOA)の実装を高速化する機械学習手法を提案する。 QAOAは、いわゆる量子超越性を証明する量子古典ハイブリッドアルゴリズムである。 提案手法は,264種類のグラフを用いて行った解析から,最適化の繰り返し回数を最大65.7%削減できることを示す。
  論文  参考訳（メタデータ） (2020-02-04T02:21:00Z)

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

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