論文の概要: On the average-case hardness of BosonSampling
- arxiv url: http://arxiv.org/abs/2411.04566v1
- Date: Thu, 07 Nov 2024 09:41:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-08 19:37:28.345078
- Title: On the average-case hardness of BosonSampling
- Title（参考訳）: ボソンサンプリングの平均ケース硬度について
- Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez,
- Abstract要約: ガウス永遠推定」予想を証明することは、量子優位の理論において中心的な問題となっている。
我々は、ほとんどのランダムなBosonSampling実験の出力確率に対して、$e-nlog n -n - O(ndelta)$加法誤差推定が$#P$-hardであることを証明する。
この結果により、ランダムなBosonSampling実験に対する古典的なサンプリング結果の難しさを初めて示すことができる。
- 参考スコア（独自算出の注目度）: 0.13194391758295113
- License:
- Abstract: BosonSampling is a popular candidate for near-term quantum advantage, which has now been experimentally implemented several times. The original proposal of Aaronson and Arkhipov from 2011 showed that classical hardness of BosonSampling is implied by a proof of the "Gaussian Permanent Estimation" conjecture. This conjecture 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. Proving this conjecture has since become the central question in the theory of quantum advantage. In this work we make progress by proving 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$. In the process, we circumvent all known barrier results for proving the hardness of BosonSampling experiments. This is nearly the robustness needed to prove hardness of BosonSampling -- the remaining hurdle is now "merely" to show that the $n^\delta$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. Our result allows us to show, for the first time, a hardness of classical sampling result for random BosonSampling experiments, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-e^{-O(n)}$, unless the Polynomial Hierarchy collapses.
- Abstract（参考訳）: ボソンサンプリングは短期量子優位の候補として人気があり、現在は数回実験的に実装されている。
2011年のアーロンソンとアルキポフの最初の提案は、ボソンサンプリングの古典的な硬さが「ガウスの永続的推定」予想の証明によって示唆されることを示した。
この予想は$e^{-n\log{n}-n-O(\log n)}$加法誤差の推定値がほとんどのランダムなボソンサンプリング実験の出力確率に$\#P$-hardであることを示している。
この予想を証明することは、量子優位の理論における中心的な問題となっている。
この研究では、任意の$\delta>0$に対して、ほとんどのランダムなBosonSampling実験の確率を出力するために、e^{-n\log n -n - O(n^\delta)}$加法誤差推定が$\#P$-hardであることを示す。
この過程で、BosonSampling実験の硬さを証明するために、既知のすべての障壁を回避した。
これは、BosonSamplingの硬さを証明するのに必要なロバスト性に近い。残りのハードルは、指数の$n^\delta$が$O(\log n)に改善可能であることを示すためである。
また、Random Circuit Smplingの類似した結果を得る。
この結果から、ランダムなボソンサンプリング実験に対する古典的なサンプリング結果の難しさを、反集中予想の下で初めて示することができる。
具体的には、確率1-e^{-O(n)}$のランダムなボソンサンプリング実験から、多項式階層が崩壊しない限り、乗法誤差サンプリングが不可能であることを証明する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。