論文の概要: Average-case hardness of estimating probabilities of random quantum
circuits with a linear scaling in the error exponent
- arxiv url: http://arxiv.org/abs/2206.05642v1
- Date: Sun, 12 Jun 2022 02:35:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 18:24:31.024923
- Title: Average-case hardness of estimating probabilities of random quantum
circuits with a linear scaling in the error exponent
- Title（参考訳）: 誤差指数の線形スケーリングによるランダム量子回路の確率推定における平均ケース硬さ
- Authors: Hari Krovi
- Abstract要約: ランダム量子回路の確率を出力するための加算近似計算の難しさを考察する。
m$ゲートを持つハールランダム回路に対しては、平均ケース加法近似の$mathsfcoC_=P$硬さを2-O(m)$の精度で示す。
ランダム$p=1$ QAOA および IQP 回路の場合、平均の場合、出力確率を 2-O(n)$ の加算誤差の範囲内で近似するのは $mathsfcoC_=P$ であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the hardness of computing additive approximations to output
probabilities of random quantum circuits. We consider three random circuit
families, namely, Haar random, $p=1$ QAOA, and random IQP circuits. Our results
are as follows. For Haar random circuits with $m$ gates, we improve on prior
results by showing $\mathsf{coC_=P}$ hardness of average-case additive
approximations to an imprecision of $2^{-O(m)}$. Efficient classical simulation
of such problems would imply the collapse of the polynomial hierarchy. For
constant depth circuits i.e., when $m=O(n)$, this linear scaling in the
exponent is within a constant of the scaling required to show hardness of
sampling. Prior to our work, such a result was shown only for Boson Sampling in
Bouland et al (2021). We also use recent results in polynomial interpolation to
show $\mathsf{coC_=P}$ hardness under $\mathsf{BPP}$ reductions rather than
$\mathsf{BPP}^{\mathsf{NP}}$ reductions. This improves the results of prior
work for Haar random circuits both in terms of the error scaling and the power
of reductions. Next, we consider random $p=1$ QAOA and IQP circuits and show
that in the average-case, it is $\mathsf{coC_=P}$ hard to approximate the
output probability to within an additive error of $2^{-O(n)}$. For $p=1$ QAOA
circuits, this work constitutes the first average-case hardness result for the
problem of approximating output probabilities for random QAOA circuits, which
include Sherrington-Kirkpatrick and Erd\"{o}s-Renyi graphs. For IQP circuits, a
consequence of our results is that approximating the Ising partition function
with imaginary couplings to an additive error of $2^{-O(n)}$ is hard even in
the average-case, which extends prior work on worst-case hardness of
multiplicative approximation to Ising partition functions.
- Abstract（参考訳）: ランダム量子回路の確率を出力するための加算近似計算の難しさを考察する。
我々は、haar random, $p=1$ qaoa, random iqp circuitの3つのランダム回路を考察する。
結果は以下の通りである。
m$ゲートを持つハールランダム回路の場合、平均加法近似の$\mathsf{coC_=P}$硬さを2^{-Oの精度で示すことにより、先行結果を改善する。
(m)}$。
このような問題の効率的な古典的シミュレーションは多項式階層の崩壊を意味する。
一定深度回路の場合、すなわち$m=O
(n)$、指数のこの線形スケーリングはサンプリングの硬さを示すのに必要なスケーリングの定数の範囲内である。
我々の研究に先立ち、この結果はBoson Smpling in Bouland et al (2021)でのみ示された。
多項式補間においても最近の結果を用いて、$\mathsf{coC_=P}$ hardness under $\mathsf{BPP}$ reductions than $\mathsf{BPP}^{\mathsf{NP}}$ reductions を示す。
これにより、誤りのスケーリングと還元のパワーの両方の観点から、haarランダム回路の事前処理の結果が改善される。
次に、ランダムな$p=1$ qaoa と iqp 回路について検討し、平均の場合、出力確率を2^{-o の加算誤差の範囲内で近似するのは$\mathsf{coc_=p}$ であることを示す。
(n)}$。
p=1$QAOA回路の場合、この研究はシェリントン・カークパトリックやエルド・"{o}s-Renyiグラフを含むランダムQAOA回路の出力確率を近似する問題に対する最初の平均ケース硬度結果を構成する。
IQP 回路の場合,Ising 分割関数を虚結合で近似し,加法誤差が 2^{-O となる結果が得られた。
(n)$ は平均の場合でさえ困難であり、乗法近似の最悪の場合のハードネスをイジング分割関数に先行研究に拡張する。
関連論文リスト
- Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。
ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文 参考訳（メタデータ） (2024-06-11T17:23:16Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。