論文の概要: QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines
- arxiv url: http://arxiv.org/abs/2205.11762v1
- Date: Tue, 24 May 2022 03:49:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-11 22:18:29.280253
- Title: QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines
- Title（参考訳）: QAOA-in-QAOA:小型量子マシンにおける大規模MaxCut問題の解法
- Authors: Zeqiao Zhou, Yuxuan Du, Xinmei Tian, Dacheng Tao
- Abstract要約: 量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
- 参考スコア（独自算出の注目度）: 81.4597482536073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The design of fast algorithms for combinatorial optimization greatly
contributes to a plethora of domains such as logistics, finance, and chemistry.
Quantum approximate optimization algorithms (QAOAs), which utilize the power of
quantum machines and inherit the spirit of adiabatic evolution, are novel
approaches to tackle combinatorial problems with potential runtime speedups.
However, hurdled by the limited quantum resources nowadays, QAOAs are
infeasible to manipulate large-scale problems. To address this issue, here we
revisit the MaxCut problem via the divide-and-conquer heuristic: seek the
solutions of subgraphs in parallel and then merge these solutions to obtain the
global solution. Due to the $\mathbb{Z}_2$ symmetry in MaxCut, we prove that
the merging process can be further cast into a new MaxCut problem and thus be
addressed by QAOAs or other MaxCut solvers. With this regard, we propose
QAOA-in-QAOA ($\text{QAOA}^2$) to solve arbitrary large-scale MaxCut problems
using small quantum machines. We also prove that the approximation ratio of
$\text{QAOA}^2$ is lower bounded by 1/2. Experiment results illustrate that
under different graph settings, $\text{QAOA}^2$ attains a competitive or even
better performance over the best known classical algorithms when the node count
is around 2000. Our method can be seamlessly embedded into other advanced
strategies to enhance the capability of QAOAs in large-scale combinatorial
optimization problems.
- Abstract（参考訳）: 組合せ最適化のための高速アルゴリズムの設計は、ロジスティクス、ファイナンス、化学といった多くの領域に大きく貢献する。
量子機械のパワーを活用し、断熱進化の精神を継承する量子近似最適化アルゴリズム(qaoas)は、潜在的なランタイムスピードアップで組合せ問題に取り組むための新しいアプローチである。
しかし、今日では量子資源が限られているため、QAOAは大規模な問題を操作できない。
この問題に対処するために、ここでは分断と探索のヒューリスティックを通じてmaxcut問題を再検討する: 部分グラフの解を並列に求め、それらの解をマージして大域解を得る。
MaxCut の $\mathbb{Z}_2$ 対称性により、マージ過程が新たな MaxCut 問題にさらにキャストされ、QAOAs や他の MaxCut ソルバによって対処できることが証明される。
そこで我々は、小さな量子マシンを用いて任意の大規模MaxCut問題を解くために、QAOA-in-QAOA ($\text{QAOA}^2$)を提案する。
また、$\text{QAOA}^2$ の近似比が 1/2 以下であることが証明される。
実験の結果、異なるグラフ設定下では、$\text{QAOA}^2$は、ノード数が2000前後のとき、最もよく知られた古典的アルゴリズムよりも、競争力や性能が向上することを示した。
本手法は,大規模な組合せ最適化問題において,QAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
関連論文リスト
- Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。
The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。
最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文 参考訳（メタデータ） (2024-06-25T09:02:31Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - QAOA with fewer qubits: a coupling framework to solve larger-scale
Max-Cut problem [6.783232060611114]
より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。
古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。
われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
論文 参考訳（メタデータ） (2023-07-28T02:06:42Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
グラフ最大カット問題(MaxCut)の課題に対処するため,Divide-and-Conquer QAOA(DC-QAOA)を提案する。
DC-QAOAは97.14%の近似比(20.32%)を達成する
また、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
論文 参考訳（メタデータ） (2021-02-26T03:10:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。