論文の概要: Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis
- arxiv url: http://arxiv.org/abs/2209.14286v1
- Date: Wed, 28 Sep 2022 17:53:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 19:26:47.284481
- Title: Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis
- Title（参考訳）: トポロジカルデータ解析のための量子アルゴリズムの複雑性理論的限界
- Authors: Alexander Schmidhuber, Seth Lloyd
- Abstract要約: 位相データ解析のための量子アルゴリズムは、ほぼ全ての入力に対して指数時間で実行されることを示す。
ベッチ数を正確に計算する問題は#P-hardであり、ベッチ数を乗算誤差まで近似する問題はNP-hardであることを示す。
- 参考スコア（独自算出の注目度）: 83.68543987898734
- 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
argue that quantum algorithms for TDA run in exponential time for almost all
inputs by showing that (under widely believed complexity-theoretic conjectures)
the central problem 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. We verify our claim by showing that the
seminal quantum algorithm for TDA developed by Lloyd, Garnerone and Zanardi
\cite{LloydAlgo} achieves a quadratic speedup over the best classical approach
on average, and a power-of-four speedup in the best case. Finally, we argue
that an exponential quantum advantage can be recovered if the data is given as
a specification of simplices rather than as a list of vertices and edges -- for
example, if we wish to calculate the homology of Facebook from a list of
Facebook groups and their members rather than from a list of pairwise
interactions between Facebook users.
- Abstract（参考訳）: トポロジカルデータ解析(TDA)のための量子アルゴリズムは、復調処理やデータローディング問題に免疫を保ちながら、古典的手法よりも指数関数的に有利である。
本稿では,tdaの量子アルゴリズムが(広く信じられている複雑性理論的な予想の下では)ほぼ全ての入力に対して指数関数時間で実行されることを議論する。
具体的には、ベッチ数を正確に計算する問題は \#p-hardであるが、ベッチ数を乗算誤差まで近似する問題はnp-hardである。
さらに、どちらの問題も、TDAの量子アルゴリズムが最善である体制に制限された場合、その困難さを保っている。
量子コンピュータは、サブ指数時間で \#p-hard や np-hard の問題を解くことが期待できないため、tda の量子アルゴリズムは多項式のアドバンテージしか与えないことを示す。
lloyd, garnerone, zanardi \cite{lloydalgo} が開発した tda の独創的な量子アルゴリズムが,平均で最高の古典的アプローチよりも2倍のスピードアップを達成し,最善のケースでは4倍のスピードアップを実現していることを示すことで,我々の主張を検証する。
最後に、データを頂点とエッジのリストとしてではなく、単純化の仕様として指定した場合、指数関数的な量子優位性は、例えば、Facebookユーザ間のペアインタラクションのリストからではなく、FacebookグループとそのメンバーのリストからFacebookのホモロジーを計算したい場合、回復できる、と論じる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。