論文の概要: Unconditional Quantum Advantage for Sampling with Shallow Circuits
- arxiv url: http://arxiv.org/abs/2301.00995v2
- Date: Thu, 5 Jan 2023 01:41:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-08 22:00:37.580644
- 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.
We introduce a distribution $D_{n}$ and give a constant-depth, $n$ qubit,
quantum circuit that 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 $n +
n^\delta$ uniformly random bits 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 which
can't be reproduced by constant-depth bounded fan-in classical circuits, even
up to additive error.
The distribution $D_n$ and classical circuit lower bounds are based on 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による最近の研究は、一定の深さの量子回路で解ける探索問題が存在するが、ファンインが有界な任意の定深さの古典回路では解けないことを示した。
彼らはまた、入力非依存のサンプリングタスクに対して、同様の分離の証明を達成できますか?
本稿では,この問題に対する答がイエスであることを示す。
分布$D_{n}$を導入し、全変動距離においてD_{n}$に近い分布からサンプリングする定数深さ$n$qubitの量子回路を与える。
任意の$\delta < 1$ に対して、無条件に、入力$n + n^\delta$ のランダムビットを入力とし、全変動距離で$d_{n}$ に近い出力を生成する有界なファンインゲートを持つ古典回路は、深さ$\omega(\log \log n)$ であることも証明する。
これにより、定数深さ量子回路が定数深さ有界ファンイン古典回路では再現できない分布からサンプルできるという無条件の証明を与える。
分布$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。