論文の概要: Unconditional Quantum Advantage for Sampling with Shallow Circuits
- arxiv url: http://arxiv.org/abs/2301.00995v3
- Date: Fri, 23 Feb 2024 04:19:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 18:47:14.338570
- Title: Unconditional Quantum Advantage for Sampling with Shallow Circuits
- Title（参考訳）: 浅回路サンプリングのための無条件量子アドバンテージ
- Authors: Adam Bene Watts, Natalie Parham
- Abstract要約: Bravyi、Gosset、Koenigによる最近の研究は、一定の深さの量子回路で解ける探索問題が存在することを示した。
この質問に対する答えは、古典回路に与えられるランダムな入力ビットの数が有界であるときにイエスであることが示される。
また、アドバイス付き定数深度量子回路と、ファンインとファンアウトの有界な古典回路との類似の分離を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work by Bravyi, Gosset, and Koenig showed that there exists a search
problem that a constant-depth quantum circuit can solve, but that any
constant-depth classical circuit with bounded fan-in cannot. They also pose the
question: Can we achieve a similar proof of separation for an input-independent
sampling task? In this paper, we show that the answer to this question is yes
when the number of random input bits given to the classical circuit is bounded.
We introduce a distribution $D_{n}$ over $\{0,1\}^n$ and construct a
constant-depth uniform quantum circuit family $\{C_n\}_n$ such that $C_n$
samples from a distribution close to $D_{n}$ in total variation distance. For
any $\delta < 1$ we also prove, unconditionally, that any classical circuit
with bounded fan-in gates that takes as input $kn + n^\delta$ i.i.d. Bernouli
random variables with entropy $1/k$ and produces output close to $D_{n}$ in
total variation distance has depth $\Omega(\log \log n)$. This gives an
unconditional proof that constant-depth quantum circuits can sample from
distributions that can't be reproduced by constant-depth bounded fan-in
classical circuits, even up to additive error. We also show a similar
separation between constant-depth quantum circuits with advice and classical
circuits with bounded fan-in and fan-out, but access to an unbounded number of
i.i.d random inputs.
The distribution $D_n$ and classical circuit lower bounds are inspired by
work of Viola, in which he shows a different (but related) distribution cannot
be sampled from approximately by constant-depth bounded fan-in classical
circuits.
- Abstract（参考訳）: Bravyi、Gosset、Koenigによる最近の研究は、一定の深さの量子回路で解ける探索問題が存在するが、ファンインが有界な任意の定深さの古典回路では解けないことを示した。
入力非依存のサンプリングタスクに対して、同様の分離の証明を達成できますか?
本稿では,古典回路に与えられるランダムな入力ビットの数が有界である場合に,この疑問に対する答えがイエスであることを示す。
我々は、$\{0,1\}^n$ 以上の分布 $d_{n}$ を導入し、全変動距離において$d_{n}$ に近い分布から$c_n$ のサンプルを得るように、定数深さの均一量子回路ファミリ $\{c_n\}_n$ を構成する。
任意の$\delta < 1$ に対して、無条件に、入力 $kn + n^\delta$ i.i.d.ベルノウリ確率変数のエントロピーが 1/k$ であり、全変動距離が $d_{n}$ に近い出力を生成する任意の古典回路は、深さ $\omega(\log \log n)$ であることも証明する。
これにより、定数深さ量子回路が定数深さ有界ファンイン古典回路では再現できない分布からサンプルできるという無条件の証明を与える。
また、アドバイス付き定数深度量子回路とバウンドファンインとファンアウト付き古典回路との類似の分離を示すが、非バウンド数のi.i.dランダム入力にアクセスする。
分布 $d_n$ と古典回路下限は、ビオラの仕事に触発され、異なる(しかし関連する)分布は、ほぼ一定の深さの有界な古典回路からサンプリングできないことを示した。
関連論文リスト
- On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
このような回路から1/textpoly(n)$のピーク値を得るには、圧倒的な確率で$tau_p = Omega(tau_r/n)0.19)$が必要である。
また、このモデルでは非自明なピーク性も可能であるという数値的な証拠を与える。
論文 参考訳（メタデータ） (2024-04-22T18:00:06Z) - Unitary k-designs from random number-conserving quantum circuits [0.0]
局所ランダム回路は効率よくスクランブルし、量子情報や量子力学に様々な応用がある。
有限モーメントは、数保存ユニタリ群全体のハールアンサンブルから局所ランダム回路が生成するアンサンブルを区別できないことを示す。
論文 参考訳（メタデータ） (2023-06-01T18:00:00Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
北エフの量子二重モデルは有限群$G$に基づく。
本稿では, (a) 基底状態の生成, (b) 任意の距離で分離されたエノン対の生成, (c) 非破壊的トポロジカル電荷測定のための量子回路について述べる。
論文 参考訳（メタデータ） (2022-05-04T08:10:36Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
本稿では,Grier と Schaeffer の対話プロトコルに耐雑音性を加えるための戦略を示す。
この削減の重要な要素は、古典的なシミュレーションタスクにおける平均ケースの硬さを示すことである。
シュミレートするために$oplus$L-hardの量子タスクでさえそうであることを示す。
論文 参考訳（メタデータ） (2021-02-13T00:54:45Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Approximate unitary $t$-designs by short random quantum circuits using
nearest-neighbor and long-range gates [0.0]
ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。
また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
論文 参考訳（メタデータ） (2018-09-18T22:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。