論文の概要: Globally optimizing QAOA circuit depth for constrained optimization
problems
- arxiv url: http://arxiv.org/abs/2108.03281v1
- Date: Fri, 6 Aug 2021 19:25:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-19 04:56:48.809178
- Title: Globally optimizing QAOA circuit depth for constrained optimization
problems
- Title(参考訳): 制約最適化問題に対するQAOA回路深さのグローバル最適化
- Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw,
Travis S. Humble, George Siopsis
- Abstract要約: 我々は、最適化問題における$n$-variable monomialsを、より少ない変数におけるmonomialsを持つ等価なインスタンスに還元するグローバル変数置換法を開発した。
量子近似最適化アルゴリズムを用いて、削減された問題を解くために必要な最適量子回路深さを解析する。
- 参考スコア(独自算出の注目度): 0.2609784101826761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop a global variable substitution method that reduces $n$-variable
monomials in combinatorial optimization problems to equivalent instances with
monomials in fewer variables. We apply this technique to $3$-SAT and analyze
the optimal quantum circuit depth needed to solve the reduced problem using the
quantum approximate optimization algorithm. For benchmark $3$-SAT problems, we
find that the upper bound of the circuit depth is smaller when the problem is
formulated as a product and uses the substitution method to decompose gates
than when the problem is written in the linear formulation, which requires no
decomposition.
- Abstract(参考訳): 我々は、組合せ最適化問題におけるn$-variable monomialsを、より少ない変数のmonomialsを持つ等価インスタンスに還元する大域変数置換法を開発した。
この手法を$3$-SAT に適用し,量子近似最適化アルゴリズムを用いて低減した問題を解くために必要な最適量子回路深さを解析する。
ベンチマーク3ドルのsat問題では、問題を積として定式化した場合、回路の深さの上限が小さいことが分かり、分解を必要としない線形定式化で問題を記述する場合よりも、置換法を用いてゲートを分解する。
関連論文リスト
- Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing [10.049166866086738]
ポートフォリオ最適化と制約付きの問題の再バランスは、しばしば難解か、正確に解くのが困難である。
我々のパイプラインは、実世界のポートフォリオ最適化問題を、約80%の削減でサブプロブレムに一貫して分解する。
大きな問題をいくつかの小さなサブプロブレムに分解することで、パイプラインは短期量子デバイスをソルバとして使用することができる。
論文 参考訳(メタデータ) (2024-09-16T14:05:52Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Optimizing Variational Circuits for Higher-Order Binary Optimization [2.578242050187029]
本稿では,ハミルトニアンを2量子ゲートのみを含む実装可能な回路に符号化する新しい手法を提案する。
本手法は,回路深度の観点から明らかな利得を示すとともに,技術状況と比較することで評価する。
論文 参考訳(メタデータ) (2023-07-31T15:27:06Z) - Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover
Problem [4.697039614904225]
量子交互演算子 ansatz (QAOA+) を用いて最小被覆(MEC)問題を解く。
数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。
また、1量子ビット回転ゲートを$R_Z$で除去することで量子回路を最適化する。
論文 参考訳(メタデータ) (2022-11-28T12:45:52Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳(メタデータ) (2020-10-01T18:14:11Z) - Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm [0.3058685580689604]
回路深度に対する下位境界の同定に問題インスタンスの構造を用いる方法を示す。
我々は、MaxCut、MaxIndSet、およびVertex CoveringおよびBoolean satisifiabilityのいくつかのケースがQAOAアプローチに適していると主張している。
論文 参考訳(メタデータ) (2020-08-04T20:52:34Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳(メタデータ) (2020-07-14T09:50:33Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。