- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes Shared Address Learning (SAL) to reduce the cost of amplitude encoding. SAL learns a permutation from unlabeled training data that preserves the amplitude kernel but can simplify state preparation. The method to find the permutation combines tests on correlation, local refinement, and selection by preparation fidelity. Experiments show improvements across several datasets and loaders.
Critical strengths
*The paper addresses an important bottleneck in quantum machine learning.
*The shared learned permutation preserves the ideal kernel. This provides a clear basis for comparing preparation methods.
*The theoretical results explain how changing the address can reduce preparation requirements.
*Improvements are consistent across several datasets, representations and loaders in experiments.
*The combination of correlation-based construction and successive refinement is interesting.
Critical weaknesses
*Comparison with alternative mapping strategies is limited. The paper discusses Jeon et al. and distinguishes their input-specific ordering from SAL’s shared permutation. However, no direct numerical comparison is provided. The experiments demonstrate improvements over natural addressing, but do not establish how SAL compares with other mapping strategies. This remains a major concern for assessing its relative benefits.
*The practical search has limited guarantees. SAL selects the best candidate from a small search set. The recovery guarantee applies to a specific constructed family. The quality on general datasets is supported empirically.
*Robustness to distribution shift is unknown. The learned permutation depends on training-data structure. Its preparation advantage may decrease on shifted data, although the ideal kernel remains preserved.
Questions for authors
The paper presents a useful approach with clear theoretical motivation and consistent empirical support. Its main value is improved state preparation under limited gate budgets. My main reservation is the limited numerical comparison with alternative mapping strategies to make the relevance of the SAL stronger. The comparisons with established loaders are useful, but address a different question: whether SAL improves those loaders relative to natural addressing. A controlled comparison with one or more mappings strategies would strengthen the evidence for SAL’s specific advantages.
Questions:
*Can SAL be compared with an alternative mapping strategy under comparable resource constraints? Jeon et al. (for example) is a relevant candidate, although its objective differs. Please explain how a fair comparison could account for preparation fidelity, classical search cost and reuse across inputs. If such a comparison is not doable, please clarify why. This discussion should be clear in the main text.
*Does a frozen learned permutation still has its loading advantage under distribution shift, such as translated or corrupted MNIST images?What about the other datasets?
To strenghten the paper content one can also (suggestions): *Add a short MNIST example showing the permutation and subsequent circuit fit. *Make the distinction between theoretical optimal fidelity and achieved fidelity more clear. *Emphasise the gate budget more clearly.
5 comments
W3 / Q2. Does a frozen learned permutation still has its loading advantage under distribution shift, such as translated or corrupted MNIST images? What about the other datasets?
Yes on MNIST, under every perturbation we tried. On the other datasets, the advantage carries over between datasets that share their dominant direction and is relearned otherwise. We froze the address and topology learned on clean MNIST and evaluated perturbed held-out images (App. G.5, Table 32; 128 fixed targets, five runs):
| Condition | 4 CX: natural | 4 CX: SAL | 20 CX: natural | 20 CX: SAL |
|---|---|---|---|---|
| Clean | 0.470 ± 0.000 | 0.587 ± 0.007 | 0.716 ± 0.020 | 0.793 ± 0.005 |
| Translation, ±2 px (4 directions) | 0.475 ± 0.000 | 0.549 ± 0.004 | 0.713 ± 0.018 | 0.774 ± 0.008 |
| Gaussian noise, σ = 0.1 | 0.496 ± 0.000 | 0.596 ± 0.007 | 0.706 ± 0.017 | 0.772 ± 0.004 |
| Gaussian blur, σ = 1 px | 0.570 ± 0.000 | 0.697 ± 0.007 | 0.813 ± 0.021 | 0.876 ± 0.004 |
| Contrast × 0.5 | 0.634 ± 0.000 | 0.711 ± 0.006 | 0.797 ± 0.014 | 0.846 ± 0.003 |
| Salt-and-pepper, 5% | 0.408 ± 0.000 | 0.497 ± 0.006 | 0.598 ± 0.016 | 0.656 ± 0.003 |
| Rotation −10° | 0.481 ± 0.000 | 0.600 ± 0.011 | 0.723 ± 0.022 | 0.807 ± 0.005 |
| Rotation +10° | 0.484 ± 0.000 | 0.610 ± 0.007 | 0.743 ± 0.019 | 0.810 ± 0.006 |
The size of the advantage follows the structure the address encodes:
- Rotations and blur keep the digit centered and its local correlations intact, and largely preserve the gain.
- Translations move content relative to the learned layout, and pixel-independent noise adds structure that no address can exploit; both reduce the gain moderately.
- Contrast reduction flattens images toward the uniform state, which raises the natural fidelity and leaves less headroom.
Other datasets. For feature data we tested the strongest form of shift, a change of dataset under the same frozen encoder (App. G.6; details in our reply to tCd3, Q5). The frozen address keeps 89–95% of its gain between CIFAR-10 and CIFAR-100, most of it from MNIST to KMNIST at , and almost none between SST-2 and AG News. What decides this is whether the two datasets share the dominant direction of , on which SAL anchors its address; the cosine between source and target (0.985, 0.842 and 0.195) is computable from unlabeled samples before reuse.
W2. The practical search has limited guarantees. SAL selects the best candidate from a small search set. The recovery guarantee applies to a specific constructed family. The quality on general datasets is supported empirically.
We agree that exact recovery is proven only for a structured family (Theorem 2), as is usual for searches over maps. The guarantees that matter for deployment, however, hold on every dataset, and where optimality can be measured, the search comes close to it.
- Dataset-independent guarantees. Whatever address is selected, the ideal kernel is preserved exactly (Eq. 3). Eq. (4) and Corollary 3 bound how any address can change a kernel learner's predictions. Eq. (9) gives every address the floor , which the principal-reference start is designed to raise.
- Measured optimality. The screened address ties with the best member of its bank at ; random family members, even screened, stay well below SAL (Table 25); and screening fidelity ranks candidates consistently with KRR validation accuracy (Spearman 0.79 on MNIST, 0.85 on CIFAR-10).
Suggestions. Add a short MNIST example showing the permutation and subsequent circuit fit. Make the distinction between theoretical optimal fidelity and achieved fidelity more clear. Emphasise the gate budget more clearly.
- MNIST example. Sec. 4.5 opens with the learned MNIST address as XOR rules over pixel row and column bits, a two-dimensional Gray code (all ten rules in Table 26). The fitted circuit of the same run is Fig. 7 (App. C.4), and prepared states at three budgets are in Fig. 14.
- Optimal versus achieved fidelity. Sec. 2.3, directly after Eq. (2), now states that the theory concerns the optimum , while experiments report the achieved fidelity of a specific loader.
- Gate budget. counts the CX gates of the preparation circuit (Sec. 2.3). Sec. 4.1 now states the range in absolute terms, 0–80 CX at , under a tenth of the order- CX of exact generic preparation.
We thank the reviewer again; the comparison has made SAL's specific advantages considerably clearer.
Thank you for the detailed response and additional experiments. The comparison with Jeon et al. at matched TT rank substantially addresses my main concern. The distribution-shift experiments also strengthen the paper. While the practical search remains supported mainly by empirical evidence on general datasets, I find the response convincing overall and maintain my weak acceptance. This is also due to my limited expertise in the specific field.
One small follow-up: could you give an approximate runtime comparison, including SAL’s initial learning cost? Roughly how many inputs are needed before reusing SAL becomes cheaper than running the per-input search?
We thank the reviewer for the constructive assessment. The main reservation, a controlled comparison with an alternative mapping strategy, is now in the main text (Sec. 4.2, Table 2), organized along the three axes the reviewer proposed.
Yes. Jeon et al. search a qubit (tensor-axis) ordering of an MPS for each input, so we compare at matched tensor-train (TT) rank, the resource both methods share. All arms use Jeon et al.'s released routine unchanged, one normalized TT-SVD scorer at rank χ and the 50 held-out targets per dataset of Table 10 (App. D.3); at χ=2 the scorer reproduces the one-layer MPS loader of Table 10. SAL arms are mean ± std over three source runs; the other arms are run-independent.
Preparation fidelity. On pretrained features the shared address alone exceeds per-input search by 0.12–0.21, with a gain over the natural order about three to five times larger. On MNIST, whose row-major order already carries spatial locality, the two are comparable. They compose: SAL followed by the search is best in every row.
Classical search cost. SAL is paid once per dataset, from unlabeled data: correlation statistics on 256 vectors and screening of at most 12 candidates on 128 inputs. A new input then costs one O(d) index gather. Per-input search is repeated for every input, at 104–105 SVD evaluations per feature vector in our runs.
Reuse across inputs. A shared address gives all inputs one coordinate system, so the ideal kernel and a single downstream model carry across the dataset. Per-input orderings give each input its own coordinates, so the same qubit carries different index bits for different inputs. This suits compressing individual states, but a learner across inputs must then undo each ordering before inputs can be compared.
Why the two differ. Qubit orderings form the n!-element bit-permutation subgroup of GL(n,2), the binary maps SAL searches. Optimal fidelity (Eq. 2) is invariant under qubit relabeling, so an ordering can adapt a fixed-chain loader to a state but cannot reduce the state's entanglement; a binary-linear address can.