Pith. sign in

REVIEW 3 major objections 2 minor 1 cited by

Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$

T0 review · 3 major / 2 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Dicke states of polylogarithmic weight can be prepared in constant-depth QAC⁰ circuits, and weight-k Dicke preparation is equivalent to having FANOUT_k in QAC⁰.

desk verdict Abstract claims a clean tight QAC⁰/FANOUT_k characterization for Dicke states, but the supplied full text is the wrong paper, so nothing is auditable. read the letter →

arxiv 2604.15298 v2 pith:6Q3QHS5F submitted 2026-04-16 quant-ph cs.DS

Lucas Gretta , Meghal Gupta , Malvika Raj Joshi This is my paper · ORCID
classification quant-phcs.DS MSC 68Q1281P68
keywords DickestatesQAC0FANOUTconstant-depthquantumcircuitssymmetricQRAMstatepreparationToffoligates
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Dicke states are uniform superpositions of all n-bit strings of a fixed Hamming weight k. They appear in quantum algorithms that claim speedups, yet preparing them on near-term hardware is hard because depth and locality are tightly constrained. QAC⁰ is the constant-depth quantum circuit class that adds arbitrary-width Toffoli gates to ordinary local gates; it is far weaker than circuits that may freely use full n-bit fan-out. This paper shows that every Dicke state whose weight is only polylogarithmic in n can already be prepared inside QAC⁰ with polynomially many ancillas. More generally, any weight-k Dicke state needs only FANOUT gates of width min(k,n-k). Combined with known hardness results, this yields a tight equivalence: for k ≤ n/2 the state is preparable in QAC⁰ if and only if FANOUT_k itself lies in QAC⁰. The same limited-fan-out toolkit also prepares every symmetric state supported on weights at most k, and every O(log n)-qubit state once a coherent QRAM gate is allowed.

What carries the argument

A limited-fanout state-synthesis toolkit for QAC⁰ that reduces Dicke-state (and more generally symmetric-state) preparation to coherent counting and indexing steps whose only non-local resource is FANOUT of width min(k,n-k) (or QRAM_n for small systems).

What would settle it

Exhibit either a QAC⁰ circuit (poly(n) ancilla, O(1) depth, only unbounded Toffolis) that prepares a weight-ω(polylog n) Dicke state, or a proof that no such circuit exists even for weight (log n)^c for every constant c; either result would break the claimed tight characterization.

Watch

Extended reading notes

Core claim

An n-qubit Dicke state of weight k can be prepared with FANOUT gates of width only min(k,n-k). Consequently every polylog(n)-weight Dicke state lies in QAC⁰, and for k ≤ n/2 the same state lies in QAC⁰ if and only if FANOUT_k does. The same toolkit prepares every n-qubit symmetric state of weight at most k with FANOUT_k, and every O(log n)-qubit state with QRAM_n (which itself sits in QAC⁰_f).

Load-bearing premise

The intermediate coherent counting and indexing steps used by the toolkit truly stay inside constant depth and use only polynomially many ancillas under the standard QAC⁰ gate set, without secretly needing larger fan-out.

Editorial extensions

If this is right

  • Any quantum algorithm whose only non-local ingredient is a polylog-weight Dicke state can be realized with constant-depth QAC⁰ circuits plus poly(n) ancilla.
  • For every k ≤ n/2 the complexity of preparing the weight-k Dicke state is exactly the complexity of realizing FANOUT_k inside QAC⁰.
  • Every symmetric n-qubit state supported on Hamming weights ≤ k becomes preparable once FANOUT_k is available.
  • Every O(log n)-qubit pure state becomes preparable once a coherent QRAM_n gate is available, and that gate itself lies in the slightly stronger class QAC⁰_f.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If future hardware can implement moderate-width fan-out more cheaply than full n-bit fan-out, the equivalence immediately supplies a practical route to all moderate-weight Dicke states.
  • The same limited-fanout counting primitives may let other permutation-symmetric or low-weight combinatorial states (e.g., certain Dicke-state superpositions used in quantum sensing) enter QAC⁰ without new ideas.
  • A separation between QRAM_n and FANOUT_n, if one exists, would separate the power of preparing small arbitrary states from the power of preparing high-weight Dicke states.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 2 minor

Summary. The manuscript (as described by its abstract and title) claims that n-qubit Dicke states of polylogarithmic weight can be prepared in QAC⁰—constant-depth circuits with unbounded-width Toffoli gates and poly(n) ancilla—without the full FANOUT_n gate used in prior work. More generally, any weight-k Dicke state is said to be preparable using only FANOUT_{min(k,n−k)}, yielding a tight characterization: for k ≤ n/2, weight-k Dicke preparation lies in QAC⁰ if and only if FANOUT_k does. A limited-fanout state-synthesis toolkit is claimed to further give (i) all n-qubit symmetric states supported on weight ≤ k via FANOUT_k, and (ii) all O(log n)-qubit states via QRAM_n (a coherent indexing resource weaker than FANOUT_n and implementable in QAC⁰_f).

Significance. If the constructions and the equivalence hold with true O(1) depth and only the stated fanout, the result would be a genuine advance in quantum circuit complexity: the first super-constant-weight Dicke states in QAC⁰, a clean resource characterization linking Dicke preparation to FANOUT_k, and a reusable limited-fanout toolkit with applications to symmetric-state synthesis and small-system state preparation via QRAM. That would matter both for the theory of constant-depth quantum circuits and for NISQ-motivated questions about which global operations suffice for states used in algorithms such as Decoded Quantum Interferometry. The claimed tightness (upper bound matching recent hardness) is especially valuable if the ancilla/depth accounting is correct.

major comments (3)
  1. The supplied full-manuscript body is not the paper under review. The CACHEABLE source text is the unrelated empirical ML paper “Benchmarking Optimizers for MLPs in Tabular Deep Learning” (arXiv:2604.15297), complete with tables on Muon/AdamW, TabM, and Optuna search spaces. None of the QAC⁰ circuit constructions, lemmas, ancilla counts, or fanout bounds for Dicke states appear. Without the actual body, the central claims cannot be audited.
  2. Load-bearing premise (abstract toolkit claim): the limited-fanout state-synthesis toolkit must realize coherent counting/indexing and uniform superpositions over weight-k strings in true O(1) depth with only poly(n) ancilla and gates no stronger than unbounded Toffolis plus FANOUT_{min(k,n−k)}. Intermediate steps that silently re-introduce FANOUT_n or super-constant depth would collapse both the polylog-weight QAC⁰ result and the claimed equivalence. This accounting is uncheckable from the abstract alone and is absent from the provided body.
  3. Tight characterization (abstract): “for k ≤ n/2, weight-k Dicke is in QAC⁰ iff FANOUT_k ∈ QAC⁰” combines the new upper bound with “recent hardness results.” The reduction direction and the precise statement of those hardness results (including ancilla model and exact gate set) must be verified in the manuscript; they are not present in the supplied text.
minor comments (2)
  1. Abstract notation: QAC⁰_f and QRAM_n are introduced without a one-line definition of the fanout/indexing gate model; a short formal definition early in the introduction would help non-specialists.
  2. Abstract claim “first QAC⁰ construction of any super-constant-weight n-qubit Dicke state” should cite the prior FANOUT_n-based constructions explicitly once the correct body is available, so the resource gap is precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detectable: abstract is a standard circuit-complexity upper/lower characterization; supplied full text is the wrong paper, so no load-bearing reduction can be exhibited.

full rationale

The target paper (Dicke states / QAC0) is available only via its abstract. That abstract states constructive upper bounds (polylog-weight Dicke states in QAC0; weight-k Dicke via FANOUT_min(k,n-k)) and a tight characterization obtained by combining those constructions with external hardness results. None of the six circularity patterns apply on the face of the abstract: Dicke states and QAC0/FANOUT are standard independent objects, not defined in terms of each other; there is no fitted parameter renamed as a prediction; and no uniqueness theorem or ansatz is imported from the authors' own prior work in a load-bearing way. The CACHEABLE full manuscript is an unrelated tabular-optimizer benchmark (arXiv:2604.15297), so intermediate circuit constructions, ancilla accounting, and any self-citations cannot be inspected. Per the hard rules, circularity may be claimed only when a specific reduction can be quoted; none can. Therefore the honest finding is no significant circularity (score 0), with empty steps.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

Abstract-only review of a quantum circuit-complexity paper. Load-bearing background is the standard QAC⁰ model (constant-depth circuits with arbitrary-width Toffolis, poly ancilla), the definition of Dicke states, and cited hardness results for FANOUT in QAC⁰. No free parameters or fitted constants appear. Invented entities are limited to the authors' limited-fanout toolkit and the use of QRAM_n as a resource; neither is a physical postulate.

assumptions (3)
  • domain assumption QAC⁰ consists of constant-depth quantum circuits with arbitrary-width Toffoli gates and poly(n) ancilla, without free FANOUT_n.
    Standard definition of the model in which the main upper bounds are claimed.
  • domain assumption Recent hardness results imply that FANOUT_k ∉ QAC⁰ for the relevant k unless the stated equivalence fails.
    Abstract says the tight characterization combines the new upper bound with recent hardness; those hardness results are taken as given.
  • standard math Standard quantum circuit model (unitaries, ancilla initialization/cleanup, Hamming-weight subspaces).
    Background for state preparation and symmetric subspaces.
invented entities (2)
  • Limited-fanout state-synthesis toolkit for QAC⁰
    purpose: Prepare weight-k Dicke states, low-weight-supported symmetric states, and (with QRAM) small arbitrary states in constant depth with restricted fanout.
    Authors' technical contribution; existence and correctness are internal to the paper and not independently evidenced from the abstract.
  • QRAM_n as a coherent indexing resource weaker than FANOUT_n
    purpose: Prepare arbitrary O(log n)-qubit states in constant depth; claimed implementable in QAC⁰_f.
    Positioned as a potentially weaker primitive; independent status relative to FANOUT is part of the claim, not established outside the paper here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$." pith.science (2026). https://pith.science/paper/6Q3QHS5F

@misc{pith2026260415298,
  author       = {Pith},
  title        = {Pith review of: Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6Q3QHS5F}},
  note         = {Machine review of arXiv:2604.15298}
}
abstract

An $n$-qubit Dicke state of weight $k$, is the uniform superposition over all $n$-bit strings of Hamming weight $k$. Dicke states are central to quantum algorithms exhibiting speedups, such as Decoded Quantum Interferometry (Jordan et al., \emph{Nature}, 2025). In the NISQ era, quantum hardware is constrained by both depth and locality, motivating the question of which global operations suffice to prepare such states. QAC$^0$, the quantum analogue of AC$^0$, minimally extends local $O(1)$-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates. We show that Dicke states of $\mathrm{polylog}(n)$ weight can be prepared in QAC$^0$. This gives the first QAC$^0$ construction of any super-constant-weight $n$-qubit Dicke state, since previous constructions relied on the much more powerful FANOUT$_n$ gate. In general, we show that any weight-$k$ Dicke state can be constructed using FANOUT$_{\min(k,n-k)}$ gates. Combined with recent hardness results, this yields a tight characterization: for $k \leq n/2$, a $n$-qubit weight-$k$ Dicke state can be prepared in QAC$^0$ if and only if FANOUT$_k$ $\in$ QAC$^0$. We develop a limited-fanout state-synthesis toolkit for QAC$^0$ that yields further constant-depth, poly$(n)$-ancilla constructions: 1. Every $n$-qubit symmetric state supported on Hamming weight $\leq k$ can be prepared using FANOUT$_k$ gates. 2. Every $O(\log n)$-qubit state can be prepared using quantum random-access memory (QRAM$_n$), which refers to a coherent indexing gate. QRAM$_n$ is a potentially weaker resource than FANOUT$_n$ and can be implemented in QAC$^0_f$.

Figures

Figures reproduced from arXiv: 2604.15298 by the authors.

Figure 1
Figure 1. Visualization of the bucket occupancy of ℓ = k 3 buckets (left) and the corresponding n = mk3 -qubit state on each bucket obtained via a controlled-W preparation on each group of m qubits (right). This gives us an equal superposition over all strings of weight k where each bucket has at most one 1. In order to show that this state has constant fidelity with |Dn k ⟩, it suffices to show that a uniformly random string… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures

    quant-ph 2026-05 unverdicted novelty 5.0 of 10

    Large qLDPC blocks in distributed quantum computing enable Pauli-based computation to run up to 10x faster than surface codes for optimization algorithms by using spare nodes to bypass serialization bottlenecks.

Reference graph

Works this paper leans on

6 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Aaron Defazio, Xingyu Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, and Ashok Cutkosky

    URLhttps://arxiv.org/abs/1910.05446. Aaron Defazio, Xingyu Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, and Ashok Cutkosky. The road less scheduled.�������� �� ������ ����������� ���������� �������, 37:9974–10007,

    arXiv 1910

  2. [2]

    Yury Gorishniy, Ivan Rubachev, and Artem Babenko

    URL https://arxiv.org/abs/2506.16791. Yury Gorishniy, Ivan Rubachev, and Artem Babenko. On embeddings for numerical features in tabular deep learning. In�������,

    arXiv

  3. [3]

    Keller Jordan, Jeremy Bernstein, Brendan Rappazzo, @fernbear.bsky.social, Boza Vlado, You Jiacheng, Franz Cesista, Braden Koszarsky, and @Grad62304977

    URLhttps://arxiv.org/abs/1803.05407. Keller Jordan, Jeremy Bernstein, Brendan Rappazzo, @fernbear.bsky.social, Boza Vlado, You Jiacheng, Franz Cesista, Braden Koszarsky, and @Grad62304977. modded-nanogpt: Speedrunning the nanogpt baseline, 2024a. URLhttps://github.com/KellerJordan/modded-nanogpt. Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz ...

    arXiv

  4. [4]

    Rikiya Takehi, Benjamin Clavié, Sean Lee, and Aamir Shakir

    Accessed: 2026-01-18. Rikiya Takehi, Benjamin Clavié, Sean Lee, and Aamir Shakir. Fantastic (small) retrievers and how to train them: mxbai-edge-colbert-v0 tech report.����� �������� ����������������,

    2026

  5. [5]

    Table 3: Comparison of Muon with Muon EMA on MLP.�score is the mean relative unified score (%) with respect to AdamW; the parenthesized value shows the improvement over AdamW

    We can see that EMA provides only a marginal gain in relative score and no gain in the overall amount of wins over AdamW. Table 3: Comparison of Muon with Muon EMA on MLP.�score is the mean relative unified score (%) with respect to AdamW; the parenthesized value shows the improvement over AdamW. W/T/L counts are based on Welch’s�-test (� � � ���) across ...

    2025

  6. [6]

    # Train”, “# Val

    featuring industrial datasets with temporal train-test splits. Together, these cover a diverse range of domains, sizes, and task types. Table 4: Extended properties of datasets used in our study. Here, “# Train”, “# Val”, “# Test” denotes the size of the corresponding dataset split; similarly, “# Num”, “# Bin”, “# Cat” denotes the number of numerical, bin...

    2025

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.