論文の概要: Low-degree approximation of QAC$^0$ circuits

• arxiv url: http://arxiv.org/abs/2411.00976v2
• Date: Thu, 07 Nov 2024 20:51:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:52:13.875378
• Title: Low-degree approximation of QAC$^0$ circuits
• Title（参考訳）: QAC$^0$回路の低次近似
• Authors: Ashley Montanaro, Changpeng Shao, Dominic Verdon,
• Abstract要約: パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: QAC$^0$ is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC$^0$, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves ${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2^{\widetilde{\Omega}(n^{1/d})}$ ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC$^0$. This implies that, for any QAC$^0$ circuit $U$ with $a={\rm poly}(n)$ ancillary qubits, and for any $x\in\{0,1\}^n$, the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetilde{\Omega}(n^{1/d})}$, where $Q(x)$ denotes the output of measuring the output qubit of $U|x,0^a\rangle$. All the above consequences rely on the following technical result. If $U$ is a QAC$^0$ circuit with $a={\rm poly}(n)$ ancillary qubits, then there is a distribution $\mathcal{D}$ of bounded polynomials of degree polylog$(n)$ such that with high probability, a random polynomial from $\mathcal{D}$ approximates the function $\langle x,0^a| U^\dag Z_{n+1} U |x,0^a\rangle$ for a large fraction of $x\in \{0,1\}^n$. This result is analogous to the Razborov-Smolensky result on the approximation of AC$^0$ circuits by random low-degree polynomials.
• Abstract（参考訳）: QAC$^0$(QAC$^0$)は、多項式的に多くの補助量子ビットを持つ定数深さ量子回路のクラスであり、トフォリは任意に多くの量子ビットにゲートする。 本研究では、20年以上前の量子回路複雑性における長年の未解決問題を解決するため、パリティ関数をQAC$^0$で計算することはできないことを示す。 その結果、${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$ が証明される。 また、$n$ビットのパリティを近似的に計算する深さ$d$のQAC回路は、$2^{\widetilde{\Omega}(n^{1/d})}$ Acillary qubits を必要とする。 これはQAC回路を用いて、ほぼ準備された猫の状態に類似した下界を示す。 最後に、QAC$^0$に対してLinial-Mansour-Nisan定理の量子類似性を証明する。 これは、任意のQAC$^0$ circuit $U$ with $a={\rm poly}(n)$ acillary qubits, and for any $x\in\{0,1\}^n$, the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetilde{\Omega}(n^{1/d})}$, $Q(x)$は$U|x,0^a\rangle$の出力量子ビットを測定する出力を表す。 上記の結果はすべて、以下の技術的結果に依存している。 U$ が $a={\rm poly}(n)$ acillary qubits を持つ QAC$^0$ 回路であれば、高確率で $\mathcal{D}$ のランダム多項式が函数 $\langle x,0^a| U^\dag Z_{n+1} U |x,0^a\rangle$ を $x\in \{0,1\}^n$ の大きな分数に対して近似するような分布 $\mathcal{D}$ が存在する。 この結果は、ランダムな低次多項式によるAC$^0$回路の近似におけるラズボロフ・スモレンスキーの結果に類似している。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
  本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。 誤差$varepsilon$を全変動距離で学習できることが示される。 また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
  論文  参考訳（メタデータ） (2024-10-21T09:39:20Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。 これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
  論文  参考訳（メタデータ） (2024-10-09T02:55:57Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。 十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$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)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• 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)
• Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
  その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。 QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
  論文  参考訳（メタデータ） (2020-08-17T16:51:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。