論文の概要: Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
- arxiv url: http://arxiv.org/abs/2401.16619v3
- Date: Mon, 25 Nov 2024 14:51:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 14:15:05.839821
- Title: 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)を計算するための量子アルゴリズムを提案する。
基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
- 参考スコア（独自算出の注目度）: 43.53835128052666
- License:
- Abstract: We propose quantum algorithms for calculating the determinant and inverse of an $(N-1)\times (N-1)$ matrix (depth is $O(N^2\log N)$) which is a simple modification of the algorithm for calculating the determinant of an $N\times N$ matrix (depth is $O(N\log^2 N)$. The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. Combination of this algorithm with the quantum algorithm for matrix multiplication, proposed in our previous work, yields the algorithm for solving systems of linear algebraic equations (depth is $O(N\log^2 N)$. Measurement of the ancilla state with output 1 (probability is $\sim 2^{-O(N\log N)}$) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation $O(N\log N)$ for the size.
- Abstract（参考訳）: 我々は、$(N-1)\times (N-1)$ matrix (deepth is $O(N^2\log N)$)の行列式と逆式を計算するための量子アルゴリズムを提案し、これは、$N\times N$ matrix (deepth is $O(N\log^2 N)$)の行列式を計算するアルゴリズムの簡単な修正である。
基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
さらに、代数的補数の観点から逆行列の元の表現を用いる。
このアルゴリズムと行列乗法のための量子アルゴリズムを組み合わせることで、線形代数方程式の系を解くアルゴリズムが得られる(深さは$O(N\log^2 N)$)。
出力1によるアシラ状態の測定(確率は$\sim 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。