論文の概要: Decomposing dense matrices into dense Pauli tensors
- arxiv url: http://arxiv.org/abs/2401.16378v2
- Date: Tue, 30 Jan 2024 13:12:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 11:38:02.757921
- Title: Decomposing dense matrices into dense Pauli tensors
- Title(参考訳): 密度行列を密度パウリテンソルに分解する
- Authors: Tyson Jones
- Abstract要約: O(2N) 時間で 2N-by-2N 複素行列と N-term Pauli テンソルの間の内積を計算する固定メモリ分岐式アルゴリズムを導出する。
提案手法は,行列を O(8N) 時間で重み付けしたパウリ弦の和に,恥ずかしく平行な分解を許容する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decomposing a matrix into a weighted sum of Pauli strings is a common chore
of the quantum computer scientist, whom is not easily discouraged by
exponential scaling. But beware, a naive decomposition can be cubically more
expensive than necessary! In this manuscript, we derive a fixed-memory,
branchless algorithm to compute the inner product between a 2^N-by-2^N complex
matrix and an N-term Pauli tensor in O(2^N) time, by leveraging the Gray code.
Our scheme permits the embarrassingly parallel decomposition of a matrix into a
weighted sum of Pauli strings in O(8^N) time. We implement our algorithm in
Python, hosted open-source on Github, and benchmark against a recent
state-of-the-art method called the "PauliComposer" which has an exponentially
growing memory overhead, achieving speedups in the range of 1.5x to 5x for N <
8. Note that our scheme does not leverage sparsity, diagonality, Hermitivity or
other properties of the input matrix which might otherwise enable optimised
treatment in other methods. As such, our algorithm is well-suited to
decomposition of dense, arbitrary, complex matrices which are expected dense in
the Pauli basis, or for which the decomposed Pauli tensors are a priori
unknown.
- Abstract(参考訳): 行列を重み付けされたパウリ弦の和に分解することは、指数的スケーリングによって容易には妨げられない量子コンピュータ科学者の共通の振舞いである。
しかし、注意してください、ナイーブ分解は必要以上に立方的に高価です!
本稿では,2^N-by-2^N複素行列とO(2^N)時間におけるN末端パウリテンソルの間の内積をグレイ符号を利用して計算する固定メモリ分岐アルゴリズムを導出する。
提案手法は, 行列を O(8^N) 時間で重み付けしたパウリ弦の和に変換することを許す。
我々はPythonでアルゴリズムを実装し、Githubでオープンソースでホストし、最近の最先端のメソッドである"PauliComposer"をベンチマークし、メモリオーバーヘッドが指数関数的に増加し、N < 8で1.5倍から5倍のスピードアップを実現した。
我々のスキームは、他の方法で最適化された処理が可能であるかもしれない入力行列のスパーシリティ、対角性、ハーミティティ、その他の性質を利用しない。
したがって、このアルゴリズムは、パウリ基底において密度の高い任意の複素行列の分解や、分解されたパウリテンソルが未定の先駆体であるような分解に適している。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳(メタデータ) (2023-11-07T22:52:56Z) - Construction of a Circuit for the Simulation of a Hamiltonian with a
Tridiagonal Matrix Representation [0.0]
三角行列表現を持つハミルトニアンのシミュレーションのための回路の構成を提案する。
結果として生じるゲートの複雑さを見積もることで効率を主張する。
論文 参考訳(メタデータ) (2023-09-29T20:27:05Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。
フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。
密度行列の力学をシミュレートする量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-14T23:08:51Z) - Fast Partitioning of Pauli Strings into Commuting Families for Optimal
Expectation Value Measurements of Dense Operators [0.0]
作用素の分解に現れるパウリ弦は、可換な族にグループ化することができる。
任意のキュービットに作用するパウリ弦の完全集合を、可換族全体の最小集合に完全に分割するアルゴリズムを詳述する。
論文 参考訳(メタデータ) (2023-05-19T17:39:33Z) - PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently [0.0]
パウリ行列のテンソル積を効率的に計算する簡単なアルゴリズムを導入する。
これは計算をこの特定のケースに合わせることで行われ、不要な計算を避けることができる。
副産物として、量子シミュレーションにおける1つの重要な計算に対して最適化された方法、すなわち、ハミルトニアンのパウリ基底分解を提供する。
論文 参考訳(メタデータ) (2023-01-02T08:48:47Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。
我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文 参考訳(メタデータ) (2022-05-09T01:49:21Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳(メタデータ) (2022-01-29T10:00:35Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳(メタデータ) (2022-01-21T12:18:06Z) - Quantum algorithms for spectral sums [79.28094304325116]
対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。