論文の概要: Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm
- arxiv url: http://arxiv.org/abs/2008.01820v2
- Date: Wed, 12 Aug 2020 15:47:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-07 04:14:36.995216
- Title: Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムの回路深さの下位境界
- Authors: James Ostrowski, Rebekah Herrman, Travis S. Humble and George Siopsis
- Abstract要約: 回路深度に対する下位境界の同定に問題インスタンスの構造を用いる方法を示す。
我々は、MaxCut、MaxIndSet、およびVertex CoveringおよびBoolean satisifiabilityのいくつかのケースがQAOAアプローチに適していると主張している。
- 参考スコア（独自算出の注目度）: 0.3058685580689604
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a method of
approximately solving combinatorial optimization problems. While QAOA is
developed to solve a broad class of combinatorial optimization problems, it is
not clear which classes of problems are best suited for it. One factor in
demonstrating quantum advantage is the relationship between a problem instance
and the circuit depth required to implement the QAOA method. As errors in NISQ
devices increases exponentially with circuit depth, identifying lower bounds on
circuit depth can provide insights into when quantum advantage could be
feasible. Here, we identify how the structure of problem instances can be used
to identify lower bounds for circuit depth for each iteration of QAOA and
examine the relationship between problem structure and the circuit depth for a
variety of combinatorial optimization problems including MaxCut and MaxIndSet.
Specifically, we show how to derive a graph, $G$, that describes a general
combinatorial optimization problem and show that the depth of circuit is at
least the chromatic index of $G$. By looking at the scaling of circuit depth,
we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and
Boolean satisifiability problems are suitable for QAOA approaches while
Knapsack and Traveling Sales Person problems are not.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化問題を解く方法である。
qaoaは、組合せ最適化の幅広いクラスを解決するために開発されているが、どのクラスがそれに適しているかは明らかではない。
量子優位性を示す1つの要因は、QAOA法を実装するのに必要な問題インスタンスと回路深さの関係である。
NISQ装置の誤差が回路深さとともに指数関数的に増加するにつれて、回路深さの低い境界を識別することで、量子的優位性が実現可能なときの洞察が得られる。
そこで本研究では,QAOAの各イテレーションにおける回路深さの下位境界の同定に問題インスタンスの構造を用いて,MaxCutやMaxIndSetなどの組合せ最適化問題に対する問題構造と回路深さの関係について検討する。
具体的には、一般組合せ最適化問題を記述するグラフである$g$を導出する方法を示し、回路の深さが少なくとも$g$の彩色指数であることを示す。
回路深さのスケーリングをみると、MaxCut、MaxIndSet、およびいくつかのVertex CoveringおよびBoolean satisifiability問題はQAOAアプローチに適しているが、KnapsackとTraking Sales Personの問題はそうではない。
関連論文リスト
- MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。
良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。
ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文 参考訳（メタデータ） (2024-09-27T12:28:18Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
制約付き最適化問題を解くためのフェルミオン量子近似最適化アルゴリズム(FQAOA)を提案する。
FQAOAは、フェルミオン粒子数保存を用いて、QAOAを通して本質的にそれらを強制する制約問題に対処する。
制約付きハミルトニアン問題に対して、運転者ハミルトニアンを設計するための体系的なガイドラインを提供する。
論文 参考訳（メタデータ） (2023-01-25T18:36:58Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文 参考訳（メタデータ） (2022-06-14T17:37:44Z) - 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) - Quantum Dropout: On and Over the Hardness of Quantum Approximate
Optimization Algorithm [4.546053983380784]
コスト関数の代わりにQAOA量子回路から難易度を導出する。
数値解析の結果,QAOAの性能は様々な種類の量子ドロップアウト実装で向上した。
論文 参考訳（メタデータ） (2022-03-18T18:00:01Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。