論文の概要: Classical simulation of peaked shallow quantum circuits
- arxiv url: http://arxiv.org/abs/2309.08405v1
- Date: Fri, 15 Sep 2023 14:01:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-18 14:31:57.324178
- Title: Classical simulation of peaked shallow quantum circuits
- Title（参考訳）: ピーク浅層量子回路の古典的シミュレーション
- Authors: Sergey Bravyi, David Gosset, Yinchen Liu
- Abstract要約: 準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
- 参考スコア（独自算出の注目度）: 2.6089354079273512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An $n$-qubit quantum circuit is said to be peaked if it has an output
probability that is at least inverse-polynomially large as a function of $n$.
We describe a classical algorithm with quasipolynomial runtime $n^{O(\log{n})}$
that approximately samples from the output distribution of a peaked
constant-depth circuit. We give even faster algorithms for circuits composed of
nearest-neighbor gates on a $D$-dimensional grid of qubits, with polynomial
runtime $n^{O(1)}$ if $D=2$ and almost-polynomial runtime
$n^{O(\log{\log{n}})}$ for $D>2$. Our sampling algorithms can be used to
estimate output probabilities of shallow circuits to within a given
inverse-polynomial additive error, improving previously known methods. As a
simple application, we obtain a quasipolynomial algorithm to estimate the
magnitude of the expected value of any Pauli observable in the output state of
a shallow circuit (which may or may not be peaked). This is a dramatic
improvement over the prior state-of-the-art algorithm which had an exponential
scaling in $\sqrt{n}$.
- Abstract（参考訳）: n$-量子回路は、少なくともn$の関数として逆ポリノミカルに大きい出力確率を持つ場合、ピークとされる。
我々は、ピーク付き定数深さ回路の出力分布からおよそサンプルをサンプリングした準多項ランタイム $n^{o(\log{n})} を持つ古典的なアルゴリズムを記述する。
量子ビットの$d$-次元グリッド上に最寄りのゲートからなる回路のより高速なアルゴリズムを提供し、多項式ランタイム$n^{o(1)}$ if $d=2$、ほぼ多項ランタイム$n^{o(\log{\log{n}})}$を$d>2$とする。
サンプリングアルゴリズムは、与えられた逆多項加算誤差の範囲内における浅回路の出力確率を推定し、従来知られていた方法を改善するために使用できる。
簡単な応用として、浅い回路の出力状態において観測可能な任意のパウリの期待値の大きさを推定する準ポリノミカルアルゴリズムを得る。
これは、$\sqrt{n}$の指数的スケーリングを持つ従来の最先端アルゴリズムよりも劇的な改善である。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - 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) - Fast estimation of outcome probabilities for quantum circuits [0.0]
我々は、$n$ qubits上の普遍量子回路のシミュレーションのための2つの古典的アルゴリズムを提案する。
我々のアルゴリズムは、パラメータの異なる条件下で最高の処理を行うことで、お互いを補完する。
アルゴリズムのC+Python実装を提供し、ランダム回路を用いてそれらをベンチマークする。
論文 参考訳（メタデータ） (2021-01-28T19:00:04Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Googleの53量子ビット回路のノイズ量子シミュレーションでは、C$は2.24pm0.21)times10-3$の忠実度値を得た。
この結果は,線形XEBテストの不正化が,量子回路の完全なシミュレーションを実現するよりも容易であることを示す証拠とみなすことができる。
論文 参考訳（メタデータ） (2020-05-05T18:01:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。