論文の概要: Positive bias makes tensor-network contraction tractable

• arxiv url: http://arxiv.org/abs/2410.05414v1
• Date: Mon, 7 Oct 2024 18:27:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-01 18:57:16.226548
• Title: Positive bias makes tensor-network contraction tractable
• Title（参考訳）: 正のバイアスがテンソル-ネットワーク収縮を誘引する
• Authors: Jiaqing Jiang, Jielun Chen, Norbert Schuch, Dominik Hangleiter,
• Abstract要約: テンソルネットワークの収縮は、量子多体物理学、量子情報、量子化学において強力な計算ツールである。 ここでは、テンソル-ネットワークの収縮の複雑さが、量子性、すなわちそのエントリの符号構造の違いにどのように依存するかを研究する。
• 参考スコア（独自算出の注目度）: 0.5437298646956507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d>~n, a small positive mean value >~1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #P-hard, like for the zero-mean case [HHEG20]. The mean value 1/d matches the phase transition point observed in [CJHS24]. Our proof makes use of Barvinok's method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least StoqMA-hard. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is BPP-Complete. This result compares to Arad and Landau's [AL10] result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is BQP-Complete.
• Abstract（参考訳）: テンソルネットワークの収縮は、量子多体物理学、量子情報、量子化学における強力な計算ツールである。 テンソルネットワークの収縮の複雑さは、主にその絡み合いの性質に依存していると考えられており、これは二部分断のシュミット階数によって反映される。 ここでは、テンソル-ネットワークの収縮の複雑さが、量子性、すなわちそのエントリの符号構造の違いにどのように依存するかを研究する。 本稿では, 成分が正のバイアスを持つテンソルネットワークの複雑性を調べることによって, この問題に厳密に対処する。 中間結合次元 d>~n に対して、テンソル成分の小さな正平均値 >~1/d は、およそ収縮するランダムテンソルネットワークの計算複雑性を劇的に減少させ、任意の 1/poly(n) 乗算近似に対する準多項式時間アルゴリズムを可能にすることを示す。 同時に、そのようなテンソルネットワークを正確に収縮させることは、ゼロ平均の場合 [HHEG20] のように#Pハードのままである。 平均値1/dは[CJHS24]で観測された相転移点と一致する。 バルビノクの近似カウント法と統計力学モデルにランダムインスタンスをマッピングする手法を応用した。 さらに、全てのエントリが非負である正のテンソルネットワークの近似収縮の最悪の複雑さを考える。 まず、誤差が指数関数的に1に近い乗法近似が少なくともStoqMA-hardであることを示す簡単な証明を与える。 次に、行列 1-ノルムにおける加法的誤差を考えると、正のテンソルネットワークの収縮は BPP-Complete であることを示す。 この結果は、Arad と Landau の [AL10] の結果と比較し、一般的なテンソルネットワークでは、行列 2-ノルム加法誤差までの近似収縮は BQP-Complete であることを示す。

関連論文リスト

• Sign problem in tensor network contraction [0.5437298646956507]
  テンソルネットワークの収縮の難しさはテンソルエントリの符号構造に依存するかを検討する。 難易度から易度への遷移は、成分が主に正になるときに起こる。 また、テンソルネットワーク波動関数の予測値の計算困難さについても検討する。
  論文  参考訳（メタデータ） (2024-04-29T18:06:38Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• One-step replica symmetry breaking in the language of tensor networks [0.913755431537592]
  我々は1段階のレプリカ対称性破断空洞法とテンソルネットワークの正確なマッピングを開発する。 この2つのスキームは補足的な数学的および数値的なツールボックスを備えており、芸術のそれぞれの状態を改善するために利用することができる。
  論文  参考訳（メタデータ） (2023-06-26T18:42:51Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  我々は, テンソル全体の精度保証を行う。 結果は数値実験により検証され、高次テンソルに対するクロス近似の有用性に重要な意味を持つ可能性がある。
  論文  参考訳（メタデータ） (2022-07-09T19:33:59Z)
• Stack operation of tensor networks [10.86105335102537]
  本稿では,テンソルネットワークスタックアプローチに対する数学的に厳密な定義を提案する。 本稿では、行列製品状態に基づく機械学習を例として、主なアイデアを例に挙げる。
  論文  参考訳（メタデータ） (2022-03-28T12:45:13Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。 検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
  論文  参考訳（メタデータ） (2021-12-23T04:05:01Z)
• Spectral Complexity-scaled Generalization Bound of Complex-valued Neural Networks [78.64167379726163]
  本論文は,複素数値ニューラルネットワークの一般化を証明した最初の論文である。 複雑な値の畳み込みニューラルネットワークを異なるデータセット上でトレーニングして実験を行う。
  論文  参考訳（メタデータ） (2021-12-07T03:25:25Z)
• Quantum Annealing Algorithms for Boolean Tensor Networks [0.0]
  ブールテンソルネットワークのための3つの一般アルゴリズムを導入・解析する。 量子アニーラー上での解法に適した2次非制約二元最適化問題として表すことができる。 我々は、DWave 2000Q量子アニールを用いて、最大数百万個の要素を持つテンソルを効率的に分解できることを実証した。
  論文  参考訳（メタデータ） (2021-07-28T22:38:18Z)
• MTC: Multiresolution Tensor Completion from Partial and Coarse Observations [49.931849672492305]
  既存の完備化の定式化は、主に1つのテンソルからの部分的な観測に依存する。 この問題を解決するために,効率的なマルチレゾリューション・コンプリート・モデル(MTC)を提案する。
  論文  参考訳（メタデータ） (2021-06-14T02:20:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。