論文の概要: Training variational quantum algorithms is NP-hard

• arxiv url: http://arxiv.org/abs/2101.07267v2
• Date: Thu, 14 Apr 2022 09:16:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-14 21:10:51.321521
• Title: Training variational quantum algorithms is NP-hard
• Title（参考訳）: 変分量子アルゴリズムの訓練はNPハードである
• Authors: Lennart Bittel and Martin Kliesch
• Abstract要約: 古典最適化の問題はNPハードであることが示される。 対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
• 参考スコア（独自算出の注目度）: 0.7614628596146599
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum ap- proximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parameterized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming P $\neq$ NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima. This means that gradient and higher order descent algorithms will generally converge to far from optimal solutions.
• Abstract（参考訳）: 変動量子アルゴリズムは、近未来の量子デバイスにおける関連する計算問題を解くために提案される。 一般的なバージョンは変分量子固有ソルバと量子ap-近位最適化アルゴリズムであり、それぞれ量子化学とバイナリ最適化の問題から基底状態問題を解決する。 それらは古典的なコンピュータを使ってパラメータ化量子回路を訓練するという考え方に基づいている。 古典最適化問題はNPハードであることを示す。 さらに、この硬さは多項式時間アルゴリズムごとに、古典的な最適化問題から生じる相対誤差が P $\neq$ NP を仮定して任意に大きいインスタンスが存在するという意味で頑健である。 対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。 このことは、古典的な最適化が本質的に困難であり、基底状態問題から単に硬さを継承しないことを意味する。 我々の分析では、トレーニングランドスケープは最適な局所最小値から遠ざかる可能性がある。 これは、勾配および高次降下アルゴリズムが一般に最適解から遠く離れることを意味する。

関連論文リスト

• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  対角ハミルトニアンの基底状態解を見つけることは、金融、物理学、計算機科学など多くの分野に関心を持つ理論的および実践的な問題の両方に関係している。 ここでは、新しいブロック符号化方式を用いて、これらの問題の基底状態を取得し、この手法をMaxCutに例証として応用する。
  論文  参考訳（メタデータ） (2024-11-16T08:17:36Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。 我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-24T22:06:05Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
  論文  参考訳（メタデータ） (2023-01-17T16:03:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。 効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
  論文  参考訳（メタデータ） (2021-05-27T13:03:52Z)
• Optimization of the Variational Quantum Eigensolver for Quantum Chemistry Applications [0.0]
  変分量子固有解法アルゴリズムは、量子力学系の基底状態を決定するように設計されている。 本研究では,変分量子固有解法において,必要な量子ビット操作数を減らし,誤りを誘発しがちな方法について検討する。
  論文  参考訳（メタデータ） (2021-02-02T22:20:12Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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