論文の概要: The matrix permanent and determinant from a spin system
- arxiv url: http://arxiv.org/abs/2307.04681v1
- Date: Mon, 10 Jul 2023 16:34:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 12:22:37.424900
- Title: The matrix permanent and determinant from a spin system
- Title(参考訳): スピン系からの行列と行列式
- Authors: Abhijeet Alase, Owen Doty, and David L. Feder
- Abstract要約: M$ の行列式に対するガウス=ジョーダンは、フェルミオン $breveM$ の一般化ゼロ固有空間の連続的な除去と同値である。
我々の分析は、永久体の古典的および量子的評価のための新しい戦略への道を示すかもしれない。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In contrast to the determinant, no algorithm is known for the exact
determination of the permanent of a square matrix that runs in time polynomial
in its dimension. Consequently, non interacting fermions are classically
efficiently simulatable while non-interacting bosons are not, underpinning
quantum supremacy arguments for sampling the output distribution of photon
interferometer arrays. This work introduces a graph-theoretic framework that
bridges both the determinant and permanent. The only non-zero eigenvalues of a
sparse non-Hermitian operator $\breve{M}$ for $n$ spin-$1/2$ particles are the
$n$th roots of the permanent or determinant of an $n\times n$ matrix $M$,
interpreting basis states as bosonic or fermionic occupation states,
respectively. This operator can be used to design a simple and straightforward
method for the classical determination of the permanent that matches the
efficiency of the best-known algorithm. Gauss-Jordan elimination for the
determinant of $M$ is then equivalent to the successive removal of the
generalized zero eigenspace of the fermionic $\breve{M}$, equivalent to the
deletion of some nodes and reweighting of the remaining edges in the graph such
that only $n$ nodes survive after the last step. In the bosonic case, the
successive removal of generalized zero eigenspaces for $\breve{M}$ is also
equivalent to node deletion, but new edges are added during this process, which
gives rise to the higher complexity of computing the permanent. Our analysis
may point the way to new strategies for classical and quantum evaluation of the
permanent.
- Abstract(参考訳): 行列式とは対照的に、その次元の時間多項式で走る正方行列の永久性を正確に決定するアルゴリズムは知られていない。
したがって、相互作用しないフェルミオンは古典的に効率よくシミュレートできるが、相互作用しないボソンはそうでないため、光子干渉計アレイの出力分布をサンプリングするための量子超越性引数が導かれる。
この研究は、決定性と永続性の両方を橋渡しするグラフ理論フレームワークを導入している。
スパースな非エルミート作用素の非零固有値 $\breve{m}$ for $n$ spin-$1/2$ particle は、n\times n$ matrix $m$ の永久または決定式の $n$th 根であり、基底状態がボソニックまたはフェルミオンの占有状態として解釈される。
この演算子は、最もよく知られたアルゴリズムの効率と一致する永続性を決定するための単純で簡単な方法の設計に使うことができる。
M$ の行列式に対するガウス=ジョーダンの除去は、フェルミオン $\breve{M}$ の一般化ゼロ固有空間の連続的な除去と等価であり、いくつかのノードの削除とグラフ内の残りのエッジの再重み付けと等価であり、最後のステップ後に残るのは$n$ノードのみである。
ボソニックの場合、$\breve{m}$ に対する一般化されたゼロ固有空間の連続的な除去は、ノードの削除と同値であるが、このプロセス中に新しいエッジが追加され、永続的な計算の複雑さが高まる。
我々の分析は、永続性の古典的および量子的評価のための新しい戦略への道を開くかもしれない。
関連論文リスト
- Quantum Eigensolver for General Matrices [5.811990276393904]
本稿では,一般行列に対する固有値問題の解法に適した新しい量子アルゴリズム群を提案する。
我々のアルゴリズムはマルコフ連鎖の緩和時間の推定を含む様々な領域の応用を見出す。
これらの応用は、様々な分野にわたる問題に対する量子固有解法の重要性を浮き彫りにしている。
論文 参考訳(メタデータ) (2024-01-22T16:29:08Z) - A Quantum Algorithm for Solving the Advection Equation using Hamiltonian
Simulation [0.0]
スパースハミルトニアンシミュレーションに基づく対流方程式を解く量子アルゴリズムを提案する。
有限差分離散化と明示的なオイラー時間積分から生じる行列は、時間内に解を進めるためにハミルトニアン内に埋め込まれる。
ユニタリ作用素はハミルトンの進化時間に関係なく行列を高い精度で埋め込むので、時間ステップは従来のオイラー法と同じ順序の確率と誤差で成功する。
論文 参考訳(メタデータ) (2023-12-15T13:39:27Z) - 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) - Purity decay rate in random circuits with different configurations of
gates [0.0]
我々は、様々なジオメトリの作用の下で、純度減衰(二部体の絡み合いの尺度)を$n$の連鎖で研究する。
ほとんどの回路において、純度は2つの段階においてその値に減衰する: 初期の熱力学的に関係した崩壊は$sim lambda_mathrmeffeff$であり、$lambda_mathrmeff$は必ずしも転移行列のスペクトルにあるとは限らない。
論文 参考訳(メタデータ) (2022-11-24T12:32:07Z) - Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson
Brownian Motion [28.431572772564518]
対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。
私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
論文 参考訳(メタデータ) (2022-11-11T18:54:01Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳(メタデータ) (2021-05-03T16:36:27Z) - Exceptional points and domains of unitarity for a class of strongly
non-Hermitian real-matrix Hamiltonians [0.0]
閉じた(すなわちユニタリな)量子系のハミルトニアンは、$N$ by $N$ 実行列形式を持つと仮定される。
系のユニタリティが失われる量子位相遷移境界$partial cal D[N]$について述べる。
論文 参考訳(メタデータ) (2021-04-22T12:27:09Z) - 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) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。