Improved Lower Bounds for QAC0

• URL: http://arxiv.org/abs/2512.14643v1
• Date: Tue, 16 Dec 2025 17:59:51 GMT
• Title: Improved Lower Bounds for QAC0
• Authors: Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright,
• Abstract summary: We present new techniques for simulating certain QAC$0$ circuits classically in AC$0$ to obtain our depth $3$ lower bounds.<n>We relax the output requirement of the quantum circuit to a single bit, making our depth $2$ bound stronger than the previous best bound of Rosenthal.<n>Our proof techniques suggest that, for inherently classical decision problems, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts.
• Score: 1.4609117117519856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we establish the strongest known lower bounds against QAC$^0$, while allowing its full power of polynomially many ancillae and gates. Our two main results show that: (1) Depth 3 QAC$^0$ circuits cannot compute PARITY regardless of size, and require at least $Ω(\exp(\sqrt{n}))$ many gates to compute MAJORITY. (2) Depth 2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage in depth $2$, regardless of size. We present new techniques for simulating certain QAC$^0$ circuits classically in AC$^0$ to obtain our depth $3$ lower bounds. In these results, we relax the output requirement of the quantum circuit to a single bit (i.e., no restrictions on input preservation/reversible computation), making our depth $2$ approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ using exponential size. Our proof techniques further suggest that, for inherently classical decision problems, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth $2$ QAC$^0$ circuits, regardless of size, cannot exactly synthesize an $n$-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth $2$ exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound).

Related papers

• Optimal lower bound for quantum channel tomography in away-from-boundary regime [32.904052887092284]
  Heisenberg scaling $(d2/varepsilon)$ is achievable.<n>In particular, this lower bound fully settles the query complexity for the commonly studied case of equal input and output dimensions.
  arXiv  Detail & Related papers  (2026-01-15T18:45:59Z)
• Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
  We present quantum online quasi-Newton methods to tackle the problem. Our method approximates the Hessian by quantum estimated inexact gradient. Such regret improves the optimal classical algorithm by a factor of $T2/3$.
  arXiv  Detail & Related papers  (2024-10-25T16:58:44Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits [12.786353781073242]
  We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure. We show that the scrambling speed of a random quantum circuit is lower bounded.
  arXiv  Detail & Related papers  (2024-07-28T19:10:46Z)
• Lower T-count with faster algorithms [2.488003578430483]
  We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times.<n>We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits.<n>We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
  arXiv  Detail & Related papers  (2024-07-11T17:31:20Z)
• Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
  We propose a query-efficient and accurate estimator for gradients that uses only $Obig(slogfrac dsbig)$ queries per step.<n>Our proposed GraCe generalizes the Indyk--Price--Woodruff (IPW) algorithm in compressed sensing from linear measurements to nonlinear functions.
  arXiv  Detail & Related papers  (2024-05-27T03:52:53Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  We conjecture that the Pauli spectrum of $mathsfQAC0$ satisfies low-degree concentration. We obtain new circuit lower bounds and learning results as applications.
  arXiv  Detail & Related papers  (2023-11-16T07:25:06Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Beyond Ans\"atze: Learning Quantum Circuits as Unitary Operators [30.5744362478158]
  We run gradient-based optimization in the Lie algebra $mathfrak u(2N)$. We argue that $U(2N)$ is not only more general than the search space induced by ansatz, but in ways easier to work with on classical computers.
  arXiv  Detail & Related papers  (2022-03-01T16:40:21Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
  We prove that QAC circuits of sublogarithmic depth can approximate parity regardless of size. QAC circuits require at least $Omega(n/d)$ multi-qubit gates to achieve a $1/2 + exp(-o(n/d))$ approximation of parity.
  arXiv  Detail & Related papers  (2020-08-17T16:51:04Z)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  We prove that $poly(t)cdot n1/D$-depth local random quantum circuits with two qudit nearest-neighbor gates are approximate $t$-designs in various measures. We also prove that anti-concentration is possible in depth O(log(n) loglog(n) using a different model.
  arXiv  Detail & Related papers  (2018-09-18T22:28:15Z)

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.