論文の概要: Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

• arxiv url: http://arxiv.org/abs/2209.14286v2
• Date: Sat, 6 Jan 2024 17:51:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-10 00:50:52.108640
• Title: Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
• Title（参考訳）: トポロジカルデータ解析のための量子アルゴリズムの複雑性理論的限界
• Authors: Alexander Schmidhuber, Seth Lloyd
• Abstract要約: トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
• 参考スコア（独自算出の注目度）: 59.545114016224254
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this paper, we give complexity-theoretic evidence that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best. Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case. We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone and Zanardi achieves a quadratic speedup over the best known classical approach in asymptotically almost all cases. Finally, we argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.
• Abstract（参考訳）: トポロジカルデータ解析(TDA)のための量子アルゴリズムは、復調処理やデータローディング問題に免疫を保ちながら、古典的手法よりも指数関数的に有利である。 本稿では, 量子コンピュータにおいても, TDA の中心課題であるベッチ数の推定が困難であることを示す。 具体的には、ベッチ数を正確に計算する問題は#Pハードであり、ベッチ数を乗算誤差まで近似する問題はNPハードである。 さらに、どちらの問題も、TDAの量子アルゴリズムが最善である体制に制限された場合、その困難さを保っている。 量子コンピュータは#p-hardやnp-hardの問題をサブ指数時間で解くことが期待できないため、tdaの量子アルゴリズムは最悪の場合には多項式のアドバンテージしか与えないことを示す。 ロイド、ガーネロン、ザナーディが開発したtdaの独創的な量子アルゴリズムは、漸近的にほぼすべてのケースにおいて、最も知られた古典的アプローチよりも二次的なスピードアップを達成していることを示すことによって、我々の主張を支持する。 最後に、入力データが頂点と辺のリストとしてではなく、単純化の仕様として与えられる場合、指数的量子優位性を取り戻すことができると論じる。

関連論文リスト

• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [5.478764356647437]
  永続ベッチ数を計算するための改良された量子アルゴリズムを提案する。 量子アルゴリズムが実用的なタスクの指数的高速化を達成できるかどうかを論じる。
  論文  参考訳（メタデータ） (2022-09-26T17:56:11Z)
• Topological data analysis on noisy quantum computers [11.975008559320875]
  トポロジカルデータ解析(TDA)は,高次元データの複雑で価値の高い形状関連要約を抽出する強力な手法である。 TDA計算のための古典的アルゴリズムの計算要求は極端であり、高次特性に対してはすぐに非現実的になる。 本稿では,高次元古典データに適用可能なエンドツーエンド量子機械学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-19T22:45:00Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
  論文  参考訳（メタデータ） (2021-08-05T18:56:17Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)

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

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