論文の概要: On the average-case complexity of learning output distributions of
quantum circuits
- arxiv url: http://arxiv.org/abs/2305.05765v1
- Date: Tue, 9 May 2023 20:53:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 15:24:11.189034
- Title: On the average-case complexity of learning output distributions of
quantum circuits
- Title（参考訳）: 量子回路の学習出力分布の平均ケース複雑性について
- Authors: Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Kueng, Jens
Eisert, Marcel Hinsche and Jonas Haferkamp
- Abstract要約: 統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
- 参考スコア（独自算出の注目度）: 55.37943886895049
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we show that learning the output distributions of brickwork
random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most
generic learning algorithms. In particular, for brickwork random quantum
circuits on $n$ qubits of depth $d$, we show three main results:
- At super logarithmic circuit depth $d=\omega(\log(n))$, any learning
algorithm requires super polynomially many queries to achieve a constant
probability of success over the randomly drawn instance.
- There exists a $d=O(n)$, such that any learning algorithm requires
$\Omega(2^n)$ queries to achieve a $O(2^{-n})$ probability of success over the
randomly drawn instance.
- At infinite circuit depth $d\to\infty$, any learning algorithm requires
$2^{2^{\Omega(n)}}$ many queries to achieve a $2^{-2^{\Omega(n)}}$ probability
of success over the randomly drawn instance.
As an auxiliary result of independent interest, we show that the output
distribution of a brickwork random quantum circuit is constantly far from any
fixed distribution in total variation distance with probability $1-O(2^{-n})$,
which confirms a variant of a conjecture by Aaronson and Chen.
- Abstract（参考訳）: 本研究では,統計的クエリモデルにおいて,ブロックワークランダムな量子回路の出力分布の学習が平均ケースハードであることを示す。
この学習モデルは、ほとんどの汎用学習アルゴリズムの抽象計算モデルとして広く使われている。
特に、n$ qubits of depth $d$ のブリックワークランダム量子回路では、次の3つの主な結果が示される: - super logarithmic circuit depth $d=\omega(\log(n))$ 任意の学習アルゴリズムは、ランダムに描画されたインスタンスに対して一定の成功確率を達成するために、スーパー多項式の多くのクエリを必要とする。
-$d=O(n)$が存在し、任意の学習アルゴリズムがランダムに描画されたインスタンスに対して$O(2^{-n})$の成功確率を達成するために$\Omega(2^n)$クエリを必要とする。
-無限回路深さ$d\to\infty$の場合、任意の学習アルゴリズムはランダムに描画されたインスタンスに対して成功の確率を2^{2^{\Omega(n)}}$2^{2^{\Omega(n)}}で達成するために多くのクエリを必要とする。
独立な利害関係の補助的な結果として、ブロックワークランダムな量子回路の出力分布は確率1-O(2^{-n})$の総変分距離における任意の固定分布から常に遠いことが示され、Aaronson と Chen の予想の変分を確認する。
関連論文リスト
- Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - 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) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。