acceptodds
Under review as a conference paper at ICLR 2027

Compositional Spectral Representations for Efficient Quantum Neural Approximation

Abstract

Universal approximation is now established for several quantum neural-network families, yet it does not determine the circuit cost of representing a structured target. Constructive spectral models compile global Fourier or Chebyshev expansions; products and compositions of simple local factors can make these expansions exponentially long while the generating computation remains small. We introduce stable quantum spectral formula networks (QSFN), which compile the bounded generating formula directly, making circuit resources follow formula complexity even when its global spectrum is exponentially long. Univariate spectral leaves expose signed Pauli-Z expectations, and internal vertices combine them through bounded maps that are affine in each input separately. We prove that these maps are exactly the transformations compatible with the interface, establish universal and quantitative analytic approximation, and give a deterministic circuit compiler with explicit query, gate, depth, normalization, and stability guarantees. For an explicit continuous bounded family, every fixed-error signed-flat Fourier approximation requires branches. QSFN gives an exact, locally query-optimal construction with unit normalization. Across three experiments, matched-error comparisons reduce entangling depth by up to 10.5-fold, exact semantic controls isolate factorization as the source of compression, and fixed-error tests reproduce the predicted polynomial-versus-exponential scaling. The results establish compositional structure as an independent determinant of quantum approximation cost.

Primary area:
learning theory
Keywords:
quantum neural networks, approximation theory, compositional structure, spectral methods, quantum circuit complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tHQtOpenReview ↗
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-ZZ 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 FdF_d whose norm does not vanish with dimension. At fixed L2L^2 error 0<ϵ<3/20<\epsilon<\sqrt{3}/2, 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
  1. 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.

  2. 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.

  3. 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
  1. 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.

  2. 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 ZZ-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.

  3. 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 ZZ 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.

  4. 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 ∥Pd∥22=2−d\|P_d\|_2^2=2^{-d}. 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.

  1. 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 Wj(θj)W_j(\theta_j), 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.

  2. 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.

  3. 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 d=32d=32, with Jackson order N=77N=77 and leaf degree 151. An analytic inner-product calculation shows that replacing the leaf with a degree-29 Jackson leaf already achieves an L2L^2 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?

  4. What role does introducing NAND play in the separation? For the pure product Bd=∏jϕd(xj)B_d=\prod_j\phi_d(x_j), the norm and coefficient bounds in the paper seem to directly yield n≥(9/16−ϵ2)(π2/4)d,ϵ<3/4,n\ge(9/16-\epsilon^2)(\pi^2/4)^d,\qquad \epsilon<3/4, while retaining the quadratic QSFN query cost. Please compare the conclusions supported by the pure-product construction with those supported by the current construction.

  5. What is the operational meaning of the exact compression ratios in E2 under finite sampling? Given ∥Pd∥22=2−d\|P_d\|_2^2=2^{-d}, 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?

  6. 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
AuthorsOpenReview ↗

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−810^{-8} target with 18 logical qubits. QSFN uses about 1/61.21/61.2 of the sine-window baseline's queries and 1/2.591/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)P_j(x_j)=\operatorname{diag}(1,e^{ix_j}) and its inverse: one query per use, including powers.

  • Preparation: For dd inputs with one degree-pp leaf per input, UBU_B encodes the product as an expectation. Cost: 3dp3dp queries and 5dp+5d−15dp+5d-1 known gates before decomposition.
  • Inverse: UB†U_B^\dagger undoes preparation at the same cost.
  • Controlled local signal: Three queries (one forward, two inverse), two Toffolis, and two Hadamards; the helper returns to zero.
  • Independent output: Rerun UBU_B at the same cost.

The sine window uses mm qubits and m−1m-1 known two-qubit gates per phase, with no preparation queries. Estimation costs d(2m−1)d(2^m-1) queries (App. I.5); see (c) for the full rotation.

Uncontrolled Wj=eiθjZ=eiθjPj(−2θj)W_j=e^{i\theta_j Z}=e^{i\theta_j}P_j(-2\theta_j) and its inverse suffice. Calls map one for one; global phases cancel in the full rotation. At xj=−2θjx_j=-2\theta_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−iHZDe^{-iHZ_D}, with H=(1+∏jϕn(xj))/2H=(1+\prod_j\phi_n(x_j))/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−810^{-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)\Omega(\epsilon^{-1/2}) worst-case queries for uniform error ϵ\epsilon on a slice with nonzero response derivative (Prop. 8). The sine window attains this order; QSFN uses O(log⁡(1/ϵ)/log⁡log⁡(1/ϵ))O(\log(1/\epsilon)/\log\log(1/\epsilon)) 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)B=\prod_j\phi_n(x_j). The full rotation costs 6KcLB6K_cL_B queries (LB=3dpL_B=3dp; truncation order KcK_c). We count forward and inverse preparation, coefficient-state preparation, and reflections, and include leaf and gate synthesis errors.

At d=4d=4 and target error 10−310^{-3}, the interaction e−iHZD1ZD2e^{-iHZ_{D_1}Z_{D_2}} 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−52.44\times10^{-5} (Apps. I.2 and I.6, Fig. 17).

At d=4d=4 and target error 10−810^{-8}, the baseline uses linear-size sine-window preparation, estimates the phases, evaluates the same HH, and rotates the data:

MethodQueriesKnown gates + queriesLogical qubitsMax. unconditional diamond error
Coherent QSFN8,568204,153186.353×10−106.353\times10^{-10}
Sine-window estimate then rotate524,284529,373187.663×10−97.663\times10^{-9}

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.

AuthorsOpenReview ↗

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).

ComponentPrior resultRole in QSFN
Expectation encodingPauli-ZZ encoding in EHands (Sec. II); probability and bipolar encodings in stochastic computingLocal spectral leaves with explicit scales
MultiplicationReversible multiplication in EHands (Sec. III); products of independent stochastic inputsProducts composed with the spectral leaves
Weighted sumsEHands weighted arithmetic; independent-selector addition in stochastic computingSigned sums and products in one recursion for scale, cost, and error
Bounded multiaffine rulesMultivariate Bernstein interpolation (Qian and Riedel)Characterization for signed expectations and an exact joint-moment test for reuse
CompilationReversible 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 F(x,y)=wx+(1−w)xyF(x,y)=wx+(1-w)xy, prepare xx and yy independently once. A CNOT gives output expectations xx and xyxy. 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 2Qx+Qy2Q_x+Q_y for separate branches to Qx+QyQ_x+Q_y (App. C.3).

Copying one measured sign SS gives E[S2]=1\mathbb E[S^2]=1, generally different from the z2z^2 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 G(z)=∑SγS∏i∈SziG(\boldsymbol z)=\sum_S\gamma_S\prod_{i\in S}z_i, with zi=tr⁡(ρZi)z_i=\operatorname{tr}(\rho Z_i) and ZS=∏i∈SZiZ_S=\prod_{i\in S}Z_i, Prop. 7 gives the reuse error:

ΔG=∑SγS[tr⁡(ρZS)−∏i∈Szi].\Delta_G=\sum_S\gamma_S\left[\operatorname{tr}(\rho Z_S)-\prod_{i\in S}z_i\right].

A particular rule is exact if and only if ΔG=0\Delta_G=0; 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.

AuthorsOpenReview ↗

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 L2L^2 error 1/21/2 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 [0.4922894015688955, 0.4922894015688956][0.4922894015688955,\,0.4922894015688956]. 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 Ω(d2)\Omega(d^2) 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 Bd=∏jϕd(xj)B_d=\prod_j\phi_d(x_j), the Fourier term count for L2L^2 error ϵ\epsilon satisfies n≥(9/16−ϵ2)(π2/4)dn\ge(9/16-\epsilon^2)(\pi^2/4)^d for ϵ<3/4\epsilon<3/4. Both constructions use dpdp local queries. The pure product uses d−1d-1 CNOTs to combine the leaves; NAND uses d/2d/2 Toffolis and d/2−1d/2-1 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, ∥Pd∥22=2−d\|P_d\|_2^2=2^{-d}, 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 NN independent root samples per input, the integrated mean squared error is (1−2−d)/N(1-2^{-d})/N, or (2d−1)/N(2^d-1)/N 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 d=8d=8 with all-to-all connectivity, QSFN-Factorized uses 1/384.441/384.44 of SAQNN-Flat's two-qubit gates and 1/2421.901/2421.90 of its two-qubit depth (App. H.3, Table 6; five seeds). The d=32d=32 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 f3f_3 (205/17205/17, both at numerical precision), now stated in both the abstract and Sec. 4.2. The earlier 10.5-fold value is for f1f_1 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 d=2,4d=2,4 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 d=8d=8 E3 O3 comparison, QSFN uses about 1/371/37 of the shared selector's known CNOTs and 1/2881/288 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 d=32d=32, where the certificate requires at least 445 native branches at error 1/161/16. The analytic branch lower bound and uniform query upper bound cross near d=64.8d=64.8, 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.

Reviewer_izedOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Stable Quantum Spectral Formula Networks (QSFN) compile a function’s local spectral factors and their composition directly, instead of expanding the function into global Fourier branches. Leaves expose signed Pauli-Z expectations, and independent child registers are combined through bounded multiaffine rules. The paper characterizes the compatible interface, provides a compiler with explicit resource accounting, proves universality and analytic approximation bounds, and separates approximation, implementation, and shot errors. For specified bounded function families, it proves exponential global Fourier-sum and native spectral-modulus branch-count lower bounds while QSFN uses quadratic local signal queries with unit normalization. Experiments compare matched-error constructions, control the effect of exact factorization, and test fixed-error scaling. Actual transpilation is distinguished from recurrence-based extrapolation. (Theorems 1–6; Proposition 4; Sections 4.1–4.3; Appendices C–H.)

Critical strengths
  1. The representation is specified precisely enough to support a concrete compiler. Theorem 1 characterizes the diagonal, Z-compatible multiaffine interface; Theorem 2 and Proposition 4 connect the construction to module assumptions and error accounting. This gives more useful guidance than a universality result alone. (Appendices C and F.)
  2. The theoretical separation is supported by a direct structural control. In E2, the same exact function and coefficients are represented in flat, expanded, and factorized forms. At d = 8, the compiled two-qubit gate counts are 24,572, 8,190, and 71. Together with the fixed-error lower bounds, this supports the benefit of preserving factorization in the stated setting. (Theorems 5–6; Appendix H, Table 3.)
Critical weaknesses
  1. The proved separation depends on the architecture and cost convention. Global Fourier terms and local signal queries are different resources. The native-modulus theorem brings the interfaces closer, but still lower-bounds branch count rather than matched physical execution cost. The results therefore need to be read alongside the separate gate, width, normalization, and sampling accounts. (Sections 3.2–3.4; Appendix F.)
  2. The evidence is stronger for compilation of known structure than for learning an unknown model. A tree is supplied through domain knowledge or a dictionary; the learning derivation assumes fixed structure. E1 compares deterministic oracle constructions, while E2 fully transpiles flat and expanded circuits only through d = 8. Larger values use recurrences. (Section 2; Appendix G; Sections 4.1–4.3; Appendix H.)
Questions for authors
  1. Which resource advantage is proved under a common convention? Please compare qubits, compiled gates and depth, precision synthesis, and final measurement costs where possible, while keeping the Fourier-term and local-query statements distinct. (Theorems 5–6; Appendix F.)
  2. How much prior structural knowledge is needed, and what is excluded from the cost of finding a suitable tree? Please relate the fixed-structure coefficient-learning result to the oracle comparisons. (Section 2, lines 155–156; Appendix G.)
  3. Please keep actual transpilation and extrapolation separate in the conclusions. The d = 32 ratio comes from recurrences; the main circuits use optimization level 0 and all-to-all connectivity. How do the savings change under the reported level-3 setting or restricted connectivity? (E2; Appendix H.3, Table 3.)
  4. What target properties predict a resource gain? E1 uses three two-variable functions, f2 shows no gain, and the oracle QSFN rows for f1 and f3 require more logical qubits. A less favorable structure would help explain this trade-off. (Figure 2; Appendix H, Tables 2–3.)
  5. Under what finite-shot and noise conditions do the depth or query savings remain useful? Appendix F notes exponentially increasing debiased variance in noisy product chains, and the native-modulus crossover in Figure 4(b) lies beyond the tested dimensions. Please distinguish measured robustness from asymptotic estimates. (Proposition 4; Appendices F.3–F.4; E3.)
7 comments
AuthorsOpenReview ↗

Q1: Proven Resource Separation and Compiled Circuit Costs

Thank you for asking how much of the theoretical advantage carries over to actual circuits. We added a same-target compilation comparison, a coherent-operation benchmark, and bounds on queries at fixed error. Below we explain what these results establish for each of your five questions.

Q1. What resource advantage is established under common assumptions?

At fixed approximation error, Theorems 5–6 show that global spectral representations of the two target families need exponentially many Fourier terms or spectral-modulus branches, respectively. QSFN realizes the corresponding targets exactly with quadratically many local signal queries. Spectral terms and branches count the size of a representation; neither is a gate or query count (Sec. 3.4, Apps. D.3 and E).

To see how this structural advantage translates into circuit costs, we compiled two approaches on the same eight-dimensional E3 target, letting the expanded baseline share phase queries. Both use the same phase-oracle access and weighted-L2L^2 tolerance of 0.50.5. QSFN compiles the full target; the shared-query baseline compiles the certified best 731-term Chebyshev approximation. The table gives O3 medians over five transpiler seeds with all-to-all connectivity.

CircuitLogical qubitsElementary phase queriesKnown CNOTsCNOT depthReadout scale
QSFN248883,5954521
Shared-query LCU2172132,696130,38665.54

Even with the baseline down to 72 phase queries, QSFN uses about 1/36.91/36.9 as many known CNOTs and 1/288.51/288.5 of the CNOT depth. It saves gates and layers while using more qubits and phase queries. See Sec. 4.4, Table 1 and App. H.5, Table 9 for the full comparison.

We also added bounds for evaluation at a prescribed error. The original 32-dimensional E3 target takes 4,832 local signal calls to realize exactly. At L2L^2 error 1/21/2, lowering the leaf degree makes 928 calls sufficient; a spectral projection bound shows that fixed-query circuits with direct expectation readout need at least 176. For the theoretical family in Theorem 5, the required query count in the same model remains quadratic at fixed error (App. D.4, Eqs. (58), (60)). These counts use E3's local signal unit, distinct from the elementary phase queries in the table.

For the construction in Theorem 5, O(d)O(d) logical qubits and Θ(d)\Theta(d) simultaneous local calls give Θ(d)\Theta(d) query depth. The aggregation tree adds d−1d-1 gates and O(log⁡d)O(\log d) depth. Both constructions have unit readout scale, and each independent preparation is charged. For a synthesis error budget ϵsyn\epsilon_{\rm syn}, a per-rotation error on the order of ϵsyn/d2\epsilon_{\rm syn}/d^2 suffices. App. F.2 counts Clifford+TT synthesis of these known rotations separately from signal-oracle and composition costs.

For NN independent runs of the ideal circuit, the integrated statistical MSE is at most 1/(4N)1/(4N) for Theorem 5 and 1/N1/N for Theorem 6 (App. F.3, Eq. (77) and the following paragraph). Thus an absolute integrated statistical RMSE of ϵstat\epsilon_{\rm stat} takes O(d2/ϵstat2)O(d^2/\epsilon_{\rm stat}^2) total local queries. At fixed absolute statistical precision, final readout adds no exponential-in-dimension sampling factor to these two constructions.

AuthorsOpenReview ↗

Q2: Structure Assumptions and Coefficient Fitting

Q2. What structure is assumed, and how does fitting connect to the oracle comparison?

We choose how the formula is put together; we do not need to know its coefficients in advance. In the model in App. G, we fix the topology, rank, and local polynomial degree before fitting the coefficients to data. The topology can come from domain knowledge or a prescribed dictionary. Variable grouping, topology search, and rank or degree selection are classical modeling costs; the compilation theorems start from the selected formula.

Take f1f_1 in E1. Once we choose a product of two univariate factors and their degrees, App. G's block ridge regression can fit the coefficients from data. The same compiler takes the fitted formula, and any fitting error enters the approximation budget (App. F.1). In E1, “oracle comparison” means supplying the analytic coefficients for both representations to isolate circuit cost. For f1f_1, the compiled circuits match in grid error. This use of analytic coefficients is separate from phase-oracle access in Q1. The 20 training seeds are for the SAQNN reimplementation. E2 goes one step further: the factorized and expanded circuits realize the same function exactly, isolating the savings from keeping the factorization (Sec. 2, Secs. 4.1–4.3, Apps. H.2–H.3).

App. G gives the cost of a fitting sweep and shows that exact block updates never increase the objective. The separate capacity bound applies to learning the outer weights on a fixed feature dictionary.

AuthorsOpenReview ↗

Q3–Q4: Compilation Results and When QSFN Saves Resources

Q3. How much does QSFN save at optimization level 3, and which counts come from transpilation?

For the eight-dimensional E2 target with all-to-all connectivity, raising the compiler's optimization level from 0 to 3 widens QSFN's lead in both two-qubit gate count and depth. The SAQNN-Flat-to-QSFN gate-count ratio rises from about 346 to 384, and the depth ratio rises from about 2,234 to 2,422. The revision reports medians over five transpiler seeds for the same target and gate set. At level 3, QSFN cuts the gate count from 24,220 to 63 and the depth from 24,219 to 10, while using 24 rather than 14 logical qubits. Keeping the factorization still saves gates and layers when both circuits use level 3 (Sec. 4.3, App. H.3, Table 6).

The 2.35×10132.35\times10^{13} ratio at d=32d=32 is a gate-count comparison at optimization level 0 that combines transpilation and recurrence. The QSFN count comes from transpilation. The SAQNN-Flat count comes from an exact recurrence checked against full transpilation through d=8d=8. Section 4.3 distinguishes the transpiled results from the recurrence-based ratio; the conclusion summarizes the savings from preserving the factorization.

For restricted connectivity, the factorization suggests a concrete layout. Each univariate factor in E2 uses a three-qubit block. If each block can be placed on a locally connected set of qubits, only the product-tree CNOTs between block outputs can require inter-block routing: d−1d-1 in total, or seven at d=8d=8. These seven are logical connections. The gate and depth ratios after routing depend on the placement and routing of both circuits on the same device graph.

Q4. Which target properties explain the gains?

The best candidates for saving gates and depth have a short local formula but a costly expanded circuit: low-degree polynomials suffice at the target accuracy, and those local values combine through a few inexpensive products, weighted sums, or hierarchical operations. Theorem 3 quantifies this for analytic sums of products: with RR products of dd local factors and degree pp per factor, the formula has size O(Rdp)O(Rdp). Theorem 2 explains how this translates into circuit costs. Gate counts add across modules, while depth follows the most expensive path through the tree. Preparing child circuits in parallel can reduce depth, but each child needs its own register. At a given accuracy, the number of products, the local degree, and the cost of combining them predict opportunities to save gates and layers; the number and width of the child registers prepared in parallel determine the width trade-off.

E1 puts favorable and unfavorable cases side by side. Each entry reads SAQNN → QSFN, using the analytic-coefficient circuits compiled at O0.

TaskTarget structureTermsTwo-qubit gatesTwo-qubit depthLogical qubits
f1f_1Product of two univariate factors49 → 8328 → 81326 → 317 → 14
f2f_2Compact joint spectrum3 → 214 → 1614 → 163 → 5
f3f_3Square of an affine function6 → 6206 → 33205 → 175 → 10

Both circuits match at a grid MSE of 1.867×10−81.867\times10^{-8} for f1f_1 and reach numerical precision for f2f_2 and f3f_3. Keeping the two low-degree factors of f1f_1 avoids compiling the expanded spectrum term by term. Implementing f3f_3 as the product of two copies of an affine response makes the circuit much shallower with no change in term count. In both cases, preparing the two children separately doubles the logical width. The counterexample is f2f_2: its joint spectrum has only three terms to begin with, and dropping one does not save gates or depth. E2 confirms the structural effect within QSFN itself: for the same eight-dimensional function, the expanded circuit uses 8,190 two-qubit gates, while keeping the product takes 71 (Secs. 4.2–4.3, Fig. 2, Apps. H.2–H.3, Tables 5–6).

Reviewer_2fhROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces stable quantum spectral formula networks (QSFNs), which combine univariate spectral leaves into a computation tree. The authors theoretically study the approximation properties and degrees of the local leaves, as well as the size of the composition tree. They show that, for a certain family of cosine polynomials, the number of global Fourier terms needed to represent a given target grows exponentially in dd, whereas QSFNs require only polynomially many terms. Finally, the paper presents experiments comparing QSFNs with SAQNN (Tang et al., 2026).

Critical strengths
  • Efficient approximation with quantum neural networks is an important topic.
  • The paper is generally well written and clear.
  • The proofs I checked appear to be correct.
Critical weaknesses
  1. The role of quantum computing remains unclear. i) The approximation rates seem to arise purely from the assumed low-rank structure (1). The proofs appear to rely on standard techniques for low-rank Chebyshev approximation, and the resulting rate appears to match that of classical low-rank polynomial approximation. The same applies to the separation result in Theorems 5 and 6: it also holds in the purely classical setting, as a comparison between a factorized and an expanded representation. ii) The paper states that "Domain knowledge or a prescribed dictionary supplies the tree topology, and local and aggregation coefficients are fitted classically before compilation for repeated quantum evaluation." In other words, the coefficients crjkc_{rjk} and ara_r in equation (2) must be learned before the quantum circuit can be constructed. At that point, FF in (2) is fully known, so one could evaluate FF directly on a classical computer instead of running the quantum circuit. This would achieve the same error, without any shot noise.

  2. Novelty with respect to the existing literature. The paper does not compare the approximation rates in Theorem 3 with existing results. One related work is cited (Yu et al., 2024), which uses a very similar proof technique, but neither the technique nor the results are compared with it. Several other quantitative approximation results have also been derived in the literature, and none of them is discussed:

  • J. Aftab, C. Schwab, H. Yang, and J. Zech. Quantum Circuit Encodings of Polynomial Chaos Expansions. https://arxiv.org/abs/2506.01811
  • J. Aftab and H. Yang. Approximating Korobov functions via quantum circuits. Communications in Mathematical Sciences, 2026
  • L. Gonon and A. Jacquier. Universal approximation theorem and error bounds for quantum neural networks and quantum reservoirs. IEEE Transactions on Neural Networks and Learning Systems, 2025.
  • A. Manzano, D. Dechant, J. Tura, and V. Dunjko. Approximation and generalization capacities of parametrized quantum circuits for functions in Sobolev spaces. Quantum, 2025.

It therefore remains unclear whether the results could be obtained directly as special cases of existing quantitative approximation results for quantum neural networks.

  1. Relevance of the low-rank analytic structure. The method can only be applied when the low-rank structure (the tree topology and the rank RR) is known in advance. Moreover, the functions used in the numerical experiments lack practical motivation, for example from science or engineering. This leaves the overall relevance of the results open.
Questions for authors
  1. Once the coefficients of FF have been determined, what is the advantage of evaluating FF with a quantum circuit rather than directly on a classical computer?
  2. How do the obtained rates and approximation results compare with those for classical low-rank Chebyshev approximation?
  3. How do the rates compare with existing approximation results for quantum neural networks in the literature?
  4. What is the practical relevance of these results? In which applications do such low-rank functions arise?
9 comments
AuthorsOpenReview ↗

Q1: What the Quantum Circuit Adds Once the Coefficients Are Known

Thank you for asking what the quantum circuit adds once the formula is known, and for pointing us to the closest approximation results. Our central result is that QSFN can uniformly approximate any continuous function on a compact set to arbitrary accuracy while retaining the local Chebyshev convergence rate for targets with compact analytic factorizations; the revision shows that preserving the factorization substantially reduces CNOT count and depth even against stronger compiled baselines for the same target at the same error tolerance, and that the compiled formula lets unknown phases drive a downstream quantum operation without first estimating them.

Q1. What does the circuit add once the coefficients are known?

Once the coefficients are known, QSFN lets the formula FF directly control a downstream quantum operation without first estimating the unknown phases. QSFN retains universal approximation. When a target has a compact factorization, compiling the formula as written can reduce gate count and depth at the same error tolerance, making it easier to use the function as part of a larger quantum program.

We added a full simulation in which four unknown phases determine a rotation on a data qubit, and compared it with sine-window phase estimation followed by rotation. Both methods know the same formula and access each input xjx_j only through Pj(xj)=diag⁡(1,eixj)P_j(x_j)=\operatorname{diag}(1,e^{ix_j}) and its inverse. On the same 24 test inputs, both meet the 10−810^{-8} channel error target with 18 logical qubits. QSFN uses about 1/61.21/61.2 of the baseline's phase queries and 1/2.591/2.59 of its combined count of known gates and queries. See Sec. 4.5 and Fig. 5 of the revision.

Concretely, let B=∏jϕn(xj)B=\prod_j\phi_n(x_j) and H=(1+B)/2H=(1+B)/2. We implement the rotation e−iHZDe^{-iHZ_D} on an arbitrary data qubit. Adding one data qubit and two CNOTs turns the same response into the interaction e−iHZD1ZD2e^{-iHZ_{D_1}Z_{D_2}} without extra signal calls (Fig. 5 and App. I.2).

MethodPhase queriesKnown gates + queriesLogical qubitsMax. diamond error
Coherent QSFN8,568204,153186.353×10−106.353\times10^{-10}
Sine-window estimation and rotation524,284529,373187.663×10−97.663\times10^{-9}

At this high precision, QSFN saves more queries than it adds quantum gates, including state preparation and inverse calls in the accounting. The error in the table is for the full output channel, including all branches. At moderate precision, the sine-window method has the lower combined cost. Fig. 5 and Table 10 in App. I.6 show the comparison across precisions; the appendix also reports the baseline's classical arithmetic separately.

The difference persists even when classical evaluation is fast. The queries are spent acquiring the signal record needed to set the rotation; higher precision requires distinguishing closer phases. For a fixed response with a nonzero derivative along an input slice, Prop. 8 proves that probing a fresh signal and acting on the data using only the resulting classical record requires Ω(ε−1/2)\Omega(\varepsilon^{-1/2}) queries in the worst case to achieve uniform channel error ε\varepsilon. This lower bound also covers adaptive quantum probing. At fixed dimension and local degree, QSFN approximates the rotation directly with O(LBlog⁡(1/ε)/log⁡log⁡(1/ε))O(L_B\log(1/\varepsilon)/\log\log(1/\varepsilon)) queries, where LB=3dpL_B=3dp is the query cost of preparing the product BB reversibly (App. I.4).

This result connects structured function approximation to downstream quantum computation. Theorem 3 establishes quantum universal approximation: QSFN approximates every continuous function uniformly on compact sets, without assuming low rank. For compactly structured targets, classical Chebyshev theory supplies the local rate; Theorems 1–2 give the circuit that preserves the composition, with explicit resource and error bounds. The frequency lower bounds in Theorems 5–6 come from the global representations and therefore apply to classical and quantum expansions alike. What QSFN adds is a circuit that compiles the short formula and realizes these targets exactly, with local queries growing only quadratically in dimension. The rotation task goes one step further and tests quantum evaluation itself: even when both methods know the same short formula, coherent implementation substantially reduces the signal-query cost at high precision.

We hope the new rotation comparison addresses your question about what the quantum circuit adds, and that you will take the query savings into account when revisiting your assessment.

AuthorsOpenReview ↗

Q2: Comparison with Classical Low-Rank Chebyshev Approximation

Q2. How does this compare with classical low-rank Chebyshev approximation?

We added a comparison with classical fully separated low-rank and tensor-Chebyshev representations on the same 32-dimensional target. QSFN keeps the local Chebyshev convergence rate and avoids the cost of expanding the formula variable by variable: a product of 16 two-variable factors represents the target exactly, whereas a fully separated sum needs at least 64,599 products just to reach a weighted L2L^2 tolerance of 0.10.1, even with freely chosen univariate factors. QSFN builds the circuit directly from the short formula (Sec. 3.4, App. H.5).

Given the same analytic factors, Theorem 3 uses the classical Chebyshev error bound for each factor. With the other parameters fixed, a fixed increase in local polynomial degree suffices to reduce uniform error by a factor of ten. The factorization stays intact, the formula size grows linearly with local degree, and the readout scale stays bounded by a constant times the sum of absolute weights.

The new comparison extends our spectral result to classical fully separated low-rank approximation. All three rows use the same pairwise NAND target from E3 and a Chebyshev-weighted L2L^2 tolerance of 0.10.1, equivalent to the phase-domain tolerance:

Representation of the same targetRepresentation sizeStatus
Pairwise formula preserved by QSFNProduct of 16 two-variable factorsExact representation of the target
Fully separated sum (arbitrary square-integrable univariate factors)64,599 productsAttained minimum
Tensor-Chebyshev expansionAt least 3,305,707,562 termsCertified lower bound

The singular values bound the error of any fully separated representation, and the truncated decomposition attains that bound. This makes 64,599 the exact minimum. For this target family, both expansion sizes have lower bounds that grow exponentially in dimension at any fixed tolerance below 3/2\sqrt{3}/2 (Sec. 3.4, Apps. D.6 and H.5, Fig. 15). A classical evaluator can also retain the two-variable factors; QSFN makes that same short formula the blueprint for a quantum circuit. The compilation comparison in Sec. 4.4 quantifies the CNOT count and depth saved on the eight-dimensional E3 target.

If you would like to see another comparison, we would be glad to examine it at the same target and accuracy.

AuthorsOpenReview ↗

Q3: Quantum Approximation Rates and Same-Target Circuit Costs

Q3. How do the rates and resources compare with existing quantum approximators?

We added a theorem-by-theorem comparison and a same-target compilation experiment. With a supplied analytic factorization, local degree p=O(log⁡(1/ϵ))p=O(\log(1/\epsilon)) suffices for uniform error ϵ\epsilon at fixed dimension, rank, and analytic and weight bounds; both formula size and local signal queries scale as O(Rdp)O(Rdp) (Theorem 3, App. C.5). On the eight-dimensional E3 target at matched tolerance, QSFN's CNOT depth and known CNOT count are about 1/288.51/288.5 and 1/36.91/36.9 of the shared-query baseline's (Sec. 4.4, Table 1).

  • Aftab et al.: same polynomial, less to compile. On common targets with a supplied factorization, tensor and factorwise truncation at the same local degree pp yield the same polynomial. Their full tensor construction (Theorem 3.5) gives a budget of O((log⁡(1/ϵ))d)O((\log(1/\epsilon))^d) terms. QSFN compiles the same polynomial from an O(Rdp)O(Rdp) formula, linear in log⁡(1/ϵ)\log(1/\epsilon) at fixed dimension and rank.
  • Yu et al.: finer partitions vs. higher local degree. Both proofs start with classical approximation. Yu et al. use Bernstein polynomials and compile monomial sums by linear combinations of unitaries; their piecewise Taylor bound for Hölder targets is O(K−β)O(K^{-\beta}) inside cells at resolution KK (Theorem 4). QSFN refines the analytic factors for uniform accuracy over the whole domain and compiles their composition with resource and error bounds beyond polynomial realization.
  • Aftab–Yang: grid refinement vs. factor refinement. Their mixed-smoothness Korobov construction gives a sufficient budget of O(ϵ−1/2log⁡3(d−1)/2(1/ϵ))O(\epsilon^{-1/2}\log^{3(d-1)/2}(1/\epsilon)) sparse-grid points for uniform error ϵ\epsilon (Props. 3.6, 3.9). At fixed dimension and with bounded analytic factors, QSFN reaches that tolerance with O(Rdlog⁡(1/ϵ))O(Rd\log(1/\epsilon)) local queries, without refining a multivariate grid.
  • Gonon–Jacquier: global frequencies vs. local queries. Under a Fourier moment condition, their O(n−1/2)O(n^{-1/2}) uniform error bound gives a sufficient budget of O(ϵ−2)O(\epsilon^{-2}) global terms (Thm. IV.1; Thm. II.4 gives weighted L2L^2). With supplied analytic factors, QSFN's local query budget grows logarithmically with 1/ϵ1/\epsilon at fixed dimension and rank, without compiling a global frequency sum.
  • Manzano et al.: a compilation budget at prescribed accuracy. Their Sobolev results cover functions and derivatives and include generalization bounds. For uniform function error and a supplied analytic factorization, QSFN gives a sufficient local degree and bounds the formula size and readout scale (Thm. 3).

Preserving structure can make an exponential difference. On the respective target families in Theorems 5–6, Fourier sums and SAQNN's native spectral-modulus representation require exponentially many frequencies at fixed error, while QSFN realizes the corresponding targets exactly with O(d2)O(d^2) local signal queries.

We added a same-target compilation experiment to see which gates the short formula saves, even when the expanded baseline can share phase queries. On the same eight-dimensional E3 target, the termwise and shared-query baselines compile the same certified best 731-term Chebyshev approximation, both with error about 0.499860.49986; QSFN compiles the full target. All three use the same phase access and weighted-L2L^2 tolerance of 0.50.5. Table 1 in Sec. 4.4 reports O3 medians over five transpiler seeds and counts coefficient-state preparation, its inverse, and selection gates for the expanded circuits.

CircuitQubitsPhase queriesKnown CNOTsCNOT depthRoot scale
QSFN248883,5954521
Termwise Chebyshev LCU2110,710398,044367,88565.54
Shared-query Chebyshev LCU2172132,696130,38665.54

The shared-query baseline uses fewer phase calls and qubits, but still has to prepare the coefficient state and select and combine global terms. QSFN saves those operations by composing the local factors directly. Its unit readout scale also avoids amplifying the variance bound when converting the readout to a function value (App. F.3). Table 9 and Fig. 16 in App. H.5 give the full O0 and O3 comparison, including the four-dimensional case at tolerance 0.50.5, where the shared circuit uses fewer CNOTs.

Thank you for pointing out the gap in our comparison; we hope the added rate analysis and same-target compilation results give you a clearer basis for reassessing the paper’s contribution.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.