論文の概要: Learning junta distributions and quantum junta states, and QAC$^0$ circuits
- arxiv url: http://arxiv.org/abs/2410.15822v1
- Date: Mon, 21 Oct 2024 09:39:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-22 13:16:40.779718
- Title: Learning junta distributions and quantum junta states, and QAC$^0$ circuits
- Title（参考訳）: 量子ユンタ状態とQAC$^0$回路の学習
- Authors: Francisco Escudero-Gutiérrez,
- Abstract要約: 本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。
誤差$varepsilon$を全変動距離で学習できることが示される。
また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: In this work we consider the problems of learning junta distributions, their quantum counter-part, quantum junta states, and QAC$^0$ circuits, which we show to be juntas. $\mathbf{Junta\ distributions.\ }$A probability distribution $p:\{-1,1\}^n\to \mathbb [0,1]$ is a $k$-junta if it only depends on $k$ variables. We show that they can be learned with to error $\varepsilon$ in total variation distance from $O(2^k\log(n)/\varepsilon^2)$ samples, which quadratically improves the upper bound of Aliakbarpour et al. (COLT'16) and matches their lower bound in every parameter. $\mathbf{Junta\ states.\ }$We initiate the study of $n$-qubit states that are $k$-juntas, those that are the tensor product of a $k$-qubit state and an $(n-k)$-qubit maximally mixed state. We show that these states can be learned with error $\varepsilon$ in trace distance with $O(12^{k}\log(n)/\varepsilon^2)$ single copies. We also prove a lower bound of $\Omega((4^k+\log (n))/\varepsilon^2)$ copies. Along the way, we give a new proof of the optimal performance of Classical Shadows based on Pauli analysis. $\mathbf{QAC^0\ circuits.\ }$Nadimpalli et al. (STOC'24) recently showed that the Pauli spectrum of QAC$^0$ circuits (with not too many auxiliary qubits) is concentrated on low-degree. We remark that they showed something stronger, namely that the Choi states of those circuits are close to be juntas. As a consequence, we show that $n$-qubit QAC$^0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2^{O(\log(s^22^a)^d)}\log (n)$ copies of the Choi state, improving the $n^{O(\log(s^22^a)^d)}$ by Nadimpalli et al. In addition, we use this remark to improve on the lower bounds against QAC$^0$ circuits to compute the address function.
- Abstract（参考訳）: 本研究では, ユンタ分布, 量子カウンター部, 量子ユンタ状態, QAC$^0$回路の学習問題を考える。
$\mathbf{Junta\ディストリビューション。
A の確率分布 $p:\{-1,1\}^n\to \mathbb [0,1]$ は $k$-junta であり、$k$変数のみに依存する。
O(2^k\log(n)/\varepsilon(n)/\varepsilon(2)$)$の合計変動距離は、Aliakbarpour et al(COLT'16)の上界を2次的に改善し、各パラメータの下位境界と一致する。
$\mathbf{Junta\ state.
n$-qubit 状態、$k$-qubit 状態のテンソル積、$(n-k)$-qubit の最大混合状態の研究を開始する。
これらの状態は、エラー$\varepsilon$と、O(12^{k}\log(n)/\varepsilon^2)$の単一コピーとのトレース距離で学習可能であることを示す。
また、$\Omega((4^k+\log (n))/\varepsilon^2)$コピーの低い境界も証明する。
その過程で、パウリ解析に基づく古典的影の最適性能の新たな証明を与える。
$\mathbf{QAC^0\ 回路。
\ }$Nadimpalli et al (STOC'24) は、最近、QAC$^0$回路のパウリスペクトルが低度に集中していることを示した。
それらの回路のチェイ状態がジャンタに近いという、より強いものを示しました。
その結果,$n$-qubit QAC$^0$の回路サイズが$s$, depth$d$, $a$の補助量子ビットは,$2^{O(\log(s^22^a)^d)}\log (n)$のChoi状態のコピーから学習でき,$n^{O(\log(s^22^a)^d)}をNadimpalliらによって改善できることがわかった。
関連論文リスト
- Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。
また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文 参考訳（メタデータ） (2024-11-01T19:04:13Z) - Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。
ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文 参考訳（メタデータ） (2024-06-11T17:23:16Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
安定度が低い」量子状態は、Haar-randomと効率的に区別できることを示す。
我々は、計算的に擬似ランダムな量子状態を作成するためには、任意のクリフォード+$T$回路に対して$omega(log(n))$$T$-gatesが必要であることを証明した。
論文 参考訳（メタデータ） (2022-09-29T03:34:03Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Unitarization Through Approximate Basis [0.0]
ユニタリゼーションは、全ての$0$状態から量子状態を生成する$k$入力回路を取る問題である。
以下のパラメータの時間に近似した基底を求める。
論文 参考訳（メタデータ） (2021-04-01T22:11:05Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。