論文の概要: Exponential improvements to the average-case hardness of BosonSampling
- arxiv url: http://arxiv.org/abs/2411.04566v2
- Date: Thu, 04 Sep 2025 00:11:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-05 14:03:58.603351
- Title: Exponential improvements to the average-case hardness of BosonSampling
- Title（参考訳）: ボソンサンプリングの平均ケース硬さの指数的改善
- Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez,
- Abstract要約: ランダムなBosonSampling実験の確率を出力するための加算誤差推定は、任意の$delta>0$に対して#P$-hardであることを示す。
また,BosonSamplingの古典的な平均的なサンプリング結果の難しさを初めて示した。
- 参考スコア（独自算出の注目度）: 0.4515414068394328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n\log{n}-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n\log n-n-O(n^\delta)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard for any $\delta>0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now "merely" to show that the $O(n^\delta)$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{\mathstrut O}(N^{1/3})}$ for input size $N$, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.
- Abstract（参考訳）: BosonSamplingとRandom Circuit Samplingは、量子計算と古典計算を分離する理論ツールとして、また量子スピードアップを実証する実験手段としても重要である。
以前の研究では、サンプリングの平均ケースの硬さは、例えばPGC(Permanent-of-Gaussian Conjecture)のような計算出力確率の硬さに関するいくつかの未証明の予想に従うことが示されており、これは、ほとんどのランダムなボソンサンプリング実験の出力確率に対する加算誤差推定が$\#P$-hardであることを示している。
以前の研究は、より弱い平均ケース硬さの結果しか示していないが、それは硬さをサンプリングすることを意味するものではない。
これらの予想を証明することは、量子複雑性において中心的な問題となっている。
本研究では,ほとんどのランダムなBosonSampling実験の確率を出力する加算誤差推定値が$\#P$-hard for any $\delta>0$であることを示す。
この過程で, PGCを証明するための既知の障壁をすべて回避した。
PGCを証明するための残りのハードルは、指数の$O(n^\delta)$が$O(\log n)に改善できることを示すためである。
また、Random Circuit Smplingの類似した結果を得る。
次に、ボソンサンプリングに対する平均ケース古典的なサンプリング結果の硬さを反集中予想の下で初めて示す。
具体的には、確率1-2^{-\tilde{\mathstrut O}(N^{1/3})} のランダムなボソンサンプリング実験による乗法誤差サンプリングの不可能性を、多項式階層が崩壊しない限り、入力サイズ$N$に対して証明する。
これにより、最先端技術が飛躍的に向上する。
そこで本研究では, 最悪のケース・ケース・リダクションにおいて, 指数損失を許容する新しい証明手法を提案する。
これにより、PGCを証明せずに平均ケースサンプリングの硬さを示すことが可能となる。
関連論文リスト
- Beyond Boson Sampling: Higher Spin Sampling as a Practical Path to Quantum Supremacy [0.0]
量子超越性への実践的な経路として、任意のスピン-S$状態に対するスピンサンプリングを導入する。
サイト数$m$とスピン数$n$ as $msim n1+epsilon$の間の準線形スケーリング関係を同定する。
これは、スピンシステム内では、線形モード領域における等価なフォック状態ボソンサンプリングタスクが、リソース要求の低減とともに実験的に実現可能であることを示唆している。
論文 参考訳（メタデータ） (2025-05-12T07:57:21Z) - Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [conference paper] [52.69179872700035]
本稿では,$pi(x)proptoexp(-U(x))$という形のGibbs分布から,潜在的に$U(x)$でサンプリングする方法を提案する。
拡散モデルに着想を得て、ターゲット密度の近似の列 $(pit_k)_k$ を考えることを提案し、そこで$pit_kapprox pi$ for $k$ small に対して $pit_k$ は、$k$のサンプリングに好適な性質を示す。
論文 参考訳（メタデータ） (2025-02-03T13:50:57Z) - Experimental lower bounds on entanglement entropy without twin copy [0.0]
断熱的に調製した地盤状態の実験的測定と関連するシャノンエントロピー$S_ABX$を計算した。
良い近似では$S_AvNpropto (2S_AX-S_ABX)$が1よりわずかに大きい例を示す。
論文 参考訳（メタデータ） (2024-04-15T17:02:17Z) - Boson Sampling from Non-Gaussian States [0.0]
このような状態を生成するスキームを用いて、一般的な単一モード状態からのボソンサンプリングについて検討する。
線形干渉計を通った後、これらの状態の出力光子数確率を計算するのに使用できる公式を導出する。
論文 参考訳（メタデータ） (2024-03-25T20:49:19Z) - Transition of Anticoncentration in Gaussian Boson Sampling [0.0]
ガウスボソンサンプリング分布のモーメントを解析するためのグラフ理論フレームワークを開発した。
初期圧縮モードの数が光子数とともに十分に緩やかにスケールすると、アンチ集中が欠如していることが示される。
論文 参考訳（メタデータ） (2023-12-13T19:00:00Z) - Classical sampling from noisy Boson Sampling and the negative
probabilities [0.0]
多重ボソン干渉を有限次まで考慮することにより、ボソンサンプリングの出力分布をボソンの総数の近似からおよそサンプリングできることが知られている。
凸サム式における量子確率因子は、有限個の多重ボソン干渉に切り替われば、平均的にランダム干渉計において有限量の負性を持つ。
負性問題は、ノイズの多いボソンサンプリングに対する全ての効率的な古典に固有のものであるという結論は、早すぎるかもしれない。
論文 参考訳（メタデータ） (2023-07-11T15:33:37Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。