Fugu-MT 論文翻訳(概要): Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

論文の概要: Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

arxiv url: http://arxiv.org/abs/2610.02146v1
Date: Thu, 01 Oct 2026 17:49:01 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-03 01:19:24.353864
Title: Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Title（参考訳）: 浅い量子回路における出力確率の多項式時間加算誤差推定
Abstract要約: 我々は、$|langle x|U|0nrangle|2$ to additive error $varepsilon$ in $mathrmpoly(n, 1/varepsilon)$ timeを推定する決定論的古典的アルゴリズムを与える。
参考スコア（独自算出の注目度）: 0.17398560678845074
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.
Abstract（参考訳）: 決定論的古典的アルゴリズムは、$|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-deepth quantum circuit consist of gates with bounded fan-in and arbitrary connection, $x$ is a arbitrary $n$-bit output string。これは、同じタスクに対して$n^{O(log(n))}$時間、$U$が幾何学的に局所であるとき$n^{O(log(log(n))}$、$n^{O(1)}$2次元幾何学的に局所的な回路に対して$n^{O(log(n)))$よりも改善される。

関連論文リスト

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文参考訳（メタデータ） (2026-09-30T17:51:21Z)
A Quantum Time-Space Tradeoff for Directed $st$-Connectivity [0.08594140167290097]
任意の$Sgeq log2(n)$に対して、空間$S$と時間$Tleq 2frac12log(n)log(n/S)+o(log2(n))$を用いてDSTCONの量子アルゴリズムが存在することを示す。
論文参考訳（メタデータ） (2025-10-09T16:22:04Z)
Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms [4.832760917132771]
我々は量子力学プログラミングフレームワークを導入し、古典的動的プログラミングアルゴリズムの大きな体系である量子領域に直接拡張することを可能にする。対応する量子力学プログラミングアルゴリズムは、計算スピードアップを達成しながら、従来のものと同じ空間の複雑さを保っている。
論文参考訳（メタデータ） (2025-07-01T14:55:18Z)
Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文参考訳（メタデータ） (2023-09-15T14:01:13Z)
Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文参考訳（メタデータ） (2023-05-25T22:27:42Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文参考訳（メタデータ） (2023-03-03T18:23:20Z)
Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (2022-03-17T23:52:08Z)
Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文参考訳（メタデータ） (2021-04-29T14:50:03Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文参考訳（メタデータ） (2020-08-20T01:04:32Z)

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