Fugu-MT 論文翻訳(概要): Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

論文の概要: Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

arxiv url: http://arxiv.org/abs/2609.39448v1
Date: Wed, 30 Sep 2026 10:21:03 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-01 18:57:27.572181
Title: Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
Title（参考訳）: ノイズ浅部回路の並列古典シミュレーション--1次元における量子的優位性
Abstract要約: 量子回路は、最寄りの2量子ビットゲートの$d$層が1行に配列された$n$量子ビットに作用すると考える。このアルゴリズムは, 1次元の回路を対数幅の独立した部分に切断する。
参考スコア（独自算出の注目度）: 11.458853556386797
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error $δ$, with parallel runtime $2^{O(d)}\log\log(n/δ)$ and $n 2^{O(d)}$ elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime $O(\log n)$. For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized $\mathsf{AC}^0$-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized $\mathsf{AC}^0$-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth $Ω(\log n/\log\log n)$. Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
Abstract（参考訳）: 量子回路は、最寄りの2量子ビットゲートの$d$層から成り、各量子ビットが各層の前に一定の確率で独立に非偏極化されるような線上に配置された$n$量子ビットに作用する。本稿では,任意の回路の出力分布から全変動誤差$δ$,並列実行時$$2^{O(d)}\log\log(n/δ)$および$n 2^{O(d)}$初等実算術演算を含むランダム化並列アルゴリズムについて述べる。ノイズがなければ、同じアプローチは並列実行時の$O(\log n)$と全く同じサンプルを提供する。定数深さについて、雑音量子回路の入出力挙動は、ランダム化された$\mathsf{AC}^0$-circuit、すなわち、アンバウンドファンインANDとORゲートとNOTゲートで多項式サイズと定数深さのブール回路によって、一定の誤差まで再現されることを示す。したがって、1次元のノイズの多い定数深度量子回路によって解決されるすべての関係問題は、基本的に同じ成功確率で、ランダム化された$\mathsf{AC}^0$-回路によって解決される。これは、1次元のノイズのある回路に対して、2次元と3次元のノイズの多い浅い回路に対して確立された無条件の量子優位性であり、同じゲート集合上の多項式サイズの古典回路は深さ$Ω(\log n/\log n)$を必要とする。このアルゴリズムは, 1次元の回路を対数幅の独立した部分に切断し, それぞれを正確に並列にサンプリングする手法である。

論文の概要: Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

関連論文リスト