REVIEW 2 major objections 3 minor 2 cited by
Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits
T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Log-depth circuits prepare Hamming-weight states optimally
desk verdict Plausible optimal-depth results for HWP state preparation, but the abstract alone can't carry a verdict; worth sending to referees. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Hamming-weight-preserving state, a superposition supported on all n-bit strings with exactly k ones (for k=2, the edges of a simple undirected graph). The construction uses ancillary qubits to parallelize the assignment of amplitudes across the binom(n,k)-dimensional subspace, reducing circuit depth from polynomial to logarithmic in the number of basis states; the matching Omega(log binom(n,k)) depth and Omega(binom(n,k)) size lower bounds show this parallelization is the best possible.
What would settle it
Find or construct a family of HWP states on n qubits with k=2 (graph states with m=O(n) edges) whose preparation from |0>^n requires circuit depth omega(log n) even when an unbounded number of ancillary qubits is available; this would contradict the claimed O(log n) upper bound. Conversely, exhibiting any k>=2 circuit family with depth o(log binom(n,k)) or size o(binom(n,k)) would refute the claimed lower bounds.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is a constructive upper bound paired with a matching lower bound: for any fixed Hamming weight k, an n-qubit HWP state |psi> = sum_{HW(x)=k} alpha_x |x> can be prepared from |0>^n by a circuit of depth O(log binom(n,k)) and size O(binom(n,k)) using O(binom(n,k)) ancillary qubits, and no circuit can do asymptotically better in depth or size. For k=2, the graph-structured case, the depth is O(log n) with O(m) ancilla, where m is the number of edges, and this improves to zero ancilla for trees and grids. The lower bounds hold for every k>=2, so the algorithms are near-optimal.
Load-bearing premise
The logarithmic depth guarantee assumes the amplitude coefficients can be supplied to the circuit as precomputed parameters free of depth cost; if the coefficients must be loaded into the circuit during execution, the stated depth could be exceeded.
Editorial extensions
If this is right
- For any fixed k, HWP states can now be prepared in asymptotically optimal depth and size, removing a bottleneck for algorithms that use these states as inputs.
- Graph-structured states with m edges are preparable in O(log n) depth; for tree- and grid-structured graphs the circuit needs no ancillary qubits at all.
- The lower bounds close the question for HWP states: any k>=2 requires Omega(log binom(n,k)) depth and Omega(binom(n,k)) size, so further improvements must come from changing the state family or allowing approximations.
- These results give concrete resource counts for quantum machine learning and Hamiltonian simulation subroutines that rely on HWP states.
Reading between the lines
- The ancilla-assisted parallelization pattern may extend to other state families whose basis set forms a combinatorial class, such as superpositions over matchings or independent sets, though the paper does not claim this.
- The zero-ancilla results for trees and grids suggest that sparse or locally structured graphs may generally admit ancilla-free logarithmic-depth preparation, a testable hypothesis for other graph families.
- Because the abstract does not specify how the coefficients alpha_x are loaded, the claimed depth is for the synthesis stage; in a practical setting where amplitudes arrive as classical data, the total end-to-end depth may include a coefficient-loading overhead.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper claims efficient quantum circuits for preparing Hamming-weight-preserving (HWP) states on n qubits, i.e., superpositions over computational basis states of fixed Hamming weight k. The abstract reports three results: (i) for graph-structured states (k=2) specified by an m-edge simple undirected graph, a preparation circuit of O(log n) depth with O(m) ancillary qubits, with the ancilla count reduced to zero for tree-structured and grid-structured graphs; (ii) for general HWP states with k >= 3, a preparation circuit of O(log binom(n,k)) depth using O(binom(n,k)) ancillary qubits and O(binom(n,k)) size; and (iii) lower bounds of Omega(log binom(n,k)) depth and Omega(binom(n,k)) size for all k >= 2, establishing that the constructions are asymptotically optimal. The available manuscript contains only the abstract; no circuit constructions, proofs, or gate-level arguments are provided.
Significance. If the claimed results hold, they would constitute a meaningful advance in quantum state preparation. Current generic state preparation can achieve logarithmic depth only at the cost of exponentially many ancillary qubits; the paper promises polynomial-ancilla logarithmic-depth circuits for a structured but nontrivial class of states used in quantum machine learning, together with matching lower bounds. The asymptotic claims are internally consistent and plausible: the size lower bound is consistent with parameter counting, and the depth upper bound is consistent with parallelization of combination amplitudes. The paper also makes precise, falsifiable complexity statements, which is a strength. However, because the review copy contains no technical content beyond the abstract, I cannot verify any of the central constructions or proofs, and the significance assessment must be conditional.
major comments (2)
- [Abstract, graph-structured states (k=2)] The central claim of O(log n)-depth preparation with O(m) ancillary qubits for arbitrary graph-structured states, and the zero-ancilla specializations for trees and grids, is stated without any algorithmic description. The transition from O(m) ancillas for general graphs to zero ancillas for trees/grids is nontrivial and load-bearing: it requires showing how edge amplitudes are rotated in parallel and how ancillas can be reused or eliminated in these restricted topologies. Without a circuit-level construction or at least a proof sketch, the claim cannot be checked from the submitted text.
- [Abstract, lower bounds] The abstract asserts matching lower bounds of Omega(log binom(n,k)) in depth and Omega(binom(n,k)) in size for every k >= 2, and states that the upper bounds 'exactly coincide' with them. No proof of either lower bound appears in the available text. The size lower bound likely follows from parameter counting, but the depth lower bound is not immediate: it requires a formal argument ruling out shallower circuits that use the same number of gates, in a model where classical parameters can set arbitrary gate angles. As submitted, the optimality claim is unverified.
minor comments (3)
- [Abstract, input model] The state is defined with coefficients alpha_x, but the abstract does not specify how these coefficients are supplied. In the standard circuit-synthesis model, gate angles are free classical parameters, so coefficient loading does not add depth; the authors should state this model explicitly to avoid ambiguity, especially since the O(log binom(n,k)) depth bound depends on it.
- [Abstract, wording] Several passages are grammatically awkward, e.g., 'the depth of preparation circuit for the most general state has been optimized to approximately optimal' and 'few log-depth preparation algorithms assisted by polynomial ancillary qubits have been come up with.' The text should be polished for clarity.
- [Abstract, notation] The phrase 'O(log{{n \choose k}})-depth' is clear, but the lower bound statement 'Omega(log{{n \choose k}})-depth and Omega({{n \choose k}})-size' should specify the gate set and whether ancilla qubits are counted in the size measure.
Circularity Check
No significant circularity identified in the available abstract
full rationale
The review is based solely on the abstract (arXiv:2508.14470); no full derivation, equations, or citation chain is available to audit. Within the abstract, the claimed results are constructive upper bounds (O(log n) and O(log C(n,k)) depth with O(m) or O(C(n,k)) ancillary qubits) and matching lower bounds (Omega(log C(n,k)) depth and Omega(C(n,k)) size). There is no fitted parameter renamed as a prediction, no definition that presupposes the target theorem, and no load-bearing self-citation visible. The concern that coefficient amplitudes alpha_x must be loaded as classical parameters is a standard assumption in the circuit model (gate angles are free classical parameters during synthesis) and does not constitute circularity under the stated hard rules. Without full text, no concrete circular step can be exhibited, and the default honest finding is no significant circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption The quantum circuit model with ancillary qubits and a universal gate set is the model in which depth, size, and ancilla counts are defined.
- domain assumption The nonzero amplitudes alpha_x (and the m edges for k=2) are available as classical input that can be encoded into rotation angles without extra query cost in the depth bound.
- domain assumption The lower-bound proof and upper-bound construction use the same asymptotics and gate model so that the matching bounds are comparable.
Cite this review
Pith. "Pith review of Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits." pith.science (2026). https://pith.science/paper/XHSSDNO3
@misc{pith2026250814470,
author = {Pith},
title = {Pith review of: Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits},
year = {2026},
howpublished = {\url{https://pith.science/paper/XHSSDNO3}},
note = {Machine review of arXiv:2508.14470}
}
abstract
Quantum state preparation is a critical task in quantum computing, particularly in fields such as quantum machine learning, Hamiltonian simulation, and quantum algorithm design. The depth of preparation circuit for the most general state has been optimized to approximately optimal, but the log-depth appears only when the number of ancillary qubits reaches exponential. Actually, few log-depth preparation algorithms assisted by polynomial ancillary qubits have been come up with even for a certain kind of non-uniform state. We focus on the Hamming-Weight-preserving states, defined as $|\psi_{\text{H}}\rangle = \sum_{\text{HW}(x)=k} \alpha_x |x\rangle$, which have leveraged their strength in quantum machine learning. Especially when $k=2$, such Hamming-Weight-preserving states correspond to simple undirected graphs and will be called graph-structured states. Firstly, for the $n$-qubit general graph-structured states with $m$ edges, we propose an algorithm to build the preparation circuit of $O(\log n)$-depth with $O(m)$ ancillary qubits. Specifically for the $n$-qubit tree-structured and grid-structured states, the number of ancillary qubits in the corresponding preparation circuits can be optimized to zero. Next we move to the preparation for the HWP states with $k\geq 3$, and it can be solved in $O(\log{{n \choose k}})$-depth using $O\left({n \choose k}\right)$ ancillary qubits, while the size keeps $O\big( {n \choose k} \big)$. These depth and size complexities, for any $k \geq 2$, exactly coincide with the lower bounds of $\Omega (\log{{n \choose k}})$-depth and $\Omega ({n \choose k})$-size that we prove lastly, which confirms the near-optimal efficiency of our algorithms.
Forward citations
Cited by 2 Pith papers
-
Quantum states supported by matroids
For states whose support is the set of bases of a matroid, genuine multipartite entanglement is tied to matroid connectivity, measurement to minors, and bit-flip duality to matroid duality.
-
Spin-$s$ $U(1)$-eigenstate preparation
A Gray-code-based quantum circuit prepares arbitrary fixed-digit-sum (U(1)) eigenstates of spin-s chains, yielding the first preparation of spin-s XXX Bethe states.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.