acceptodds
Under review as a conference paper at ICLR 2027

Prototype-Guided Optimization of Quantum Data Embeddings with Linear Cost

Abstract

In supervised quantum machine learning with classical data, classification performance critically depends on the geometry induced by quantum data embedding. Existing data-adaptive approaches rely on pairwise fidelity evaluations between samples, which scale as for samples and create a computational bottleneck in iterative embedding optimization. To address this issue, we propose a prototype-guided framework for efficient data-adaptive quantum embedding. Using class-prototype separation and sample-to-prototype compactness, we derive a measurable lower certificate for class-ensemble distinguishability and construct a prototype-based objective requiring only fidelity evaluations. We integrate this objective into an end-to-end pipeline that combines task-specific quantum circuit architecture optimization with continuous refinement of the data-embedding parameters. Across five benchmark datasets with up to 20 qubits, our method retains competitive quantum kernel support vector machine (SVM) performance while reducing fidelity-evaluation cost, with particularly strong gains over budget-matched pairwise optimization on T-MNIST. Geometric analyses examine how the learned embeddings relate to kernel alignment and classification margins, revealing dataset-dependent benefits and limitations. We further derive a prototype-based classifier in the reproducing kernel Hilbert space that provides an explicit witness for the SVM objective and a low-cost proxy for model selection, and extend the framework to multiple prototypes for multimodal class structures.

Primary area:
optimization
Keywords:
Quantum Machine Learning, Quantum Data Embedding, Optimization, Quantum Kernel Method, Quantum Support Vector Machine

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_bmByOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper replaces the O(B²) pairwise fidelity objective in quantum embedding optimization with a prototype-based objective that needs O(B) fidelity evaluations. It derives a trace-distance lower certificate for class-ensemble distinguishability, an RKHS prototype classifier as a cheap witness for the soft-margin SVM, and a multi-prototype extension. Experiments on five small datasets show competitive QKSVM performance, with a clear gain on T-MNIST.

Critical strengths
  1. The paper identifies a real bottleneck in data-adaptive quantum embedding optimization, namely the O(B²) pairwise fidelity evaluations repeated at every update, and addresses it with a change in objective structure rather than an approximation.

  2. The paper reports its limitations and supports the central claims with diagnostic analysis rather than only headline numbers.

Critical weaknesses
  1. Propositions 1–2 follow from standard trace norm inequalities, while Proposition 3 simply evaluates the SVM objective on a restricted classifier. The certificate is also vacuous on three of five datasets (Fig. 2), weakening its practical justification.

  2. Pairwise-B samples pairs globally, whereas Full uses class-balanced averaging in Appendix D.1. Their weighting differs on imbalanced data. A stratified, class-balanced sampling baseline would make the comparison more convincing.

  3. Linear scaling applies to fidelity counts per objective evaluation with fixed prototypes. Final QKSVM training still requires a quadratic kernel matrix. Total optimization costs, runtime, and finite-shot robustness are missing.

  4. Table 1 reports means without uncertainty, and most improvements outside T-MNIST are small or inconsistent. Paired confidence intervals and additional data splits would help establish reliability.

  5. The multi-prototype result is confounded. GLASS uses extra subclass labels and changes the scalarization strategy. Unsupervised prototypes and controlled objective ablations are needed to isolate the benefit of multiple prototypes.

Questions for authors
  1. Which configuration produced the GLASS and T-MNIST Prototype numbers in Table 1?
  2. Pairwise-B uses a refreshed random pair set per generation, while Prototype uses fixed anchors. Could authors report a fixed-pair budget-matched baseline, and ablate L_in, L_out, and L_sample separately? Without this, I cannot tell whether the T-MNIST gain comes from the certificate structure or from persistent anchors.?
  3. Are the test-split diagnostics in Section 3.2 and Appendices F.1 and F.2 used to make any design or reporting choice? The paper states that test data are not used for selection, but the margin and CKTA analyses are computed on test samples and support mechanistic conclusions.
6 comments

W1

Propositions 1–3 rely on standard inequalities, and the certificate is vacuous on three datasets.

We agree that Propositions 1–2 use standard trace-norm inequalities and that Proposition 3 evaluates the SVM objective at a feasible classifier. We do not claim a new norm inequality. Their contribution is to connect a small set of measurable prototype fidelities to the class-ensemble distinguishability ΔΦ\Delta_{\Phi} and to the downstream SVM objective. ΔΦ\Delta_{\Phi} is a trace norm between two mixed states and cannot be measured directly, so existing embedding objectives replace it with a Hilbert–Schmidt relaxation over all B(B−1)/2B(B-1)/2 pairwise fidelities (Lloyd et al., 2020; Hur et al., 2024). Because the prototype states are pure, Propositions 1–2 bound ΔΦ\Delta_{\Phi} itself from B+K(K−1)/2B+K(K-1)/2 fidelities, and Proposition 3 bounds the QKSVM objective from the same fidelities, without forming the B×BB\times B kernel.

The certificate is a measurable lower bound on ΔΦ\Delta_{\Phi}, obtained from B+K(K−1)/2B+K(K-1)/2 fidelities. On IRIS and T-CELL the low-loss circuits reach a positive value (Figure 2(a)), so there it certifies a non-trivial class-ensemble distinguishability at linear cost. On the other three datasets it is negative, and hence vacuous as a lower bound. Even there it keeps its second role, which is to determine which quantities the objective should contain and how they should be combined. Two observations support this role.

Both terms of the bound are needed. Removing either term of the objective on T-MNIST leads to a degenerate embedding (Q2). With the sample-to-prototype term alone, all states collapse to one point (Test MCC 0.0060.006). With the prototype-separation term alone, all states become mutually orthogonal and the kernel approaches the identity (Test MCC 0.5080.508, against 0.7610.761 for the full objective, all ten seeds).

The certificate tracks training performance on the tabular datasets, even where its value is vacuous. Figure 2(c) reports, over the circuits of Figure 2, the correlation of the Train-CV MCC of the QKSVM with the certificate (column "Prototype") and with the negative full pairwise loss (column "Full"). On the four tabular datasets the correlation with the certificate is positive (r=0.40r = 0.40–0.660.66), including VERTEBRAL and GLASS, where the certificate is negative. On noiseless T-MNIST it is negative (r=−0.39r = -0.39), but the full pairwise loss on the same circuits gives the same value (r=−0.39r = -0.39), so this behaviour is not specific to the prototype certificate. On IBM Heron, where the certificate of the selected circuit of each seed is estimated from measured counts, the correlation is positive (r=0.77r = 0.77, ten seeds).

W2 and Q2

A class-balanced, budget-matched fixed-pair baseline, and a separate ablation

Fixed-pair baseline. Following the reviewers' suggestion (and Reviewer 9ftv), we added a pairwise baseline with fixed, class-balanced pairs on every dataset. It uses the same number of fidelity evaluations per step as Prototype (e.g., 160 pairs on T-MNIST). Half of the pairs are same-class pairs, the classes and class pairs are sampled uniformly, and the pairs are drawn once and kept fixed for the whole run. Results are in Table 6.

On T-MNIST, Prototype outperforms all baselines on all 10 seeds:

T-MNISTTest MCCΔ\Delta (Prototype −- baseline) [95% CI]
Prototype.7787–
Full pairs.6868+.0919+.0919 [+.0656+.0656, +.1222+.1222]
Fixed class-balanced pairs.5180+.2607+.2607 [+.2117+.2117, +.3148+.3148]
Pairwise-B (original).6423+.1364+.1364 [+.1023+.1023, +.1706+.1706]

Class balancing does not close the gap. The fixed class-balanced baseline scores even below the original Pairwise-B.

The difference in weighting between Pairwise-B and Full therefore does not change any conclusion. On T-MNIST, persistence alone does not explain the gain. The fixed pairs are persistent, yet they are below Prototype on every seed and also below the refreshed Pairwise-B. Appendix G.1 shows that the fixed-pair objective already separates the training samples weakly, and that its fit is tied to its own pairs (loss 0.1750.175 on the 160160 optimized pairs, 0.2770.277 on all pairs of the same samples).

Ablation of LoutL_{\mathrm{out}} and LsampleL_{\mathrm{sample}}.

We first ablated the objective on T-MNIST, where the gain is clear. With one prototype per class, LinL_{\mathrm{in}} is identically zero, so the objective has two terms, LoutL_{\mathrm{out}} and LsampleL_{\mathrm{sample}}. We removed each term in turn, keeping the same fixed prototypes, GA budget and validation-based selection (Δ\Delta is Prototype −- variant, with paired 95% CI over 10 seeds):

ObjectiveTest MCCΔ\Delta [95% CI]
Lout+LsampleL_{\mathrm{out}}+L_{\mathrm{sample}} (paper).761–
LsampleL_{\mathrm{sample}} only.006+.755+.755 [+.724+.724, +.784+.784]
LoutL_{\mathrm{out}} only.508+.253+.253 [+.205+.205, +.299+.299]

Prototype objective without abilation outperforms both variants on every seed, and each term alone leads to a degenerate geometry. With LsampleL_{\mathrm{sample}} only, all states collapse to one point and every fidelity is close to 1. With LoutL_{\mathrm{out}} only, all states become mutually orthogonal, including each sample and its own prototype. As a result, the mean off-diagonal fidelity is 6⋅10−56\cdot10^{-5} and the effective rank of the kernel is 149 of 150, so the kernel approaches the identity. The two terms correspond to the two quantities in Proposition 1, prototype separation and sample-to-prototype distance, and neither suffices alone. Since both variants keep the same fixed prototypes, persistent anchors by themselves do not produce the T-MNIST gain.

Ablation of LinL_{\mathrm{in}}. LinL_{\mathrm{in}} is active only with several prototypes per class, so we ablated it in the multi-prototype GLASS setting of Section 3.3, removing each term in turn under the same GA budget:

ObjectiveTest MCCΔ\Delta [95% CI]
Lout+Lin+LsampleL_{\mathrm{out}}+L_{\mathrm{in}}+L_{\mathrm{sample}} (full).634–
without LoutL_{\mathrm{out}}.000+.634+.634 [+.604+.604, +.664+.664]
without LinL_{\mathrm{in}}.620+.014+.014 [−.038-.038, +.067+.067]
without LsampleL_{\mathrm{sample}}.603+.031+.031 [−.010-.010, +.075+.075]
LoutL_{\mathrm{out}} only.552+.082+.082 [+.027+.027, +.135+.135]

LoutL_{\mathrm{out}} is also essential. Without it, all states collapse to one point, and the test MCC drops to zero. For the two attraction terms the picture is less sharp. Removing LinL_{\mathrm{in}} or LsampleL_{\mathrm{sample}} alone changes the test MCC by +.014+.014 and +.031+.031, and both intervals include zero. Removing both costs .082.082 [+.027+.027, +.135+.135]. We read this as partial redundancy between the two terms, which is consistent with how the prototypes are built. In proxy-based metric learning the class representatives are defined in the embedding space, either as free parameters trained by the loss (Proxy-NCA, Proxy-Anchor) or as cluster centers of the embedded points (magnet loss). Our prototypes are defined in the input space, as the circular mean of each sub-cluster, and are then embedded by the same circuit as the samples. A change of the circuit therefore moves a prototype together with the samples whose inputs lie close to that mean, and a term that acts only on prototypes still constrains these samples indirectly. The same reasoning explains why LoutL_{\mathrm{out}} alone still reaches .552.552. This indirect control weakens as the inputs of a sub-cluster spread out around their mean, because samples far from the mean need not follow the prototype. Multi-center metric learning has the same structure, where guarantees on centers transfer to the examples only up to the sample-to-center distance (Qian et al., 2019). Controlling this distance directly is the role of LsampleL_{\mathrm{sample}}. We keep both terms, since the full objective has the highest mean MCC, but we do not claim that its difference from the single-term variants is significant.

W3

Total optimization cost, runtime and finite-shot robustness; the final QKSVM still needs a quadratic kernel.

We agree. The linear scaling refers to the number of fidelities per objective evaluation, with the prototypes fixed before the search, and the final QKSVM still requires the B×BB\times B training kernel and the Test ×\times Train kernel. These kernels are common to every objective and are computed once, after the optimization. The saving of the prototype objective lies inside the optimization loop, where the objective is evaluated for every candidate at every iteration. To measure both parts on a real QPU, we ran the full pipeline (GA and NQE) on IBM Heron processors (ibm_pittsburgh and ibm_boston) on T-MNIST (20 qubits, K=5K=5) for ten seeds, with a training coreset of B=100B=100 samples (20 per class). The same experiment is described in our answers to Reviewer LXe5 (W2, Q3) and Reviewer 9ftv (Q3), where we also give the per-step circuit counts for gradient-based training.

  • Optimization. Each candidate is evaluated with B+K(K−1)/2=110B+K(K-1)/2=110 inversion test at 1024 shots, and elite candidates are re-estimated with up to 4096 shots. The GA (population 50, 20 epochs per stage, 5 stages), together with 40 SPSA steps of NQE, took 10.6 QPU-hours per seed on average. An exact pairwise objective on the same samples needs B(B−1)/2=4950B(B-1)/2=4950 circuits per candidate, 45 times as many.
  • Final QKSVM kernel. After the optimization, the kernel of the selected embedding is measured once. The training kernel (upper triangle) and the Test ×\times Train kernel require 29,950 circuits per embedding at 1024 shots, about 2.4 QPU-hours per embedding (0.29 QPU-seconds per circuit, estimated from the submitted workload). This cost is quadratic in BB but is paid once and is the same for every objective. With the prototype objective it is smaller than the optimization cost above (10.6 QPU-hours). With an exact pairwise objective, the optimization would dominate the total cost by a wide margin.
  • Performance of the hardware-optimized circuits. The circuits optimized entirely on hardware, with 1024-shot fidelity estimates and a coreset of 100 training subsamples, reach a Test MCC of 0.7480.748 with the hardware kernel. This is slightly below the noiseless Prototype result in Table 1 (0.7610.761), and remains above the noiseless Full pairs (0.6570.657) and Pairwise-B (0.6360.636).
  • Effect of shot noise on the kernel. Evaluating the same circuits with the noiseless kernel gives a Test MCC of 0.7450.745, a difference of +0.003±0.015+0.003\pm0.015 over ten seeds. The 1024-shot hardware kernels correlate with the noiseless kernels at r=0.97r=0.97–0.9980.998.

W4

Table 1 uncertainty. We now report the 10-seed mean ±\pm standard deviation of Test MCC and ROC-AUC for every cell of Table 1. Table 6 also gives, for each baseline, a paired bootstrap 95% confidence interval of its difference from Prototype, with runs matched by seed.

On the four tabular datasets, most intervals include zero. After NQE, every tabular interval includes zero. At the GA stage, there are three exceptions:

  • On IRIS, Prototype is above Pairwise-B (+.019+.019 [+.006+.006, +.032+.032]) and marginally below Full pairs (−.017-.017 [−.033-.033, −.000-.000]).
  • On VERTEBRAL, Prototype is below Pairwise-B (−.046-.046 [−.079-.079, −.014-.014]).

On T-MNIST, every interval excludes zero in favour of Prototype.

The fixed ZZ feature map scores below every other method on every dataset, and all of its intervals against Prototype exclude zero. To save space, we omit it from the table.

We agree with the reviewer that on the tabular datasets a random subsample of pairs performs as well as the prototype objective, and we no longer claim a gain there. The gain we now claim is restricted to T-MNIST, where Prototype outperforms every pairwise variant on all 10 seeds. We analyse where this gain comes from in our response to W2 and Q2.

W5

The multi-prototype result is confounded by the subclass labels and by the change of scalarization

We agree that the comparison in Section 3.3 changes several things at once, and we separated them with two controlled experiments on GLASS. Both keep the GA, its budget and the validation-based selection fixed.

Subclass labels. We replaced the sub-label prototypes by unsupervised ones. The prototypes are the kk-means centers of the inner training samples, and the cell weights are the cluster fractions. No subclass label is used. But the number of prototypes per class (K=(2,1,3)K=(2,1,3)), the objective and its scalarization are unchanged. The unsupervised prototypes reach a Test MCC of 0.665±0.0650.665\pm0.065 (10 seeds), compared with 0.6340.634 for the sub-label prototypes. Against the single-prototype objective of Table 1 (0.5980.598) the difference is +0.067+0.067 [−0.003-0.003, +0.123+0.123], with 88 of 1010 seeds higher, and against Full +0.058+0.058 [−0.005-0.005, +0.119+0.119]. Because both intervals reach zero, we describe the gain over a single prototype as consistent across seeds but not dramatic.

Objective terms. With the scalarization held fixed, we removed each term of the multi-prototype objective in turn (W2/Q2). The two cohesion terms, LinL_{\mathrm{in}} and LsampleL_{\mathrm{sample}}, can replace each other, and LinL_{\mathrm{in}} alone does not account for the multi-prototype result. Its benefit comes from the additional prototypes.

Q1

Prototype configuration in Table 1

All Prototype rows of Table 1, including GLASS and T-MNIST, use a single prototype per class (K=1K = 1, circular-mean prototypes). We set them to one because we want to check first our optimization works well. The multi-prototype GLASS results are reported separately in Section 3.3 and do not enter Table 1.

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

The paper addresses the computational overhead of pairwise fidelity evaluations in data-adaptive quantum embedding for supervised quantum machine learning. The authors propose a prototype guided framework that reduces the number of fidelity evaluations from O(B2)\mathcal{O}(B^2) to O(B)\mathcal{O}(B) by optimizing class-prototype separation and sample to prototype compactness. The paper also provides a theoretical analysis connecting prototype geometry to quantum class-ensemble distinguishability.

Critical strengths
  1. The paper is well-written, clearly organized, and easy to follow.
  2. The paper is well-motivated and addresses a relevant computational bottleneck in data-adaptive quantum embedding optimization. It also establishes a theoretical connection between prototype geometry and quantum class ensemble distinguishability.
Critical weaknesses
  1. The central idea of replacing pairwise comparisons with prototype-based optimization has been extensively studied in classical metric learning, such as Proxy-NCA (https://arxiv.org/pdf/1703.07464) and Proxy Anchor Loss (https://openaccess.thecvf.com/content_CVPR_2020/papers/Kim_Proxy_Anchor_Loss_for_Deep_Metric_Learning_CVPR_2020_paper.pdf), etc. The proposed framework appears to follow the same general optimization principle, with quantum fidelity replacing classical similarity or distance measures.
  2. The experiments rely on noiseless statevector simulations, without analyzing the measurement overhead or wall-clock performance on quantum hardware.
  3. Although the paper provides a theoretical certificate, its tightness and practical relevance remain unclear.
Questions for authors
  1. How does the proposed method fundamentally differ from existing proxy-based deep metric learning approaches such as Proxy-NCA? What is the key quantum-specific novelty?
  2. Since Propositions 1 and 2 follow from standard norm inequalities, what additional theoretical insight do they provide beyond known prototype approximation bounds?
  3. What is the total computational cost of the proposed method, including circuit optimization, finite-shot fidelity estimation, and measurement overhead?
2 comments

W1 and Q1

Fundamental novelty against classical metric learning

Our contribution concerns what the prototypes let us establish for quantum embeddings. The trace norm ΔΦ=∥p+ρˉ+−p−ρˉ−∥1\Delta_{\Phi}=\lVert p_{+}\bar{\rho}_{+}-p_{-}\bar{\rho}_{-}\rVert_{1} is the fundamental quantity of interest: in binary classification it determines the minimum error for discriminating the embedded class ensembles, Perr∗=(1−ΔΦ)/2P_{\mathrm{err}}^{\ast}=(1-\Delta_{\Phi})/2, and it also affects the generalization performance (Banchi et al., 2021; Hur & Park, 2025). Evaluation of ΔΦ\Delta_{\Phi} generally requires spectral information about mixed states, which is difficult to obtain experimentally. Proposition 1 instead lower-bounds it using the fidelity between two pure prototype states and the fidelities between samples and their class prototypes. This requires B+1B+1 fidelity evaluations for BB samples, compared with B(B−1)/2B(B-1)/2 for the exact pairwise Hilbert–Schmidt objective. When the certificate is positive, it gives an upper bound on the optimal state-discrimination error.

This operational guarantee differs from the proxy-loss bounds in classical metric learning. Proposition 2 extends the geometric bound to multiple prototypes, and Proposition 3 connects the prototype classifier to the quantum-kernel SVM objective. We have clarified that our practical fidelity loss is motivated by the certificate; minimizing that loss does not guarantee an increase in the certificate or in QKSVM accuracy.

W3 and Q2

What Propositions 1–2 add beyond known prototype approximation bounds, and how tight and practically relevant the certificate is

Proposition 1 is an instance of the standard prototype-approximation argument. Replacing each sample by its representative changes a class-level quantity by at most the representation error. Here this error is the trace distance from the class-average state to the prototype state, bounded through convexity by the mean sample-to-prototype distance. The proxy bound of Movshovitz-Attias et al. (2017) has the same form.

What the propositions add is where the argument is applied. The quantity, ΔΦ\Delta_{\Phi}, is the trace norm of the difference between two mixed class-ensemble states, and it cannot be measured directly because it requires spectral information about this difference. Existing embedding objectives therefore replace it with a Hilbert–Schmidt relaxation (Lloyd et al., 2020; Hur et al., 2024), which is expressed through all B(B−1)/2B(B-1)/2 pairwise fidelities. We are not aware of a prior result that bounds ΔΦ\Delta_{\Phi} itself by prototype-level fidelities. This bound has three consequences:

  • Because the prototype states are pure, the separation term has the closed form 1−4p+p−Fc\sqrt{1-4p_{+}p_{-}F_{c}}, which needs one fidelity per class pair.
  • Compactness around each sample's own prototype and separation between prototypes suffice, and no per-sample negative comparisons are needed. This gives the cost of B+K(K−1)/2B+K(K-1)/2 fidelities.
  • Proposition 2 extends the certificate to several prototypes per class, for multimodal classes.

Tightness and practical relevance. The certificate is a measurable lower bound on ΔΦ\Delta_{\Phi}, obtained from B+K(K−1)/2B+K(K-1)/2 fidelities. On IRIS and T-CELL the low-loss circuits reach a positive value (Figure 2(a)), so there it certifies a non-trivial class-ensemble distinguishability at linear cost. On the other three datasets it is negative, and hence vacuous as a lower bound. Even there it keeps its second role, which is to determine which quantities the objective should contain and how they should be combined. Two observations support this role.

  • Both terms of the bound are needed. Removing either term of the objective on T-MNIST leads to a degenerate embedding. With the sample-to-prototype term alone, all states collapse to one point (Test MCC 0.0060.006). With the prototype-separation term alone, all states become mutually orthogonal and the kernel approaches the identity (Test MCC 0.5080.508). The full objective reaches 0.7610.761 and outperforms both variants on all ten seeds (see Reviewer bmBy).
  • The certificate tracks training performance on the tabular datasets, even where its value is vacuous. Figure 2(c) reports, over the circuits of Figure 2, the correlation of the Train-CV MCC of the QKSVM with the certificate (column "Prototype") and with the negative full pairwise loss (column "Full"). On the four tabular datasets the correlation with the certificate is positive (r=0.40r = 0.40–0.660.66), including VERTEBRAL and GLASS, where the certificate is negative. On noiseless T-MNIST it is negative (r=−0.39r = -0.39), but the full pairwise loss on the same circuits gives the same value (r=−0.39r = -0.39), so this behaviour is not specific to the prototype certificate. On IBM Heron, where the certificate of the selected circuit of each seed is estimated from measured counts, the correlation is positive (r=0.77r = 0.77, ten seeds).

W2 and Q3

Measurement overhead, total cost and wall-clock performance on quantum hardware.

To address this, we ran the full prototype pipeline on IBM Heron processors (ibm_pittsburgh, ibm_boston) on T-MNIST (2020 qubits, K=5K=5) for ten seeds, with a training coreset of B=100B=100 samples (2020 per class). All numbers below are measured on hardware unless stated otherwise.

  • Optimization. Each candidate is evaluated with B+K(K−1)/2=110B+K(K-1)/2=110 inversion test circuits at 1024 shots, and elite candidates are re-estimated with up to 4096 shots. The GA (population 50, 20 epochs per stage, 5 stages), together with 40 SPSA steps of NQE, took 10.6 QPU-hours per seed on average, as charged by IBM. An exact pairwise objective on the same samples needs B(B−1)/2=4950B(B-1)/2=4950 circuits per candidate, 45 times as many.

  • Final QKSVM kernel. After the optimization, the kernel of the selected embedding is measured once. The training kernel (upper triangle) and the Test ×\times Train kernel require 29,950 circuits per embedding at 1024 shots, about 2.4 QPU-hours per embedding (0.29 QPU-seconds per circuit, estimated from the submitted workload). This cost is quadratic in BB but is paid once and is the same for every objective. With the prototype objective it is smaller than the optimization cost above (10.6 QPU-hours). With an exact pairwise objective, the optimization would dominate the total cost by a wide margin.

  • Performance of the hardware-optimized circuits. The circuits optimized entirely on hardware, with 1024-shot fidelity estimates and a coreset of 100 training subsamples, reach a Test MCC of 0.7480.748 with the hardware kernel. This is slightly below the noiseless Prototype result in Table 1 (0.7610.761), and remains above the noiseless Full pairs (0.6570.657) and Pairwise-B (0.6360.636).

  • Effect of shot noise on the kernel. Evaluating the same circuits with the noiseless kernel gives a Test MCC of 0.7450.745, a difference of +0.003±0.015+0.003\pm0.015 over ten seeds. The 1024-shot hardware kernels correlate with the noiseless kernels at r=0.97r=0.97–0.9980.998.

Comparison with exact pairwise objectives. The number of circuits per optimization step is as follows (PP: number of data-dependent angles per embedding).

per optimization stepexact all pairsPrototype
objective evaluationB(B−1)/2B(B-1)/2B+K(K−1)/2B+K(K-1)/2
parameter-shift gradient(4P+1)B(B−1)/2(4P+1)B(B-1)/2(4P+1)(B+K(K−1)/2)(4P+1)(B+K(K-1)/2)
SPSA gradientB(B−1)B(B-1)2(B+K(K−1)/2)2(B+K(K-1)/2)

For the hardware setting (B=100B=100, K=5K=5) the exact pairwise objective needs 4545 times as many circuits per evaluation (49504950 against 110110). With the same shot schedule, the GA above would thus have required on the order of 4545 times its QPU time.

And thank you for our comments.

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

The paper studies the optimization of data-adaptive quantum data embeddings for supervised learning with classical data, where the learned embedding defines the fidelity kernel of a quantum kernel SVM (QKSVM). Many existing data-adaptive methods optimize objectives built from pairwise fidelities between embedded samples, so exact evaluation over BB samples requires O(B2)O(B^2) fidelity evaluations. The authors propose to replace the pairwise comparisons with comparisons between each sample and a prototype of its class, together with comparisons between the prototypes themselves. This requires B+(Ktot2)B+\binom{K_{\mathrm{tot}}}{2} fidelity evaluations for KtotK_{\mathrm{tot}} prototypes, which is O(B)O(B) when the number of prototypes is fixed. In the experiments, the prototype of a class is the coordinate-wise circular mean of its training inputs, embedded with the same circuit.

The objective is motivated by a lower bound, which the authors call a certificate, on the class-ensemble distinguishability ΔΦ\Delta_\Phi. Proposition 1 lower bounds the distinguishability in terms of the fidelity between the two prototype states and the mean trace distance between the samples their prototype. This is then extended to several prototypes per class. The practical objective replaces the trace distances with fidelity terms for sample-to-prototype compactness, within-class prototype coherence (when a class has several prototypes) and cross-class prototype separation. The authors also observe that the prototype classifier lies in the RKHS of the fidelity kernel, so the optimal soft-margin SVM objective is at most the objective at τhproto\tau h_{\mathrm{proto}} for any τ≥0\tau\ge0). They use this classifier as a cheap rule for choosing circuits on validation data.

The objective is used in a pipeline that first searches over circuit architectures with a genetic algorithm (GA) and then refines the embedding with neural quantum embedding (NQE), which keeps the circuit fixed and trains a small residual network that transforms the inputs. Experiments are run in noiseless statevector simulation on five datasets (IRIS, VERTEBRAL, T-CELL, GLASS and a five-class MNIST subset called T-MNIST) with 4 to 20 qubits, with the test MCC and AUC of the QKSVM as metrics. The baselines are a fixed ZZ feature map, full pairwise optimization, and a budget-matched pairwise baseline (Pairwise-B) that uses as many randomly sampled pairs as the prototype objective uses fidelities. The prototype objective is close to full pairwise optimization on the four datasets where the latter was run, and it is much better than Pairwise-B on T-MNIST (test MCC .7787 against .6423 after NQE). Further experiments compare circuits with low and high prototype loss in terms of the certificate, CKTA, test MCC and test margins, compare three validation rules for choosing a circuit, and test the multi-prototype objective on GLASS, where one prototype per original glass type raises the test MCC from 0.592 to 0.647.

Critical strengths

A simple proxy objective The prototype objective is easy to implement and needs only N+(C2)N+\binom{C}{2} fidelities per candidate circuit instead of (N2)\binom{N}{2}. At the GA stage it is within about 0.02 test MCC of full pairwise optimization on the four datasets where both were run, and it beats the fixed ZZ feature map on all datasets. For QML researchers that are interested in circuit embeddings, this is a useful practical option and the main strength of the paper.

Experimental results are well-presented The paper is careful in maintaining a consistent baseline and is upfront about when the methods fail their checks.

Critical weaknesses
  1. The main empirical claim is not well supported

The paper claims that the prototype objective keeps QKSVM performance competitive at linear cost, with a particularly strong gain over Pairwise-B on T-MNIST. On the four tabular datasets, the differences between Prototype, Pairwise-B and Full pairs in Table 1 are a few hundredths of MCC, and no standard deviations or confidence intervals are reported, so I cannot tell which of these differences are real. A random subsample of pairs of the same size does about as well as the prototype objective there.

This leaves T-MNIST as the dataset that separates the methods. However, Figure 2(c) shows that on T-MNIST the ten circuits with the highest training prototype loss reach a mean test MCC of about 0.83, while the ten circuits with the lowest loss reach about 0.72, and the two confidence intervals do not overlap. The circuit selected by the pipeline reaches .7606 (.7787 after NQE). So on this dataset a lower prototype loss goes with a lower test MCC, and circuits with a high prototype loss do better than the circuit selected by the pipeline. Given this, I do not think the gain over Pairwise-B on T-MNIST is shown to be attributed to the geometry induced by the prototype objective, as is claimed in the paper. A simpler explanation is that Pairwise-B is a weak baseline for a five-class task: it uses <200 of the 11175 training pairs, and only a fifth of them are same-class pairs. Full pairs would help settle this, but it is not reported on T-MNIST and the paper does not say why. The main text describes this behavior only as higher CKTA not translating "monotonically" into MCC, and it compares the low-loss circuits with the ZZ feature map rather than with the high-loss circuits, which I think somewhat understates the issue.

  1. Limited conceptual contribution

The paper is motivated by the O(B2)O(B^2) cost of exact pairwise objectives, but this count treats every fidelity as exact. On hardware, each fidelity is itself estimated from shots, and an average over pairs can be estimated to a fixed accuracy by sampling pairs, with a number of circuit runs that does not grow with BB. Lloyd et al. (2020), upon which this paper builds, estimate the Hilbert-Schmidt terms with repeated SWAP or inversion tests between sampled inputs and train with batches of two to five points, and the paper itself notes that NQE subsamples pairs. In the statevector simulations used for all experiments, the BB states can be computed once, and the full Gram matrix then costs one matrix product, which is small for the 4 to 9 qubit datasets. This makes the stated reason for omitting full-pairwise NQE refinement hard to follow for those datasets. The paper reports neither wall-clock times nor shot counts and never varies BB, so the practical size of the saving is not measured. At a comparable computational budget, the question is whether the prototype objective beats a subsampled pairwise objective, which brings us back to the first point.

Replacing pairwise comparisons with comparisons to class prototypes is also a well-established idea in metric learning, and this literature is not cited. Examples include center loss (Wen et al., 2016), prototypical networks (Snell et al., 2017), and Proxy-NCA (Movshovitz-Attias et al., 2017). Magnet loss (Rippel et al., 2016) represents each class by several k-means centers, which is conceptually close to the multi-prototype extension. Since Lloyd et al. (2020) already describe trainable quantum embeddings as quantum metric learning, this connection is direct and should be discussed further.

Questions for authors

Clarification requests.

  1. On T-MNIST, which depths do the high-loss and low-loss circuits in Figure 2 have? How do the authors reconcile the higher test MCC of the high-loss circuits with attributing the T-MNIST gain to the prototype geometry? Why is Full pairs not reported on T-MNIST, and could it be run, even with a smaller GA budget, together with a Pairwise-B variant that uses a fixed, class-balanced set of pairs? If Prototype still clearly beats both, the T-MNIST gain would be much more convincing.
  2. Could the authors report standard deviations or confidence intervals over the ten seeds for Tables 1 and 2? Without them I cannot tell whether the differences on the four tabular datasets are real.
  3. How are fidelities computed in the simulations, and what are the wall-clock times of the three objectives? In particular, why was full-pairwise NQE refinement too costly for the 4 to 9 qubit datasets? Evidence that the pairwise cost dominates in practice would change my view of the motivation.
  4. Beyond the use of quantum fidelities in place of classical similarity measures, what do the authors see as new relative to proxy-based metric learning, in particular Proxy-NCA and magnet loss?
5 comments

Response of Q1 and W1

Depths of the High-loss and Low-loss circuits of T-MNIST in Figure 2. Each group contains 100 circuits (10 seeds ×\times 10 circuits). Their depths are distributed as follows:

Depth2345
High-loss group93331
Low-loss group0102070

What the High-loss circuits are. The GA builds a circuit one layer at a time. At stage kk, every candidate keeps the incumbent layers 1,…,k−11,\dots,k-1 fixed, and only the new kk-th layer is searched. The High-loss circuits of the submitted figure therefore came mostly from depth 2.

Q1, Q3 and W2

Cost of full-pairwise objectives and NQE on T-MNIST, and a stronger baseline.

Our original GA runs compute each fidelity ∣⟨ϕ(x′)∣ϕ(x)⟩∣2|\langle\phi(x')|\phi(x)\rangle|^2 with the inversion test. The circuit U†(x′)U(x)U^\dagger(x')U(x) is applied to ∣0⟩⊗n|0\rangle^{\otimes n}, and the fidelity is the probability of the all-zero outcome. Our original tabular NQE uses Qiskit's EstimatorQNN, which evaluates every fidelity as a separate circuit instead of computing each embedded state once. Its cost therefore grows with the number of fidelity terms. Full-pairwise objective needs 3,486–14,878 fidelities per step on the tabular datasets, against 87–174 for Prototype. This is why full-pairwise NQE and the T-MNIST runs were expensive in our pipeline.

As the reviewer points out, this cost comes from that implementation, not from statevector simulation. We have re-implemented NQE with an exact PyTorch statevector backend, whose fidelities differ from Aer by at most 1.1⋅10−51.1\cdot10^{-5}, and we now report full-pairwise NQE on every dataset.

All results are now included in Table 1 and 6. On T-MNIST, Prototype achieves a higher Test MCC than the full-pairwise objective (after NQE), and the 95% confidence interval of the difference (Prototype minus Full pairs) excludes zero. The numbers are shown below.

Fixed, class-balanced Pairwise-B Baseline

Following the reviewer's suggestion, we added a pairwise baseline with fixed, class-balanced pairs on every dataset. It uses the same number of fidelity evaluations per step as Prototype (e.g., 160 pairs on T-MNIST). Half of the pairs are same-class pairs, the classes and class pairs are sampled uniformly, and the pairs are drawn once and kept fixed for the whole run. Results are in Table 6.

T-MNISTTest MCCΔ\Delta (Prototype −- baseline) [95% CI]
Prototype.7787–
Full pairs.6868+.0919+.0919 [+.0656+.0656, +.1222+.1222]
Fixed class-balanced pairs.5180+.2607+.2607 [+.2117+.2117, +.3148+.3148]
Pairwise-B (original).6423+.1364+.1364 [+.1023+.1023, +.1706+.1706]

Class balancing does not close the gap. The fixed class-balanced baseline scores even below the original Pairwise-B.

Wall-clock time in simulation

With the statevector backend, the pair count no longer determines the cost, because each embedded state is computed once and all fidelities are then obtained from one matrix product. On the tabular datasets, one NQE step with all pairs takes the same time as one step with the fixed pairs (13.5, 34, 89 and 134 ms on IRIS, VERTEBRAL, T-CELL and GLASS). On T-MNIST (20 qubits, one RTX PRO 6000 GPU), the GA took about 7.6 hours per seed with all 11,175 pairs and about 7.2 hours with the 160 fixed pairs, and one NQE step took about 8 and 15 seconds, respectively. We therefore do not claim that the pairwise cost dominates in statevector simulation at these sizes. It dominates when every fidelity has to be estimated as a separate circuit, which is the hardware setting below.

Wall-clock time in the Hardware

On a device, every fidelity is computed with the inversion test. With B samples, K prototypes and P data-dependent angles per embedding circuit, one optimization step needs:

per optimization stepexact all pairsPrototype
objective evaluationB(B−1)/2B(B-1)/2B+K(K−1)/2B+K(K-1)/2
parameter-shift gradient(4P+1) B(B−1)/2(4P+1)\,B(B-1)/2(4P+1) (B+K(K−1)/2)(4P+1)\,(B+K(K-1)/2)
SPSA gradientB(B−1)B(B-1)2 (B+K(K−1)/2)2\,(B+K(K-1)/2)

For T-MNIST (B=150B=150, K=5K=5, P≤200P\le200), one parameter-shift step needs 8.95⋅1068.95\cdot10^6 circuits with full pairs and 1.28⋅1051.28\cdot10^5 circuits with Prototype. On IBM Heron devices, a 1024-shot circuit took 0.29 QPU-seconds on average (299,500 kernel circuits in 24.1 QPU-hours). One parameter-shift step would therefore take about a month with full pairs and about ten hours with Prototype. Our hardware runs avoid parameter-shift gradients: the GA is gradient-free and NQE uses SPSA, which needs two objective evaluations per step. With a training coreset of B=100B=100, the complete optimization of one seed (GA and 40 SPSA steps of NQE) took 10.6 QPU-hours on these devices.

Subsampling pairs reduces the cost of the full-pair objective, but only a subset of the pairwise terms is optimized. At the Prototype budget, both the original Pairwise-B and the fixed class-balanced pairs perform clearly worse than Prototype on T-MNIST.

W1 and Q2

Variability across seeds and significance of the differences from the baselines.

We now report the 10-seed mean ±\pm standard deviation of Test MCC and ROC-AUC for every cell of Table 1. Table 6 also gives, for each baseline, a paired bootstrap 95% confidence interval of its difference from Prototype, with runs matched by seed. On T-MNIST, every interval excludes zero in favor of Prototype.

The fixed ZZ feature map scores below every other method on every dataset, and all of its intervals against Prototype exclude zero. To save space, we omit it from the table.

We agree with the reviewer that on the tabular datasets a random subsample of pairs performs as well as the prototype objective, and we no longer claim a gain there. The gain we claim is about T-MNIST, where Prototype outperforms every pairwise variant on all 10 seeds. We analyze where this gain comes from in our next response.

W1 and Q1

Reconciling the higher Test MCC of the High-loss circuits with attributing the T-MNIST gain to prototype geometry.

We agree that Figure 2 does not support attributing the T-MNIST gain to a geometry induced by lowering the prototype loss.

1. The reversal is real. In the submitted Figure 2, the two groups differed in depth, so we repeated the comparison within the selected depth of each seed, again taking the 10 lowest-loss and the 10 highest-loss circuits per seed. The revised Figure 2(b) shows this comparison. The Low-loss group still has the lower Test MCC (.723 vs .821; difference −.098-.098 [−.130-.130, −.071-.071]). It is specific to T-MNIST. On the tabular datasets, the Low-loss group performs equally well or better.

The new Figure 2(c) reports, over the circuits of Figure 2, the correlation of the Train-CV MCC with the certificate and with the negative full pairwise loss. Both quantities are oriented so that larger is better, so a positive rr means that a better training quantity goes with a higher Train-CV MCC. For the certificate, rr is positive on the four tabular datasets (0.400.40–0.660.66) and negative on T-MNIST (−0.39-0.39). The full pairwise loss gives the same value on T-MNIST (r=−0.39r=-0.39). Circuits with a lower full pairwise loss also have a lower Train-CV MCC. The reversal is therefore not specific to the prototype objective.

2. Where the T-MNIST gain comes from. We measured how much class separation each objective produces on the Train and validation samples after GA (new Appendix G.1), using the standardized contrast κ\kappa of Eq. (28).

T-MNIST, 10 seedsFull pairsPairwise-BFixed pairsPrototype
κ\kappa on Train / validation.68 / .54.36 / .36.29 / .27.61 / .63
Train-CV / validation MCC.674 / .563.475 / .514.387 / .397.630 / .673
Test MCC (Table 1).657.636.518.761
  • The pairwise loss value mainly reflects the overall fidelity level. With randomly permuted training labels, the Full-pairs loss still falls to .255, against .235 with the true labels. We therefore compare the objectives by κ\kappa and MCC, not by their loss values.
  • Pairwise-B and fixed pairs separate the classes weakly even on Train. The fixed-pairs loss is .175 on its own 160 pairs but .277 on all pairs of the same samples, so the separation it learns does not extend beyond the pairs it was trained on.
  • Full pairs separate best on Train but lose part of this separation on validation. Prototype does not. Relative to Full pairs, Prototype has a lower Train κ\kappa (−.063-.063 [−.106-.106, −.018-.018]) but a smaller drop from Train to validation (+.154+.154 [+.133+.133, +.172+.172]). On validation it is therefore higher both in κ\kappa (+.090+.090 [+.053+.053, +.130+.130]) and in MCC (+.110+.110 [+.074+.074, +.150+.150]), on all 10 seeds.
  • The smaller drop is not specific to T-MNIST. On three of the four tabular datasets, Prototype also drops less than Full pairs, by a similar margin (.12 to .19). There, however, Full pairs are far ahead on Train and stay ahead on validation. On T-MNIST the Train-side difference is small, so the smaller drop decides the comparison.

3. What we now claim. The T-MNIST gain comes from how the objectives behave on this task. Prototype separates the classes better than Pairwise-B and fixed pairs already on Train, and its separation carries over to new samples better than that of Full pairs.

W2 and Q4

beyond the use of quantum fidelities in place of classical similarity measures, what is new relative to proxy-based metric learning

We thank the reviewer for identifying this connection. Sample-to-representative learning is well established, and we now discuss Proxy-NCA, Proxy Anchor Loss, and Magnet loss in the revised paper. We do not claim that using prototypes is new.

Our contribution concerns what the prototypes let us establish for quantum embeddings. The trace norm ΔΦ=∥p+ρˉ+−p−ρˉ−∥1\Delta_{\Phi}=\lVert p_{+}\bar{\rho}_{+}-p_{-}\bar{\rho}_{-}\rVert_{1} is the fundamental quantity of interest: in binary classification it determines the minimum error for discriminating the embedded class ensembles, Perr∗=(1−ΔΦ)/2P_{\mathrm{err}}^{\ast}=(1-\Delta_{\Phi})/2, and it also affects the generalization performance (Banchi et al., 2021; Hur & Park, 2025). Evaluation of ΔΦ\Delta_{\Phi} generally requires spectral information about mixed states, which is difficult to obtain experimentally. Proposition 1 instead lower-bounds it using the fidelity between two pure prototype states and the fidelities between samples and their class prototypes. This requires B+1B+1 fidelity evaluations for BB samples, compared with B(B−1)/2B(B-1)/2 for the exact pairwise Hilbert–Schmidt objective. When the certificate is positive, it gives an upper bound on the optimal state-discrimination error.

This operational guarantee differs from the proxy-loss bounds in classical metric learning. Proposition 2 extends the geometric bound to multiple prototypes, and Proposition 3 connects the prototype classifier to the quantum-kernel SVM objective. We have clarified that our practical fidelity loss is motivated by the certificate; minimizing that loss does not guarantee an increase in the certificate or in QKSVM accuracy.

And thank you for your comments

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response for Summary of Revisions

We thank the reviewers for the time and care they devoted to evaluating our submission. Their feedback has been invaluable in helping us clarify and improve the paper. We appreciate their recognition that the problem is well motivated (LXe5, bmBy), that the prototype objective is simple, practical and a useful tool for researchers in this domain (9ftv), and that the paper connects prototype geometry to class-ensemble distinguishability (LXe5). We are also grateful for their assessment during the discussion that the primary weaknesses in the empirical evaluation are now addressed and that the revised framing in the context of existing work has improved the presentation (9ftv), that the new baseline and ablations strengthen the empirical support and the hardware results substantiate the optimization-cost argument (bmBy), and that the T-MNIST results are promising (bmBy).

Below we summarize the main experiments, analyses, and clarifications added in the revision. Test MCC values are 10-seed means, and intervals are paired bootstrap 95% confidence intervals. Detailed results are provided in our replies to the individual reviewers.

  1. Uncertainty (9ftv-Q2, bmBy-W4). Table 1 now reports mean ± standard deviation, and Table 6 gives the interval of every baseline's difference from Prototype. On T-MNIST every interval excludes zero in favor of Prototype; on the tabular datasets we no longer claim a gain.
  2. Full pairs on every dataset (9ftv-W1, Q1, Q3). With an exact statevector NQE, full-pairwise results are now reported everywhere. On T-MNIST, Prototype reaches .7787 against .6868 for Full pairs (+.0919 [+.0656, +.1222]).
  3. Fixed, class-balanced pair baseline (9ftv-Q1, bmBy-W2, Q2). At the same fidelity budget as Prototype it reaches .5180 on T-MNIST (+.2607 [+.2117, +.3148]); the original Pairwise-B reaches .6423 (+.1364 [+.1023, +.1706]). Prototype is higher on all 10 seeds.
  4. Source of the T-MNIST gain (9ftv-W1, Q1). The new Appendix G.1 measures class separation on Train and validation only. Prototype's separation carries over to new samples better than that of Full pairs (validation MCC +.110 [+.074, +.150], all 10 seeds).
  5. Objective ablations (bmBy-Q2). On T-MNIST, either term alone gives a degenerate embedding (Test MCC .006 and .508, against .761 for the full objective). On multi-prototype GLASS, removing the separation term collapses the embedding (.000 against .634).
  6. Hardware cost and performance (LXe5-W2, Q3; bmBy-W3; 9ftv-W2, Q3). The full pipeline was run on IBM Heron processors (T-MNIST, 20 qubits, 10 seeds, B=100B=100): 110 circuits per candidate against 4,950 for exact pairs, 10.6 QPU-hours per seed, and a Test MCC of .748 with the hardware kernel (noiseless Prototype in Table 1: .761).
  7. Multi-prototype control (bmBy-W5). Unsupervised kk-means prototypes on GLASS, with no subclass label, reach .665 against .598 for a single prototype, higher on 8 of 10 seeds.
  8. Relation to metric learning and the role of the theory (9ftv-W2, Q4; LXe5-W1, Q1, Q2; bmBy-W1). The revised paper discusses Proxy-NCA, Proxy Anchor and Magnet loss. Using prototypes is not claimed as new. The trace-norm distinguishability of the class ensembles governs optimal discrimination but cannot be measured directly; the contribution is a lower bound on it, and an explicit witness for the QKSVM objective, from a linear number of prototype fidelities.
  9. Use of Test data (bmBy-Q3). No Test diagnostic entered any selection, and the mechanistic analysis now rests on Train and validation data only.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.