論文の概要: Parity vs. AC0 with simple quantum preprocessing
- arxiv url: http://arxiv.org/abs/2311.13679v2
- Date: Wed, 29 Nov 2023 21:04:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-01 22:58:51.648200
- Title: Parity vs. AC0 with simple quantum preprocessing
- Title(参考訳): 単純量子前処理によるパリティ対AC0
- Authors: Joseph Slote
- Abstract要約: 我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent line of work has shown the unconditional advantage of constant-depth
quantum computation, or $\mathsf{QNC^0}$, over $\mathsf{NC^0}$,
$\mathsf{AC^0}$, and related models of classical computation. Problems
exhibiting this advantage include search and sampling tasks related to the
parity function, and it is natural to ask whether $\mathsf{QNC^0}$ can be used
to help compute parity itself. We study $\mathsf{AC^0\circ QNC^0}$ -- a hybrid
circuit model where $\mathsf{AC^0}$ operates on measurement outcomes of a
$\mathsf{QNC^0}$ circuit, and conjecture $\mathsf{AC^0\circ QNC^0}$ cannot
achieve $\Omega(1)$ correlation with parity. As evidence for this conjecture,
we prove:
$\bullet$ When the $\mathsf{QNC^0}$ circuit is ancilla-free, this model
achieves only negligible correlation with parity.
$\bullet$ For the general (non-ancilla-free) case, we show via a connection
to nonlocal games that the conjecture holds for any class of postprocessing
functions that has approximate degree $o(n)$ and is closed under restrictions,
even when the $\mathsf{QNC^0}$ circuit is given arbitrary quantum advice. By
known results this confirms the conjecture for linear-size $\mathsf{AC^0}$
circuits.
$\bullet$ Towards a switching lemma for $\mathsf{AC^0\circ QNC^0}$, we study
the effect of quantum preprocessing on the decision tree complexity of Boolean
functions. We find that from this perspective, nonlocal channels are no better
than randomness: a Boolean function $f$ precomposed with an $n$-party nonlocal
channel is together equal to a randomized decision tree with worst-case depth
at most $\mathrm{DT}_\mathrm{depth}[f]$.
Our results suggest that while $\mathsf{QNC^0}$ is surprisingly powerful for
search and sampling tasks, that power is "locked away" in the global
correlations of its output, inaccessible to simple classical computation for
solving decision problems.
- Abstract(参考訳): 最近の研究の行は、定数深度量子計算の非条件的優位性、または$\mathsf{QNC^0}$、$\mathsf{NC^0}$、$\mathsf{AC^0}$、および関連する古典計算のモデルを示している。
この利点を示す問題はパリティ関数に関連する探索およびサンプリングタスクであり、$\mathsf{qnc^0}$がパリティ自体を計算するのに役立つかどうかを問うのは自然である。
我々は$\mathsf{AC^0\circ QNC^0}$ -- $\mathsf{AC^0}$が$\mathsf{QNC^0}$回路の測定結果に基づいて動作するハイブリッド回路モデルについて研究し、$\mathsf{AC^0\circ QNC^0}$は$\Omega(1)$パリティとの相関が得られない。
この予想の証拠として、$\bullet$ が、$\mathsf{qnc^0}$回路がアンシラフリーであるとき、このモデルはパリティとの無視できない相関のみを達成する。
$\bullet$ 一般(非アンシラ自由)の場合、予想が近似次数 $o(n)$ を持つ任意の種類の後処理関数に対して持つ非局所ゲームとの接続を通して、$\mathsf{QNC^0}$ 回路が任意の量子アドバイスを受けるときでさえ、制限の下で閉じていることを示す。
既知の結果により、これは線型サイズ$\mathsf{AC^0}$回路の予想を確認する。
$\bullet$は、$\mathsf{AC^0\circ QNC^0}$のスイッチング補題に向けて、ブール関数の決定木複雑性に対する量子前処理の効果を研究する。
この見地からすると、非局所的チャネルはランダム性以上のものではないことが分かる:$n$の非局所的チャネルで予め構成されたブール関数$f$は、最大$\mathrm{dt}_\mathrm{depth}[f]$で最悪の場合の深さを持つランダム化された決定木に等しい。
以上の結果から,$\mathsf{QNC^0}$は,タスクの探索とサンプリングに驚くほど強力であるが,その出力のグローバルな相関は,決定問題を解くための単純な古典計算には到達できない。
関連論文リスト
- On the Pauli Spectrum of QAC0 [2.5602836891933074]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々はこの予想を、少なくとも$nO(1/d)$補助量子ビットを持つ深さ-d$,-size $mathsfQAC0$回路のクラスで証明する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳(メタデータ) (2023-11-16T07:25:06Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳(メタデータ) (2022-09-04T10:01:39Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳(メタデータ) (2022-07-28T17:50:53Z) - 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) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳(メタデータ) (2020-12-03T14:03:20Z) - Degree vs. Approximate Degree and Quantum Implications of Huang's
Sensitivity Theorem [4.549831511476248]
すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。
f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
論文 参考訳(メタデータ) (2020-10-23T19:21:28Z) - 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) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳(メタデータ) (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。