When is it possible to learn to predict the outputs of a quantum channel E ? Such questions arise naturally in a variety of settings, such as the experimental study of complex quantum dynamics [HBC + 22, HKP21], and in fast-forwarding simulations of Hamiltonian evolutions [CHI + 20, GHC + 24]. However, in the worst case this problem is intractable, as it generalizes the classical problem of learning an arbitrary Boolean function over the uniform distribution from black-box access. To circumvent this, our goal is to understand families of natural restrictions on the problem under which efficient estimation is possible.
One way to avoid this exponential scaling would be to posit further structure on the channel, e.g. by assuming it is given by a shallow quantum circuit [NPVY23, HLB + 24] or a structured Pauli channel [HFW20, FO21, HYF21, VDBMKT23, ADGP24]. However, there are settings where the evolutions may be quite complicated -e.g. the channel might correspond to the time evolution of an evaporating black if and only if 퐷 is one of the aforementioned two-point distributions. With this, we can now state our main result: Theorem 1.1 (Learning an unknown quantum channel). Let 휀, 훿, 휂 ∈ (0, 1). Let 퐷 be an unknown distribution over the Bloch sphere with Pauli second moment matrix S such that S op ≤ 1 -휂. Let E be an unknown 푛-qubit quantum channel, and let O be a known 푛-qubit observable. There exists an algorithm with time and sample complexity min(2 푂 (푛) /휀 2 , 푛 푂 (log(1/휀)/log (1/(1-휂) ) ) ) •log(1/훿) that outputs an efficiently computable map 푓 ′ such that
with probability at least 1 -훿.
Note that the only condition on 퐷 we require is a quantitative bound on the spectral norm of its Pauli second moment matrix. In other words, so long as the distribution 퐷 is far from any two-point distribution, i.e., it is far from any classical distribution, we demonstrate that there is an efficient algorithm for learning to predict general quantum dynamics under this distribution. Previously it was only known how to achieve the above guarantee in the special case where 퐷 has mean zero. Indeed, as soon as one deviates from the mean zero case, the Pauli decomposition approach of [HCP23] breaks down. In contrast, our guarantee works for any product distribution whose marginal second moment matrices have operator norm bounded away from 1.
Remark 1.2. We note that our techniques generalize to the case where the distribution is the product of different distributions over qubits, so long as each distribution has second moment with operator norm bounded by 1 -휂. However, for readability we will primarily focus on the case where all of the distributions are the same. See Remark 4.7 for a discussion of how to easily generalize our techniques to this setting.
Beyond low-degree concentration in an orthonormal basis. Here we briefly highlight the key conceptual novelties of our analysis, which may be of independent interest. We begin by recalling the analysis in [HCP23] in greater detail. They considered the decomposition of O ′ E † [O] into the basis of 푛-qubit Pauli operators, i.e. O ′ = 푃 ∈ {퐼,푋,푌,푍 } 훼 푃 • 푃 and argued that this is well-approximated by the low-degree truncation O ′ low = |푃 |<푡 훼 푃 • 푃. This can be readily seen from the following calculation. By rotating the distribution 퐷, we may assume the covariance is diagonal, with entries bounded by 1-휂.
Then the error achieved by the low-degree truncation is given by
where the second step follows from the fact that E[Tr(푃 휌)
is mean zero and its covariance is diagonal with entries bounded by 1 -휂), and the last step follows by the assumption that O ′ op ≤ 1. Note that when 퐷 is not mean zero, this step breaks, and we do not have this nice exponential decay in 푡. In fact, in Section 5.2 we construct examples of operators which are not well-approximated by their low-degree truncations in the Pauli basis when 퐷 has mean bounded away from zero.
A natural attempt at a workaround would be to change the basis under which we truncate. At least classically, biased product distributions over the Boolean hypercube still admit suitable orthonormal bases of functions, namely the biased Fourier characters. As we show in Section 3, this idea can be used to give the following learning guarantee in the classical case where 퐷 is only supported along the 푍 direction in the Bloch sphere: Theorem 1.3 (PAC learning over a concentrated product distribution). Let 휀, 훿, 휂 ∈ (0, 1). Let 퐷 be an unknown distribution over the interval [-(
be an unknown bounded, multilinear function. There exists an algorithm with time and sample complexity 푛 푂 (log (1/휀)/log (1/(1-휂) ) ) • log(1/훿) that outputs a hypothesis 푓 ′ such that
Unfortunately, when we move beyond the classical setting, the picture becomes trickier. In particular, it is not immediately clear what the suitable analogue of the biased Fourier basis should be in the quantum setting. We could certainly try to consider single-qubit operators of the form 푃 = 푃 -휇 푃 • 퐼 for 푃 ∈ {푋, 푌 , 푍 }, where 휇 푃 denotes the 푃-th coordinate of the mean of 퐷 regarded as a distribution over the Bloch sphere. We could then extend naturally to give a basis over 푛 qubits, and the functions 휌 ↦ → Tr( 푃휌) would by design be orthogonal to each other with respect to the distribution 퐷 ⊗푛 . Writing
we can mimic the calculation above and obtain
Unfortunately, at this juncture the above naive approach hits a snag. In the mean zero case, we could
퐹 because of a fortuitous peculiarity of the mean-zero setting. In that setting, we implicitly exploited both that the Pauli operators 푃 are orthogonal to each other with respect to the trace inner product, and also that that the functions 휌 ↦ → Tr(푃 휌) are orthogonal to each other with respect to 퐷 ⊗푛 . In the above approach for nonzero mean, we achieved the latter condition by shifting the Pauli operators to define 푃, but these shifted operators are no longer orthogonal to each other with respect to the trace inner product. Circumventing this issue is the technical heart of our proof. As we will see in Section 4, several key technical moves are needed. First, instead of assuming that the covariance of 퐷 is diagonalized, we will fix a rotation that simplifies the mean, E[휌]. Second, instead of shifting the basis operators {푋, 푌 , 푍 } so that the resulting functions 휌 ↦ →
Tr( 푃휌) are orthogonal with respect to 퐷 ⊗푛 , we shift them so that E[휌] is orthogonal to them, and define O ′ low by truncating in this new basis instead. Finally, instead of directly bounding the truncation error E[Tr( (O ′ -O ′ low )휌) 2 ] using the above sequence of steps, we crucially relate it to the quantity Tr( (O ′ ) 2 E[휌]) in order to establish exponential decay. Note that Tr(
) ≤ 1. To our knowledge, all three of these components are new to our analysis. We leave it as an intriguing open question to find other applications of these ingredients to domains where "biased Pauli analysis" arises.
Remark 1.4 (Predicting multiple observables). Just as in [HCP23], we can also easily extend our guarantee to the setting where we wish to learn the joint mapping
(1) This is the natural channel learning analogue of the question of classical shadows for state learning [HKP20] -recall that in the latter setting, one would like to perform measurements on copies of 휌 and obliviously produce a classical description of the state that can then be used to compute some collection of observable values. We sketch the argument for extending to learning the joint mapping in Eq. (1) in Remark 4.6.
Impossibility for general concentrated distributions. It is natural to wonder to what extent our results can be generalized, especially to states that are entangled. Could it be that all one needs is some kind of global covariance bound? Unfortunately, we show in Section 5 that even in the classical setting, this is not the case. Since classical distributions can be encoded by distributions over qubits, this implies hardness for learning in the quantum setting as well.
Theorem 1.5 (Hardness of learning over general concentrated distributions). There exists a distribution
푛 and a concept class C such that no algorithm PAC-learns the class C over 퐷 in subexponential time.
There is a wide spectrum of distributional assumptions that interpolates between fully product distributions and general concentrated distributions -for instance, products of 푘-dimensional qudit distributions, output states of small quantum circuits, or distributions over negatively associated variables. As discussed earlier, our understanding of when it is possible to predict the average-case behavior of arbitrary quantum dynamics is still nascent, and understanding learnability with respect to these more expressive distributional assumptions remains an important open question.
Organization. In Section 2, we state some preliminaries. In Section 3, we prove Theorem 1.3, which is the classical setting and can be viewed as a warm-up to the quantum setting. In Section 4, we prove Theorem 1.1, our main result. Finally, in Section 5, we show impossibility results including Theorem 1.5 and the failure of low-degree truncation in the standard Pauli basis.
Our work is part of a growing literature bridging classical computational learning theory and its quantum counterpart. Its motivation can be thought of as coming from the general area of quantum process tomography [MRL08], but as this is an incredibly extensive research direction, here we only focus our attention on surveying directly relevant works.
Quantum analysis of Boolean functions. In [MO08], it was proposed to study Pauli decompositions of Hermitian unitaries as the natural quantum analogue of Boolean functions. One notable follow-up work [RWZ22] proved various quantum versions of classical Fourier analytic results like Talagrand's variance inequality and the KKL theorem in this setting, and also obtained corollaries about learning Hermitian unitaries in Frobenius norm given oracle access (see also [CNY23,BY23] for the non-Hermitian case). Recently, [NPVY23] considered the Pauli spectrum of the Choi representation of quantum channels and proved low-degree concentration for channels implemented by QAC 0 . One technical difference with our work is that these notions of Pauli decomposition are specific to the channel, whereas the object whose Pauli decomposition we consider is specific to the Heisenberg-evolved operator
Additionally, we note that all of the above mentioned works focus on questions more akin to learning a full description of the channel and thus are inherently tied to channels with specific structure. In contrast, our focus is on learning certain properties of the channel, and only in an average-case sense over input states. As mentioned previously, this specific question was first studied in [HCP23]. There have been two direct follow-up works to this paper which are somewhat orthogonal to the thrust of our contributions. The first [VZ23] establishes refined versions of the so-called non-commutative Bohnenblust-Hille inequality which was developed and leveraged by [HCP23] to obtain logarithmic sample complexity bounds. In this work, we did not pursue this avenue of improvement but leave it as an interesting open question to improve our sample complexity guarantees accordingly. The second follow-up [KSVZ23] to [HCP23] studies the natural qudit generalization of the original question where the distribution over qudits is similarly closed under a certain family of single-site transformations.
Finally, we note the recent work of [ADGP24] which studied the learnability of quantum channels with only low-degree Pauli coefficients. Their focus is incomparable to ours as they target a stronger metric for learning, namely ℓ 2 -distance for channels, but need to make a strong assumption on the complexity of the channel being learned. In contrast, we target a weaker metric, namely average-case error for predicting observables, but our guarantee applies for arbitrary channels.
theory is too prevalent to do full justice to in this section. This idea of learning Boolean functions by approximating their low-degree Fourier truncation was first introduced in the seminal work of [LMN93]. Fourier-analytic techniques have been used to obtain new classical learning results for various concept classes like decision trees [KM91], linear threshold functions [KKMS08], Boolean formulas [KS01], lowdegree polynomials [EI22], and more.
While Fourier analysis over biased distributions dates back to early work of Margulis and Russo [Mar74, Rus81, Rus82], it was first applied in a learning-theoretic context in [FJS91], extending the aforementioned result of [LMN93].
The Pauli matrices 퐼, 푋, 푌 , 푍 provide the basis for 2 × 2 Hermitian matrices. This is captured by the following standard fact on expanding a single-qubit state using Pauli matrices.
and 푋, 푌 , 푍 are the standard Pauli matrices:
The set of all such ì 훼 of unit norm is the Bloch sphere. Any single-qubit distribution 퐷 can be viewed as a distribution over the Bloch sphere. We use E 퐷 [휌] ∈ C 2×2 and ì 휇 ∈ R 3 to refer to the expected state and the expected Bloch vector respectively.
By taking tensor products of Pauli matrices, we obtain the collection of 4 푛 Pauli observables {퐼, 푋, 푌 , 푍 } ⊗푛 , which form a basis for the space of 2 푛 × 2 푛 Hermitian matrices:
where O(푃) Tr(O푃 )/2 푛 .
Next, we define the Pauli covariance and second moment matrices associated to any distribution 퐷 over the single-qubit Bloch sphere.
Definition 2.1 (Pauli covariance and second moment matrices). Let 퐷 be a distribution over the Bloch sphere. We will associate with 퐷 the second moment matrix S ∈ R 3×3 and covariance matrix Σ ∈ R 3×3 , indexed by the non-identity Pauli components 푋, 푌 , and 푍 . We define S such that S 푃,푄 = E 휌∼퐷 [Tr(푃 휌)Tr(푄휌)],
and
The following is a consequence of Fact 2.1:
Fact 2.3. For any distribution over the Bloch sphere, the Pauli second moment matrix S satisfies Tr(S) = 1.
In this paper we consider the following, standard access model, see e.g. [HCP23]. We assume that we can interact with the unknown channel E by preparing any input state, passing it through E , and performing a measurement on the output. Additionally, we are given access to training examples from some distribution D = 퐷 ⊗푛 over product states, and their corresponding classical descriptions. Because product states over 푛 qubits can be efficiently represent efficiently using 푂 (푛) bits, the training set can be stored efficiently on classical computers. The standard approach to represent a product state on a classical computer is as follows. For each state 휌 = ⊗ 푛 푖=1 |휓 푖 sampled from D, the classical description can be given by their 1-qubit Pauli expectation values:
Given these classical samples from D and the ability to query E , the learning goal is to produce a hypothesis 푓 ′ which takes as input the classical description of a product state 휌 and outputs an estimate for Tr(O E [휌]). Formally, we want this hypothesis to have small test loss in the sense that
) 2 ] ≤ 휀 with probability at least 1 -훿 over the randomness of the learning algorithm and the training examples from D.
For our learning protocol, we will use the following elementary results about linear and polynomial regression: Fact 2.4 (Rademacher complexity generalization bound [MRT18]). Let F be the class of bounded linear functions [-1, 1] 푑 → [-퐵, 퐵], and let ℓ be a loss function with Lipschitz constant 퐿 and a uniform upper bound of 푐. With probability 1 -훿 over the choice of a training set 푆 of size 푚 drawn i.i.d. from distribution D,
Then linear regression over the set of degree-푑 polynomials with coefficients in [-1, 1] has time and sample complexity poly(푛 푑 , log 1/휀) • log 1/훿 and finds ℎ such that
with probability 1 -훿.
In this section we will prove Theorem 1.3, which is a special case of Theorem 1.1 where the distribution is classical, i.e. supported only on the 푍 component.
The key ingredient in the proof is to show that for any function which is 퐿 2 -integrable with respect to a product distribution over [-(1 -휂), 1 -휂] 푛 and whose extension to the hypercube is bounded, the function admits a "low-degree" approximation under an appropriate orthonormal basis. Roughly, the intuition is that the space of linear functions over a distribution 퐷 on [-(1-휂), 1-휂] has an orthonormal basis which is a (1-휂)-scaling of a basis for a distribution on {-1, 1}. Therefore, the space of multilinear functions over the corresponding product distribution 퐷 ⊗푛 has a basis whose degree-푑 components are scaled by (1 -휂) 푑 . This, combined with the assumption that the function is bounded on the hypercube, allows us to conclude that the contribution of the degree-푑 component to the variance of 푓 over 퐷 ⊗푛 is at most (1 -휂) 2푑 .
We prove this structural result in Section 3.1 and conclude the proof of Theorem 1.3 in Section 3.2.
We first review some basic facts about classical biased Fourier analysis. For a more extensive overview of this topic, we refer the reader to [O'D14, Chapter 8].
Given a measure 휇, we let 퐿 2 (휇) denote the space of 퐿 2 -integrable functions with respect to 휇.
The functions 휙 푆 provide an orthonormal basis for the space of functions 퐿 2 (퐷 ⊗푛 ), where 퐷 is the distribution over {1, -1} with mean 휇. We can naturally extend this to arbitrary product distributions over R 푑 as follows:
Fact 3.2 (Basis for an arbitrary product distribution). Let 퐷 be a distribution over R with mean 휇 and variance 휎 2 > 0. Then {1, 푥 -휇 휎 } is an orthonormal basis for 퐿 2 (퐷), and thus {1,
The orthonormality of the basis immediately implies the following simple fact:
The following is the crucial structural result in the classical setting that gives rise to Theorem 1.3.
Roughly speaking, it ensures that for the "concentrated product distributions" 퐷 considered therein, any bounded multilinear function has decaying coefficients when expanded in the orthonormal basis for 퐿 2 (퐷 ⊗푛 ).
Lemma 3.4. Let 푓 : [-1, 1] 푛 → [-1, 1] be a multilinear function and let 퐷 be a distribution over R with mean 휇 and variance 휎 2 < 1 -휇 2 . Then there exists a function 푓 ≤푑 such that
Proof. Let 푓 be expressed in the basis 퐵 hypercube = {1,
where
In light of Lemma 3.4, the proof of Theorem 1.3 is straightforward given the following elementary fact: Fact 3.5 (Bernoulli maximizes variance). Let 퐷 be a distribution over the interval [
We can now conclude the proof of Theorem 1.3: Proof of Theorem 1.3. By Fact 3.5, we have Var 퐷 (푥) ≤ (1 -휂) 2 (1 -휇 2 ). Then Lemma 3.4 gives us a degree-푑 approximation 푓 ≤푑 to 푓 such that
Taking 푑 ≔ log(1/휀)/log(1/(1 -휂)) gives an approximation with error ≤ 휀. Then by Corollary 2.5, linear regression on the space of polynomials of degree log(1/휀)/log(1/(1 -휂)) finds an 푂 (휀)-error hypothesis in 푛 푂 (log (1/휀)/log (1/(1-휂) ) ) • log(1/훿) time and samples.
Remark 3.6. In the classical setting linear regression is not required, as we can estimate the mean, and the coefficients satisfy
so they can be estimated directly. We give the guarantee in terms of linear regression because the approach of directly estimating the coefficients does not generalize to the quantum setting.
In this section we will prove Theorem 1.1. First we will show that under any product distribution with second moment S such that S op ≤ 1 -휂 for some 휂 ∈ (0, 1), every observable has a low-degree approximation. A distribution has S op = 1 only if it is effectively a classical distribution; i.e. it is supported on two antipodal points in the Bloch sphere. So we are showing that any product distribution which is "spread out" within the Bloch sphere behaves well with low-degree approximation.
To do this, we cannot use exactly the same argument as in Section 3, because there is not necessarily an orthonormal basis for our product distribution 퐷 ⊗푛 that is a "stretched" basis for some other distribution over the Bloch sphere. Instead, we compare the variance of the observable under 퐷 ⊗푛 to the quantity
. This allows us to use the boundedness of O to derive bounds for the contribution of the degree-푑 part to the variance of O under 퐷 ⊗푛 . The learning algorithm will find the low-degree approximation by linear regression over the degree-log(1/휀) Pauli coefficients. The notion of low-degreeness will be with respect to a basis adapted to 퐷 ⊗푛 . Definition 4.1. Let 퐷 be a distribution over the Bloch sphere. Let 푈 † 퐴푈 be the eigendecomposition of
The fact that the degree is defined for any observable (which is equivalent to 푋 , 푌 , 푍 forming a basis of the space of operators) is the content of Lemma 4.2. The existence of low-degree approximation is guaranteed by the following lemma. Lemma 4.1 (Low-degree approximation). Let O be a bounded 푛-qubit observable and let 퐷 be a distribution over the Bloch sphere with mean ì 휇 and Pauli second moment matrix S such that S ≤ 1 -휂 for some 휂 ∈ (0, 1). Then there exists a degree-푑 observable O ≤푑 and a constant 휂 ′ ∈ (0, 1) such that
where 휂 ′ is a function of 휂.
Once Lemma 4.1 is established, Theorem 1.1 follows readily from an application of Corollary 2.5.
Proof of Theorem 1.1, using Lemma 4.1. Let 1 -휂 be a known upper bound on S op . We assume the access model of Section 2.2, where we get a set 푆 of examples [Tr(푃 휌)] for 1-local 푃. Our algorithm is as follows:
1. Compute 휂 ′ as in the last line of Lemma 4.5. Let 푑 ≔ 푂 (log(1/휀)/log(1/(1 -휂 ′ )).
2. Draw a set 푆 of size 푛 푑 • log(1/훿), and initialize 푆 ′ to be empty.
to the set 푆 ′ .
4. Run linear regression on 푆 ′ and output the returned hypothesis ℎ.
By Hoeffding's inequality, each estimate of Tr(OE [휌]) is within 휀 of its expectation with probability 1exp(-Ω(|푇 |휀 2 )). By union bound over the |푆 | estimates, with probability ≥ 1 -훿, all estimates are within 휀 of Tr(OE [휌]). The time, sample, and error bounds follow from Lemma 4.1, which guarantees that E † [O] is 휀-close
to some degree-푑 polynomial. This implies the labels of our sample set are 2휀-close to such a polynomial. ) , as there are 3 choices for each non-identity component. Then by Corollary 2.5, linear regression has time and sample complexity
and outputs a hypothesis ℎ such that
The proof of Lemma 4.1 follows from three technical Lemmas. The first gives, for any product distribution over 푛-qubit states, a (non-orthogonal) decomposition of any observable into operators which are centered and bounded in variance with respect to that distribution.
Lemma 4.2. Let 퐷 be a distribution over the Bloch sphere. Let 푈 † 퐴푈 be the eigendecomposition of 휌 = E 퐷 [휌], and let 푋 , 푌 , 푍 := 푈 † 푋푈 , 푈 † 푌푈 ,
Then {퐼, 푋 , 푌 , 푍 } is a basis for the set of 2 × 2 unitary Hermitian matrices, and thus every 푛-qubit observable O can be written as
Proof. It is clear that {퐼, 푋 , 푌 , 푍 } is linearly independent and thus 퐵 forms a basis for any 푛-qubit observable. Note that Tr(푃 휌) = 푛 푖=1 Tr(푃 푖 휌 푖 ) as 휌 is a product state, so we can restrict the analysis to single qubit states drawn from 퐷.
For 푃 = 푋 or 푌 , it is clear that E 휌∼퐷 [Tr(푃 휌)] = 0 and E 휌∼퐷 [Tr(푃 휌) 2 ] = 1. For 푍 , we have
Moreover,
Remark 4.3. Going forward, we will assume w.l.o.g. that the mean of the distribution E 퐷 [휌] is diagonal because we can always transform the basis according to 푈 . Thus, we will assume that the mean state
We next prove two important components required in the proof of Lemma 4.1. The first lemma gives an eigenvalue lower bound on a Hermitian matrix that arises when we expand Tr(O 2 E[휌]).
Lemma 4.4. Let 휇 ∈ (-1, 1) and
Then 휆 min (Re( 푀 ⊗푘 )) ≥ (1 -휇 2 ) 푘/2 for any 푘 ∈ N.
Proof. Note that 푀 = 퐼 + 휇푌 and 푌 is imaginary. Thus,
Note also that the eigenvalues of the above remain the same if we replace the 푌 's with 푍 's. Thus, the eigenvalues of the above can be indexed by 푥 ∈ {±1} 푘 , and can be expressed as follows:
The next lemma gives an upper bound on the Pauli covariance matrix Σ (recall Definition 2.1) scaled by a specific diagonal matrix.
Lemma 4.5. Let 퐷 be a distribution over the Bloch sphere with mean ì 휇 = (0, 0, 휇), Pauli second moment matrix S such that S op ≤ 1 -휂 for some 휂 ∈ (0, 1), and Pauli covariance matrix Σ. Let Δ = diag( (1 -휇 2 ) -1/4 , (1 -휇 2 ) -1/4 , (1 -휇 2 ) -1/2 ). Then there exists 휂 ′ ∈ (0, 1) such that ΔΣΔ op ≤ 1 -휂 ′ , where 휂 ′ is a function of 휂.
Proof. We split into two cases based on whether 휇 2 ≥ 휂/2. The case where 휇 2 < 휂/2 is the simpler case: since Σ op ≤ S op ≤ 1 -휂 and Δ 2 op ≤ (1 -휇 2 ) -1 , we have
Now we consider the case where the inequality is not satisfied. We note that Σ = S -ì 휇 ì 휇 ⊤ and ì 휇 = (0, 0, 휇), thus we have that ΔΣΔ has the following block structure:
, where S 2×2 is the top left 2 × 2 block of S, S 푧푧 is the bottom right entry, and 푏 is the remaining part (its values will not be directly relevant). Note also that ΔΣΔ 0, and it is well-known that any PSD matrix of the form 퐴 푏 푏 † 푐 0 has operator norm at most 퐴 op + 푐. We thus know that
where we use the fact that 1 = Tr(S) = Tr(S 2×2 ) + S 푧푧 . Then we have
The third line is by the fact that S 푧푧 ≤ S op ≤ 1 -휂, and the last inequality is because the function
increasing with 휇 2 and that we are in the 휇 2 ≥ 휂/2 case. Thus, combining the two cases, there always exists 휂 ′ such that ΔΣΔ op ≤ 1 -휂 ′ . Specifically, we have
/2 > 0 . Remark 4.6. As mentioned in Remark 1.4, our techniques can be extended to learn not just the mapping 휌 ↦ → Tr(푂E [휌]), but also the joint mapping (푂, 휌) ↦ → Tr(푂E [휌]). As this is standard, here we only briefly sketch the main ideas. The general strategy is to produce a classical description of the channel that we can then use to make predictions about properties of output states. To do this, we draw many input states 휌 1 , . . . , 휌 푁 from D, query the channel on each them, and for each of the output states E [휌 푗 ], we apply a randomized Pauli measurement to each of them and use these to form unbiased estimators for the output state. Concretely, given an output state E [휌 푗 ], a randomized Pauli measurement will result in a stabilizer state |휓 ( 푗 ) = ⊗ 푛 푖=1 |푠 ( 푗 ) 푖 ∈ {|0 , |1 , |+ , |-, | + , | -} ⊗푛 , and the expectation of
The classical description of the channel is given by the 푂 (log(1/휀))-body reduced density matrices of the input states 휌 1 , . . . , 휌 푁 , together with the classical encodings of |휓 (1) , . . . , |휓 (푁 ) .
Given an observable 푂, we can then perform regression to predict the labels
. Because the labels are unbiased estimates of Tr(푂 E [휌 푗 ]), the resulting estimator will be an accurate approximation to 휌 ↦ → Tr(푂 E [휌]) for 휌 ∼ D.
In this work, we do not belabor these details as they are already investigated in depth in [HCP23]. Instead, we focus on the single observable case as this is where the main difficulty lies in extending the results of [HCP23] to more general input distributions. Now we prove Lemma 4.1 which shows the existence of a low-degree approximator.
Proof of Lemma 4.1. Assume w.l.o.g., as in Remark 4.3, that E 퐷 [휌] = 1 2 (퐼 + 휇푍 ) and ì 휇 = (0, 0, 휇). Let O be expressed in the basis 퐵 = {퐼, 푋, 푌 ,
we will denote by {푃 ∈ 퐵 : 푃 ∼ 푆 } the set of basis elements with non-identity components at indices in 푆 and identity components at indices in 푆. We will also denote by |푃 | the number of non-identity components in 푃.
Let O >푑 ≔ |푆 |>푑 푃 ∼푆 O(푆)푃. We will show that O >푑 satisfies E 휌∼퐷 ⊗ [Tr(O >푑 휌) 2 ] ≤ (1 -휂 ′ ) 푑 where 휂 ′ ∈ (0, 1) depends on 휂.
We first note a bound on the related quantity
) ≤ 1 as well. We will expand this quantity as a quadratic form.
Note that the product is 0 whenever exactly one of 푃 푖 , 푄 푖 is 퐼 for any 푖 ∈ [푛] (as Tr( (푍 -휇퐼 )•(퐼 +휇푍 )) = 0).
Therefore, we can partition the terms into groups that share a subset of identity variables:
where O 푆 is the vector of coefficients for the set {푃 : 푃 ∼ 푆 }, and 푀 is the 3 × 3 matrix such that 푀 푃,푄 = Tr(푃푄 E 퐷 [휌]):
Here, the entry 푖휇 arises because 푋푌 = 푖푍 and Tr(푋푌 • 1 2 (퐼 + 휇푍 )) = 푖휇. Since 푀 is positive semidefinite, we have O † 푆 푀 ⊗ |푆 | O 푆 ≥ 0 for all 푆, and therefore we have
(2) Now we will write the desired quantity E 휌∼퐷 ⊗ [Tr(O >푑 휌) 2 ] as a quadratic form as well:
Similarly, the product is 0 whenever exactly one of 푃 푖 and 푄 푖 is identity (by the guarantee of Lemma 4.2 that E[Tr(푃 푖 휌)] = 0 for 푃 푖 ≠ 퐼 ), so we can make the same partition:
words, it is the second moment matrix of the non-identity elements of our biased Pauli basis. Below, we show the entries of 푀 ′ in terms of the Pauli covariance matrix Σ:
Our aim is to bound 푀 ′ in terms of 푀 in order to show the existence of some 휂 ′ ∈ (0, 1) such that
Comparing Eq. ( 2) and (3), it suffices to show that
Let 푀 2×2 be the top left 2×2 block in 푀, which is exactly the matrix in Lemma 4.4. From Lemma 4.4, we have 휆 min (Re(푀
. Thus, we can establish Eq. (4) by proving that
(5) Now, note that 푀 ′ can be written as ΔΣ Δ, where Σ is the covariance matrix of 퐷 and Δ = diag(1, 1, (1-휇 2 ) -1/2 ). Letting Δ = diag( (1-휇 2 ) -1/4 , (1-휇 2 ) -1/4 , (1-휇 2 ) -1/2 ) (which is the diagonal matrix defined in Lemma 4.5), we can see that Eq. ( 5) is equivalent to
By Lemma 4.5, this is true by our assumption that S op ≤ 1 -휂. This establishes Eq. ( 5) and thus Eq. (4), and from Eq. ( 2) and (3), we have
Therefore,
Hence, we have obtained the claimed result. Remark 4.7. In the proof of Lemma 4.1, we relate the quantity E 휌∼퐷 ⊗ [Tr(O >푑 휌) 2 ] that we wish to bound to the related quantity E 휌∼퐷 ⊗ [Tr(O 2 휌)], which is at most 1 since O op ≤ 1. Due to the choice of our biased Pauli basis 퐵 = {퐼, 푋, 푌 , 푍 -휇퐼 √ 1-휇 2 } ⊗푛 , we may write both quantities as sums of
(2) and (3)). Suppose 휌 is a product of different distributions where each qubit has mean Bloch vector ì 휇 푖 = (0, 0, 휇 푖 ) (after rotation; see Remark 4.3) and second moment bounded by 1 -휂. We will instead use the basis 퐵 = ⊗ 푛 푖=1 {퐼, 푋, 푌 ,
One can easily see that the above quantities are essentially the same, with 푀 ⊗ |푆 | replaced by ⊗ 푖 ∈푆 푀 푖 and similarly for 푀 ′ . Then, the next steps in the proof (establishing Eq. (4) and (5)) are exactly the same.
In this section, we show lower bounds in the classical case, which automatically imply hardness in the quantum case. In Section 5.1, we prove Theorem 1.5, which shows hardness of learning without the product distribution assumption in Theorem 1.3. In Section 5.2, we show that truncating in the unbiased basis fails when the distribution is not mean zero.
In this section, we prove Theorem 1.5. We show that if D is an arbitrary distribution, then even if D is supported on [-(1 -휂), (1 -휂)] 푛 (i.e., in the interior of the hypercube), there is no learning algorithm.
Let 퐶 be a code over {0, 1} 푛 of size 2 Θ(푛) and distance 푛/4. The following fact is standard.
Fact 5.1. For any constant 휀 > 0, any learning algorithm that can learn an arbitrary function 푓 : {±1} 푛 → {±1} over 퐶 to 휀 error requires 2 Ω (푛) queries.
Proof of Theorem 1.5. Let 휂 = 0.1. We set the distribution D to be the uniform distribution over (1-휂)•퐶, which is supported in [-(1 -휂), (1 -휂)] 푛 . Let 푓 : {±1} 푛 → {±1} be an arbitrary function. Since the code 퐶 has distance 푛/4, we can without loss of generality assume that 푓 (푥 ′ ) = 푓 (푥) whenever 푑 (푥, 푥 ′ ) ≤ 푛/8. Suppose for contradiction that there is an algorithm that, with only 2 표 (푛) queries to 푓 , outputs a function 푔 : [-1, 1] 푛 → R such that E 푥∼D [(푔(푥) -푓 (푥)) 2 ] ≤ 휀. Let 푝 ≔ 1 -휂/2, and let Ber(푝) be the distribution where we have +1 with probability 푝 and -1 otherwise. Then, for any 푥 ∈ {±1} 푛 , we have 푓 ((1 -휂)푥) = E 푧∼Ber(푝 ) ⊗ [푓 (푥 • 푧)], where • denotes entry-wise product.
We claim that for any 푥 ∈ 퐶, | E 푧∼Ber(푝 ) ⊗ [푓 (푥 •푧)] -푓 (푥)| ≤ 표 푛 (1). The number of -1 coordinates in 푧 is distributed as a Bin(푛, 휂/2). By the Chernoff bound, Pr[Bin(푛, 휂/2) ≥ (1 +훿) 1
2 휂푛] ≤ 푒 -푂 (훿 2 휂푛) = 표 푛 (1). In particular, for 휂 = 0.1, we have that Pr[Bin(푛, 휂/2) ≥ 푛/8] ≤ 표 푛 (1). Thus, with probability 1 -표 푛 (1), 푑 (푥 • 푧, 푥) < 푛/8, which means that 푓 (푥 • 푧) = 푓 (푥). This proves that |푓 ((1 -휂)푥) -푓 (푥)| ≤ 표 푛 (1) for all 푥 ∈ 퐶.
Then, let ℎ(푥) = 푔((1 -휂)푥).
This means that ℎ is an 휀-approximation of 푓 over 퐶. This contradicts Fact 5.1 thus completing the proof.
In Theorem 1.3, if the product distribution D over [-(1 -휂), 1 -휂] 푛 has mean zero, then directly truncating 푓 with respect to the standard monomial basis at degree 푂 (log(1/휀)/log(1/(1-휂))) (independent of 푛) suffices. However, in this section, we will show that without the mean zero assumption, even truncating at Ω(푛) degree w.r.t. the monomial basis does not give a small approximation error. Our counter-example implies that truncation in any distribution-oblivious basis will fail on some product distribution. In the quantum setting, this implies that low-degree truncation in the standard Pauli basis fails on some product distribution as well.
The counter-example is quite simple: 푓 is the multilinear extension of the Boolean majority function, and D is supported on a single nonzero point (which is in fact a product distribution).
). Let 푓 be the multilinear extension of the Boolean majority function. Then the ℓ 2 Fourier weight on terms of degree 푘 is Θ(푘 -3/2 ).
The following is a well-known fact in approximation theory.