- 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
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 and inverse DWT must be applied.
2. Theoretical analysis. Following the permutation-reversal construction in [1], a permutation of qubit positions requires at most CX gates. For inverse DWT, [2] establishes a gate complexity of . For fixed wavelet order and , the combined restoration overhead is at most 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 to .
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.
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 , compiled CX gate counts, and full circuit depths for Standard MPS, Permuted MPS, and QuSAE across all five datasets at three matched fidelity thresholds: , , and . 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 (), with the fitted exponents and fitting errors annotated alongside the curves. Original Table 2 further reports the normalized fidelity-compatible support budgets () and the fitted tree-compressibility exponent (). The corresponding fidelity tolerances are .
To improve clarity, we have reorganized these results into a unified table (revised Table 4 in Appendix D.1), reporting the fitted exponents () and (), their goodness-of-fit values ( and ), and the resulting bond-dimension and sequential gate-count scaling exponents for all five datasets.
| Dataset | ||||||
|---|---|---|---|---|---|---|
| MNIST | 1.533 | 0.304 | 0.832 | 0.712 | 0.099 | 0.198 |
| COIL-20 | 0.828 | 0.329 | 0.935 | 0.841 | 0.199 | 0.397 |
| CelebA | 0.791 | 0.494 | 0.932 | 0.957 | 0.312 | 0.625 |
| MIT-BIH | 1.199 | 0.501 | 0.997 | 0.954 | 0.209 | 0.417 |
| STEAD | 1.023 | 0.418 | 0.773 | 0.788 | 0.204 | 0.409 |
Three observations follow from these results. First, all datasets exhibit and , supporting the empirical tree- and prefix-compressibility assumptions. Second, the resulting gate-scaling exponents implies sublinear growth of the representative bound with respect to . Third, higher 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) , (ii) on the same fidelity-feasible supports under the shared mapping, and (iii) , , and the associated constants to remain independent of over the considered range. For the practical joint-search output, its support size must additionally satisfy , where is independent of , 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.
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}. The complete results across all three fidelity thresholds (F≥0.95, 0.99, and 0.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.99, together with their relative changes with respect to the Standard MPS baseline:
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.