QAC0 Can Prepare Every Logarithmic-Qubit State

• URL: http://arxiv.org/abs/2609.17408v1
• Date: Tue, 15 Sep 2026 16:35:52 GMT
• Title: QAC0 Can Prepare Every Logarithmic-Qubit State
• Abstract summary: $mathsfQAC0$ is the class of constant-depth $mathrmpoly(n)$-ancilla circuits.<n>We show that every $O(log n)$-qubit state can be exactly and cleanly prepared by a $mathrmpoly(n)$-ancilla $mathsfQAC0$ circuit.
• Score: 1.4018975578160688
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: $\mathsf{QAC}^0$ is the class of constant-depth $\mathrm{poly}(n)$-ancilla circuits obtained by extending $\mathsf{QNC}^0$, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, $\mathsf{QNC}^0_f$, obtained by including arbitrary-width FANOUT gates instead ($\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_f$ [Moo99]). In this note, we show that every $O(\log n)$-qubit state can be exactly and cleanly prepared by a $\mathrm{poly}(n)$-ancilla $\mathsf{QAC}^0$ circuit. Previous known $\mathrm{poly}(n)$-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in $\mathsf{QAC}^0$. Equivalently, prior constructions of arbitrary $n$-qubit states in $\mathsf{QAC}^0$ require doubly exponential size and we obtain an exponential factor improvement.

Related papers

• On the Computational Complexity of Geometrically Local QAC0 circuits [13.101369903953804]
  We show that any $mathsfQAC0$ circuit can be exactly simulated by a two-dimensional geometrically local $mathsfQAC0$ circuit.<n>We prove a nearly logarithmic depth lower bound on $mathsf1Dtext-QAC0 $ circuits to compute the Parity function.
  arXiv  Detail & Related papers  (2026-04-08T15:07:09Z)
• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$ is the class of constant-depth quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates.<n>We show that $mathsfQAC0$ circuits are significantly more powerful than their classical counterparts.
  arXiv  Detail & Related papers  (2026-01-06T18:40:44Z)
• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  We show that it is not necessary for every user to hold a key, thereby strictly enlarging the best-known achievable region in the literature.<n>Our results uncover the novel fact that it is not necessary for every user to hold a key, thereby strictly enlarging the best-known achievable region in the literature.
  arXiv  Detail & Related papers  (2026-01-06T18:34:07Z)
• Low-degree approximation of QAC$^0$ circuits [0.0]
  We show that the parity function cannot be computed in QAC$0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2widetildeOmega(n1/d)$.
  arXiv  Detail & Related papers  (2024-11-01T19:04:13Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  We show that any depth-$d$ $mathrmQAC0$ circuit requires $n1+3-d$ ancillae to compute a function with approximate degree $ta(n)$.<n>This is the first superlinear lower bound on the super-linear sized $mathrmQAC0$.
  arXiv  Detail & Related papers  (2024-10-09T02:55:57Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
  arXiv  Detail & Related papers  (2023-11-22T20:27:05Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.