論文の概要: Quantum computational complexity of matrix functions

• arxiv url: http://arxiv.org/abs/2410.13937v1
• Date: Thu, 17 Oct 2024 18:00:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:24:21.615300
• Title: Quantum computational complexity of matrix functions
• Title（参考訳）: 行列関数の量子計算複雑性
• Authors: Santiago Cifuentes, Samson Wang, Thais L. Silva, Mario Berta, Leandro Aolita,
• Abstract要約: 2つの原始問題の計算複雑性について検討する。 単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
• 参考スコア（独自算出の注目度）: 2.7488316163114823
• License:
• Abstract: We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function $f$ and a Hermitian matrix $A$, compute a matrix element of $f(A)$ or compute a local measurement on $f(A)|0\rangle^{\otimes n}$, with $|0\rangle^{\otimes n}$ an $n$-qubit reference state vector, in both cases up to additive approximation error. We consider four functions -- monomials, Chebyshev polynomials, the time evolution function, and the inverse function -- and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm, sparsity), the approximation error, and function-specific parameters. We identify BQP-complete forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-hard, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree $\mathrm{poly}(n)$ both problems can be efficiently classically simulated when $A$ has $O(\log n)$ non-zero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP-complete in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity $O(\log n)$. Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.
• Abstract（参考訳）: 行列関数の性質を推定する際,古典的計算量と量子的計算量との分断線について検討する。 より正確には、関数 $f$ と Hermitian 行列 $A$ が与えられたとき、$f(A)$ の行列要素を計算するか、または$f(A)|0\rangle^{\otimes n}$ の局所的な測定を$|0\rangle^{\otimes n}$ で計算する。 単項関数、チェビシェフ多項式、時間発展関数、逆関数の4つの関数を考察し、異なる問題入力状態をカバーする広い景観にわたって複雑さを探索する。 すなわち,2種類の行列入力(スパースアクセスとパウリアクセス),行列特性(ノルム,スパーシティ),近似誤差,関数固有パラメータを考える。 各関数の両問題のBQP完全形式を特定し、問題のパラメータを調整して、難易度がどこにあるか、問題は古典的に容易になるかを確認する。 古典的に効率のよいモノミアルのアルゴリズムを持つパラメータ体系では、他の3つの関数はすべて、BQP-ハードあるいは通常の計算複雑性の仮定の下で頑健に残る。 古典的に簡単なレジームを同定する際、例えば次数$\mathrm{poly}(n)$の任意の多項式に対して、両者の問題は、パウリ基底において$A$が$O(\log n)$非ゼロ係数を持つときに、効率的に古典的にシミュレートできることを示す。 これは、一定の行間隔であってもスパースアクセスモデルにおいて問題はBQP完全であるのに対し、パウリアクセスは行間隔$O(\log n)$でスパースアクセスを効率的に構築するという事実とは対照的である。 我々の研究は、基本的な線形代数問題に対する効率的な量子アルゴリズムと古典アルゴリズムのカタログを提供する。

関連論文リスト

• 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)
• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。 本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。 我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
  論文  参考訳（メタデータ） (2024-08-11T10:28:49Z)
• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。 ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。 有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
  論文  参考訳（メタデータ） (2024-06-06T11:33:29Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。 提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
  論文  参考訳（メタデータ） (2023-06-20T18:01:07Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
  本稿では,行列方程式の解法に関わる問題について検討する。 Harrow/Hassidim/Lloydアルゴリズムを固有位相推定のための代替ユニタリを提供することにより一般化する。 このユニタリは任意の行列方程式に対して十分に定義されているという利点があり、それによって解の手順を量子ハードウェアに直接実装することができる。
  論文  参考訳（メタデータ） (2021-12-05T15:42:32Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
  論文  参考訳（メタデータ） (2020-08-14T12:17:48Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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