論文の概要: Exponential Separation Criteria for Quantum Iterative Power Algorithms

• arxiv url: http://arxiv.org/abs/2502.05506v1
• Date: Sat, 08 Feb 2025 09:53:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:29:58.263218
• Title: Exponential Separation Criteria for Quantum Iterative Power Algorithms
• Title（参考訳）: 量子イテレーティブパワーアルゴリズムの指数分離基準
• Authors: András Czégel, Boglárka G. -Tóth,
• Abstract要約: その結果,QIPAとvarQITEの指数的分離は実現不可能であることが判明した。 理論的な結果にもかかわらず、実際に関係のある拡張がまだ可能であることも示している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In the vast field of Quantum Optimization, Quantum Iterative Power Algorithms (QIPA) has been introduced recently with a promise of exponential speedup over an already established and well-known method, the variational Quantum Imaginary Time Evolution (varQITE) algorithm. Since the convergence and error of varQITE are known, the promise of QIPA also implied certain collapses in the complexity hierarchy - such as NP $\subseteq$ BQP, as we show in our study. However the original article of QIPA explicitly states the algorithm does not cause any collapses. In this study we prove that these collapses indeed do not occur, and with that, prove that the promised exponential separation is practically unachievable. We do so by introducing criteria for the exponential separation between QIPA that uses a double exponential function and varQITE, and then showing how these criteria require certain properties in problem instances. After that we introduce a preprocessing step that enforces problems to satisfy these criteria, and then we show that the algorithmic error blows up exponentially for these instances, as there is an inverse polynomial term between speedup and the error. Despite the theoretical results, we also show that practically relevant polynomial enhancement is still possible, and show experimental results on a small problem instance, where we used our preprocessing step to achieve the improvement.
• Abstract（参考訳）: 量子最適化の分野では、量子イテレーティブ・パワー・アルゴリズム (QIPA) が最近導入され、すでに確立された、よく知られた方法である変分量子イマジナリー・タイム・エボリューション (varQITE) アルゴリズムよりも指数的なスピードアップを約束している。 varQITE の収束と誤差が知られているので、QIPA の約束はまた、NP $\subseteq$ BQP のような複雑性階層におけるある種の崩壊を示唆している。 しかし、QIPAのオリジナルの記事は、アルゴリズムがいかなる崩壊も起こさないことを明言している。 本研究では、これらの崩壊が実際に起こらないことを証明し、それとともに、約束される指数的分離が事実上達成不可能であることを証明した。 二重指数関数とvarQITEを用いるQIPAの指数分離の基準を導入し、これらの基準が問題インスタンスにおいてどのように特定の性質を必要とするかを示す。 その後、これらの基準を満たすために問題を強制する前処理ステップを導入し、その後、スピードアップとエラーの間に逆多項式項が存在するため、アルゴリズムエラーが指数関数的に爆発することを示す。 理論的な結果にもかかわらず、実際に関係のある多項式拡張がまだ可能であることを示し、その改善を達成するために前処理のステップを用いた小さな問題インスタンスで実験結果を示す。

関連論文リスト

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Hamiltonian variational ansatz without barren plateaus [0.0]
  変分量子アルゴリズムは、短期量子コンピュータの最も有望な応用の1つである。 その大きな可能性にもかかわらず、数十量子ビットを超える変分量子アルゴリズムの有用性は疑問視されている。
  論文  参考訳（メタデータ） (2023-02-16T19:01:26Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations [0.0]
  本稿では,量子特異値変換の枠組みにおいて,$alpha$-QPEのスケーリングが自然かつ簡潔に導出可能であることを示す。 符号関数の近似が良くなるほど、符号を正確に決定する必要があるサンプルは少なくなる。
  論文  参考訳（メタデータ） (2022-07-29T17:57:03Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Mitigating algorithmic errors in quantum optimization through energy extrapolation [4.426846282723645]
  基底状態エネルギーの推定において、非無視誤差を緩和するスケーラブルな外挿法を提案する。 我々は,IBM量子コンピュータ上での数値シミュレーションと実験により,これらの手法の有効性を検証した。
  論文  参考訳（メタデータ） (2021-09-16T17:39:11Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
  論文  参考訳（メタデータ） (2021-08-05T18:56:17Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)

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

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