論文の概要: S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for
unstructured sparse matrices
- arxiv url: http://arxiv.org/abs/2401.04234v1
- Date: Mon, 8 Jan 2024 20:57:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 18:20:44.269520
- Title: S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for
unstructured sparse matrices
- Title（参考訳）: S-FABLEとLS-FABLE:非構造スパース行列に対する高速近似ブロック符号化アルゴリズム
- Authors: Parker Kuklinski, Benjamin Rempfer
- Abstract要約: Fast Approximate BLock-Lazyアルゴリズム(FABLE)は、任意の$Ntimes N$高密度行列を量子回路にブロックエンコードする手法である。
スパース行列を効率的に符号化するFABLEの2つの修正について述べる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Fast Approximate BLock-Encoding algorithm (FABLE) is a technique to
block-encode arbitrary $N\times N$ dense matrices into quantum circuits using
at most $O(N^2)$ one and two-qubit gates and $\mathcal{O}(N^2\log{N})$
classical operations. The method nontrivially transforms a matrix $A$ into a
collection of angles to be implemented in a sequence of $y$-rotation gates
within the block-encoding circuit. If an angle falls below a threshold value,
its corresponding rotation gate may be eliminated without significantly
impacting the accuracy of the encoding. Ideally many of these rotation gates
may be eliminated at little cost to the accuracy of the block-encoding such
that quantum resources are minimized. In this paper we describe two
modifications of FABLE to efficiently encode sparse matrices; in the first
method termed Sparse-FABLE (S-FABLE), for a generic unstructured sparse matrix
$A$ we use FABLE to block encode the Hadamard-conjugated matrix $H^{\otimes
n}AH^{\otimes n}$ (computed with $\mathcal{O}(N^2\log N)$ classical operations)
and conjugate the resulting circuit with $n$ extra Hadamard gates on each side
to reclaim a block-approximation to $A$. We demonstrate that the FABLE circuits
corresponding to block-encoding $H^{\otimes n}AH^{\otimes n}$ significantly
compress and that overall scaling is empirically favorable (i.e. using S-FABLE
to block-encode a sparse matrix with $\mathcal{O}(N)$ nonzero entries requires
approximately $\mathcal{O}(N)$ rotation gates and $\mathcal{O}(N\log N)$ CNOT
gates). In the second method called `Lazy' Sparse-FABLE (LS-FABLE), we
eliminate the quadratic classical overhead altogether by directly implementing
scaled entries of the sparse matrix $A$ in the rotation gates of the S-FABLE
oracle. This leads to a slightly less accurate block-encoding than S-FABLE,
while still demonstrating favorable scaling to FABLE similar to that found in
S-FABLE.
- Abstract（参考訳）: Fast Approximate BLock-Encoding algorithm (FABLE) は、任意の$N\times N$高密度行列を最大$O(N^2)$1と2キュービットゲートと$\mathcal{O}(N^2\log{N})$古典演算を用いて量子回路にブロックエンコードする手法である。
この方法は、行列$A$をブロック符号化回路内の$y$回転ゲートのシーケンスで実装される角度の集合に非自明に変換する。
角度がしきい値以下であれば、その対応する回転ゲートを符号化の精度に悪影響を及ぼすことなく除去することができる。
理想的には、これらの回転ゲートの多くは、量子リソースが最小化されるようなブロックエンコーディングの精度のために、少ないコストで排除できる。
本稿では, スパース行列を効率的にエンコードするFABLEの2つの修正について述べる; 最初の方法 Sparse-FABLE (S-FABLE) において, 一般的な非構造スパース行列に対して$A$ を用いて, アンダマール共役行列 $H^{\otimes n}AH^{\otimes n}$ ($\mathcal{O}(N^2\log N)$ 古典演算で計算) をエンコードし, 結果として回路をそれぞれの側で$n$ 余分なアダマールゲートで共役し, ブロック近似を$A$に戻す。
ブロックエンコードする $h^{\otimes n}ah^{\otimes n}$ に対応するfable回路は著しく圧縮され、全体的なスケーリングは経験的に有利である(すなわち、$\mathcal{o}(n)$ のスパース行列をブロックエンコードするのに s-fable を使うことは、約 $\mathcal{o}(n)$ 回転ゲートと $\mathcal{o}(n\log n)$ cnot ゲートが必要である)。
lazy' sparse-fable (ls-fable) と呼ばれる第二のメソッドでは、s-fable oracle の回転ゲートに sparse matrix $a$ のスケールされたエントリを直接実装することで、二次古典的オーバーヘッドを完全に排除する。
これにより、S-FABLEよりも少し精度の低いブロックエンコーディングが実現される一方で、S-FABLEと同様のスケールがFABLEに向いている。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
本稿では,量子ゲート生成の符号化問題について述べる。
emphReference Input Generation Algorithm (RIGA) はこの研究で一般化されている。
論文 参考訳（メタデータ） (2024-09-02T10:41:15Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Block encoding of matrix product operators [0.0]
本稿では,その行列積演算子(MPO)表現に基づいてハミルトニアンをブロックエンコードする手法を提案する。
より具体的には、すべてのMPOテンソルを次元$D+2$でエンコードし、$D = lceillog(chi)rceil$ は、仮想結合次元と対数的にスケールする後に縮約された量子ビットの数である。
論文 参考訳（メタデータ） (2023-12-14T12:34:24Z) - Improved Synthesis of Toffoli-Hadamard Circuits [1.7205106391379026]
Kliuchnikovが2013年にClifford+$T$回路に対して導入した手法はトフォリ・ハダード回路に容易に適用可能であることを示す。
また、同様のコスト改善の代替合成法を提案するが、その応用は3キュービット未満の回路に限られる。
論文 参考訳（メタデータ） (2023-05-18T21:02:20Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳（メタデータ） (2020-09-08T05:39:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。