論文の概要: Improving the Quantum Approximate Optimization Algorithm with postselection

• arxiv url: http://arxiv.org/abs/2011.05425v1
• Date: Tue, 10 Nov 2020 22:17:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-24 18:45:38.146981
• Title: Improving the Quantum Approximate Optimization Algorithm with postselection
• Title（参考訳）: ポストセレクションによる量子近似最適化アルゴリズムの改良
• Authors: Sami Boulebnane
• Abstract要約: 組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。 理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.
• Abstract（参考訳）: 組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。 本研究では,3次元正則グラフ上のマックスカット問題に適用する量子近似最適化アルゴリズム (qaoa) について,組合せ最適化のためのよく研究された量子アルゴリズムを考える。 我々は,最も単純なアルゴリズム (depth-1 qaoa) によって返される解を,状態準備によって効率的にシミュレートできるポストセレクションの形式を用いて改善するアイデアを検討する。 理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。 大規模問題インスタンスの数値実験(古典的同化可能性を超える)は、我々の境界を補完し支持する。 ローカルアップデートはqaoaだけでなく、あらゆる最適化アルゴリズムにも適用できます。 QAOAの場合、結果として得られる改善は、大きな問題の場合とポストセレクションがない場合の理論的に急激な定量化が可能である。 ポストセレクションとローカルアップデートを組み合わせることで、理論はもはや理解できないが、数値的な証拠から両方の方法による改善が組み合わさることが示唆される。

関連論文リスト

• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy [1.14219428942199]
  繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。 基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
  論文  参考訳（メタデータ） (2022-11-08T02:12:49Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• A Gauss-Newton based Quantum Algorithm for Combinatorial Optimization [0.0]
  最適化問題に対するガウス・ニュートン型量子アルゴリズム(GNQA)を提案するが、最適条件下では、局所的なミニマやプラトーに閉じ込められることなく、最適解の1つに迅速に収束する。 我々のアプローチは、最適解を正確に表すテンソル積状態と、二項変数のすべての組み合わせを含むハミルトニアンに対して適切な関数を用いることによってそれらを緩和する。 そこで,本研究では,GNQAが収束特性と精度の両方において,他の最適化手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-03-25T23:49:31Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Warm-starting quantum optimization [6.832341432995627]
  最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。 これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
  論文  参考訳（メタデータ） (2020-09-21T18:00:09Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。 我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。 アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
  論文  参考訳（メタデータ） (2020-05-20T18:00:01Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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