論文の概要: Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems

• arxiv url: http://arxiv.org/abs/2401.16619v4
• Date: Sun, 15 Dec 2024 08:28:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:50:04.327979
• Title: Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Title（参考訳）: 行列の行列式と逆数の計算と線形代数系の解法のための純粋量子アルゴリズム
• Authors: Alexander I. Zenchuk, Georgii A. Bochkin, Wentao Qi, Asutosh Kumar, Junde Wu,
• Abstract要約: そこで我々は,行列式と逆行列の計算に$(N-1)倍 (N-1)$行列を求める量子アルゴリズムを提案する。 このアプローチは、N×N$行列の行列式を決定するための既存のアルゴリズムの簡単な修正である。 3つのアルゴリズムすべてに対して適切な回路設計を提供し、それぞれが空間的に$O(N log N)$と見積もられている。
• 参考スコア（独自算出の注目度）: 43.53835128052666
• License:
• Abstract: We propose quantum algorithms that are fundamentally quantum in nature for the computation of the determinant and inverse of an $(N-1) \times (N-1)$ matrix, with a computational depth of $O(N^2 \log N)$. This approach is a straightforward modification of the existing algorithm for determining the determinant of an $N \times N$ matrix, which operates with a depth of $O(N \log^2 N)$. The core concept involves encoding each row of the matrix into a pure state of a quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm, in conjunction with the matrix multiplication algorithm discussed in the appendix, facilitates solving systems of linear algebraic equations with a depth of $O(N \log^2 N)$. The measurement of the ancilla state yielding an output of 1 occurs with a probability of approximately $2^{-O(N \log N)}$, and eliminates the extraneous data generated during the computation. We provide suitable circuit designs for all three algorithms, each estimated to require $O(N \log N)$ in terms of space, specifically the number of qubits utilized in the circuit.
• Abstract（参考訳）: 計算深度が$O(N^2 \log N)$である$(N-1) \times (N-1)$行列の行列と逆行列の計算に対して、本質的に量子的な量子アルゴリズムを提案する。 このアプローチは、深さが$O(N \log^2 N)$で作用する$N \times N$Matrixの行列式を決定するための既存のアルゴリズムの簡単な修正である。 中心となる概念は、行列の各行を量子系の純粋な状態に符号化することである。 さらに、代数的補数の観点から逆行列の元の表現を用いる。 このアルゴリズムは、付録で議論された行列乗法アルゴリズムとともに、深さが$O(N \log^2N)$の線形代数方程式系の解法を容易にする。 1の出力をもたらすアシラ状態の測定は、約2^{-O(N \log N)}$の確率で起こり、計算中に生成された外部データを除去する。 我々は3つのアルゴリズムすべてに対して適切な回路設計を提供し、それぞれが空間の点で$O(N \log N)$と推定される。

関連論文リスト

• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。 このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。 また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
  論文  参考訳（メタデータ） (2023-11-07T22:52:56Z)
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
  本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。 量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
  論文  参考訳（メタデータ） (2023-02-03T17:22:49Z)
• Efficient quantum algorithms for solving quantum linear system problems [0.0]
  拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。 どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
  論文  参考訳（メタデータ） (2022-08-14T02:49:26Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。 これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
  論文  参考訳（メタデータ） (2022-02-10T08:12:20Z)
• Quantum Algorithm for Matrix Logarithm by Integral Formula [0.0]
  近年,行列ベクトル積 $f(A)b$ に対応する状態 $|frangle$ を計算する量子アルゴリズムが提案されている。 サブルーチンとしてLCU法とブロック符号化技術を用いる量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-17T05:46:12Z)
• 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)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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