acceptodds
Under review as a conference paper at ICLR 2027

Characterizing Projected Quantum Kernel Learning via Data-to-Readout Interfaces

Abstract

Quantum kernel methods map classical data into high-dimensional quantum state spaces, but projected learners access only a prescribed readout, leaving unclear how circuit structure determines the information available for learning. We introduce the data-to-readout interface to characterize this transfer. For linear projected quantum kernels, we show that the reachable readout dimension is exactly determined by the transfer channel restricted to the encoder span, while the intrinsic transfer dimension is bounded by the squared operator Schmidt rank of the fixed quantum process. Controlled interfaces further admit an exact factorization into input-dependent probabilities and fixed readout geometry. This factorization characterizes the population-kernel spectrum and effective dimension, determines when widening the interface provides additional target-relevant information, and yields finite-sample and measurement guarantees. We further show that statistical simplicity does not imply classical tractability: under standard complexity and cryptographic assumptions, even low-width interfaces can remain classically hard to evaluate, and a logarithmic-width construction yields a quantum–classical learning separation. Experiments on controlled circuits with up to 1000 qubits and on disordered transverse-field Ising ground states validate the structural bounds, target-alignment predictions, and finite-measurement trade-offs.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
quantum machine learning, projected quantum kernels

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_PPCNOpenReview ↗
Rating
3(+1)
Confidence
3(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a data-to-readout interface to connect circuit structure with the representation available to projected quantum kernel learning. It derives bounds on the readout dimension, classical tractability, and tests selected predictions numerically. From a high-level perspective, understanding how much useful information remains accessible through a limited quantum readout is an interesting problem in quantum machine learning. However, I find that some parts of both the theoretical and numerical contributions are overstated, and the essential contributions may not really meet the bar of ICLR (details are provided in the weakness part) I therefore do not recommend acceptance in its current form.

Critical strengths

The paper addresses a worthwhile research question, with a clear problem formulation and a thorough discussion of related work. It presents theoretical results alongside numerical experiments that provide some support for the authors’ theoretical claims.

Critical weaknesses
  1. The contribution beyond prior work is unclear. Several central observations have close precedents. Kübler et al. (2021) already discussed low-dimensional quantum kernels whose features can be classically hard to compute. Gan et al. (2023) studied feature representations and expressivity within a broad framework for quantum kernels. The connection between useful additional features and their correlation with the prediction residual also appears in Bang et al. (2026). Although these works are discussed, the substantial new insight beyond organizing existing ideas within the proposed interface model remains unclear, and it makes the current manuscript more like an incremental work.

  2. Much of the analysis applies to a restricted projected kernel construction: data are encoded only in subsystem A, while B starts in a fixed state and receives input dependence through a fixed circuit. Moreover, the decomposition into fixed states \tau_s requires the controlled structure in Eq. (3), or compatible extensions. This decomposition does not generally apply when data are encoded directly into both subsystems or when the circuit lacks this structure. In particular, the broader scope of Theorem 1 should be distinguished from the restricted analysis based on \tau_s . The latter does not provide a general characterization of projected quantum kernels. Actually, Huang et al. 2021 did not give such structure assumptions, and this dramatically diminishes the significance and generality of the proposed results.

  3. The theoretical analysis provides limited conceptual novelty, and the information-loss interpretation needs clarification. Theorem 1 follows from an operator Schmidt expansion and a dimension count, together with the established submultiplicativity of operator Schmidt rank. The efficient-evaluation part of Theorem 2 follows directly from K. These arguments are natural, but their implications seem largely expected. More importantly, the introduction asks, “How much input information can reach the readout,” suggesting an analysis of information lost through projection. However, M is the second-moment matrix of features already determined by the chosen encoder and projected kernel. It describes the resulting representation, but does not by itself measure what projection removes from the original representation.

  4. The quantum-advantage results also appear to offer limited additional insight. The observation that a constant-dimensional readout can retain computational hardness is not particularly surprising: a standard BQP computation already makes its decision by measuring a single output qubit. Copying this output into a blank readout register gives a straightforward construction of this kind. Furthermore, the two learning separations in Corollary 4 inherit their quantum learners and classical lower bounds from Liu et al. (2021) and Molteni et al. (2026), as the authors explicitly acknowledge. The added contribution is to represent these existing separations through narrow readouts. Theorem 2 includes a separate construction based on the Goldreich–Levin hard-core predicate, but its conceptual advance over established hardness-based constructions needs a clearer explanation. I recognize the statistical role of D yet D alone cannot determine classical tractability or quantum advantage. It remains unclear what additional guidance its analysis provides for identifying projected kernels that offer a learning advantage.

  5. The emphasis on 1000 qubits overstates the scale of the numerical evidence. In the 1000-qubit rank experiment, the largest tested interface has only five crossing gates, and both Q, G have rank 32. The tested circuits also admit efficient classical evaluation through low-width tensor-network contractions. This is a useful verification of the predicted rank bound, but it involves a highly structured circuit and a small readout feature space. It does not demonstrate learning with a computationally demanding 1000-qubit representation. The abstract should make these qualifications clearer, since emphasizing the total qubit count gives an exaggerated impression of the scale and difficulty of the experiment.

Questions for authors

Please refer to the weakness part.

16 comments
AuthorsOpenReview ↗

Response to Reviewer PPCN: Part1

Thank you for your thoughtful and constructive feedback! Your comments have helped us more clearly demonstrate our contribution beyond prior work and the scope of our results. We sincerely appreciate your valuable suggestions and address your questions point by point in the following eight comments.

W1. The contribution beyond prior work is unclear. Several central observations have close precedents. … Although these works are discussed, the substantial new insight beyond organizing existing ideas within the proposed interface model remains unclear, and it makes the current manuscript more like an incremental work.

Response to W1. To clarify what is new relative to prior work, we compared the dimension bound D≤2beffD\le2^{b_{\mathrm{eff}}} that Corollary 1 gives for controlled gates as in Eq. (3) with the bounds and feature counts of the three closest prior analyses [1,2,3] on the same circuits. In the revised manuscript, this comparison is in Appendix A.5 and in Table 8 of Appendix H.1.4 (Table R1 below), and the relation to [3] is discussed after Corollary 3. Overall, the comparison shows that the gates from the data register to the readout, with the local gates between them, set a bound on the dimension DD of Eq. (1), and this bound can lie far below the readout-size bound 4nB4^{n_B}. Specifically, on the circuits of Table R1 the prior bounds and counts stay near 4,096, while DD equals 2b2^b and grows only from 2 to 32. Below we explain in part 1 why DD follows the gates between the registers rather than the readout size, and in parts 2 to 4 how Corollary 1 differs from each of [1], [2], and [3].

Table R1. Dimension DD of Eq. (1) vs. feature counts of prior analyses (controlled circuits of Appendix G with six data and six readout qubits, m=512m=512 multi-XOR training inputs).

Number of CNOTs between the registers bbReadout bound 4nB4^{n_B} [1]Pauli expectation values, with identity [2]Non-identity Pauli observables 4nB−14^{n_B}-1 [3]Dimension DDExcess risk of kernel regression (σ2/m\sigma^2/m)
14,0964,0964,09522.1
24,0964,0964,09544.2
34,0964,0964,09588.3
44,0964,0964,0951617.9
54,0964,0964,0953236.0

1. DD and the estimation risk follow the gates between the registers, not the readout size. Table R1 compares DD with the bounds and counts of [1,2,3] on circuits that differ only in the number bb of CNOTs. Those bounds and counts stay near 46=4,0964^6=4,096, and even counting only the bb readout qubits reached by the CNOTs, the readout-size bound is still 4b4^b. In contrast, D=2bD=2^b grows only from 2 to 32. Sec. 4.1 of our paper gives the same D=2bD=2^b for N=20N=20 to 1,000 qubits, so DD does not grow with the readout. Accordingly, for targets in the feature span, the excess risk of kernel regression, averaged over label noise and training sets, follows DD rather than the readout size and stays close to σ2D/m\sigma^2D/m (last column of Table R1).

2. [1] uses the readout size 4nB4^{n_B} as the dimension bound, whereas Corollary 1 tells from the circuit when DD lies far below 4nB4^{n_B}. [1] argues that low-dimensional kernels can have classically hard features, and Corollary 1 shows when a circuit gives such a low-dimensional kernel. The bound 2beff2^{b_{\mathrm{eff}}} of Corollary 1 depends only on the controlled gates between the registers, not on the readout size.

3. Where [2] represents projected kernels in a Pauli or Mercer basis, Corollary 1 bounds the span dimension from the circuit before any feature is evaluated. In the Pauli basis, for example, 4,096 Pauli features have non-zero weight in Table R1 yet span only 2b2^b dimensions. In the Mercer basis, Corollary 1 likewise limits the number of nonzero eigenvalues to 2beff2^{b_{\mathrm{eff}}}.

References

[1] Kübler, Jonas, Simon Buchholz, and Bernhard Schölkopf. “The inductive bias of quantum kernels.” Advances in Neural Information Processing Systems 34 (2021): 12661–12673.

[2] Gan, Beng Yee, Daniel Leykam, and Supanut Thanasilp. “A unified framework for trace-induced quantum kernels.” arXiv preprint arXiv:2311.13552 (2023).

[3] Bang, Jeongho, et al. “Learning with active quantum subspaces: Scalable hybrid advantage without full quantum data-encoding.” arXiv preprint arXiv:2606.00932 (2026).

AuthorsOpenReview ↗

Response to Reviewer PPCN: Part2

4. Corollary 1 bounds the kernel-matrix rank from the circuit rather than from the number of measured observables as in [3], and Appendix C extends the residual criterion of Corollary 3 to refined features. [3] bounds this rank by the classical rank plus the number of measured observables. The circuits of Table R1 have no classical features, and then measuring all non-identity readout Pauli observables gives 4nB−1=4,0954^{n_B}-1=4,095, or 4nB4^{n_B} with the constant term. [3] also links useful extra features to the prediction residual, and the residual criterion of Corollary 3 likewise concerns appended features. In the coordinates of Eq. (4), however, adding CNOTs between the registers refines existing features rather than appending new ones. Appendix C therefore extends this residual criterion to the refinement under a compatible ridge penalty.

W2. Much of the analysis applies to a restricted projected kernel construction: data are encoded only in subsystem A, while B starts in a fixed state and receives input dependence through a fixed circuit. Moreover, the decomposition into fixed states τs\tau_s requires the controlled structure in Eq. (3), or compatible extensions. This decomposition does not generally apply when data are encoded directly into both subsystems or when the circuit lacks this structure. In particular, the broader scope of Theorem 1 should be distinguished from the restricted analysis based on τs\tau_s. The latter does not provide a general characterization of projected quantum kernels. Actually, Huang et al. 2021 did not give such structure assumptions, and this dramatically diminishes the significance and generality of the proposed results.

Response to W2. To show which results need the two restrictions named in the review, a blank readout and the controlled structure of Eq. (3), and which do not, we proved, as Proposition 3 in Appendix B.5 of the revised manuscript, a dimension bound that needs neither restriction, D≤min⁡{r2dim⁡VB, 4nB}D\le\min\{r^2\dim\mathcal V_B,\,4^{n_B}\} with rr as in Eq. (2) and VB\mathcal V_B the span of the data-encoded readout states σB(x)\sigma_B(x). We also checked this bound numerically in Table 4 of the same appendix (Table R2 below), and listed the results that still need both restrictions in a new paragraph after Corollary 1 and in Table 2 of Appendix A.4. Overall, when the data enter each register separately before a fixed circuit, the dimension bound of Proposition 3 needs neither restriction, whereas the factorization into fixed states τs\tau_s and the matrix GG, and the results built on this factorization, require both. Table R2 checks the first half of this statement. With one RyR_y angle on each readout qubit, DD grows with the number of CNOTs from 81 to 192 and never exceeds the bound of Proposition 3. Below we derive this bound in part 1, list which results need the two restrictions in part 2, and contrast the bound with the geometric difference of [4] in part 3.

Table R2. Dimension DD with a data-encoded readout and bb CNOTs between two fixed random local layers (nA=nB=4n_A=n_B=4).

Readout encodingb=0b=0b=1b=1b=2b=2b=3b=3
RyR_y angle on each qubit81108144192
RzRyR_zR_y angles on each qubit256256256256

1. The bound of Proposition 3 does not require a blank readout. Suppose the readout starts in a data-encoded state σB(x)\sigma_B(x), and the fixed circuit acts on ρA(x)⊗σB(x)\rho_A(x)\otimes\sigma_B(x). Expand the circuit into rr operator-Schmidt terms, with rr as in Eq. (2). Then ρB(x)\rho_B(x) is a sum of r2r^2 terms, each a fixed linear map of σB(x)\sigma_B(x) times an input-dependent coefficient. Hence D≤min⁡{r2dim⁡VB, 4nB}D\le\min\{r^2\dim\mathcal V_B,\,4^{n_B}\}, where VB\mathcal V_B is the span of the states σB(x)\sigma_B(x). Table R2 evaluates this bound. With one RyR_y angle on each readout qubit, DD equals dim⁡VB=81\dim\mathcal V_B=81 at b=0b=0 and grows to 192 at b=3b=3, within the bound. With RzRyR_zR_y angles, DD already reaches the maximum 4nB=2564^{n_B}=256 at b=0b=0. For controlled gates as in Eq. (3), decomposing ρB(x)\rho_B(x) over the control sectors replaces r2r^2 by 2beff2^{b_{\mathrm{eff}}} and gives D≤min⁡{2beffdim⁡VB, 4nB}D\le\min\{2^{b_{\mathrm{eff}}}\dim\mathcal V_B,\,4^{n_B}\}. The branch states then depend on xx and are no longer fixed (we write them here as τs(x)\tau_s(x)), but this bound still holds.

References

[3] Bang, Jeongho, et al. “Learning with active quantum subspaces: Scalable hybrid advantage without full quantum data-encoding.” arXiv preprint arXiv:2606.00932 (2026).

[4] Huang, Hsin-Yuan, et al. “Power of data in quantum machine learning.” Nature Communications 12.1 (2021): 2631.

AuthorsOpenReview ↗

Response to Reviewer PPCN: Part3

2. The analysis based on τs\tau_s differs in scope from Theorem 1, and the revised manuscript states which results rely on τs\tau_s. With a blank readout, Theorem 1 holds for any fixed circuit after the encoder. The fixed states τs\tau_s and the fixed matrix GG, by contrast, additionally require Eq. (3) or the sector-preserving extensions of Appendix B. The results that rely on τs\tau_s and GG are Corollary 1, the control-qubit sampling results of Sec. 4.3, the explicit form of Corollary 3, Theorem 2, and the controlled realization in Corollary 4. Theorem 1, Corollary 2, the bound (4b+2)/3(4^b+2)/3 of Appendix F, and the KRR risk bounds of Appendices E.2–E.3 do not rely on τs\tau_s and GG. In particular, with a blank readout the bound of Appendix F holds for controlled gates with arbitrary local gates between them, so it does not need Eq. (3).

3. Unlike the geometric difference of [4], the bound D≤min⁡{r2dim⁡VB, 4nB}D\le\min\{r^2\dim\mathcal V_B,\,4^{n_B}\} of Proposition 3 is set by the circuit before any kernel entry is computed, and it needs neither restriction when the data are encoded in each register separately. The geometric difference of [4] compares the prediction-error bounds of a quantum and a classical kernel through a scalar computed from both evaluated kernel matrices, so the matrices must be computed first. On the other hand, when both restrictions hold, that is, with a blank readout and the controlled structure of Eq. (3), the blank readout gives dim⁡VB=1\dim\mathcal V_B=1, so the controlled-case bound D≤min⁡{2beffdim⁡VB, 4nB}D\le\min\{2^{b_{\mathrm{eff}}}\dim\mathcal V_B,\,4^{n_B}\} of Proposition 3 gives the bound 2beff2^{b_{\mathrm{eff}}} of Corollary 1. The results built on GG then also become available. In the revised manuscript, this comparison with [4] is in Appendix A.5.

References

[4] Huang, Hsin-Yuan, et al. “Power of data in quantum machine learning.” Nature Communications 12.1 (2021): 2631.

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

This paper introduced the data-to readout interface to characterize how circuit structure determines the information available for learning. The authors introduced the data-to-readout interface to characterize this transfer. Controlled interfaces further admit an exact factorization into input-dependent probabilities and fixed readout geometry. Experiments on controlled circuits with up to 1000 qubits and on disordered transverse-field Ising ground states validate the structural bounds, target-alignment predictions, and finite measurement trade-offs. The work provides an interesting result to understand the capability of readout for quantum kernel learning. It is an excellent addition to the emerging area of quantum machine learning.

Critical strengths

The authors well investigated the following three important questions theoretically and experimentally: How much input information can reach the readout, which part is useful under finite learning resources, and when can the resulting representation be evaluated classically? The theoretical and experimental results are well presented. The work provides an interesting addition to existing results in the emerging area of quantum machine learning.

Critical weaknesses

The results are mainly limited to linear projected quantum kernels. The applicability should be more clearly clarified. The authors claimed that their experiments are implemented up to 1000 qubits. The circuit details seem to not be clear.

Questions for authors

What is the specific circuit used for 1000 qubits? What is the impact of noise on the performance?

4 comments
AuthorsOpenReview ↗

Response to Reviewer ptye: Part1

Thank you for your thoughtful and constructive feedback! Your comments have helped us more clearly demonstrate where our results apply, specify the 1,000-qubit circuit, and quantify the effect of noise. We sincerely appreciate your valuable suggestions and address your questions point by point in the following three comments.

W1. The results are mainly limited to linear projected quantum kernels. The applicability should be more clearly clarified.

Response to W1. To state which projected kernels each result covers, we wrote the scope of each result into the paper and compared linear and Gaussian projected kernels on the same readout states. In the revised manuscript, the scope is stated in the Abstract, in Sec. 3.1, and in Table 2 of Appendix A.4, and the comparison is Table 14 of Appendix H.3.7 (Table R1 below). Overall, our results on the dimension DD hold for every projected kernel, and our spectral, sample, and measurement results are for the linear projected kernel. The comparison further shows that, in our experiments, the wiring of the control qubits matters far more than the kernel. Below we explain the scope in part 1 and the comparison in part 2.

1. The results on DD cover every projected kernel because any projected kernel sees the input only through ρB(x)\rho_B(x). Any projected kernel, including the Gaussian projected kernel of [1], accesses the input only through ρB(x)\rho_B(x), and the span of ρB(x)\rho_B(x) has dimension DD. The bounds on DD therefore hold for all of these kernels. A nonlinear kernel, however, can have a feature space larger than DD, whereas the spectral, sample, and measurement results use the DD-dimensional feature space of the linear kernel, so these results are for the linear projected kernel.

Table R1. Linear vs. Gaussian projected kernels on the same readout states (bb CNOTs between the registers). The Gaussian kernel is exp⁡(−∥ρB(x)−ρB(x′)∥F2/ℓ2)\exp(-\|\rho_B(x)-\rho_B(x')\|_F^2/\ell^2) on the whole readout state, with ℓ\ell chosen by cross-validation.

KernelTFIM test MSE, localized wiring (b=4b=4)TFIM test MSE, distributed wiring (b=2b=2)XOR test accuracy, 1,000 qubits, localized wiring (b=8b=8)XOR test accuracy, 1,000 qubits, distributed wiring (b=8b=8)
Linear projected kernel2.46×10−32.46\times10^{-3}7.06×10−147.06\times10^{-14}0.900.66
Gaussian projected kernel2.58×10−32.58\times10^{-3}7.7×10−107.7\times10^{-10}0.930.66

2. In our experiments, the choice between linear and nonlinear kernels matters far less than the wiring of the control qubits. Table R1 compares linear and Gaussian kernels on the same readout states. For both kernels, distributed wiring gives a far lower TFIM test MSE than localized wiring, and the Gaussian kernel does not close this gap. On the 1,000-qubit XOR task, the two kernels differ by at most 0.03, whereas distributed wiring lowers accuracy to 0.66 for both.

References

[1] Huang, Hsin-Yuan, et al. “Power of data in quantum machine learning.” Nature Communications 12.1 (2021): 2631.

AuthorsOpenReview ↗

Response to Reviewer ptye: Part2

W2&Q1. The authors claimed that their experiments are implemented up to 1000 qubits. The circuit details seem to not be clear. What is the specific circuit used for 1000 qubits?

Response to W2&Q1. To specify the 1,000-qubit circuit, we added a diagram with the direction of the CNOT chain in each encoder layer and the positions of the CNOTs between the registers as Figure 4 in Appendix G.1 of the revised manuscript. Overall, the controlled circuit of Appendix G with localized wiring has 500 data qubits and 500 readout qubits initialized in ∣0⟩|0\rangle, with two encoder layers followed by bb CNOTs from data qubits to readout qubits.

Specifically, each encoder layer applies an input-dependent RyR_y rotation and fixed random RyR_y and RzR_z rotations to every data qubit. It ends with a one-directional CNOT chain between neighboring data qubits. A fixed random single-qubit layer then acts on all qubits. Next, bb CNOTs run from the first bb data qubits to the corresponding readout qubits, and a second such layer follows. No two-qubit gate acts in the readout. We evaluate the kernel using K=QGQ⊤K=QGQ^\top (Eq. (6)). To check this evaluation, for an off-diagonal input pair at b=5b=5, the result agrees with the four-copy contraction of Appendix G within 3.1×10−133.1\times10^{-13}.

Q2. What is the impact of noise on the performance?

Response to Q2. To verify the effect of noise, we adopted the common incoherent noise models, Pauli, depolarizing, dephasing, and amplitude-damping noise, analyzed them inside the controlled interface, and simulated gate noise in three settings, with readout noise added in the MNIST setting. The new results are in the revised manuscript, the theory as Lemma 9 with its proof in Appendix F.1 and the experiments as Tables 24–26 of Appendix H.4.10 (Tables R2–R4 below). Overall, under the conditions of Lemma 9, these noise models cannot raise DD above the noiseless bound 2beff2^{b_{\mathrm{eff}}} of Eq. (4). The experiments add that, in our tested settings, noise mainly requires more shots rather than changing DD. Below we explain the theory in part 1 and the experimental results in part 2.

1. Two results bound DD under noise, one for noise on the readout after the circuit and one for noise inside the controlled interface. First, fixed noise acting only on the readout after the whole circuit is a fixed linear map, so it cannot increase DD (Proposition 17 of the revised manuscript, Proposition 14 in the submitted version). Second, Lemma 9 covers fixed, input-independent noise before, between, or after the CNOTs whose Kraus operators act on the other data qubits as a scalar multiple of a unitary, map each control basis state to a multiple of a basis state, injectively on the patterns they do not annihilate, and act arbitrarily on the readout. Channels acting only on the other data qubits are also allowed. Pauli, depolarizing, dephasing, and amplitude-damping noise [2] satisfy these conditions. Under these conditions, the partial trace still removes all cross terms, and the readout state remains a mixture of 2beff2^{b_{\mathrm{eff}}} fixed states with input-dependent weights, so D≤2beffD\le2^{b_{\mathrm{eff}}}. Both results are upper bounds and do not say that DD stays unchanged under noise. A coherent rotation that mixes the control sectors, such as an RxR_x rotation at a generic angle between two CNOTs on the same control, is not covered by Lemma 9.

References

[2] Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

AuthorsOpenReview ↗

Response to Reviewer ptye: Part3

2. In the tested settings, incoherent noise leaves DD unchanged and mainly costs shots, and control-qubit sampling is less affected than the SWAP test. We ran three tests, on the dimension, on TFIM regression, and on MNIST classification.

Table R2. Effect of noise after each CNOT on DD in the tested layouts.

Noise after each CNOTControl qubitsDimension DD
NoneDistinct or shared2beff2^{b_{\mathrm{eff}}}
Depolarizing, dephasing, or amplitude dampingDistinct or shared2beff2^{b_{\mathrm{eff}}}
Coherent RxR_x rotationEach used once2beff2^{b_{\mathrm{eff}}}
Coherent RxR_x rotationShared by several CNOTs4beff4^{b_{\mathrm{eff}}}

(i) Dimension. Table R2 applies a noise channel to every qubit after each CNOT in exact simulations. Depolarizing, dephasing, and amplitude-damping noise leave DD at 2beff2^{b_{\mathrm{eff}}} in all tested layouts. By contrast, coherent RxR_x rotations at generic angles mix the control sectors and fall outside Lemma 9, and in the tested layouts they raise DD only when several CNOTs share the rotated control qubit. For example, DD rises from 2 to 4 with two CNOTs on one control.

Table R3. Ratio of TFIM test MSE under depolarizing noise to the noiseless value, with 10510^5 readout shots per input.

Noise strength pp0.010.050.10.2
Predicted ratio1.091.572.476.53
Measured ratio, distributed wiring, b=2b=21.141.762.466.57
Measured ratio, localized wiring, b=5b=51.091.562.406.02

(ii) TFIM with depolarizing noise. Depolarizing noise of strength pp acts on each control qubit before its CNOT and on the target qubit afterward, and leaves DD unchanged. In both wirings of Table R3, the target ⟨Z0Z4⟩\langle Z_0Z_4\rangle is exactly representable, and without shot noise the test MSE stays below 10−710^{-7} for p≤0.2p\le 0.2. With 10510^5 readout shots per input, the largest budget tested, noise raises the test MSE by the factors in Table R3, 1.09 to 6.57, and a variance estimate predicts these factors within 13%. These results agree with the known concentration of kernel values under noise, which requires more shots [3].

Table R4. MNIST 3 vs. 5 test accuracy under gate and readout noise (b=6b=6). The noise scale η\eta multiplies all depolarizing strengths. The strengths are 10−410^{-4} for data-qubit rotation blocks and 10−310^{-3} for data-register CNOTs and readout targets after CNOTs between the registers. Every measured bit flips with probability 10−2η10^{-2}\eta.

Estimatorη=0\eta=0η=1\eta=1η=3\eta=3η=10\eta=10
Exact noisy kernel0.8690.8700.8690.869
Control-qubit sampling, 1,000 shots per input0.8450.8450.8400.807
Control-qubit sampling, 100 shots per input0.7770.7570.7500.681
SWAP test, 1,000 shots per input pair0.6300.6170.5970.527

(iii) MNIST with gate and readout noise. Table R4 evaluates classification on a smaller MNIST circuit with eight data and eight readout qubits. Up to noise scale η=10\eta=10, exact noisy kernels achieve accuracy between 0.869 and 0.870. Control-qubit sampling measures only the control qubits, uses the known overlaps of the noisy fixed states, and corrects flips at known rates. For η≤3\eta\le 3 and 1,000 shots per input, it loses at most 0.5 percentage points from its noiseless accuracy.

For comparison, the SWAP test [4] measures each input pair separately. For our simulated 512×512512\times512 kernel matrix, the SWAP test uses 256.5 times as many shots in total as control-qubit sampling. We model the SWAP test with Gaussian sampling noise on each kernel entry, applying the bit flips to the Bell-measured bits of each qubit pair and inverting them at the known rates. For η≤3\eta\le 3 it loses up to 3.3 percentage points and at η=10\eta=10 it loses 10.3, against 0.5 and 3.8 for control-qubit sampling.

References

[3] Thanasilp, Supanut, et al. “Exponential concentration in quantum kernel methods.” Nature Communications 15.1 (2024): 5200.

[4] Buhrman, Harry, et al. “Quantum fingerprinting.” Physical Review Letters 87.16 (2001): 167902.

Thank you again for highlighting these important and practical questions.

We wanted to gently follow up on the questions you raised. Our rebuttal responds directly to your questions about the applicability of our results beyond linear projected quantum kernels (W1); the specific circuit used for the 1,000-qubit experiments (W2&Q1); and the impact of noise on the performance (Q2).

Whenever convenient, please let us know whether these responses address your questions, or whether the scope of our results or the experimental details remain unclear. We would be glad to clarify further.

Thank you again for your time and thoughtful feedback.

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

The paper studies linear projected quantum kernels in a “bottleneck” architecture that is the circuit-level map from encoded data. Specifically, it aims to answer the following questions: How much input information can reach the readout, which part is useful under finite learning resources, and when can the resulting representation be evaluated classically?

The paper introduces the “data-to-readout interface” and provides upper bound on the reachable feature dimension using the rank of the transfer channel. On the computational side the paper shows the constant feature dimension interfaces can hide BQP-hard quantities, snd gives a Goldreich–Levin learning separation. Experiments support the theoretical results particularly they verify rank saturation.

Critical strengths

Experiments are thorough. The finite shot results are the most informative part. The paper is carefully written and, as far as I checked (Theorem 1, Corollaries 1–2) are correct.

Critical weaknesses

The paper is very difficult to follow! For some reason, I could not follow the text. So I started reading the technical parts such as Thm1. But I found some of these results elementary. For example, theorem 1 is the statement that ρB(x)=N(ρA(x))ρ_B(x) = \mathcal{N}(ρ_A(x)) for a fixed linear map, so rank is bounded by channel rank. The r2r^2 bound is immediate from the Schmidt decomposition. Corollary 2 is data processing.

Questions for authors

How does the analysis apply when readout qubits are data-encoded (standard PQK, see for example Huang et al. (2021))? Is there any case where D is strictly smaller than the 2b2^b (or 4nB4^{n_B}) count one gets from “number of classical features”?

4 comments
AuthorsOpenReview ↗

Response to Reviewer iYKJ: Part1

Thank you for your thoughtful and constructive feedback! Your comments have helped us improve the exposition and more clearly demonstrate what our results reveal about circuits. We sincerely appreciate your valuable suggestions and address your questions point by point in the following three comments.

W1. The paper is very difficult to follow! For some reason, I could not follow the text.

Response to W1. To make the paper easier to follow, we adjusted the order of presentation in Sec. 3 and revised the language. For the order, the revised manuscript keeps the original order of the theorems, but Sec. 3 now opens by summarizing the main results, each of its subsections opens with what it shows, and every result is followed directly by the main step of its proof and a pointer to the full proof. For the language, we defined each term at first use, split long sentences, expanded abbreviations, and removed repeated framing in Sec. 1–5, in the descriptive text of Appendices A, G, and H, and in the statements and proof outlines of Appendices B–F. In addition, Table 2 in Appendix A.4 lists the assumptions behind each result. Overall, a reader can now see what each result of Sec. 3 states, why it holds, and which assumptions it needs, without first working through the derivations.

W2. So I started reading the technical parts such as Thm1. But I found some of these results elementary. For example, theorem 1 is the statement that ρB(x)=N(ρA(x))\rho_B(x)=\mathcal N(\rho_A(x)) for a fixed linear map, so rank is bounded by channel rank. The r2r^2 bound is immediate from the Schmidt decomposition. Corollary 2 is data processing.

Response to W2. To separate the standard steps named in the review from the results built on them, we added small examples that compare DD with the r2r^2 bound and the channel rank rtrr_{\mathrm{tr}}, and an outline at the start of each proof. In the revised manuscript, the examples are Table 3 in Appendix A.6 (Table R1 below), and each of the 35 proofs in Appendices B–F opens with an outline naming the standard tool and the step where assumptions enter. Overall, we agree that Theorem 1, the r2r^2 bound, and Corollary 2 use standard tools, and the results built on them, Corollary 1 with its extension in Appendix F and the hardness and learning parts of Theorem 2, are not elementary. The examples of Table R1 also show that Theorem 1 gives the exact value of DD and that DD can lie well below the channel rank, for example D=7D=7 where rtr=16r_{\mathrm{tr}}=16 in the last row of Table R1. Below we explain that Theorem 1 gives DD exactly in part 1, how Corollary 1 improves on the r2r^2 bound in part 2, and the hardness and learning results of Theorem 2 in part 3.

Table R1. Upper bounds r2r^2 and rtrr_{\mathrm{tr}} of Eq. (2) vs. dimension DD (nA=nB=3n_A=n_B=3).

Gates across the registersEncoderBound r2r^2Bound rtrr_{\mathrm{tr}}Dimension DD
One CNOTRyR_y angle on each qubit422
One two-qubit Haar-random gateRyR_y angle on each qubit1643
Haar brick-wall, two crossing gatesHaar-random states2561616
Haar brick-wall, two crossing gatesRyR_y angle on each qubit2561612
Haar brick-wall, two crossing gatesOne angle shared by all qubits256167

1. Theorem 1 gives DD exactly, and DD can lie well below the channel rank rtrr_{\mathrm{tr}}. Specifically, DD is the rank of the transfer map on the span of the encoder states (Eq. (2)). Table R1 compares DD with r2r^2 and rtrr_{\mathrm{tr}} on five small examples, and in the last row, rtr=16r_{\mathrm{tr}}=16 but D=7D=7.

2. The r2r^2 bound is direct, and Corollary 1 improves on it and leads to our finite-shot results. The r2r^2 bound follows directly from the operator Schmidt decomposition of the circuit [1], and for bb CNOTs it gives r2≤4br^2\le4^b. Corollary 1 improves on the r2r^2 bound by using the controlled structure of Eq. (3), and it bounds DD by 2beff2^{b_{\mathrm{eff}}} for beffb_{\mathrm{eff}} distinct control qubits (Eq. (4)). When local gates mix the control sectors, Appendix F gives (4b+2)/3(4^b+2)/3, attained at b=4b=4 with D=86D=86 (Sec. 4.1). Corollary 1 also leads to the finite-shot results of Sec. 4.3, which the review calls most informative. With known GG, measuring only the control qubits reduces the mean relative Frobenius error of the kernel matrix by 4.44×4.44\times to 78.19×78.19\times compared with the best baseline. This holds at equal numbers of state preparations (Table 1 of our paper).

References

[1] Nielsen, Michael A., et al. “Quantum dynamics as a physical resource.” Physical Review A 67.5 (2003): 052301.

AuthorsOpenReview ↗

Response to Reviewer iYKJ: Part2

3. Under standard complexity assumptions, Theorem 2 shows that a small DD does not guarantee classically tractable kernel evaluation. Assuming an injective function that is classically one-way and quantumly invertible, Theorem 2 also proves a learning separation by reduction to the Goldreich–Levin theorem [2].

Q1. How does the analysis apply when readout qubits are data-encoded (standard PQK, see for example Huang et al. (2021))?

Response to Q1. To cover readouts that are themselves data-encoded, we proved, as Proposition 3 in Appendix B.5 of the revised manuscript, the dimension bound D≤min⁡{r2dim⁡VB, 4nB}D\le\min\{r^2\dim\mathcal V_B,\,4^{n_B}\} for such readouts, with rr as in Eq. (2) and VB\mathcal V_B the span of the data-encoded readout states σB(x)\sigma_B(x), and checked it numerically in Table 4 of the same appendix (Table R2 below). Overall, when the data enter each register separately before a fixed circuit, the dimension bounds r2r^2 and 2beff2^{b_{\mathrm{eff}}} still hold for a data-encoded readout once multiplied by dim⁡VB\dim\mathcal V_B, whereas the results based on the fixed matrix GG still need a blank readout. All 120 circuits that we simulated exactly, including those of Table R2, agree with Proposition 3. Below we derive the bound and state which results still need a blank readout in part 1, and give the numerical check in part 2.

1. The bound D≤min⁡{r2dim⁡VB, 4nB}D\le\min\{r^2\dim\mathcal V_B,\,4^{n_B}\} holds when the data enter each register separately before a fixed circuit. The projected quantum kernels of [3] whose data enter each register separately, such as their separable encoding, are of this kind. In the IQP-type and Hamiltonian-evolution encodings of [3], data-dependent gates act jointly on both registers, so the fixed transfer map of Eq. (2) does not apply directly and in general only the readout-size bound 4nB4^{n_B} remains. If a causal separator of qq qubits follows the last data-dependent gate, Corollary 2 gives D≤4qD\le4^q, which is smaller than 4nB4^{n_B} when q<nBq<n_B. For separately encoded data, let the readout start in a data-encoded state σB(x)\sigma_B(x) with span VB\mathcal V_B, and let the fixed circuit act on ρA(x)⊗σB(x)\rho_A(x)\otimes\sigma_B(x). Expanding the circuit into rr operator-Schmidt terms makes ρB(x)\rho_B(x) a sum of r2r^2 terms, each a fixed linear map applied to σB(x)\sigma_B(x) times an input-dependent coefficient, so the span of ρB(x)\rho_B(x) has dimension at most r2dim⁡VBr^2\dim\mathcal V_B. For controlled gates as in Eq. (3), ρB(x)\rho_B(x) still decomposes over the control sectors, so r2r^2 can be replaced by 2beff2^{b_{\mathrm{eff}}}. The branch states then depend on xx, however, so GG is no longer fixed, and the results built on the fixed matrix GG, such as K=QGQ⊤K=QGQ^\top and control-qubit sampling with known GG, need a blank readout.

Table R2. Dimension DD with a data-encoded readout and bb CNOTs between the registers (nA=nB=4n_A=n_B=4).

Readout encodingb=0b=0b=1b=1b=2b=2b=3b=3
RyR_y angle on each qubit81108144192
RzRyR_zR_y angles on each qubit256256256256

2. Numerically, DD never exceeds the bound of Proposition 3. In Table R2, with RyR_y angles dim⁡VB=81\dim\mathcal V_B=81, and DD equals 81 at b=0b=0 and grows to 192 at b=3b=3, below the maximum 4nB=2564^{n_B}=256. With RzRyR_zR_y angles dim⁡VB\dim\mathcal V_B is already 256, and DD reaches 256 before the registers interact. Beyond Table R2, the bound of Proposition 3 also holds on all 120 circuits that we simulated exactly, with CNOT, controlled-Ry(0.7)R_y(0.7), and Haar-random two-qubit gates across the registers.

References

[2] Goldreich, Oded, and Leonid A. Levin. “A hard-core predicate for all one-way functions.” Proceedings of the 21st Annual ACM Symposium on Theory of Computing (1989): 25–32.

[3] Huang, Hsin-Yuan, et al. “Power of data in quantum machine learning.” Nature Communications 12.1 (2021): 2631.

AuthorsOpenReview ↗

Response to Reviewer iYKJ: Part3

Q2. Is there any case where DD is strictly smaller than the 2b2^b (or 4nB4^{n_B}) count one gets from "number of classical features"?

Response to Q2. To find when DD falls strictly below 2b2^b and 4nB4^{n_B}, we examined three causes that lower DD and compared DD with the feature counts of prior analyses. In the revised manuscript, examples of the three causes and the symmetry argument are in Table 9 of Appendix H.1.5 (Table R3 below), and the comparison with prior analyses is in Table 8 of Appendix H.1.4 (Table R4 below) and in Appendix A.5, which discusses [4,5,6]. Overall, yes, DD can be strictly smaller than both 2b2^b and 4nB4^{n_B}. Specifically, dependent data, repeated control qubits, and symmetry each bring DD below 2b2^b in our examples, and DD stays far below the 4,096 features counted by prior analyses. Below we explain the three causes in part 1 and the comparison with prior analyses in part 2.

Table R3. Examples of DD strictly below 2b2^b and their causes.

ExampleCauseNumber of CNOTs bb2b2^bDimension DD
Three CNOTs Aj→BjA_j\to B_j between fixed random local layers, one angle on all data qubitsDependent data386
Five CNOTs sharing two control qubitsRepeated controls5324
240 TFIM ground statesParity symmetry66432

1. Dependent data, repeated control qubits, and symmetry can make DD strictly smaller than 2b2^b. Table R3 lists three natural examples with DD below 2b2^b. First, dependent encoded data can reduce DD. With one angle on all data qubits, the three CNOTs of Table R3 give D=6D=6 instead of 8. Second, a repeated control qubit lowers the bound 2b2^b of Eq. (4) to 2beff2^{b_{\mathrm{eff}}}. For example, the five CNOTs in Table 7 of the revised manuscript use only two control qubits, and D=4D=4 attains 2beff2^{b_{\mathrm{eff}}}. Third, for our TFIM ground states, the Hamiltonian's parity symmetry makes each control sector and its complement equally likely. Hence DD is at most 2b−12^{b-1}, and this value is attained for every bb from 1 to 6.

Table R4. Dimension DD vs. feature counts of prior analyses for different numbers bb of CNOTs (nB=6n_B=6, m=512m=512).

Number of CNOTs bbReadout bound 4nB4^{n_B} [4]Pauli expectation values, with identity [5]Non-identity Pauli observables 4nB−14^{n_B}-1 [6]Dimension DDExcess risk of kernel regression (σ2/m\sigma^2/m)
14,0964,0964,09522.1
24,0964,0964,09544.2
34,0964,0964,09588.3
44,0964,0964,0951617.9
54,0964,0964,0953236.0

2. DD stays far below 4nB4^{n_B} and the feature counts of prior analyses. Table R4 compares DD with 4nB4^{n_B} and earlier feature counts on five circuits differing only in bb, each with nB=6n_B=6. Here the Lego features of [5] are, in the Pauli basis, the Pauli expectation values of the readout, so Table R4 counts them as Pauli expectation values. The readout bound of [4], the Lego feature count, and the count of [6] for all non-identity Pauli observables stay near 46=4,0964^6=4,096. In contrast, D=2bD=2^b grows only from 2 to 32, and the excess risk follows DD.

References

[4] Kübler, Jonas, Simon Buchholz, and Bernhard Schölkopf. “The inductive bias of quantum kernels.” Advances in Neural Information Processing Systems 34 (2021): 12661–12673.

[5] Gan, Beng Yee, Daniel Leykam, and Supanut Thanasilp. “A unified framework for trace-induced quantum kernels.” arXiv preprint arXiv:2311.13552 (2023).

[6] Bang, Jeongho, et al. “Learning with active quantum subspaces: Scalable hybrid advantage without full quantum data-encoding.” arXiv preprint arXiv:2606.00932 (2026).

Thank you again for your valuable feedback.

We wanted to gently follow up on the questions you raised. Our rebuttal responds directly to your concerns about the clarity of the presentation (W1); whether results such as Theorem 1, the r2r^2 bound, and Corollary 2 are elementary (W2); how the analysis applies when the readout qubits are data-encoded, as in the standard PQK of Huang et al. (2021) (Q1); and whether there are cases where DD is strictly smaller than 2b2^b or 4nB4^{n_B} (Q2).

Could you kindly let us know whether these responses address your questions, or whether any part of the paper is still hard to follow? We would be very happy to clarify further.

Many thanks again for your careful review.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.