acceptodds
Under review as a conference paper at ICLR 2027

QuSAE: Quantum Structure-aware amplitude encoding with improved fidelity-complexity trade-off

Abstract

Efficiently loading classical data into quantum states is a prerequisite for translating the potential advantages of quantum computing into practical data-intensive applications. Yet exact amplitude encoding of generic data can require exponentially many gates, which is beyond the reach of current quantum devices. Approximate amplitude encoding alleviates this overhead by trading state fidelity for representation complexity. However, most existing methods treat the target state generically from a quantum perspective, overlooking structural regularities inherent in real-world data that could be exploited to achieve more efficient encoding. To address this gap, we propose a multiscale Quantum Structure-Aware Amplitude Encoding (QuSAE) framework, which exploits the intrinsic multiscale organization of classical data to guide structured sparsification and efficient tensorization for approximate state preparation. This enables explicit control over approximation fidelity while reducing representation complexity. Comprehensive experiments across five benchmark datasets demonstrate that QuSAE exhibits favorable fidelity–complexity trade-off over competing methods, while preserving multiscale information in the resulting compact representations. More broadly, our results highlight structure-aware state construction as a general design principle for efficient quantum data encoding.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Quantum state preparation, approximate amplitude encoding, matrix product states, structure-aware encoding, fidelity--complexity trade-off.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_wigZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper targets approximate amplitude encoding with matrix product states. Instead of fixing a tensorization and truncating, QuSAE treats two objects as variables: a wavelet-domain support that decides what is kept, and a qubit-index mapping that decides how the kept coefficients are laid out across the MPS cuts. An ancestor-closed support is chosen by a tree-knapsack dynamic program under a retained-energy constraint, which by Proposition 1 is exactly the encoding fidelity; the mapping is then searched over a family of structure-preserving tree traversals, scored by a prefix-complexity surrogate that upper bounds each bond dimension. The two are alternated, and TT-SVD builds the final tensors. Experiments cover MNIST at 32 x 32, COIL-20 and CelebA images, and the MIT-BIH and STEAD signals, against standard MPS, the permuted-MPS mapping of Jeon et al., and low-rank state preparation. The reported result is a better fidelity-complexity trade-off, with the advantage concentrated in the medium-to-high fidelity regime, plus a GMSD analysis suggesting that edge structure survives compression.

Critical strengths

1.The problem is stated in the right variables. Separating what to retain from how to tensorize is the actual design space here, and most MPS encoding papers fix one and tune the other. 2.Proposition 1 is a genuinely useful observation: for an orthogonal wavelet transform, the fidelity of the truncated state equals the retained energy ratio and is invariant under the index mapping. That lets the support be certified before any MPS is built, and it cleanly decouples fidelity from compression. 3.The prefix-complexity bound gives a cheap surrogate - O(nK) instead of repeated SVDs - for the thing the mapping search is supposed to optimize. The paper is explicit that it is an upper bound and uses it only as a search score, which is the right way to deploy a loose bound.

Critical weaknesses

1.The metric being improved is not the quantity that matters. CMPS counts entries in the MPS tensors. The one place a preparation budget is computed (Appendix D.3) shows no improvement on MNIST and STEAD, two of the five datasets. So the claim 'improved fidelity-complexity trade-off' is established for a representation-level surrogate, and only partially for the quantity a device cares about - two-qubit gates and depth. The main text should either report the local-isometry budget for every dataset or say plainly that the circuit-level transfer is partial. 2.The mapping changes the encoded state. After the DWT and the permutation, the amplitudes no longer sit at the basis indices of x; they sit at pi(j). The paper says downstream can use the mapped state directly. That is true only if the downstream algorithm is written for that basis. Otherwise the inverse mapping and the inverse DWT have to be undone, which costs gates and eats part of the saving. The claim should be qualified as 'encoding of a fixed unitary image of x', with the cost of undoing it stated. 3.There is no table of numbers at matched fidelity. The baselines sweep a bond cap and QuSAE sweeps ε, so the comparison lives entirely in a trade-off plot, and 'upper left is better' is argued qualitatively. What is needed is a small table per dataset: CMPS and realized fidelity at F = 0.95, 0.99 and 0.995 for every method. From the text, the permuted-MPS mapping already recovers 1.66 points on MNIST, so the marginal value of the full pipeline on that dataset may be small - a number would settle it. 4.The scaling result is conditional on fitted exponents. The bound G2q = O(n ε-β/s) assumes s-tree compressibility and a prefix exponent β < 1, and both are estimated from fits (Figure 8). The paper should report the fitted s and β per dataset, together with the ε range over which the fit holds, so a reader can tell whether the experiments are in the asymptotic regime the bound describes. As written the bound is illustrative rather than predictive.

Questions for authors

1.Can you report CMPS and achieved fidelity at fixed F = 0.95, 0.99, 0.995 for all methods on all five datasets? 2.What is the local-isometry (two-qubit gate) budget for every dataset, not just the three shown in Appendix D.3? 3.If a downstream algorithm needs the original index order, what is the cost of undoing the permutation and the DWT, and does the advantage survive it? 4.What are the fitted s and β per dataset, and over what ε range is the scaling law valid? 5.How sensitive are the results to ηK, ηPi and wi, and was the operating point selected on validation?

10 comments
AuthorsOpenReview ↗

Author Response to Reviewer wigZ W(1)

W1. The metric being improved is not the quantity that matters. CMPS counts entries in the MPS tensors. The one place a preparation budget is computed (Appendix D.3) shows no improvement on MNIST and STEAD, two of the five datasets. So the claim 'improved fidelity-complexity trade-off' is established for a representation-level surrogate, and only partially for the quantity a device cares about - two-qubit gates and depth. The main text should either report the local-isometry budget for every dataset or say plainly that the circuit-level transfer is partial.

Response to W1. Thank you for this valuable suggestion. We originally chose MPS tensor count as the primary metric because it directly characterizes representation complexity through the bond profile, independently of circuit decomposition, gate basis, and compiler optimization, while serving as a proxy for local-isometry resources. Nevertheless, we agree that actual compiled gate counts and circuit depth are essential quantum resource metrics. We address this concern by extending the sequential circuit compilation experiments and incorporating the additional results into Section 4.2 Experimental Results of the main text.

First, we apologize for the ambiguity in the original presentation. The original Appendix D.3 did not include circuit-level comparisons against Standard MPS and Permuted MPS. Fig. 9 only reports QuSAE's local-isometry resource budgets across five datasets under different fidelity tolerances, rather than comparative improvements over these baselines. Thus, the original figure was not intended to establish circuit-level advantages over the reference methods.

To provide a direct comparison, we have extended the sequential circuit compilation experiments in the revised manuscript. We compile the MPS representations produced by Standard MPS, Permuted MPS, and QuSAE using a common sequential local-isometry construction with the basis gates {Rz,SX,X,CX}\{R_z,\mathrm{SX},X,\mathrm{CX}\}. The complete results across all three fidelity thresholds (F≥0.95F\geq 0.95, 0.990.99, and 0.9950.995), including MPS representation complexity, CX counts, circuit depths, and their relative changes, are reported in Table 1 of the revised manuscript.

The following table reports the mean compiled CX counts and full circuit depths at F≥0.99F\geq 0.99, together with their relative changes with respect to the Standard MPS baseline:

MethodMetricMNISTCOIL-20CelebAMIT-BIHSTEAD
Standard MPSCX1,685.65,087.61,355.2136.14,207.8
Depth6,480.919,489.95,242.5538.016,064.8
Permuted MPSCX1,178.94,565.51,070.8136.14,208.4
Change(-30.1%)(-10.3%)(-21.0%)(0.0%)(0.0%)
Depth4,536.617,454.64,153.9538.516,068.5
Change(-30.0%)(-10.4%)(-20.8%)(+0.1%)(0.0%)
QuSAECX1,072.13,351.2803.388.83,510.0
Change(-36.4%)(-34.1%)(-40.7%)(-34.7%)(-16.6%)
Depth4,132.312,802.63,119.7348.413,407.6
Change(-36.2%)(-34.3%)(-40.5%)(-35.2%)(-16.5%)

Across all five datasets, QuSAE achieves lower CX counts and circuit depths than both baselines. Compared with Standard MPS, it reduces CX counts and circuit depth by up to 40.7% and 40.5%, respectively. Importantly, the savings also persist against Permuted MPS, reaching 34.7% fewer CX gates and 35.3% lower circuit depth. These results demonstrate that the reduction in MPS representation complexity can be translated into lower compiled sequential state-preparation costs under a common gate set.

AuthorsOpenReview ↗

Author Response to Reviewer wigZ W(2)

W2. The mapping changes the encoded state. After the DWT and the permutation, the amplitudes no longer sit at the basis indices of x; they sit at pi(j). The paper says downstream can use the mapped state directly. That is true only if the downstream algorithm is written for that basis. Otherwise the inverse mapping and the inverse DWT have to be undone, which costs gates and eats part of the saving. The claim should be qualified as 'encoding of a fixed unitary image of x', with the cost of undoing it stated.

Response to W2. We thank the reviewer for pointing out this important distinction. We have expanded Appendix D.3 to fully address this concern from three aspects: (1) distinguishing two downstream application scenarios, (2) theoretically analyzing the resource costs of inverse transformations, and (3) conducting practical inverse-transformation circuit compilation experiments.

1. We distinguish two downstream scenarios. (1) Direct consumption of the mapped representation: When the downstream algorithm is formulated in the mapped wavelet basis, the encoded state can be consumed directly without inverse transformations. This is the intended setting for QuSAE's representation-level resource savings. (2) Recovery of the original representation: When the downstream algorithm requires the original computational-basis state, both the inverse mapping Uπ⋆†U_{\pi^\star}^{\dagger} and inverse DWT W†W^\dagger must be applied.

2. Theoretical analysis. Following the permutation-reversal construction in [1], a permutation of nn qubit positions requires at most 3(n−1)=O(n)3(n-1)=\mathcal{O}(n) CX gates. For inverse DWT, [2] establishes a gate complexity of O(dn+dM3/2)\mathcal{O}(dn+dM^{3/2}). For fixed wavelet order and d≤nd\leq n, the combined restoration overhead is at most O(n2)\mathcal{O}(n^2) under the experimental settings considered in this work. Joint compilation can further reduce the restoration cost by exploiting cancellations between inverse mapping and inverse DWT. Moreover, for fixed-depth wavelet decompositions, the restoration overhead reduces from the worst-case (n2)\mathcal(n^2) to (n)\mathcal(n).

3. Practical evaluation. Inverse transform costs vary across different wavelet families. For MNIST under the Haar wavelet, joint compilation reduces the restoration overhead to 24 CX gates, preserving a 36.9% CX-count reduction over Standard MPS. We therefore argue that wavelet family selection should account for the overall preparation and restoration costs for applications requiring restoration of the original representation. We then evaluated the Haar configuration across five datasets and found that QuSAE retains lower CX counts and circuit depths than Standard MPS across all five datasets, demonstrating that appropriate wavelet selection can preserve its resource advantages after restoration.

[1] Jeon et al. (2024). Optimal Qubit Mapping Search for Encoding Classical Data into Matrix Product State Representation with Minimal Loss. Physics Letters A. https://doi.org/10.1016/j.physleta.2024.129642.

[2] Bagherimehrab and Aspuru-Guzik (2024). Efficient Quantum Algorithm for All Quantum Wavelet Transforms. Quantum Science and Technology. https://doi.org/10.1088/2058-9565/ad3d7f.

AuthorsOpenReview ↗

Author Response to Reviewer wigZ W(3) & W(4)

W3. There is no table of numbers at matched fidelity. The baselines sweep a bond cap and QuSAE sweeps ε, so the comparison lives entirely in a trade-off plot, and 'upper left is better' is argued qualitatively. What is needed is a small table per dataset: CMPS and realized fidelity at F = 0.95, 0.99 and 0.995 for every method. From the text, the permuted-MPS mapping already recovers 1.66 points on MNIST, so the marginal value of the full pipeline on that dataset may be small - a number would settle it.

Response to W3. We sincerely thank the reviewer for this constructive suggestion. Following the suggestion, we have added Table 1 to the revised manuscript, reporting CMPSC_{\mathrm{MPS}}, compiled CX gate counts, and full circuit depths for Standard MPS, Permuted MPS, and QuSAE across all five datasets at three matched fidelity thresholds: F≥0.95F\geq 0.95, F≥0.99F\geq 0.99, and F≥0.995F\geq 0.995. This provides a direct quantitative comparison of representation complexity and actual circuit resources at each operating point.

W4. The scaling result is conditional on fitted exponents. The bound G2q = O(n ε-β/s) assumes s-tree compressibility and a prefix exponent β < 1, and both are estimated from fits (Figure 8). The paper should report the fitted s and β per dataset, together with the ε range over which the fit holds, so a reader can tell whether the experiments are in the asymptotic regime the bound describes. As written the bound is illustrative rather than predictive.

Response to W4. We thank the reviewer for the suggestion. In the original manuscript, Fig. 8 fits the two power laws over the empirically observed support-size range (K/NK/N), with the fitted exponents and fitting errors annotated alongside the curves. Original Table 2 further reports the normalized fidelity-compatible support budgets (Kε/NK_\varepsilon/N) and the fitted tree-compressibility exponent (ss). The corresponding fidelity tolerances are ε∈{10−1,10−2,10−3,10−4}\varepsilon\in\{10^{-1},10^{-2},10^{-3},10^{-4}\}.

To improve clarity, we have reorganized these results into a unified table (revised Table 4 in Appendix D.1), reporting the fitted exponents (ss) and (β\beta), their goodness-of-fit values (Rs2R_s^2 and Rβ2R_\beta^2), and the resulting bond-dimension and sequential gate-count scaling exponents for all five datasets.

Datasetssβ\betaRs2R_s^2Rβ2R_\beta^2β/(2s)\beta/(2s)β/s\beta/s
MNIST1.5330.3040.8320.7120.0990.198
COIL-200.8280.3290.9350.8410.1990.397
CelebA0.7910.4940.9320.9570.3120.625
MIT-BIH1.1990.5010.9970.9540.2090.417
STEAD1.0230.4180.7730.7880.2040.409

Three observations follow from these results. First, all datasets exhibit s>0s>0 and β<1\beta<1, supporting the empirical tree- and prefix-compressibility assumptions. Second, the resulting gate-scaling exponents β/s\beta/s implies sublinear growth of the representative bound with respect to 1/ε1/\varepsilon. Third, higher R2R^2 indicates that the observed data more closely follow the fitted power law, whereas the actual resource-scaling behavior depends on both the fitted exponents and dataset-dependent scaling constants.

Regarding the applicability conditions, we have further clarified them in Appendix D.1. Eq. (7) requires (i) etree(K)≤γtreeK−2se_{\mathrm{tree}}(K)\leq\gamma_{\mathrm{tree}}K^{-2s}, (ii) Πmax⁡(Ω,π⋆)≤γπ⋆∣Ω∣β\Pi_{\max}(\Omega,\pi^\star)\leq\gamma_{\pi^\star}|\Omega|^\beta on the same fidelity-feasible supports under the shared mapping, and (iii) ss, β\beta, and the associated constants to remain independent of ε\varepsilon over the considered range. For the practical joint-search output, its support size must additionally satisfy ∣Ω⋆∣≤cbudKε|\Omega^\star|\leq c_{\mathrm{bud}}K_\varepsilon, where cbudc_{\mathrm{bud}} is independent of ε\varepsilon, and the prefix bound must also hold on these supports. Under these conditions, Eq. (7) provides a conditional resource-scaling characterization supported by finite-range empirical fits, rather than an unconditional asymptotic guarantee for the practical solver.

Reviewer_NBX8OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies efficient loading of classical data into quantum states and proposes approximate amplitude encoding (AAE) with MPS and proposes QuSAE, which exploits the inherent multiscale structure of classical data. This reduces representation cmpexity and allow explicit control over approximation fidelity. Experiments across five datasets are conducted, showing better trade-off between fidelity and MPS parameter count than standard MPS and other related works. Also fidelity guarantees for wavelet tree truncation is established and a prefix-complexity upper bound is driven.

Critical strengths
  • Using the parent–child structure to decide both what to keep and how to place it across the register seem practical.
  • The ablation study is well designed to separate the effects of tree structure, mapping, etc
  • The experiments cover both image and 1D-signal datasets with code provided for easy reproducibility.
Critical weaknesses
  • The main comparison seems apples to oragnes. QuSAE prepares UπW∣ψ(x)⟩U_\pi W|\psi(x)\rangle: the truncated wavelet coefficients. This is only mentioned near end of section 3.4: "directly uses the mapped wavelet... without applying an inverse DWT or inverse index mapping". The baselines however encode xx directly and does extra stuff.
  • The theory is pretty light, using elementary tools.
  • Marginal: font size in figures are a bit too small. Making them bigger would benefit readers.
Questions for authors
  • Please clarify weakness 1. How would fig 3 change if methods are compared on the same domain?
4 comments
AuthorsOpenReview ↗

Author Response to Reviewer NBX8

W(1) The main comparison seems apples to oranges. QuSAE prepares the truncated wavelet coefficients. This is only mentioned near the end of Section 3.4: "directly uses the mapped wavelet... without applying an inverse DWT or inverse index mapping". The baselines, however, encode directly and do extra stuff.

Response to W1. Thank you for this valuable comment. We would like to address it by (1) clarifying the rationale for the original comparison and (2) expanding Fig. 3 to include both raw-domain and wavelet-domain baselines.

First, we clarify that QuSAE's resource advantages are primarily intended for downstream quantum algorithms that directly consume the mapped representation. Under this setting, we retain the original raw-domain comparison to evaluate complete encoding pipelines under the same raw inputs, since the wavelet transform is an integral part of QuSAE's pipeline. For applications requiring recovery of the original computational-basis representation, the additional inverse transformation costs are analyzed in Appendix D.3.

To further ensure a fair same-representation comparison, we have expanded Fig. 3 in the revised manuscript to include wavelet-domain counterparts of Standard MPS, Permuted MPS, and LRSP, using the same dataset-specific orthogonal discrete wavelet transform (DWT) as QuSAE.

W(2) The theory is pretty light, using elementary tools.

Response to W2. We thank the reviewer for this criticism. In this work, we focus on the resource challenges of high-fidelity quantum amplitude encoding of classical data and propose a structure-aware support–mapping optimization framework to reduce MPS representation and state-preparation costs. The theoretical analysis is primarily designed to establish algorithmically useful structural guarantees that support QuSAE's optimization framework, rather than introduce complex mathematical principles.

Specifically, our theoretical contributions are:

1. Retained-energy certificate (Proposition 1). It provides an explicit fidelity guarantee, allowing the required approximation accuracy to be certified before MPS construction.

2. Prefix-complexity surrogate (Proposition 2). It establishes an upper bound on MPS bond dimensions using a combinatorial prefix-based measure, converting repeated matrix-rank or SVD evaluations into an efficiently computable objective with O(nK)\mathcal{O}(nK) evaluation cost, thereby enabling tractable mapping search.

3. Theoretical tightness and optimization validity. Appendix B.2 analyzes the tightness of the prefix-complexity upper bound through bipartite maximum matching and characterizes conditions for attaining the bound. Appendix B.3 establishes the feasibility and attainment of the joint optimization and further analyzes the discrepancy between the prefix-based surrogate and the actual MPS tensor-entry cost.

We have also extended the resource complexity analysis in Appendix D.2 and D.3 to cover the complete encoding pipeline and inverse transformations. Together, these results establish the theoretical connection between fidelity-controlled tree approximation, structure-preserving mapping, and tractable MPS complexity optimization.

W(3) Marginal: font size in figures are a bit too small. Making them bigger would benefit readers.

Response to W3. We thank the reviewer for the suggestion. We have increased the font sizes of the figures to improve readability in the revised manuscript.

Q(1) Please clarify weakness 1. How would Fig. 3 change if methods are compared on the same domain?

Response to Q1. We have revised Fig. 3 to include wavelet-domain counterparts of Standard MPS, Permuted MPS, and LRSP. QuSAE still achieves the lowest MPS complexity across all five datasets under the same domain and matched fidelity.

The following table reports the MPS complexities at F≥0.99F\geq 0.99:

MethodMNISTCOIL-20CelebAMIT-BIHSTEAD
Standard MPS (raw)737.13,453.8912.8134.62,467.5
Permuted MPS (raw)648.04,088.8742.6130.72,467.5
LRSP (raw)745.66,252.01,736.0208.03,624.0
Standard MPS (DWT)1,351.66,578.41,288.0168.02,760.0
Permuted MPS (DWT)1,219.010,612.01,704.0168.02,760.0
LRSP (DWT)1,339.88,569.61,736.0208.03,240.0
QuSAE637.42,523.8559.089.51,960.2

Notably, applying the DWT alone rarely improves upon the corresponding raw-domain baselines. This is because an orthogonal transform itself does not guarantee sparse coefficients or low-rank tensor unfoldings under a given index ordering. DWT exposes multiscale structure, which must be further exploited through structured support selection and mapping. These results demonstrate the additional benefit of QuSAE beyond simply applying the DWT or optimizing mappings.

AuthorsOpenReview ↗

Author Response to Reviewer NBX8

Dear Reviewer NBX8,

We sincerely appreciate your time and effort in reviewing our work. In response to your comments, we have made the following revisions:

  1. Added same-representation baselines to Fig. 3, further demonstrating QuSAE's structural benefits beyond the wavelet transformation itself.
  2. Further clarified the theoretical contributions, highlighting their algorithmic utility.
  3. Enlarged the figure fonts to improve readability.

If our rebuttal has addressed your concerns, we would be grateful if you took our clarifications and additional results into account in your assessment. We would also welcome any further feedback before the discussion closes.

Best,

Authors

Apologies for the late reply, and thank you for the additional experiments and clarifications. The wavelet-domain baselines and compiled circuit-resource comparisons substantially address my main concern about comparison fairness. I find the structure-aware state preparation approach relevant to quantum ML pipelines, and the added experiments make the practical contribution more convincing. I am increasing my score to 3. Please retain a clear distinction between native mapped-state preparation and original-basis preparation, including restoration costs. My score is provisional, and I will engage in further discussion with the AC and other reviewers before finalizing my assessment.

AuthorsOpenReview ↗

Author Response to Reviewer NBX8

Dear Reviewer NBX8,

Thank you for your positive reassessment and recognition of our additional experimental evidence. We appreciate your constructive feedback and continued consideration.

Following your suggestion, we have further revised the methodology, experimental evaluation, and appendix to explicitly distinguish the two application scenarios and their associated preparation costs.

We sincerely appreciate your feedback, which has helped us further clarify the scope and practical applicability of QuSAE.

Best regards,

Authors

Reviewer_4DEoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes QuSAE, a structure‑aware approximate quantum amplitude‑encoding framework that jointly optimizes wavelet‑tree coefficient truncation and structure‑preserving index mapping to produce compact matrix‑product‑state representations. It achieves improved fidelity‑complexity trade‑offs for real‑world classical data and is tested by numerical simulations on five image and signal datasets.

Critical strengths

(1) QuSAE jointly optimizes coefficient truncation and index mapping under explicit fidelity constraints. It derives provable fidelity guarantees and computable prefix‑complexity upper bounds for matrix‑product‑state bond dimensions.

(2) It provides fidelity‑complexity trade‑offs on multiple real‑world image and signal datasets and better preserves multiscale structural information compared with the existing approximate amplitude‑encoding baselines.

Critical weaknesses

(1) The comparison of encoding objectives needs further stronger justification. QuSAE directly prepares a mapped wavelet state, whereas the main reference methods prepare raw amplitude states. A common unitary preserves fidelity, but preparation complexity need not be invariant. Same-representation baselines or downstream validation are needed to establish the practical benefit fairly.

(2) The resource evidence primarily concerns MPS tensor counts and implied local-isometry budgets, rather than compiled gate counts or circuit depth.

(3) The O(N2)O(N^2) classical preprocessing and mapping search are not sufficiently reflected in an end-to-end cost comparison.

Questions for authors

(1) How does QuSAE compare with standard and optimized MPS preparation when all methods use the same wavelet representation and target state?

(2) Do the representation savings persist after compilation to a common elementary gate set at matched fidelity?

(3) What is the complete classical preprocessing cost? When does it outweigh the state-preparation savings?

5 comments
AuthorsOpenReview ↗

Author Response to Reviewer 4DEo W(1) & Q(1)

W(1) The comparison of encoding objectives needs further stronger justification. QuSAE directly prepares a mapped wavelet state, whereas the main reference methods prepare raw amplitude states. A common unitary preserves fidelity, but preparation complexity need not be invariant. Same-representation baselines or downstream validation are needed to establish the practical benefit fairly.

Response to W1. Thank you for this valuable comment. We would like to address it via 1) clarifying the rationale for the original comparison and 2) expanding Fig. 3 to include both raw-domain and wavelet-domain baselines.

First, we clarify that QuSAE's resource advantages are primarily intended for downstream quantum algorithms that directly consume the mapped representation. Under this setting, we retain the original raw-domain comparison to evaluate complete encoding pipelines under the same raw inputs, since the wavelet transform is an integral part of QuSAE's pipeline. For applications requiring recovery of the original computational-basis representation, the additional inverse transformation costs are analyzed in Appendix D.3.

To further ensure a fair same-representation comparison, we have expanded Fig. 3 in the revised manuscript to include wavelet-domain counterparts of Standard MPS, Permuted MPS, and LRSP, using the same dataset-specific orthogonal discrete wavelet transform (DWT) as QuSAE.

Q(1) How does QuSAE compare with standard and optimized MPS preparation when all methods use the same wavelet representation and target state?

Response to Q1. QuSAE achieves the lowest complexity across all five datasets over both raw-domain and wavelet-domain baselines. The revised Fig. 3 and Table 1 report these additional results.

The following table shows representative MPS complexities at F≥0.99F\geq 0.99.

MethodMNISTCOIL-20CelebAMIT-BIHSTEAD
Standard MPS (raw)737.13,453.8912.8134.62,467.5
Permuted MPS (raw)648.04,088.8742.6130.72,467.5
LRSP (raw)745.66,252.01,736.0208.03,624.0
Standard MPS (DWT)1,351.66,578.41,288.0168.02,760.0
Permuted MPS (DWT)1,219.010,612.01,704.0168.02,760.0
LRSP (DWT)1,339.88,569.61,736.0208.03,240.0
QuSAE637.42,523.8559.089.51,960.2

QuSAE still achieves the lowest complexity across all five datasets, demonstrating the benefit of its structure-aware optimization beyond the wavelet transform itself. However, for individual methods, switching from the raw domain to the DWT domain does not consistently reduce representation complexity. This is because an orthogonal transform itself does not guarantee sparse coefficients or low-rank tensor unfoldings under a given index ordering. We adopt the DWT primarily because it exposes the multiscale structure of the input, which can be further exploited through structured support selection and mapping.

AuthorsOpenReview ↗

Author Response to Reviewer 4DEo W(2) & Q(2)

W(2) The resource evidence primarily concerns MPS tensor counts and implied local-isometry budgets, rather than compiled gate counts or circuit depth.

Response to W2. We agree that compiled gate counts and circuit depth are important quantum resource metrics. The original manuscript already included sequential circuit compilation experiments in Appendix D.3. In the revision, we have further expanded these experiments and presented the additional results in the second part of Section 4.2 Experimental Results.

We originally chose MPS tensor count as the primary metric because it directly reflects representation complexity through the bond profile, independently of circuit decomposition, gate basis, transpiler optimization, or hardware connectivity, while serving as a proxy for local-isometry resources.

We then compile the MPS representations using a common sequential local-isometry construction with the basis gates {Rz,SX,X,CX}\{R_z,\mathrm{SX},X,\mathrm{CX}\}. Results are averaged over the same samples as those used in the fidelity–complexity trade-off experiments. Table 1 in the revised manuscript comprehensively reports the MPS representation complexities, compiled CX gate counts, and circuit depths of QuSAE and the baseline methods across all five datasets, together with their relative changes with respect to Standard MPS.

Q(2) Do the representation savings persist after compilation to a common elementary gate set at matched fidelity?

Response to Q2. Yes. Table 1 in the revised manuscript reports sequential circuit compilation results across all five datasets at three matched fidelity thresholds (F≥0.95F\geq 0.95, 0.990.99, and 0.9950.995). Across all 15 dataset–fidelity configurations, QuSAE achieves lower CX counts and circuit depths than both Standard MPS and Permuted MPS under a common elementary gate set.

For clarity, the following table reports the mean CX counts and full circuit depths per dataset at F≥0.99F\geq 0.99:

MethodMetricMNISTCOIL-20CelebAMIT-BIHSTEAD
Standard MPSCX1,685.65,087.61,355.2136.14,207.8
Depth6,480.919,489.95,242.5538.016,064.8
Permuted MPSCX1,178.94,565.51,070.8136.14,208.4
Change(-30.1%)(-10.3%)(-21.0%)(0.0%)(0.0%)
Depth4,536.617,454.64,153.9538.516,068.5
Change(-30.0%)(-10.4%)(-20.8%)(+0.1%)(0.0%)
QuSAECX1,072.13,351.2803.388.83,510.0
Change(-36.4%)(-34.1%)(-40.7%)(-34.7%)(-16.6%)
Depth4,132.312,802.63,119.7348.413,407.6
Change(-36.2%)(-34.3%)(-40.5%)(-35.2%)(-16.5%)

QuSAE achieves lower CX counts and circuit depths than both baselines across all five datasets. Compared with Standard MPS, it reduces CX counts and circuit depth by up to 40.7% and 40.5%, respectively. More importantly, the savings persist even against Permuted MPS, achieving up to 34.7% fewer CX gates and 35.3% lower circuit depth. These results confirm that the MPS representation savings translate into reduced compiled sequential state-preparation resources under a common gate set.

AuthorsOpenReview ↗

Author Response to Reviewer 4DEo W(3) & Q(3)

W(3) The O(N2)O(N^2) classical preprocessing and mapping search are not sufficiently reflected in an end-to-end cost comparison.

Response to W3. We thank the reviewer for highlighting the importance of classical preprocessing costs. We have expanded Appendix D.2 to address this concern from three aspects: (1) end-to-end cost decomposition, (2) theoretical complexity analysis, and (3) practical runtime comparison.

1. End-to-end cost decomposition. We divide the pipeline into four stages: (1) classical preprocessing, (2) MPS construction, (3) classical circuit synthesis, and (4) quantum circuit execution. Classical preprocessing includes input normalization, the Discrete Wavelet Transform (DWT), wavelet-tree construction, support selection, and mapping search. As the reviewer points out, classical preprocessing constitutes a major computational difference among Standard MPS, Permuted MPS, and QuSAE. We compare these costs from both theoretical and practical perspectives.

2. Theoretical complexity. For an input of dimension N=2nN=2^n, the forward DWT and wavelet-tree construction require O(N)\mathcal{O}(N) time for fixed-length filters, while exact fidelity-controlled tree-support selection requires O(N2)\mathcal{O}(N^2) time. In our practical joint search, the support candidate pool is finite, the mapping family contains only four structure-preserving candidates, and each prefix-complexity evaluation costs O(nK)\mathcal{O}(nK). With a fixed candidate-pool budget, calibration-set size, and iteration limit, the practical joint-search complexity is polynomial in NN. Moreover, QuSAE calibrates a single dataset-level mapping shared across samples, avoiding unrestricted n!n! sample-wise permutation searches.

3. Practical runtime comparison. We measured the classical preprocessing and MPS construction time of all three methods on an 11th Gen Intel Core i7-11800H processor, using a single process with BLAS threads restricted to one. The table reports per-sample CPU time and QuSAE's one-time dataset-level calibration cost, in seconds.

DatasetStandard MPSPermuted MPSQuSAEQuSAE calibration
MNIST0.00440.07060.00290.1862
COIL-200.031780.5240.03971.663
CelebA0.00733.6770.00960.4660
MIT-BIH0.0009630.03570.0009710.0753
STEAD0.01190.30010.00530.3853

Compared with Permuted MPS, QuSAE substantially reduces per-sample CPU time, with its one-time calibration cost amortized after approximately 1–3 samples. Compared with Standard MPS, QuSAE incurs modest additional classical preprocessing costs on some datasets. However, these costs do not outweigh its substantial quantum-resource savings in CX gate counts and circuit depths, as demonstrated by our sequential circuit compilation experiments.

Q(3) What is the complete classical preprocessing cost? When does it outweigh the state-preparation savings?

Response to Q3. As analyzed in W3, under a fixed candidate-pool budget and iteration limit, the practical joint-search complexity is polynomial in NN. The practical runtime measurements show that QuSAE incurs modest additional per-sample classical costs on some datasets compared with Standard MPS, while substantially reducing runtime compared with Permuted MPS.

Regarding when this overhead outweighs state-preparation savings, our theoretical analysis and practical measurements indicate that classical preprocessing is not the dominant bottleneck, consistent with the amortization perspective discussed by [1]. Dataset-level calibration is performed only once and reused across samples, whereas quantum state-preparation circuits must be repeatedly executed. Given the importance of CX count and circuit depth on current quantum hardware, the additional classical computation is worthwhile when it yields substantial quantum-resource savings.

Therefore, the classical preprocessing overhead does not outweigh the quantum state-preparation savings, and QuSAE retains its overall resource advantages.

[1] Israel F. Araujo, Daniel K. Park, Francesco Petruccione, Adenilton J. da Silva. A divide-and-conquer algorithm for quantum state preparation. Scientific Reports 11, 6329, 2021. https://doi.org/10.1038/s41598-021-85474-1

Comments on the paper

3 comments
AuthorsOpenReview ↗

Author Response to Area Chair and Reviewers

We thank for the Area Chair for coordinating the review process of our work, and thank all Reviewers for their meaningful and constructive comments. We appreciate the Reviewers' recognition of the following strengths of our work:

  1. Problem formulation and structure-aware solution. QuSAE exploits the parent–child structure of wavelet tree representation to jointly decide which coefficients to retain and how to map them to the qubit register under an explicit fidelity constraint with lower complexity.

  2. Theoretical guarantees and cheap surrogate. Proposition 1 establishes that the retained-energy ratio exactly determines the truncation fidelity, enabling fidelity certification before MPS construction. Proposition 2 provides a computable prefix-based upper bound on MPS bond dimensions, avoiding repeated SVD computations during mapping search.

  3. Comprehensive and reproducible experiments. Comprehensive experiments on real-world images and signals demonstrate the trade-off between fidelity and representation complexity and the preservation of multiscale structure. Ablations isolate the contributions of tree structure and index mapping, and the provided code supports reproducibility.

In the rebuttal, we have addressed the reviewer's comments including:

  1. Same-representation baseline comparisons (Reviewer 4DEo, Reviewer NBX8, Reviewer wigZ). We expanded Fig. 3 in the revised manuscript to include both raw-domain and wavelet-domain baselines, isolating the contributions of QuSAE's structure-aware optimization beyond the wavelet transform.

  2. Quantum circuit resource validation (Reviewers 4DEo and wigZ). We substantially expanded the sequential circuit compilation experiments and incorporated the additional results into Section 4.2 and Table 1 of the revised manuscript. The updated results report MPS representation complexity, compiled CX counts, and circuit depths across five datasets and three fidelity thresholds, demonstrating that the representation-level savings translate into consistent reductions in actual compiled circuit resources.

  3. End-to-end cost analysis and theoretical scope (Reviewers 4DEo and wigZ). We expanded the appendices to provide a more comprehensive end-to-end cost analysis. We clarified the downstream application scenarios and analyzed the additional costs of inverse transformations. We also report the fitted tree- and prefix-compressibility exponents across all five datasets, and explicitly clarify the conditions under which the theoretical resource-scaling bounds apply.

We sincerely thank the Area Chair and all reviewers for their insightful feedback and constructive suggestions, which have helped us strengthen our work.

AuthorsOpenReview ↗

Follow-up on Rebuttal and Remaining Concerns

Dear Reviewers,

May we ask whether you have any remaining concerns regarding our rebuttal and additional experiments? We would greatly appreciate any further feedback on aspects that may require clarification or additional evidence, so that we can address them before the discussion closes.

Thank you again for your time and consideration.

Best regards,

Authors

AuthorsOpenReview ↗

Summary of Manuscript Revisions

We thank the reviewers for their constructive feedback. The major revisions in the revised manuscript, highlighted in blue, are summarized below:

  • Expanded the comparison with wavelet-domain baselines to assess the contribution of structure-aware optimization beyond the wavelet transform alone (Section 4.2 and Figure 3).
  • Added circuit compilation experiments across five datasets and three fidelity thresholds, reporting compiled CX gate counts and circuit depths under a common compilation protocol (Section 4.2, Table 1, and Appendix C.5).
  • Added end-to-end complexity and runtime analyses (Appendix D.2).
  • Analyzed inverse-transformation costs and added compiled original-domain preparation results (Appendix D.3).
  • Enlarged figure fonts and adjusted the layouts to improve readability and presentation (Figure 4 and Figure 5).
  • Updated the abstract, introduction, and conclusion to incorporate the circuit results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.