論文の概要: 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}$ に対する一般化されたゼロ固有空間の連続的な除去は、ノードの削除と同値であるが、このプロセス中に新しいエッジが追加され、永続的な計算の複雑さが高まる。
我々の分析は、永続性の古典的および量子的評価のための新しい戦略への道を開くかもしれない。
関連論文リスト
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - 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) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Rank-one matrix estimation: analytic time evolution of gradient descent
dynamics [16.067228939231047]
我々は、付加雑音によって劣化したランク1対称行列を考える。
推定器と未知ベクトルの重なり合いの時間的進化の明示的な公式とコストは厳密に導出される。
論文 参考訳（メタデータ） (2021-05-25T23:31:08Z) - 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 [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。