On the fundamental resource for exponential advantage in quantum channel learning

Domain: physics
Published: 2026-01-20
Editorial outcome: minor_revision

Abstract
Quantum resources enable us to achieve an exponential advantage in learning the properties of unknown physical systems by employing quantum memory. While entanglement with quantum memory is recognized as a necessary qualitative resource, its quantitative role remains less understood. In this work, we distinguish between two fundamental resources provided by quantum memory—entanglement and ancilla qubits—and analyze their separate contributions to the sampling complexity of quantum learning. Focusing on the task of Pauli channel learning, a prototypical example of quantum channel learning, remarkably, we prove that vanishingly small entanglement in the input state already suffices to accomplish the learning task with only a polynomial number of channel queries in the number of qubits. In contrast, we show that without a sufficient number of ancilla qubits, even learning partial information about the channel demands an exponentially large sample complexity. Thus, our findings reveal that while a large amount of entanglement is not necessary, the dimension of the quantum memory is a crucial resource. Hence, by identifying how the two resources contribute differently, our work offers deeper insight into the nature of the quantum learning advantage.

Introduction
Quantum advantage arises from the utilization of quantum effects, manifesting in diverse tasks such as accelerating computation by quantum computing1–11, and improving sensitivity by quantum metrology12–15. In addition to the above, a particularly promising approach to realize a quantum advantage, recently attracting much attention, is quantum learning, which leverages quantum effects to achieve high efficiency in learning unknown physical systems that classical approaches cannot achieve from an information perspective16,17. Various forms of quantum learning advantage have been investigated, including expectation value estimation16,17, learning quantum channels18–23, and extension of learning techniques to continuous-variable systems for the characterization of quantum states24 and channels25. Especially, quantum channel learning has attracted increasing attention due to its utility in learning errors of quantum devices26,27 and mitigating noise28–30 for quantum computing.

The quantum advantage in channel learning is often defined by the accessibility to quantum memory16,17; thus, quantum memory is regarded as a quantum resource in this context. Hence, two different families of learning schemes are considered and compared with each other20,22,24,25, which are illustrated in Fig. 1. As depicted in Fig. 1(a), learning an unknown n-qubit quantum channel Λ involves preparing input states, applying Λ, and estimating its parameters from measurement outcomes16. Without quantum memory, the required sample complexity for learning—the number of channel applications—often scales exponentially with n18,20–23. In contrast, by using quantum memory [Fig. 1(b)], the sample complexity can be significantly reduced. As an example, Pauli channel learning, which is a crucial task for various applications26–30, can be accomplished with only O(n) samples by employing a 2n-qubit Bell pair as input, while any scheme in Fig. 1(a) requires Ω(2n) samples21,23, establishing exponential quantum advantage through quantum memory. In addition, this advantage has recently been demonstrated experimentally31,32.

Accordingly, quantum memory has been identified as a key resource in quantum learning. In fact, in the literature, entanglement-enabled learning and ancilla-assisted learning are used interchangeably in this context20,22,24,25, which implicitly treats the two resources as equivalent. From an information-theoretic perspective, however, two distinct types of resources emerge when quantum memory is provided: the ancilla qubits in the memory and the entanglement between these ancilla qubits and the system. In many cases, these two resources can be regarded as effectively identical, such as when Bell pairs are used as input probes. However, this equivalence does not necessarily hold in general, and understanding its breakdown is the main focus of this work.

In this work, we consider Pauli channel learning and show that the two resources, ancilla qubits and entanglement between the ancilla and the system, contribute in fundamentally distinct ways to the exponential quantum advantage. In particular, we first prove that while the sample complexity must be exponential when the number of ancilla qubits is limited20,21,23, even with a vanishingly small amount of entanglement, a polynomial number of samples is sufficient to learn a Pauli channel. This highlights that a large amount of entanglement is not necessary for the exponential quantum advantage as long as the number of ancilla qubits is sufficient. To understand the necessary number of ancilla qubits in practice, we consider learning a subset of the channel parameters—specifically, the Pauli eigenvalues associated with low-weight Pauli strings (see Definition 1). We then prove that even in this easier setting, if the number of ancilla qubits is limited, the sample complexity must be exponential. This result emphasizes that the number of ancilla qubits plays an even more crucial role than previously recognized. Therefore, by revealing the distinct contributions of entanglement and ancilla qubit number to the exponential quantum learning advantage, our work provides a comprehensive connection between quantum resources and the sample complexity of channel learning.

Results
Pauli channel learning setup
We begin by introducing the definitions of Pauli strings, Pauli channels, and Pauli channel learning, which are the main subject of this work. Each Pauli operator P ∈ {I, X, Y, Z} is labeled by a 2-bit string a := (ax, az) ∈ Z22, and expressed as Pa = i axaz Xax Zaz. This extends to an n-qubit system via the Pauli string P = ⊗nj=1 P aj determined by a 2n-bit string a := (a1, ..., an) ∈ Z2n2. Any P and P satisfy Pa Pb = (−1)⟨a, b⟩ Pb Pa, where ⟨a, b⟩ := ∑nj=1 (ax,j bz,j + az,j bx,j) mod 2. The Pauli weight |a| is defined as the number of non-identity operators in the Pauli string Pa. A Pauli channel Λ(⋅) is defined as
Λ(⋅) := ∑a∈Z2n2 p(a) Pa (⋅) Pa = 1/2n ∑b∈Z2n2 λ(b) Tr[Pb (⋅)] Pb, (1)
where p(a) is a Pauli error rate, and λ(b) is a Pauli eigenvalue. They are related via the Walsh-Hadamard transform, given by p(a) = 1/2n ∑b∈Z2n2 λ(b) (−1)⟨a, b⟩18.

As shown in Fig. 1(b), we treat the ancilla as an additional register consisting of k qubits. Since the channel acts only on the system, the output state corresponding to an input state ρin is given by (I ⊗ Λ)(ρin) = 1/2n ∑b∈Z2n2 λ(b) Trsys[(I ⊗ Pb) ρin] ⊗ Pb, where I and I denote the identity channel and operator on the ancilla, respectively, and Trsys denotes the partial trace over the system.

Based on the definition of the Pauli channel in Eq. (1), we define the Pauli channel learning task.
Definition 1. ((ε, δ, w)-Pauli channel learning task) We are given access to N copies of the Pauli channel Λ. Classical data are collected by preparing an input state, applying a single copy of the channel, and measuring the output. In each round, both the input and measurement POVM can be chosen adaptively based on prior measurement outcomes. After N measurements, the goal is to provide an estimate λ(b) satisfying |λ(b) − λ(b)| ≤ ε for any b ∈ Z2n2 such that |b| ≤ w with success probability at least 1 − δ.

In this setting, the number of channel queries required to accomplish the task, denoted by N, is referred to as the sample complexity. The motivation for estimating λ(b) for low |b| stems from realistic physical error models18. The number of parameters to learn is determined by the maximum weight w; when w = n, the learning task requires estimating a total of 4n parameters. We consider only 0 ≤ k ≤ n, since k = n ancilla qubits are sufficient to accomplish the task with N = O(n) even when w = n21. In addition, as implied in the definition, this work focuses on non-concatenated applications of the channel, although concatenated applications might potentially reduce the sample complexity23, which we leave as future work.

Learning with restricted entanglement
We first analyze the sample complexity in Pauli channel learning depending on the entanglement between the system and the ancilla. Here, the entanglement is defined as the entanglement entropy of the input probe state, and we denote it as Sa|s [Fig. 1(b)]. As highlighted in several previous works16,20–23, if Sa|s = 0, an exponentially large N is required to accomplish the (ε, δ, w = n)-Pauli channel learning task. Consequently, one might expect that even if enough k = n ancilla qubits are available, the exponential N may still be necessary when the input state has small Sa|s, i.e., it is close to a separable state. Remarkably, our first main result shows that the exponential advantage can be achieved using only small Sa|s, even for estimating all λ(b), i.e., w = n. More precisely, our theorem below reveals that even when Sa|s in the input state is inverse-polynomially small, the Pauli channel can be learned with polynomially many samples in n.

Theorem 1. For an n-qubit system with k = n ancilla qubits, there exists a scheme that accomplishes the (ε, δ, n)-Pauli channel learning task with sample complexity N = O(nα−2 × ε−2 log δ−1) by using input states, each with entanglement Sa|s = Θ(nα), where α = Θ(1/poly(n)).

Hence, Theorem 1 implies that the exponential advantage remains attainable even when highly entangled states are inaccessible. This reveals that the contributions of entanglement and ancilla qubit number to the exponential advantage are fundamentally distinct, which becomes evident by comparing the two cases: (1) If only k ancilla qubits are allowed, even if maximally entangled states are used, i.e., Sa|s = k, N = Ω(2(n−k)/3) is required20,21,23 (the lower bound will be improved later). (2) In contrast, when n ancilla qubits are provided, by preparing input states such that each has the same amount of entanglement Sa|s = k (i.e., setting α = k/n), the learning task can be accomplished with a sample complexity that scales polynomially with n.

Note that a smaller Sa|s leads to a larger N as a trade-off. Thus, the total entanglement resource of the N copies of the input state cannot be arbitrarily reduced. For instance, when we set α = 1, each input state has entanglement Sa|s = Θ(n), and O(n) such states are required; consequently, the total entanglement is O(n2) (this corresponds to the case where a Bell pair is employed in ref. 21). However, if we take α = 1/nc (c > 0), each input has Sa|s = Θ(n1−c) and O(n1+2c) such states are required, so the total required entanglement is O(n2+c).

Proof Sketch. (See Supplementary Material (SM) Sec. S2 for the full proof) To prove Theorem 1, we provide an explicit input state |Ψin(α) parameterized by a constant α, with Sa|s = Θ(nα). The input state is defined as a superposition of the 2n-qubit Bell pair |ΨB and a separable state |Ψsep:
|Ψin(α) := √α |ΨB + √1−α |Ψsep, (2)
where α0 := α + (1−α)/2n − (1−α)/2n. Here, the separable state |Ψsep is defined as |Ψsep := [ρsep]⊗n ⊗ [ρsep]⊗n, where ρsep = 1/2(I + 1/√3(X+Y+Z)). Note that ρsep is a pure product state, and setting α = 1 recovers |Ψin(α=1) = |ΨB. As a result of the superposition of the two states with weight α, the entanglement Sa|s is reduced from n (of the Bell pair) to Θ(nα). For measurement, we use the Bell measurement POVM {Ev}, where Ev = 1/4n ∑a,b∈Z2n2 (−1)⟨b, v⟩ Pa ⊗ Pa. When the input state is |Ψin(α) in Eq. (2) and the measurement is performed using {Ev}, the probability Pr(v) of obtaining outcome v is related to the Pauli eigenvalue λ(b) as follows:
λ(b) = ∑v∈Z2n2 Pr(v) (−1)⟨b, v⟩ / E(b), E(b) = α + (1−α)3−|b|/2n. (4)
Therefore, we obtain an unbiased estimator λ(b), which is given by λ(b) = 1/N ∑Nl=1 (−1)⟨b, v(l)⟩ / E(b), where {v(l)}Nl=1 are the outcomes of N measurements. Applying Hoeffding’s inequality, the sample complexity N(b) sufficient to estimate a single parameter λ(b) within error ε with success probability at least 1 − δ is
N(b) = O(1/E2(b) × ε−2 log δ−1). (5)
From the union bound, to ensure this level of precision and confidence for any λ(b) among the 4n parameters, the sufficient sample complexity is N = O(nα−2 × ε−2 log δ−1).

Although our main example is the specific state given in Eq. (2), a broad class of states shares the same property: having an inverse polynomially small entanglement while enabling the learning task to be accomplished with polynomial sample complexity in n. As a generalization of the input state in Eq. (2), we find that the state |Ψin(α, φ) := √α |ΨB + √1−α |φ, where |φ is an arbitrary state in the n-qubit Hilbert space, retains Sa|s = Θ(nα) and E(b) = Ω(α) (see SM Sec. S2D). In addition, we show that the Werner state also exhibits this property (see SM Sec. S2E). Since it is a mixed state, we use the entanglement of formation as the entanglement measure, instead of the entanglement entropy Sa|s. Although our analysis focuses on the Bell-measurement POVM, employing more general POVMs may enable a broader set of input states to satisfy these properties.

Learning with a restricted number of ancilla qubits
In the previous section, we showed that when the system is assisted by the k = n ancilla qubits, with only limited entanglement, the full set of Pauli channel parameters can be learned within polynomial N. In contrast, if k is insufficient, it is known that an exponential N is necessary to accomplish (ε, δ, w = n)-Pauli channel learning task21,23. In the following theorem, we show that under the restriction on k, learning even a subset of the parameters (i.e., w < n) requires an exponentially large N.

Theorem 2. To accomplish the (ε, δ, w)-Pauli channel learning task by using k ancilla qubits, the lower bound on the required sample complexity N is
N = Ω(2−k ∑w u=0 (n u) 3u × ε−2(1−2δ)) w > n/2, Ω(1/2−k 3w × ε−2(1−2δ)) w ≤ n/2. (6)

In Fig. 2, we illustrate the regime where the exponential N is required in the maximum weight-ancilla qubit number (w−k) plane, according to Eq. (6). As shown in Fig. 2, Theorem 2 highlights that a sufficient k is crucial for achieving the exponential advantage. When k is limited, even for relatively simple tasks with w < n, an exponentially large N is required regardless of the entanglement of the input state. This presents a complementary case to that in Theorem 1, which considers the situation where k is large enough but Sa|s is limited. Therefore, we concretely establish that the two scenarios—limited k and limited Sa|s—are qualitatively different in terms of their impact on the exponential quantum learning advantage. Furthermore, for the case w = n, we improve the lower bound from the previously suggested N = Ω(2(n−k)/3) in refs. 21,23 to N = Ω(2n−k).

Theorem 3. When k = 0, the upper bound on N to accomplish the (ε, δ, w)-Pauli channel learning task is
N = O(n5/2 ∑w u=0 (n u) 3u × ε−2 log δ−1) w > n/2, O(n 23w × ε−2 log δ−1) w ≤ n/2. (10)

When k = 0, the lower bound in Eq. (6) matches the upper bound in Eq. (10) up to a polynomial factor of n. Theorem 3 implies that when w = Θ(log(n)), although the number of parameters to be learned scales quasi-polynomially, the sample complexity grows only polynomially. Additionally, by combining with the lower bound in Theorem 2, we reveal that the scaling of the sample complexity exhibits a transition at the threshold w = n/2. We prove the theorem by explicitly constructing the learning scheme using the concept of the stabilizer covering.

Proof Sketch. (Further details can be found in SM Sec. S4.) To derive the upper bound on the sample complexity, we employ the concept of the stabilizer covering18. Given a set of Pauli strings P, a set C = {Si} of stabilizer groups Si is called a stabilizer covering of P if it satisfies P ⊆ S. A stabilizer covering of P is not unique, and we denote by CN(P) the minimal size |C| among all stabilizer coverings of P.

For the task of learning all λ(b) such that Pb ∈ P, the stabilizer covering provides an upper bound on N as21
N = O(n × CN(P) × ε−2 log δ−1). (11)
The proof is as follows: given a stabilizer group S, all λ(b) such that Pb ∈ S can be estimated by using only N = O(n × ε−2 log δ−1) samples. Accordingly, for a stabilizer covering C of P satisfying |C| = CN(P), repeating the above estimation for each Si ∈ C enables us to estimate all λ(b) such that Pb ∈ P, since every element in P is contained in some Si ∈ C. To obtain the upper bound on CN(P), we develop the concept of a uniform stabilizer covering. We refer to a stabilizer covering U = {S} of P as uniform if it satisfies the following conditions: (1) For every Si ∈ U, |Si ∩ P| = Σ, and we call Σ the covering power. (2) For all Pi ∈ P, |{Si ∈ U: Pi ∈ Si}| = R, and according to condition (1), the relation |U| × Σ = |P| × R holds. By extending the theory of covering arrays37–40, we prove that for a given P, if a uniform stabilizer covering U with covering power Σ exists, an upper bound on CN(P) is given by
CN(P) ≤ |P|/Σ log |P|. (12)
Furthermore, we provide a heuristic density-based greedy algorithm41,42 to find a stabilizer covering of size specified in Eq. (12). For the (ε, δ, w)-Pauli channel learning, we consider a set P(w) := {Pa : |Pa| = w} where |P(w)| = (n w) 3w. For the set P(w), we construct two uniform stabilizer coverings, namely U(w≤n/2) with covering power (n w) and U(w>n/2) with covering power Ω(√2n), corresponding to the regimes w ≤ n/2 and w > n/2, respectively. Combining Eq. (12) with the covering powers of U(w≤n/2) and U(w>n/2), we derive
CN(P(w)) = O(n3w) w ≤ n/2, O(n3/2 (n w) 3w / 2n) w > n/2. (13)
where we used log |P(w)| = O(n). Finally, by using Eqs. (11) and (13), along with the inequality CN(∪w P(u)) ≤ ∑w u=0 CN(P(u)), we derive the upper bound on N stated in Theorem 3.

In addition, from Eqs. (6) and (11), we conclude that our bound on CN(P(w)) in Eq. (13) is tight within a polynomial factor of n. Although finding the exact value of CN(P) for an arbitrary set P is NP-hard43, by exploiting the specific structure of weight-w Pauli strings, we derive this tight bound.

Additionally, we derive an upper bound on N for the case k > 0 by generalizing the strategy developed for the case k = 0. In particular, by extending the concept of the uniform stabilizer covering, we show that Eqs. (11) and (12) also hold when the k-qubit ancilla is used (see SM Sec. S5 A). Accordingly, we construct a uniform stabilizer covering of P(w) and compute the corresponding covering power. Specifically, we find two uniform stabilizer coverings U(2w≤k+n) and U(2w>k+n), for the regimes 2w ≤ k+n and 2w > k+n, respectively. According to our construction, when k and w scale proportionally with n, the (ε, δ, w)-Pauli channel learning task can be accomplished with N = O(poly(n)) only for the case k = n. In detail, we find that
|P(w)|/Σ log |P(w)| = Ω(n3/2 3w(1 − k/n)), (14)
where the left-hand side is related with Eq. (12). This result is illustrated in Fig. 2.

Methods

Peer review rounds
[{"round": 1, "reviewer_comments": {"reviewer_1": "This paper investigates the distinct roles of two quantum resources---entanglement and ancilla qubits---in enabling exponential efficiency gains in Pauli channel learning, the goal of which is to estimate Pauli eigenvalues of an unknown channel acting on n-qubit systems. Classically or without memory, learning such channels requires exponentially many samples. Prior work showed that quantum memory---typically realized through entangled Bell pairs---reduces the complexity to polynomial. However, the precise quantitative contributions of entanglement versus memory size had remained unclear. The authors prove two central results. Firstly, they show that only a vanishingly small amount of entanglement suffices: with k=n ancilla qubits, input states possessing just inverse-polynomial entanglement entropy (n\\alpha scaling for inverse-polynomial \\alpha) still allow polynomial sample complexity O(n^{\\alpha-2}). They also provide explicit construction of the input state by considering the superposition of separable states and Bell-pairs. This demonstrates that large-scale entanglement is unnecessary for exponential advantage, as long as sufficient ancilla qubits are available. Secondly, they establish that the number of ancilla qubits is the decisive resource. If the ancilla register is too small, then even estimating a restricted subset of parameters (low-weight Pauli eigenvalues of weight at most w) demands exponential samples. They sharpen previous lower bounds at k=n and show a transition at w=n/2. Complementing this, they provide matching upper bounds at k=0 using stabilizer coverings, a combinatorial construction from quantum error correction. They also provide upper bounds at k\\neq 0 extending the concept of the uniform stabilizer covering.\n\nThis paper makes a clear and meaningful contribution to the theory of quantum learning by disentangling the quantitative roles of entanglement and ancilla qubits in enabling exponential advantage. From a technical perspective, while Theorem 1 and Theorem 2 can be obtained by extending the prior works, the idea of using the superposition of a Bell pair and a separable state in Theorem 1 and of adding a carefully crafted probability distribution to the alternative hypothesis in the distinguishing task in Theorem 2 are nontrivial. The authors further introduce stabilizer coverings into quantum learning theory. The paper is well-written, and the results are presented clearly. I thus think this work is a natural fit for nature communication after addressing the following comments:\n1. While the previous work [21] showed that the Bell-pair input algorithm (or the partially Bell-pair input algorithm when the number of ancillas is bounded) is robust against state-preparation and measurement (SPAM) noise, it is unclear whether the algorithms proposed in Theorem 1 and Theorem 3 are SPAM robust. I would thus like to suggest the authors providing further discussion on the robustness of the proposed algorithms.\n2. In the proof of Theorem 1, the authors construct the input by considering the superposition of Bell pair and a carefully crafted product state. I am thus curious if it is possible to replace the specific product state in Eq. (3) with, say, a family of other separable quantum states. Also, can we characterize what kind of separable quantum states can (not) be potentially used to achieve polynomial sample complexity with bounded entanglement entropy?\n3. In the Supplementary Material, the authors also compute the sample complexity upper bound of Pauli channel learning provided by stabilizer covering with eigenvalues corresponding to Paulis of weight at most w if the protocol has k ancillas. However, the upper bound here does not match the lower bound in Theorem 2. The authors then suggest that there is an improved proof technique for the lower bound may lead to a tighter bound that matches the upper bound. I am wondering why it is impossible that the upper bound provided by stabilizer covering is not tight. I would like to invite the authors to explain more above this claim (conjecture).\n4. In Figure 2, the authors plot the regime where exponential sample complexity is necessary from the lower bound in Theorem 2. I suggest the authors also plotting the upper bound computed in Supplementary Materials Section S5 so that we can better understand the gap between the upper and the lower bounds.", "reviewer_2": "This paper studies the question of learning Pauli channels and focuses on the source of the exponential advantage discovered in recent works. More precisely, the paper asks whether this advantage comes from the ancillary qubits or from entanglement in the input state. The first result shows that when n ancilla qubits are available, then exponential advantage occurs even with input states of very low entanglement (e.g., 1/poly(n)). The algorithm is a slight modification of Bell sampling.\n\nThe second result provides lower bounds on the sample complexity for various numbers of ancilla k \\le n and Pauli weight w \\le n. Interestingly, the lower bound 2^(n-k) (for w = n) was established, improving prior bounds and matching the existing upper bound. The proof uses the Le Cam method along with the SWAP trick.\n\nThe third result provides upper bounds on the sample complexity when no ancilla qubits are allowed. The sample complexity depends on the weight of the Pauli and is optimal up to polynomial prefactors in n. The algorithm uses a new method to construct Pauli stabilizer coverings, generalizing the one used by Flammia and Wallman for general Pauli channel learning.\n\nThese results improve our understanding of Pauli channel learning, and in particular, the cause of the exponential advantage.\n\nThere are some typos: polynomial in n (instead of \"N\") after Theorem 1. In theorem 2, there is a missing 1/sqrt(2n), cf. S75. This is a repeated remark whenever you use Stirling’s formula, e.g., in Theorem 3, (S101) and covering power Omega(2^n). After Eq (9), it should be ...(3x)^u."}, "author_response": "Response to the Reviewers\nReviewer #1\nThis paper investigates the distinct roles of two quantum resources—entanglement and ancilla\nqubits—in enabling exponential e!ciency gains in Pauli channel learning, the goal of which is\nto estimate Pauli eigenvalues of an unknown channel acting on n-qubit systems. Classically or\nwithout memory, learning such channels requires exponentially many samples. Prior work showed\nthat quantum memory—typically realized through entangled Bell pairs—reduces the complexity\nto polynomial. However, the precise quantitative contributions of entanglement versus memory\nsize had remained unclear. The authors prove two central results. Firstly, they show that only\na vanishingly small amount of entanglement su!ces: with k = n ancilla qubits, input states\npossessing just inverse-polynomial entanglement entropy (n\\omega scaling for inverse-polynomial \\omega) still\nallow polynomial sample complexity O(n\\omega 2). They also provide explicit construction of the input\n→\nstate by considering the superposition of separable states and Bell-pairs. This demonstrates that\nlarge-scaleentanglementisunnecessaryforexponentialadvantage,aslongassu!cientancillaqubits\nare available. Secondly, they establish that the number of ancilla qubits is the decisive resource. If\nthe ancilla register is too small, then even estimating a restricted subset of parameters (low-weight\nPauli eigenvalues of weight at most w) demands exponential samples. They sharpen previous lower\nbounds at k = n and show a transition at w = n/2. Complementing this, they provide matching\nupper bounds at k = 0 using stabilizer coverings, a combinatorial construction from quantum error\ncorrection. Theyalsoprovideupperboundsatk = 0extendingtheconceptoftheuniformstabilizer\n→\ncovering.\nThis paper makes a clear and meaningful contribution to the theory of quantum learning by\ndisentangling the quantitative roles of entanglement and ancilla qubits in enabling exponential\nadvantage. From a technical perspective, while Theorem 1 and Theorem 2 can be obtained by\nextending the prior works, the idea of using the superposition of a Bell pair and a separable state\ninTheorem1andofaddingacarefullycraftedprobabilitydistributiontothealternativehypothesis\nin the distinguishing task in Theorem 2 are nontrivial. The authors further introduce stabilizer\ncoverings into quantum learning theory. The paper is well-written, and the results are presented\nclearly. I thus think this work is a natural fit for nature communication after addressing the\nfollowing comments:\nReply: We sincerely appreciate Reviewer #1’s thoughtful evaluation and recognition of our main\ncontributions. We are also grateful for the insightful and constructive comments, particularly re-\ngardingthetechnicalaspectsofourwork. Thesevaluablecommentshaveenabledustoimprovethe\nqualityofthemanuscript,bringingitclosertothepublicationstandardofNatureCommunications.\nBelow, we provide our detailed responses to each of Reviewer #1’s comments.\n1. Whilethepreviouswork[21]showedthattheBell-pairinputalgorithm(orthepartiallyBell-\npair input algorithm when the number of ancillas is bounded) is robust against state-preparation\nand measurement (SPAM) noise, it is unclear whether the algorithms proposed in Theorem 1 and\nTheorem 3 are SPAM robust. I would thus like to suggest the authors providing further discussion\non the robustness of the proposed algorithms.\nReply: We thank Reviewer #1 for this interesting question. We would like to first clarify that\nthe discussion about SPAM-robustness in Phys. Rev. A 105, 032435 (2022) (Ref. [21] in our\n2\nmanuscript) is provided in the context of randomized benchmarking (RB), rather than the learning\nscheme itself. In particular, an RB method employing an n-qubit ancilla was presented. This\nscheme accounts for the case of an arbitrary 2n-qubit state, referred to as a noisy Bell-state input\nin the paper; due to the generality of the result in the paper, our input state in Eq. (2) immediately\nconforms to this framework. Additionally, since the scheme in Theorem 3 stems from the stabilizer\ncovering and requires no ancilla qubits, the RB approach proposed in ACM Trans. Quantum\nComput. 1, 1 (2020) can be adapted to the (\\epsilon,\\vartheta,w)-Pauli channel learning task to be robust to\nSPAM noise.\nOn the other hand, regarding the SPAM-robustness of our learning schemes, it is well-known\nthatdepolarizingnoisecanexponentiallyincreasetherequiredsamplecomplexity, eveninscenarios\nwhere n ideal Bell pairs are used (e.g., Phys. Rev. Lett. 132, 180805 (2024)). Therefore, we do\nnot expect that our learning algorithms themselves are SPAM-robust. We have incorporated these\ndiscussions on the SPAM robustness and RB schemes into the discussion section of the main text.\n2. In the proof of Theorem 1, the authors construct the input by considering the superposition\nof Bell pair and a carefully crafted product state. I am thus curious if it is possible to replace the\nspecific product state in Eq. (3) with, say, a family of other separable quantum states. Also, can\nwe characterize what kind of separable quantum states can (not) be potentially used to achieve\npolynomial sample complexity with bounded entanglement entropy?\nReply: Beyond Eq. (3), we extend our analysis to a more general input state, ” (\\omega,\\varpi ,\\varpi ) :=\nin a s\n| ↑\n↓\\omega ” +↓1 \\omega \\varpi \\varpi , where \\varpi and \\varpi denote arbitrary ancilla and system states, and\n↑ B a s a s\n| ↑ ↔ | ↑↗| ↑ | ↑ | ↑\n\\omega isdeterminedby\\omegaandtheoverlap ” ( \\varpi \\varpi ). Weshowthatwhen( \\varpi ) = \\varpi and\\omega =\n↑ B a s s ↓ a\n↘ | | ↑↗| ↑ | ↑ | ↑\n#(1/poly(n)), both key properties of Eq. (2) continue to hold with the Bell measurement POVM\napplied: (1) S =#( n\\omega) and (2) the required sample complexity is N = O(n\\omega 2 \\epsilon 2log\\vartheta 1).\nas → → →\n| ≃\nMoreover, we find that when ( \\varpi ) = \\varpi , under the Bell measurement POVM, the required\ns ↓ a\n| ↑ → | ↑\nsample complexity can increase exponentially.\nHowever, we note that in Theorem 1 and its extended version above, the POVM is fixed to be\ntheBellmeasurement. Hence,thisleavesopenthepossibilitythatmoregeneralPOVMscouldallow\na broader class of input states to exhibit the same properties. We have included this discussion in\nSec. II B of the main text, with the detailed derivation provided in Sec. S2 D of SM.\n3. In the Supplementary Material, the authors also compute the sample complexity upper\nbound of Pauli channel learning provided by stabilizer covering with eigenvalues corresponding to\nPaulis of weight at most w if the protocol has k ancillas. However, the upper bound here does not\nmatch the lower bound in Theorem 2. The authors then suggest that there is an improved proof\ntechnique for the lower bound may lead to a tighter bound that matches the upper bound. I am\nwondering why it is impossible that the upper bound provided by stabilizer covering is not tight.\nI would like to invite the authors to explain more above this claim (conjecture).\nReply: We thank Reviewer #1 for the careful comment. Thanks to this comment, we have\nrealized that improving the lower bound might not be su!cient to meet the upper bound since a\nmoree!cientschemethanourstabilizer-coveringapproachmayexist. Accordingly,wehaverevised\nthe discussion section and Sec. S5 B of SM to address this comment.\nOn the other hand, it is true that the current lower bound is not optimal and can thus be\nimproved through a refined analysis. The reason is that some parts of the proof can likely be\nimproved at a technical level, which originally motivated our previous conjecture that the upper\nbound might be tight. More precisely, to establish the lower bound in Theorem 2, we need to\n3\nderive an upper bound for a matrix equation subject to a maximum-rank constraint, given by (see\nEq. (S61) of SM)\nTr2(P CP C )\nmax E e e † . (R1)\nC:rank(C) 2k e Tr2(CC † )\n↔\nHowever, the upper bound ETr2(PeCPeC†) 2k 1+x n in Eq. (S69) of SM is not yet tight. Al-\ne Tr2(CC † ) ⇐ 1+3x\nthough we cannot prove it, we present the expec!ted ti\"ght bound as follows:\nmax E Tr2(P e CP e C † ) = 1+x n → k , (R2)\nC:rank(C) ↔ 2k e Tr2(CC † ) # 1+3x $\nas shown in Eq. (S85) of SM. In addition, we have numerically verified Eq. (R2) for system sizes\nup to n 5. If Eq. (R2) turns out to be correct, we can argue that a su!ciently large k is even\n⇐\nmore essential than what Theorem 2 currently guarantees: for any proportional scaling of k and w\nwith n, the sample complexity remains exponential whenever k < n, i.e., the boundary in Fig. 2\nsaturates at k/n = 1. We discuss this expectation in Sec. II C of the main text, along with a\ndetailed explanation in Sec. S3 E of SM.\nWe note that even if Eq. (R2) holds, the resulting improved lower bound on sample complexity\nstill does not reach the upper bound. This implies that tightening the lower bound on the sample\ncomplexity alone may not be enough to bring it up to the upper bound.\n4. In Figure 2, the authors plot the regime where exponential sample complexity is necessary\nfrom the lower bound in Theorem 2. I suggest the authors also plotting the upper bound computed\ninSupplementaryMaterialsSectionS5sothatwecanbetterunderstandthegapbetweentheupper\nand the lower bounds.\nReply: We agree that plotting the upper bound makes the figure more informative. Accordingly,\nfrom the covering power obtained in Eqs. (S122) and (S127), we compute the required sample com-\nplexity under our extended stabilizer covering scheme for the case k > 0, as denoted in Eq. (S117).\nTo compare this result with the lower bound presented in Fig. 2 of the main text, we consider\nthe same situation, where both k and w scale proportionally with n. In this case, we find that\nregardless of the w value, the required N grows exponentially in n unless k = n. In other words,\nin Fig. 2, the regime where N = O(poly(n)) appears only along the line k = n; we plot this line as\na red dashed line, and have revised the caption. We have also revised the main text to include this\nupper bound in Sec. II C, and the corresponding details have been added in Sec. S5 C of SM.\nReviewer #2\nThispaperstudiesthequestionoflearningPaulichannelsandfocusesonthesourceoftheexponen-\ntial advantage discovered in recent works. More precisely, the paper asks whether this advantage\ncomes from the ancillary qubits or from entanglement in the input state. The first result shows\nthat when n ancilla qubits are available, then exponential advantage occurs even with input states\nof very low entanglement (e.g., 1/poly(n)). The algorithm is a slight modification of Bell sampling.\nThe second result provides lower bounds on the sample complexity for various numbers of\nancilla k n and Pauli weight w n. Interestingly, the lower bound 2n k (for w = n) was\n→\n⇐ ⇐\n4\nestablished, improving prior bounds and matching the existing upper bound. The proof uses the\nLe Cam method along with the SWAP trick.\nThe third result provides upper bounds on the sample complexity when no ancilla qubits are\nallowed. The sample complexity depends on the weight of the Pauli and is optimal up to poly-\nnomial prefactors in n. The algorithm uses a new method to construct Pauli stabilizer coverings,\ngeneralizing the one used by Flammia and Wallman for general Pauli channel learning.\nThese results improve our understanding of Pauli channel learning, and in particular, the cause\nof the exponential advantage.\nReply: We thank Reviewer #2 for succinctly summarizing the key aspects of our study. We are\nalso sincerely grateful to Reviewer #2 for clearly highlighting the significance of our contribution\nin comparison to previous works. Furthermore, we greatly appreciate Reviewer #2’s positive and\nencouraging evaluation of our study.\nThere are some typos: polynomial in n (instead of “N”) after Theorem 1. In theorem 2, there\nis a missing 1/↓2n, cf. S75. This is a repeated remark whenever you use Stirling’s formula, e.g.,\nin Theorem 3, (S101) and covering power $(2n). After Eq. (9), it should be ...(3x)u.\nReply: We are grateful to Reviewer #2 for the attentive reading and helpful comments. The\nmanuscript has been revised to correct the typographical errors that you kindly pointed out."}, {"round": 2, "reviewer_comments": {"reviewer_1": "I have read the revised manuscript, and the authors have addressed my comments. In particular, I am happy to see that my comments motivated the authors to refine their results and prove tighter lower and upper bounds. I believe the current manuscript is suitable for publication.", "reviewer_2": "Reviewer #1\nThis paper investigates the distinct roles of two quantum resources—entanglement and ancilla\nqubits—in enabling exponential e!ciency gains in Pauli channel learning, the goal of which is\nto estimate Pauli eigenvalues of an unknown channel acting on n-qubit systems. Classically or\nwithout memory, learning such channels requires exponentially many samples. Prior work showed\nthat quantum memory—typically realized through entangled Bell pairs—reduces the complexity\nto polynomial. However, the precise quantitative contributions of entanglement versus memory\nsize had remained unclear. The authors prove two central results. Firstly, they show that only\na vanishingly small amount of entanglement su!ces: with k = n ancilla qubits, input states\npossessing just inverse-polynomial entanglement entropy (nω scaling for inverse-polynomial ω) still\nallow polynomial sample complexity O(nω 2). They also provide explicit construction of the input\n→\nstate by considering the superposition of separable states and Bell-pairs. This demonstrates that\nlarge-scaleentanglementisunnecessaryforexponentialadvantage,aslongassu!cientancillaqubits\nare available. Secondly, they establish that the number of ancilla qubits is the decisive resource. If\nthe ancilla register is too small, then even estimating a restricted subset of parameters (low-weight\nPauli eigenvalues of weight at most w) demands exponential samples. They sharpen previous lower\nbounds at k = n and show a transition at w = n/2. Complementing this, they provide matching\nupper bounds at k = 0 using stabilizer coverings, a combinatorial construction from quantum error\ncorrection. Theyalsoprovideupperboundsatk = 0extendingtheconceptoftheuniformstabilizer\n→\ncovering.\nThis paper makes a clear and meaningful contribution to the theory of quantum learning by\ndisentangling the quantitative roles of entanglement and ancilla qubits in enabling exponential\nadvantage. From a technical perspective, while Theorem 1 and Theorem 2 can be obtained by\nextending the prior works, the idea of using the superposition of a Bell pair and a separable state\ninTheorem1andofaddingacarefullycraftedprobabilitydistributiontothealternativehypothesis\nin the distinguishing task in Theorem 2 are nontrivial. The authors further introduce stabilizer\ncoverings into quantum learning theory. The paper is well-written, and the results are presented\nclearly. I thus think this work is a natural fit for nature communication after addressing the\nfollowing comments:\n\nReviewer #2\nThispaperstudiesthequestionoflearningPaulichannelsandfocusesonthesourceoftheexponen-\ntial advantage discovered in recent works. More precisely, the paper asks whether this advantage\ncomes from the ancillary qubits or from entanglement in the input state. The first result shows\nthat when n ancilla qubits are available, then exponential advantage occurs even with input states\nof very low entanglement (e.g., 1/poly(n)). The algorithm is a slight modification of Bell sampling.\nThe second result provides lower bounds on the sample complexity for various numbers of\nancilla k n and Pauli weight w n. Interestingly, the lower bound 2n k (for w = n) was\n→\n⇐ ⇐\nestablished, improving prior bounds and matching the existing upper bound. The proof uses the\nLe Cam method along with the SWAP trick.\nThe third result provides upper bounds on the sample complexity when no ancilla qubits are\nallowed. The sample complexity depends on the weight of the Pauli and is optimal up to poly-\nnomial prefactors in n. The algorithm uses a new method to construct Pauli stabilizer coverings,\ngeneralizing the one used by Flammia and Wallman for general Pauli channel learning.\nThese results improve our understanding of Pauli channel learning, and in particular, the cause\nof the exponential advantage.\nThere are some typos: polynomial in n (instead of “N”) after Theorem 1. In theorem 2, there\nis a missing 1/↓2n, cf. S75. This is a repeated remark whenever you use Stirling’s formula, e.g.,\nin Theorem 3, (S101) and covering power $(2n). After Eq. (9), it should be ...(3x)u."}, "author_response": ""}]

Decision letter