論文の概要: Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

• arxiv url: http://arxiv.org/abs/2607.22088v1
• Date: Fri, 24 Jul 2026 08:35:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-27 20:58:57.085155
• Title: Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling
• Title（参考訳）: ボソンサンプリングにおけるランダムガウス行列の弱持続集束
• Abstract要約: ボソンサンプリングは 線形光ネットワークの 出力分布からサンプリングする ランダムガウス永遠の典型的な等級は、ベルヌーイ行列に対するタオとヴのセミナルな結果と同程度であることを示す。 この結果から,超指数的に小さな全変動距離内での古典的なボソンサンプリングが階層構造を崩壊させる可能性が示唆された。
• 参考スコア（独自算出の注目度）: 9.33606630554665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.
• Abstract（参考訳）: 最近の量子計算上の優位性の実証は、主にサンプリング問題によって進められている。 著名なモデルであるボソンサンプリングでは、線形光ネットワークの出力分布からサンプリングを行う。 しかし、古典的な硬さは、ガウスの永遠を近似する平均ケース硬度(英語版)と、永遠の反集中予想(英語版)(PACC)という、2つの可算かつ研究の少ない予想に基づいている。 PACC はランダムガウス行列の分布性に関する純粋に数学的主張である。 離散的ランダム行列の典型的な等級は確立されているが、線形光学ネットワークの遷移振幅を規定する複素ガウスのケースは、未開のままである。 ここでは、ランダムなガウス永遠が標準偏差よりも極端に小さいという確率を上界化することによって、弱い反集束を確立する。 これを逆多項式分数に制限すると、元の PACC が証明される。 corollary として、Tao や Vu のベルヌーイ行列に対するセミナル結果と同等に、ガウス永遠の典型的等級を確立する。 Aaronson-Arkhipov フレームワークと組み合わせることで、古典的にボソンサンプリングを超指数的に小さな全変動距離内でシミュレーションすると、残りの予想が成り立つと仮定して多項式階層が崩壊する。

関連論文リスト

• Analytic Cancellation of Interference Terms and Closed-Form 1-Mode Marginals in Canonical Boson Sampling [4.653967722732359]
  CBSにおける正確な1モードの辺り分布を,$mathcalORR時間で計算可能な直接ボトムアップで導出する。 この物理導出をランク1行列の数学的理論で明示的にブリッジし、多光子干渉が因子的束縛因子によってスケールされた対称性に還元されることを証明した。
  論文  参考訳（メタデータ） (2026-03-01T04:26:35Z)
• Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination [40.15176310729312]
  平均シフト汚染の有無における平均推定の基本的な課題について検討する。 対象平均を任意の精度で推定する,サンプル効率のアルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2026-02-25T17:21:23Z)
• The symplectic rank of non-Gaussian quantum states [0.0]
  非ガウス性はボソニックプラットフォームにおける量子上の優位性を達成するための鍵となる資源である。 ここでは, 顕著な操作性および資源理論的性質を満たす新しい非ガウス性モノトンであるシンプレクティックランクについて検討する。 シンプレクティックなランクは頑健な非ガウス測度であり、実験でそれを見る方法と、異なるボソニックなプラットフォームを有意にベンチマークする方法を説明する。
  論文  参考訳（メタデータ） (2025-04-27T18:00:31Z)
• Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations [29.212403229351253]
  ガウス機構の複素変項を解析し、この機構によって出力される行列と最高のランク-k$近似との差のフロベニウスノルムの上界を求める。 ガウス雑音によって摂動される行列の固有値$M$は高い確率で大きなギャップを持つことを示す。
  論文  参考訳（メタデータ） (2025-02-11T15:46:03Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  離散化マルコフ過程に基づく$mu_phi $の線形汎函数の2つの推定器を検討する。 誤差境界は、本質的に定義されたランゲヴィン拡散の離散化を用いてサンプリングと推定のために導出される。
  論文  参考訳（メタデータ） (2023-12-22T18:01:11Z)
• Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
  ランダムウォーカーは、サンプリングと近傍探索により、ネットワークトポロジ上のターゲット量を近似するように設計されている。 目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。 正の実アルファでパラメータ化されたSRRWのクラスに対して、プロセスの経験的分布がターゲットにほぼ確実に収束することを証明する。
  論文  参考訳（メタデータ） (2023-05-08T23:59:09Z)
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods [35.24886589614034]
  一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。 我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
  論文  参考訳（メタデータ） (2022-02-17T21:43:50Z)
• The Complexity of Bipartite Gaussian Boson Sampling [0.0]
  我々は、標準のアンチ・集中とガウスの永続予想の下で、階層が崩壊しない限り理想GBSからサンプリングする効率的なアルゴリズムは存在しないことを示した。 また、光子よりもモードが四分の一以下である体制において、硬さを証明するという目標に向かって前進する。
  論文  参考訳（メタデータ） (2021-10-13T18:08:37Z)
• A Random Matrix Perspective on Random Tensors [40.89521598604993]
  与えられたランダムテンソルの収縮から生じるランダム行列のスペクトルについて検討する。 本手法は,ML問題の局所的な最大値の未知な特徴を与える。 我々のアプローチは万能であり、非対称、非ガウス的、高階的など他のモデルにも拡張できる。
  論文  参考訳（メタデータ） (2021-08-02T10:42:22Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)

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

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