論文の概要: Quantum algorithm for the gradient of a logarithm-determinant

• arxiv url: http://arxiv.org/abs/2501.09413v1
• Date: Thu, 16 Jan 2025 09:39:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-17 15:09:00.425874
• Title: Quantum algorithm for the gradient of a logarithm-determinant
• Title（参考訳）: 対数行列式の勾配に対する量子アルゴリズム
• Authors: Thomas E. Baker, Jaimie Greasley,
• Abstract要約: スパースランク入力演算子の逆を効率的に決定することができる。 入力演算子のすべての$N2$要素の代わりに、量子状態の期待値を測定することは、$O(ksigma)$ timeで実現できる。 このアルゴリズムは、完全に誤り訂正された量子コンピュータ向けに構想されているが、短期的なマシンで実装可能である。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The logarithm-determinant is a common quantity in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k\sigma)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix. A factor $\sigma=\frac1{\varepsilon^3}$ or $-\frac1{\varepsilon^2}\log_2\varepsilon$ depends on the version of the quantum Fourier transform used for a precision $\varepsilon$. Practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O(k\sigma\log_2 N)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. For non-sparse-rank inputs, the algorithm can be evaluated provided that an equal superposition of eigenstates is provided. The output is given in $O(1)$ queries of oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.
• Abstract（参考訳）: 対数行列式は物理学や計算機科学の多くの分野において一般的な量である。 対数行列式の導出物は、統計物理学モデル、量子場理論、行列の逆数などにおいて物理的に関係のある量を計算する。 ここでは、対数行列式の導関数を評価するために、量子勾配アルゴリズムの多変数バージョンを開発した。 これにより、スパースランク入力演算子の逆を効率的に決定することができる。 入力作用素のすべての$N^2$要素の代わりに、量子状態の期待値を測定することは、入力行列の$k$関連固有ベクトルの理想化された場合、$O(k\sigma)$時間で達成できる。 因子 $\sigma =frac1{\varepsilon^3}$ または $-\frac1{\varepsilon^2}\log_2\varepsilon$ は精度 $\varepsilon$ に使用される量子フーリエ変換のバージョンに依存する。 必要な演算子の実装には$\log_2N$オーバーヘッドが必要になり、全体的な複雑さは$O(k\sigma\log_2N)$である。 この方法は広く適用され、条件数が高ければ$k$で超直線的に収束する。 非スパースランク入力に対しては、固有状態の均等な重ね合わせが提供されるので、アルゴリズムを評価することができる。 出力はオラクルの$O(1)$クエリで与えられ、これは明示的にここで与えられ、任意に小さなエラーで実装できる時間進化演算子にのみ依存する。 このアルゴリズムは、完全に誤り訂正された量子コンピュータ向けに構想されているが、短期的なマシンで実装可能である。 このアルゴリズムがカーネルベースの量子機械学習にどのように使えるかについて議論する。

関連論文リスト

• Entanglement-Assisted Coding for Arbitrary Linear Computations Over a Quantum MAC [34.32444379837011]
  量子多重アクセスチャネル(LC-QMAC)上の線形計算問題について検討する。 本稿では、安定化器形式と絡み合い支援量子誤り訂正符号(EAQECC)のアイデアに基づくLC-QMACの達成可能なスキームを提案する。
  論文  参考訳（メタデータ） (2025-01-27T18:35:33Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  そこで我々は,行列式と逆行列の計算に$(N-1)倍 (N-1)$行列を求める量子アルゴリズムを提案する。 このアプローチは、N×N$行列の行列式を決定するための既存のアルゴリズムの簡単な修正である。 3つのアルゴリズムすべてに対して適切な回路設計を提供し、それぞれが空間的に$O(N log N)$と見積もられている。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• A quantum algorithm for computing the Carmichael function [0.0]
  量子コンピュータは、多くの数理論問題を効率的に解くことができる。 本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-03T19:30:27Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator [0.0]
  我々は、特定の基底に対して$mathcal O(mathrm N2logmathrm N)$演算のみを含む効率的なアルゴリズムを提案する。 このアルゴリズムは$mathcal O(mathrm N3)$演算よりも少ないため、大きな$mathrm N$の場合、量子コンピューティングアルゴリズムの事前処理ステップとして使用できる。
  論文  参考訳（メタデータ） (2020-11-17T20:57:39Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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