論文の概要: Quantum Computational Phase Transition in Combinatorial Problems
- arxiv url: http://arxiv.org/abs/2109.13346v4
- Date: Wed, 15 Jun 2022 12:49:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-13 11:33:58.788459
- Title: Quantum Computational Phase Transition in Combinatorial Problems
- Title（参考訳）: 組合せ問題における量子計算相転移
- Authors: Bingzhi Zhang, Akira Sone and Quntao Zhuang
- Abstract要約: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子コンピュータにおける離散最適化問題の近似解を求めることを目的としたアルゴリズムである。
SATのような難解な問題を解く際に,QAOAの計算位相遷移を同定する。
本稿では,QAOAの性能に限界がある高問題密度領域が,実際はQAOAを利用するのに最適であることを示す。
- 参考スコア（独自算出の注目度）: 0.966840768820136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum Approximate Optimization algorithm (QAOA) aims to search for
approximate solutions to discrete optimization problems with near-term quantum
computers. As there are no algorithmic guarantee possible for QAOA to
outperform classical computers, without a proof that $BQP\neq NP$, it is
necessary to investigate the empirical advantages of QAOA. We identify a
computational phase transition of QAOA when solving hard problems such as SAT
-- random instances are most difficult to train at a critical problem density.
We connect the transition to the controllability and the complexity of QAOA
circuits. Moreover, we find that the critical problem density in general
deviates from the SAT-UNSAT phase transition, where the hardest instances for
classical algorithm lies. Then, we show that the high problem density region,
which limits QAOA's performance in hard optimization problems ({\it
reachability deficits}), is actually a good place to utilize QAOA: its
approximation ratio has a much slower decay with the problem density, compared
to classical approximate algorithms. Indeed, it is exactly in this region that
quantum advantages of QAOA over classical approximate algorithms can be
identified.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(quantum approximation optimization algorithm,qaoa)は、短期量子コンピュータにおける離散最適化問題の近似解を探索することを目的としている。
QAOAが古典的コンピュータより優れているという保証はないため、$BQP\neq NP$の証明がなければ、QAOAの実証的な利点を調べる必要がある。
satのような難しい問題を解決する場合、qaoaの計算位相遷移を識別する -- ランダムインスタンスは重要な問題密度でトレーニングするのが最も困難である。
制御性への遷移とQAOA回路の複雑さを結合する。
さらに、古典的アルゴリズムの最も難しい例があるSAT-UNSAT相転移から一般の臨界問題密度が逸脱していることが分かる。
そこで本研究では,QAOAのハード最適化問題における性能を制限する高次問題密度領域を,従来の近似アルゴリズムと比較すると,近似比が問題密度と非常に遅いため,実際にQAOAを利用するのに適した場所であることを示す。
実際、古典的近似アルゴリズムよりもQAOAの量子的優位性を特定できるのはまさにこの領域である。
関連論文リスト
- Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Mean-Field Approximate Optimization Algorithm [0.17812428873698405]
平均場近似最適化アルゴリズム(平均場AOA)は、QAOAの量子進化を古典的なスピン力学に置き換えることで開発された。
我々は,シェリントン・カークパトリック(SK)モデルにおけるQAOAとパーティション問題を比較検討した。
そこで本アルゴリズムは,古典的に解けない問題から解ける最適化問題を記述するためのツールとして機能する。
論文 参考訳（メタデータ） (2023-03-01T08:47:06Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
ADAPT-QAOA施行時に発生する絡みについて検討した。
この柔軟性を漸進的に制限することにより、初期におけるより多くの絡み合いエントロピーが、後段におけるより速い収束と一致していることが分かる。
論文 参考訳（メタデータ） (2022-05-24T18:00:02Z) - 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) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳（メタデータ） (2021-07-11T10:56:24Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。