- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes Quantum Spectral Formula Networks (QSFN). A QSFN represents a target function as a formula tree: leaves are univariate spectral functions, and internal nodes apply bounded multiaffine composition rules. The tree is then compiled into a quantum circuit whose output is the Pauli- expectation at the root.
The authors characterize the composition rules supported by the independent-expectation interface, and provide resource recurrences, error propagation, universal approximation, and approximation guarantees for low-rank separable analytic functions. The main theoretical result constructs a family of bounded continuous functions whose norm does not vanish with dimension. At fixed error , any Fourier sum with arbitrary integer frequencies and complex coefficients requires exponentially many spectral terms. In contrast, QSFN implements the function exactly with a quadratic number of queries in the local signal-query model, and attains the asymptotic query lower bound for exact implementation. The paper also gives a separate exponential lower bound for SAQNN's native modulus readout.
Through matched-error comparisons, exact expansion controls, and spectral lower-bound certificates, the experiments demonstrate the compiled-resource benefits of preserving factorized structure.
Critical strengths
-
The separation at fixed absolute error has real substance. The Jackson leaves remain bounded with near-unit energy, which keeps the norm of high-dimensional products from vanishing and the approximation task from degenerating. Combined with the spread-out Fourier coefficients, this yields a lower bound on the best sparse Fourier approximation, not merely on a particular training or truncation strategy. Unit normalization also ensures that, under ideal independent sampling, the bound on the number of measurements needed for a fixed absolute accuracy and confidence level does not grow with dimension.
-
The framework provides a unified analysis of resources and errors. Local approximation, composition semantics, circuit resources, normalization, and error propagation are brought into a single framework. The explicit link between normalization and measurement cost is particularly helpful for distinguishing representation complexity from output-estimation cost.
-
The experimental controls and transparent disclosure are commendable. QSFN-Expanded and QSFN-Factorized keep the same function and coefficients, which effectively isolates the role of factorized structure. The main table uses a strengthened SAQNN implementation with additional branch fusion, rather than relying only on a weaker baseline. The supplementary code, archived results, and labeling of resource provenance provide a fairly complete basis for independent verification. The authors also clearly disclose the width cost, the task with no advantage, and the boundary between recurrence-based and actually transpiled results.
Critical weaknesses
-
The scope of the main conclusions is narrower than the stated significance. The Fourier term-count lower bound cannot be directly regarded as a gate-count lower bound for general PQCs. A corresponding circuit-cost lower bound follows only for architectures that pay implementation resources separately for each spectral term. On the other hand, in the paper's setting of classical inputs, known leaf polynomials, and explicit formulas, the target can be evaluated efficiently on a classical computer at a cost proportional to the size of the formula description. The paper does not yet adequately explain the application value of this quantum implementation, or its relation to direct classical evaluation and to other compact quantum representations. This does not negate the representational separation, but it limits how far the result generalizes to quantum approximation cost in general.
-
The technical novelty still needs to be decomposed more clearly. Expectation encoding, CNOT multiplication, and weighted arithmetic are directly related to EHands. The multiaffine characterization for independent inputs is closely related to the probabilistic and spectral-transform analyses of stochastic computing. At the level of the root -measurement distribution, the paper's composition layer can be reproduced by measuring the leaves and then applying classical post-processing with auxiliary random coins. The advantage of factorized structure over expanded representations also has precedents in classical depth-separation results for deep versus shallow networks. Although the authors cite some related work, they do not yet adequately separate the technical increments of the existing components, the interface characterization, the compilation guarantees, and the lower-bound construction.
-
The resource guarantees apply to formula trees and do not yet cover general shared computation graphs. Here one needs to distinguish full-state broadcasting from reuse under the expectation interface. Copying a measured classical bit preserves the expectation of each copy but introduces correlation, so it cannot replace independent copies. For example, XOR-ing a bit with its own copy yields an output expectation identically equal to 1, rather than the square of the original expectation. The appendix discusses re-preparation, estimate-then-re-encode, and stronger interfaces, but the main text does not yet adequately explain how these limitations affect the resource conclusions.
-
The experimental evidence mainly supports compilation efficiency under known structure, and its coverage is limited.
- E1 contains only two-dimensional tasks, the QSFN side consists entirely of deterministic constructions, and part of the depth gain comes with doubled logical width. No learning-level benefit can therefore be inferred from it.
- The high-dimensional expanded resources in E2 come from validated recurrences, and the target satisfies . The very large exact compression ratios therefore do not directly demonstrate an estimation benefit under finite sampling.
- The native lower-bound certificates in E3 are not yet sufficient to establish a resource advantage within the tested dimensions, and the crossover point comes from analytic extrapolation beyond the tested range.
Questions for authors
Among the following questions, Q1 and Q2 carry the most weight for my score. The remaining questions are mainly intended to clarify the stated conclusions and the experimental reporting.
-
Application value of the quantum implementation and the access model. In the setting of classical inputs and known leaf polynomials, the cost of direct classical evaluation is already of the same order as the formula description size. Please give a testable quantum-signal access task that connects directly to the existing framework, and address the following:
- (a) Access model: Are the input values available? What are the respective costs of state preparation, inverse operations, controlled calls, and independent copies? For example, in a model with access only to a hidden-phase oracle , which compilation guarantees and resource separations still hold?
- (b) Necessity of a coherent interface: If only the final scalar output at the root is required, leaf measurement plus classical randomized post-processing can reproduce the output distribution of the composition layer. Please address this alternative directly, and explain why the task still requires a coherent formula implementation.
- (c) Subsequent coherent calls: If the target application uses the QSFN output in subsequent coherent operations, please give at least one complete usage scenario, together with full resource accounting under the same access model.
I do not require the authors to demonstrate general quantum advantage. However, a response that merely relabels the inputs as "unknown quantum signals," or restates that Theorem 1 and Theorem 2 apply to quantum states, would not be sufficient to change my assessment of Weakness 1.
-
Technical increment and shared reuse. Please compare QSFN item by item with EHands and with the stochastic-computing framework. For expectation encoding, multiplication, weighted sums, the multiaffine interface, and the compilation guarantees, identify the counterpart in prior work and the technical increment of this paper. Regarding shared reuse, please distinguish the independence requirement, the correlation of classical copies, and the full-state broadcasting requirement, and explain which forms of reuse can preserve the resource benefits.
-
Please clearly distinguish query optimality for exact implementation from query cost at fixed error. Take as an example the fixed target used in E3 at , with Jackson order and leaf degree 151. An analytic inner-product calculation shows that replacing the leaf with a degree-29 Jackson leaf already achieves an error of about 0.4923. Under the same construction, this corresponds to 928 ideal logical queries, compared with 4,832 for the original exact construction. This is only a feasible upper bound that has not been actually synthesized. It does not refute the quadratic asymptotic scaling, but it indicates that a lower-cost fixed-error operating point exists. Can the authors report the corresponding resource bounds, and state whether a nontrivial query lower bound exists at fixed error?
-
What role does introducing NAND play in the separation? For the pure product , the norm and coefficient bounds in the paper seem to directly yield while retaining the quadratic QSFN query cost. Please compare the conclusions supported by the pure-product construction with those supported by the current construction.
-
What is the operational meaning of the exact compression ratios in E2 under finite sampling? Given , can the authors jointly report the target magnitude, the measurement budget, and the output error, so as to distinguish exact representational compression from estimation benefits at fixed absolute or relative error?
-
Please summarize the existing O3 results in the main text and distinguish three cases: circuits with bound numerical inputs, reusable parameterized circuits, and the opaque-oracle model. Please state the scope of each resource conclusion, make the reported maximum depth improvement consistent between the abstract and the main text, and, for the native comparison, clearly distinguish certificates within the tested dimensions from extrapolation beyond the tested range.
7 comments
Q2: Technical Advances over Prior Arithmetic and Exact Reuse
Q2. Technical contribution and reuse
Our addition to existing arithmetic is a formula-level resource and stability guarantee (Theorem 2) and an exact test for when sharing preserves the result (Proposition 7). We added a comparison with EHands and stochastic computing and a circuit that saves one input preparation while remaining exact. Theorem 2 gives circuit costs, readout scale, and the effect of local errors on the output. Higher accuracy can come from higher local degree while the formula's composition stays the same (Sec. 1.1, App. A, Table 2, and App. C.3).
| Component | Prior result | Role in QSFN |
|---|---|---|
| Expectation encoding | Pauli- encoding in EHands (Sec. II); probability and bipolar encodings in stochastic computing | Local spectral leaves with explicit scales |
| Multiplication | Reversible multiplication in EHands (Sec. III); products of independent stochastic inputs | Products composed with the spectral leaves |
| Weighted sums | EHands weighted arithmetic; independent-selector addition in stochastic computing | Signed sums and products in one recursion for scale, cost, and error |
| Bounded multiaffine rules | Multivariate Bernstein interpolation (Qian and Riedel) | Characterization for signed expectations and an exact joint-moment test for reuse |
| Compilation | Reversible polynomial circuits, resource counts, and parallel trees in EHands (Sec. IV, App. E) | Formula compilation linking local degree and approximation to resources, normalization, and error propagation |
QSFN uniformly approximates any continuous function on a compact set. For supplied analytic factors, its error bounds give the local degree, formula size, and root scale; the compiler and stability results translate these into circuit resources and output error. On the target families in Theorems 5–6, preserving the formula gives exact realization with quadratically many local queries, while the compared global spectral representations need exponentially many terms even at fixed error.
Sharing works when the next operation needs only joint statistics that the shared outputs still provide. For , prepare and independently once. A CNOT gives output expectations and . These outputs can be correlated: an independent selector still gives the correct weighted sum. The circuit uses one CNOT, one selector rotation, and one controlled swap, combining the product-with-memory relation from EHands with selector addition. The signal cost falls from for separate branches to (App. C.3).
Copying one measured sign gives , generally different from the obtained from independent preparations. Broadcasting is a separate task: both outputs must retain the full input state as their marginals. Even for a commuting family that can be broadcast, the next operation still needs the right joint statistics.
For a rule , with and , Prop. 7 gives the reuse error:
A particular rule is exact if and only if ; deviations can cancel. Exactness for all bounded multiaffine rules requires independent computational-basis outcomes, even though the quantum state can be entangled (App. C.3, pp. 17–18). Known phase tables and circuit descriptions can be reused; we charge every preparation actually executed. The separation already counts all independent leaf preparations, so its bounds stand, and compatible sharing can save further preparations.
We hope the comparison and the explicit reuse circuit make clear what these results add to the existing arithmetic.
Q3–Q6: Fixed-Error Queries, Pure Products, Sampling, and O3 Results
Q3. Exact evaluation and query cost at fixed error
Exact evaluation uses 4,832 local calls in 32 dimensions; allowing error under direct signed-expectation readout puts the minimum between 176 and 928. For the same target, we tested the lower-degree construction you suggested and added a matching-tolerance lower bound (Secs. 3.4 and 4.4, App. D.4).
Replacing degree-151 leaves with degree-29 polynomials gives a 928-call construction with certified error in . Bandwidth projection gives the 176-call lower bound at the same tolerance. Thus 928 is an achievable upper bound. App. D.4, Eq. (58) gives the finite-dimensional certificate, and Eq. (60) proves an fixed-error local-query lower bound for the theoretical family. Both use the original E3 local-signal query unit.
Q4. Is a pure product sufficient, and what does NAND add?
A pure product already gives an exponential separation; NAND shows that bounded pairwise interactions can give it too. We added this comparison at the same leaf budget (Sec. 3.4, App. D.5, Table 3).
For , the Fourier term count for error satisfies for . Both constructions use local queries. The pure product uses CNOTs to combine the leaves; NAND uses Toffolis and CNOTs. NAND also gives the simple norm and coefficient bounds used in the main text. App. D.5 gives the derivation and matched-budget comparison.
Q5. Target norm, normalization, and sampling in E2
E2 saves gates when compiling the same exact function; at fixed relative mean squared error, the number of shots still grows exponentially with dimension. We now give the sampling cost alongside the compilation result (Sec. 4.3, App. H.3).
In E2, , while both the quantum root scale and the sum of absolute Fourier coefficients equal one. The norm describes the size of the target; the root scale converts the expectation into a function value. The quantum state itself remains normalized.
With independent root samples per input, the integrated mean squared error is , or relative to the squared norm. Every shot requires fresh preparation, so its gates and queries are counted again. E3's targets have nonvanishing norm and support the fixed-error separation. See App. H.3, Eq. (83) and Table 7 for the sampling costs.
Q6. Optimization, circuit models, and extrapolation
The E2 savings survive level-3 optimization (O3). We now report in Sec. 4.3 that, at with all-to-all connectivity, QSFN-Factorized uses of SAQNN-Flat's two-qubit gates and of its two-qubit depth (App. H.3, Table 6; five seeds). The flat gate count comes from the verified level-0 recurrence, not from transpiling that circuit.
- Bound numerical inputs. E1's largest depth reduction is 12.06-fold at level 0 on (, both at numerical precision), now stated in both the abstract and Sec. 4.2. The earlier 10.5-fold value is for at matched grid error. E2 compiles templates at representative inputs or nondegenerate angles.
- Reusable parameterized circuits. One symbolic template can be used across inputs. The supplemental O3 checks at preserve input symbols and query counts in the preparation circuits; the bound-input ratios are reported separately.
- Opaque phase oracles. We count calls separately from known gates. In the E3 O3 comparison, QSFN uses about of the shared selector's known CNOTs and of its CNOT depth, while the shared selector makes fewer phase queries (Sec. 4.4). The full operation in Sec. 4.5 and App. I also counts inverse preparation, coefficient preparation, and reflections.
For native spectral-modulus readout, the certificates at evaluated dimensions and the analytic crossover are separate results. The tests go up to , where the certificate requires at least 445 native branches at error . The analytic branch lower bound and uniform query upper bound cross near , beyond those tests (Fig. 4(b), App. Fig. 13). Finite-sample tests and gate-noise analysis are reported separately (Apps. H.4 and F.4).
Thank you for focusing the discussion on the use and technical contribution of the circuit. We hope the new task, comparisons, and reuse criterion address your main concerns, and we would be grateful if you reconsidered your overall assessment and score in light of the revision.
Q1: Signal Access and Coherent Rotation with Unknown Phases
Thank you for asking what the circuit adds. We now compare a complete quantum operation with a strong measurement-first baseline under matched signal access and show when reuse can save a preparation without changing the result.
Q1. Quantum use, signal access, and downstream operations
We simulated an unknown-phase-driven coherent rotation using the original four-factor product. The operation must also work on data entangled with a reference. On the same 24 inputs, both methods meet the 10−8 target with 18 logical qubits. QSFN uses about 1/61.2 of the sine-window baseline's queries and 1/2.59 of its gate-plus-query count (Sec. 4.5, Fig. 5).
(a) What is available, and what does it cost?
QSFN and the sine-window baseline receive no numerical phase or leaf values. The formula, polynomials, and QSP phases are known. Access is through Pj(xj)=diag(1,eixj) and its inverse: one query per use, including powers.
The sine window uses m qubits and m−1 known two-qubit gates per phase, with no preparation queries. Estimation costs d(2m−1) queries (App. I.5); see (c) for the full rotation.
Uncontrolled Wj=eiθjZ=eiθjPj(−2θj) and its inverse suffice. Calls map one for one; global phases cancel in the full rotation. At xj=−2θj, gate counts, queries, error guarantees, quadratic local-query constructions, and fixed-error exponential lower bounds on Fourier terms and spectral-modulus branches carry over (Theorems 5–6, App. I.1).
(b) Can leaf measurements and classical processing replace the circuit?
QSFN lets the formula drive a coherent rotation directly, saving the queries needed for high-precision phase estimation. Independent leaf measurements and classical randomization reproduce the scalar distribution (Sec. 3.2), but a random rotation can dephase the data even with an unbiased angle. We added a task that applies e−iHZD, with H=(1+∏jϕn(xj))/2, even to data entangled with a reference. We match signal access and compare full-channel error per fresh input, counting all branches. On the same 24 four-phase inputs at target error 10−8, QSFN uses 8,568 vs. 524,284 queries and 204,153 vs. 529,373 known gates plus queries against the sine-window baseline (c).
Even with adaptive probes and forward, inverse, or controlled queries, acquiring a classical record first takes Ω(ϵ−1/2) worst-case queries for uniform error ϵ on a slice with nonzero response derivative (Prop. 8). The sine window attains this order; QSFN uses O(log(1/ϵ)/loglog(1/ϵ)) at fixed dimension and leaf degree (Apps. I.3–I.4).
(c) Complete operations and resource counts
We tested two uses of the same formula: a data-qubit rotation and a two-qubit interaction, with only two extra CNOTs, one extra data qubit, and no extra queries for the interaction. Both use the reversible preparation of B=∏jϕn(xj). The full rotation costs 6KcLB queries (LB=3dp; truncation order Kc). We count forward and inverse preparation, coefficient-state preparation, and reflections, and include leaf and gate synthesis errors.
At d=4 and target error 10−3, the interaction e−iHZD1ZD2 uses 18 logical qubits, 4,896 queries, and 93,171 known gates. The full output's concurrence differs from the target by at most 2.44×10−5 (Apps. I.2 and I.6, Fig. 17).
At d=4 and target error 10−8, the baseline uses linear-size sine-window preparation, estimates the phases, evaluates the same H, and rotates the data:
QSFN and the baseline use 195,585 and 5,089 known basis gates, respectively; their longest coherent subcircuits have depths 54,450 and 65,685. QSFN saves more queries than it adds gates. Each gate and query counts once; classical arithmetic is separate. The sine window costs less at moderate precision. Fig. 5 and App. I.6 (Table 10, Fig. 18) distinguish fixed-input results from uniform certificates for two dimensions and seven error targets.
We hope this complete task and matched comparison clarify the value of the coherent implementation.