Predicting quantum channels over general product distributions
Sitan Chen Jaume de Dios Pont Jun-Ting Hsieh Hsin-Yuan Huang Jane Lange Jerry Li

Infrared spectroscopy study of kagome material CsTi_3Bi_5
    Rongyan Chen
    Accepted XXX. Received YYY; in original form ZZZ
=========================================================



§ ABSTRACT 
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an n-qubit channel ℰ and an observable 𝒪, we aim to learn the mapping

    ρ↦(𝒪ℰ[ρ])

to within a small error for most ρ sampled from a distribution 𝒟. Previously, Huang, Chen, and Preskill <cit.> proved a surprising result that even if ℰ is arbitrary, this task can be solved in time roughly n^O(log(1/ϵ)), where ϵ is the target prediction error. 
However, their guarantee applied only to input distributions 𝒟 invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states ρ. 

In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution 𝒟, provided it is not “classical” in which case there is a trivial exponential lower bound. Our method employs a “biased Pauli analysis,” analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.

    
    
    
    
    
    
    

    




§ INTRODUCTION


When is it possible to learn to predict the outputs of a quantum channel ?
Such questions arise naturally in a variety of settings, such as the experimental study of complex quantum dynamics <cit.>, and in fast-forwarding simulations of Hamiltonian evolutions <cit.>.
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 <cit.> or a structured Pauli channel <cit.>.
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 hole <cit.> — and where it is advantageous to avoid such strong structural assumptions on the underlying channel.










Recently, <cit.> considered an alternative workaround in which one only attempts to learn a complicated n-qubit channel in an average-case sense. Given query access to , and given an observable , the goal is to learn the mapping

    ρ↦([ρ])

accurately on average over input states ρ drawn from some n-qubit distribution , rather than over worst-case input states. The authors of <cit.> came to the surprising conclusion that this average-case task is tractable even for arbitrary channels , provided  comes from a certain class of “locally flat” distributions. Their key observation was that the Heisenberg-evolved observable ^†[] admits a low-degree approximation in the Pauli basis, where the quality of approximation is defined in an average-case sense over input state ρ.

Another interesting feature of this result is that their learning algorithm only needs to query  on random product states, regardless of the choice of locally flat distribution . This is both an advantage and a shortcoming. On one hand, if one is certain that the states ρ one wants to predict on are samples from a locally flat distribution, no further information about  is needed to implement the learning protocol in <cit.>. On the other hand, locally flat distributions are quite specialized: they are constrained to be invariant under any single-qubit Clifford gate. In particular, almost all product distributions over product states fall outside this class. Worse yet, the general approach of low-degree approximation in the Pauli basis can be shown to fail when local flatness does not hold (see <Ref>). We therefore ask:



    Are there more general families of distributions  under which one can

        learn to predict arbitrary quantum dynamics?
    



Identifying rich settings where it is possible to characterize the average-case behavior of such dynamics, while making minimal assumptions on the dynamics, is of intense practical interest. Unfortunately, our understanding of this remains limited: even for general product distributions, known techniques break down. In this work we take an important first step towards this goal by completely characterizing the complexity of learning to predict arbitrary quantum dynamics in the product setting.
Informally stated, our main result is that learning is possible so long as the distribution is not classical.
That is, for this problem there is a “blessing of quantum-ness”: as long as the distribution displays any quantitative level of quantum behavior, there is an efficient algorithm for predicting arbitrary quantum dynamics under this distribution.

More formally, note that if D is the uniform distribution over the computational basis states |0⟩ and |1⟩, then the task of predicting ([ρ]) on average over ρ∼≜ D^⊗ n for an arbitrary channel  is equivalent to the task of learning an arbitrary Boolean function from random labeled examples, which trivially requires exponentially many samples. This logic naturally extends to any “two-point” distribution in which D is supported on two diametrically opposite points on the Bloch sphere. 
Note that any such distribution, up to a rotation, is an embedding of a classical distribution onto the Bloch sphere.

A natural way of quantifying closeness to such distributions is in terms of the second moment matrix ∈^3× 3 of the distribution D, when D is viewed as a distribution over the Bloch sphere (see <Ref> for formal definitions).
We refer to this matrix as the Pauli second moment matrix of D.
For the purposes of this discussion, the key property of this matrix is that _𝗈𝗉≤ 1 for all D, and moreover, _𝗈𝗉 = 1 if and only if D is one of the aforementioned two-point distributions.
With this, we can now state our main result:



    Let , δ, η∈ (0,1).
   Let D be an unknown distribution over the Bloch sphere with Pauli second moment matrix  such that _≤ 1-η.
   Let  be an unknown n-qubit quantum channel, and let  be a known n-qubit observable.
   There exists an algorithm with time and sample complexity
   min(2^O(n)/ϵ^2, n^O(log(1/)/log(1/(1-η))))·log(1/δ) that outputs an efficiently computable map f' such that 
   
    _ρ∼ D^⊗ n [(([ρ]) - (f'(ρ)))^2] ≤

   with probability at least 1-δ. 
   
   

Note that the only condition on D we require is a quantitative bound on the spectral norm of its Pauli second moment matrix.
In other words, so long as the distribution D 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 D has mean zero. Indeed, as soon as one deviates from the mean zero case, the Pauli decomposition approach of <cit.> breaks down. In contrast, our guarantee works for any product distribution whose marginal second moment matrices have operator norm bounded away from 1.


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 <Ref> 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 <cit.> in greater detail. They considered the decomposition of '≜^†[] into the basis of n-qubit Pauli operators, i.e. ' = ∑_P ∈{I,X,Y,Z}^nα_P· P and argued that this is well-approximated by the low-degree truncation '_ low = ∑_|P|<tα_P · P. This can be readily seen from the following calculation. By rotating the distribution D, we may assume the covariance is diagonal, with entries bounded by 1 - η. Then the error achieved by the low-degree truncation is given by

    [((' - '_ low)ρ)^2] = [(∑_|P|≥ tα_P·(Pρ))^2] ≤∑_|P|≥ t (1 - η)^|P|·α_P^2 ≤ (1 - η)^t ·1/2^n'^2_F ≤ (1 - η)^t  ,

where the second step follows from the fact that
[(Pρ) (Qρ)] = 0 if P ≠ Q and is at most (1-η)^|P| if P = Q (since D is mean zero and its covariance is diagonal with entries bounded by 1 - η), and the last step follows by the assumption that '_ op≤ 1.

Note that when D is not mean zero, this step breaks, and we do not have this nice exponential decay in t. In fact, in <Ref> we construct examples of operators which are not well-approximated by their low-degree truncations in the Pauli basis when D 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 <Ref>, this idea can be used to give the following learning guarantee in the classical case where D is only supported along the Z direction in the Bloch sphere:



    Let , δ, η∈ (0,1).
    Let D be an unknown distribution over the interval [-(1-η),1-η].
    Let f:[-1,1]^n → [-1,1] be an unknown bounded, multilinear function.
    There exists an algorithm with time and sample complexity 
   n^O(log(1/)/log(1/(1-η)))·log(1/δ) that outputs a hypothesis f' such that 
   
    _x ∼ D^⊗ n[(f(x) - f'(x))^2] ≤

   with probability at least 1-δ. 


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 P = P - μ_P· I for P∈{X,Y,Z}, where μ_P denotes the P-th coordinate of the mean of D regarded as a distribution over the Bloch sphere. We could then extend naturally to give a basis over n qubits, and the functions ρ↦(Pρ) would by design be orthogonal to each other with respect to the distribution D^⊗ n. Writing ' = ∑_P α_P ·P and defining _ low≜∑_|P|<tα_P ·P, we can mimic the calculation above and obtain

    [((' - _ low)ρ)^2] = [(∑_|P|≥ tα_P·(Pρ))^2] ≤ (1 - η)^|P|∑_|P|≥ tα^2_P .

Unfortunately, at this juncture the above naive approach hits a snag. In the mean zero case, we could easily relate ∑_P α_P^2 to 1/2^n'^2_F because of a fortuitous peculiarity of the mean-zero setting. In that setting, we implicitly exploited both that the Pauli operators P are orthogonal to each other with respect to the trace inner product, and also that that the functions ρ↦(Pρ) are orthogonal to each other with respect to D^⊗ n. In the above approach for nonzero mean, we achieved the latter condition by shifting the Pauli operators to define P, 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 <Ref>, several key technical moves are needed. First, instead of assuming that the covariance of D is diagonalized, we will fix a rotation that simplifies the mean, [ρ]. Second, instead of shifting the basis operators {X,Y,Z} so that the resulting functions ρ↦(Pρ) are orthogonal with respect to D^⊗ n, we shift them so that [ρ] is orthogonal to them, and define '_ low by truncating in this new basis instead. Finally, instead of directly bounding the truncation error [((' - '_ low)ρ)^2] using the above sequence of steps, we crucially relate it to the quantity

    ((')^2 [ρ])

in order to establish exponential decay. Note that ((')^2 [ρ]) ≤'^2_ op·([ρ]) ≤ 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.


    Just as in <cit.>, we can also easily extend our guarantee to the setting where we wish to learn the joint mapping
    
    (ρ, ) ↦([ρ]) .

    This is the natural channel learning analogue of the question of classical shadows for state learning <cit.> ­– 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. (<ref>) in <Ref>.





  
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 <Ref> 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.



There exists a distribution  over [-(1-η), 1-η]^n and a concept class  such that no algorithm PAC-learns the class  over D 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 k-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 <Ref>, we state some preliminaries.
In <Ref>, we prove <Ref>, which is the classical setting and can be viewed as a warm-up to the quantum setting.
In <Ref>, we prove <Ref>, our main result.
Finally, in <Ref>, we show impossibility results including <Ref> and the failure of low-degree truncation in the standard Pauli basis.




 §.§ Related work


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 <cit.>, 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 <cit.>, it was proposed to study Pauli decompositions of Hermitian unitaries as the natural quantum analogue of Boolean functions. One notable follow-up work <cit.> 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 <cit.> for the non-Hermitian case). Recently, <cit.> considered the Pauli spectrum of the Choi representation of quantum channels and proved low-degree concentration for channels implemented by 𝖰𝖠𝖢^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 <cit.>. There have been two direct follow-up works to this paper which are somewhat orthogonal to the thrust of our contributions. The first <cit.> establishes refined versions of the so-called non-commutative Bohnenblust-Hille inequality which was developed and leveraged by <cit.> 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 <cit.> to <cit.> 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 <cit.> 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.



  
Classical low-degree learning.

The general technique of low-degree approximation in classical learning 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 <cit.>. Fourier-analytic techniques have been used to obtain new classical learning results for various concept classes like decision trees <cit.>, linear threshold functions <cit.>, Boolean formulas <cit.>, low-degree polynomials <cit.>, and more.

While Fourier analysis over biased distributions dates back to early work of Margulis and Russo <cit.>, it was first applied in a learning-theoretic context in <cit.>, extending the aforementioned result of <cit.>.




§ PRELIMINARIES





 §.§ Bloch sphere and Pauli covariance matrices



The Pauli matrices I, X, Y, Z 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.

[Pauli expansion of states]

Any single-qubit mixed state ρ can be written as

    ρ = 1/2(I + α_xX + α_yY + α_zZ)  ,

where α⃗∈^3, α⃗_2 ≤ 1, and X,Y,Z are the standard Pauli matrices:

    X = [ 0 1; 1 0 ]   Y = [  0 -i;  i  0 ]   Z=[  1  0;  0 -1 ] .

The set of all such α⃗ of unit norm is the Bloch sphere.

Any single-qubit distribution D can be viewed as a distribution over the Bloch sphere.
We use _D[ρ] ∈^2 × 2 and μ⃗∈^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^n Pauli observables {I,X,Y,Z}^⊗ n, which form a basis for the space of 2^n × 2^n Hermitian matrices:

[Pauli expansion of observables]
Let  be an n-qubit observable. Then  can be written in the following form:

    = ∑_P ∈{I,X,Y,Z}^⊗ n(P) · P  ,

where (P) ≜( P) / 2^n. 



Next, we define the Pauli covariance and second moment matrices associated to any distribution D over the single-qubit Bloch sphere.

 
Let D be a distribution over the Bloch sphere.
We will associate with D the second moment matrix ∈^3× 3 and covariance matrix Σ∈^3× 3,
indexed by the non-identity Pauli components X, Y, and Z.
We define  such that _P,Q = _ρ∼ D[(Pρ)(Qρ)],
and Σ such that Σ_P,Q = _ρ∼ D[(Pρ)(Qρ) - (P[ρ])(Q[ρ])].


The following is a consequence of <Ref>:

For any distribution over the Bloch sphere, the Pauli second moment matrix  satisfies () = 1.





 §.§ Access model


In this paper we consider the following, standard access model, see e.g. <cit.>. We assume that we can interact with the unknown channel  by preparing any input state, passing it through , and performing a measurement on the output. Additionally, we are given access to training examples from some distribution = D^⊗ n over product states, and their corresponding classical descriptions.
Because product states over n qubits can be efficiently represent efficiently using O(n) 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 ρ = ⊗^n_i=1|ψ_i⟩ sampled from , the classical description can be given by their 1-qubit Pauli expectation values: (P |ψ_i ⟩⟨ψ_i |) for all i∈[n] ranging over each qubit and P∈{X,Y,Z}.

Given these classical samples from  and the ability to query , the learning goal is to produce a hypothesis f' which takes as input the classical description of a product state ρ and outputs an estimate for ([ρ]). Formally, we want this hypothesis to have small test loss in the sense that _ρ∼[(([ρ]) - (f'(ρ)))^2] ≤ϵ with probability at least 1 - δ over the randomness of the learning algorithm and the training examples from .




 §.§ Generalization bounds for learning







For our learning protocol, we will use the following elementary results about linear and polynomial regression:

[Rademacher complexity generalization bound <cit.>]
Let  be the class of bounded linear functions [-1,1]^d→[-B,B], and let ℓ be a loss function with Lipschitz constant L and a uniform upper bound of c. 
With probability 1-δ over the choice of a training set S of size m drawn i.i.d. from distribution ,

    _(x,y) ∼[ℓ(f(x),y)] ≤_(x,y) ∼ S[ℓ(f(x),y)] + 4LB√(d/m) + 2c √(log 1/δ/2m) .











Let f be a function that is -close to a degree-≤ d polynomial f^⋆:

    _x ∼[(f(x)-f^⋆(x))^2] ≤.


Then linear regression over the set of degree-d polynomials with coefficients in [-1,1] has time and sample complexity (n^d, log 1/) ·log 1/δ and finds h such that 

    _x ∼[(f(x)-h(x))^2] ≤ O()

with probability 1-δ.




§ WARM-UP: THE CLASSICAL CASE


In this section we will prove <Ref>, which is a special case of <Ref> where the distribution is classical, i.e. supported only on the Z component. 

The key ingredient in the proof is to show that for any function which is L^2-integrable with respect to a product distribution over [-(1-η),1-η]^n 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 D 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 D^⊗ n has a basis whose degree-d components are scaled by (1-η)^d.
This, combined with the assumption that the function is bounded on the hypercube, allows us to conclude that the contribution of the degree-d component to the variance of f over D^⊗ n is at most (1-η)^2d.

We prove this structural result in <Ref> and conclude the proof of <Ref> in <Ref>.



 §.§ Existence of low-degree approximation



We first review some basic facts about classical biased Fourier analysis. For a more extensive overview of this topic, we refer the reader to <cit.>. 

Given a measure μ, we let L^2(μ) denote the space of L^2-integrable functions with respect to μ.

[Biased Fourier basis]

Let D be a distribution over  with mean μ∈ (-1,1). Given f∈ L_2(D^⊗ n), the μ-biased Fourier expansion of f: ^n → is 

    f(x) = ∑_S ⊆ [n]f̂(S) ϕ_S(x)  ,

where ϕ_S(x) = ∏_i ∈ Sx_i - μ/√(1-μ^2) and 
f̂(S) = _x∼ D^⊗ n[ϕ_S(x)f(x)].


The functions ϕ_S provide an orthonormal basis for the space of functions L^2(D^⊗ n), where D is the distribution over {1, -1} with mean μ. We can naturally extend this to arbitrary product distributions over ^d as follows:






[Basis for an arbitrary product distribution]

Let D be a distribution over  with mean μ and variance σ^2 > 0.
Then {1, x - μ/σ} is an orthonormal basis for L^2(D),
and thus {1, x - μ/σ}^⊗ n is an orthonormal basis for L^2(D^⊗ n).


The orthonormality of the basis immediately implies the following simple fact:

[Parseval’s Theorem]


For any function f expressed as f(x) = ∑_S ⊆ [n]f(S) ϕ_S(x), we have
_x∼ D^⊗ n[f(x)^2] = ∑_S⊆ [n]f(S)^2.


The following is the crucial structural result in the classical setting that gives rise to <Ref>. Roughly speaking, it ensures that for the “concentrated product distributions” D considered therein, any bounded multilinear function has decaying coefficients when expanded in the orthonormal basis for L^2(D^⊗ n).



Let f:[-1,1]^n → [-1,1] be a multilinear function and let D be a distribution over  with mean μ and variance σ^2 < 1-μ^2.
Then there exists a function f^≤ d such that 

    _x ∼ D^⊗ n[(f(x) - f^≤ d(x))^2] ≤σ^2/1-μ^2^d.




Let f be expressed in the basis B_hypercube = {1, x - μ/√(1-μ^2)}^⊗ n; i.e. as 

    f(x) = ∑_S ⊆ [n]f(S)ψ_S(x)

where ψ_S = ∏_i ∈ Sx_i - μ/√(1-μ^2).
Note that {ψ_S}_S⊆ [n] is orthonormal with respect to the distribution D^⊗ n where D is supported on {±1} with mean μ.
Since |f(x)| ≤ 1 for x ∈ [-1,1]^n, it follows that

    1 ≥_x∼D^⊗ n[f(x)^2] = ∑_S ⊆ [n]f(S)^2

via <Ref>.

Now, consider the basis ϕ_S ∏_i∈ Sx_i-μ/σ = (√(1-μ^2)/σ)^|S|·ψ_S.
By <Ref>, we know that {ϕ_S}_S⊆[n] is orthonormal with respect to D.

Let f^>d∑_|S| > df(S)ψ_S.
We have

    _x ∼ D^⊗ n[f^>d(x)^2]    = _x ∼ D^⊗ n[(∑_|S| > df(S)ψ_S)^2] 
       = _x ∼ D^⊗ n[(∑_|S| > df(S) (σ/√(1-μ^2))^|S|ϕ_S)^2 ] 
       = ∑_|S|>df(S)^2 (σ^2/1-μ^2)^|S|
       ≤(σ^2/1-μ^2)^d∑_|S|>df(S)^2  ,

again using <Ref>.
Since ∑_Sf(S)^2 ≤ 1,









we have

    _x ∼ D^⊗ n[(f(x) - f^≤ d(x))^2] ≤(σ^2/1-μ^2)^d

as desired.




 §.§ Sample complexity and error analysis



In light of <Ref>, the proof of <Ref> is straightforward given the following elementary fact:

[Bernoulli maximizes variance]

    Let D be a distribution over the interval [-(1-η), 1-η] with mean μ.
    Then _x ∼ D(x) ≤ (1-η)^2(1-μ^2).




We can now conclude the proof of <Ref>:


By <Ref>, we have _D(x) ≤ (1-η)^2(1-μ^2).
Then <Ref> gives us a degree-d approximation f^≤ d to f such that

    _x ∼ D^⊗ n[(f(x)-f^≤ d(x))^2] ≤ (1 -η)^2d.

Taking d log(1/)/log(1/(1-η))
gives an approximation with error ≤.
Then by <Ref>, linear regression on the space of polynomials of degree log(1/)/log(1/(1-η)) finds an O()-error hypothesis in 
n^O(log(1/)/log(1/(1-η)))·log (1/δ) time and samples.



In the classical setting linear regression is not required, 
as we can estimate the mean, and the coefficients satisfy 

    f̂(S) = _x ∼ D^⊗ n [f(x) ϕ_S(x)]  ,

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.







§ LEARNING AN UNKNOWN QUANTUM CHANNEL



In this section we will prove <Ref>.
First we will show that under any product distribution with second moment  such that _𝗈𝗉≤ 1-η for some η∈ (0,1),
every observable has a low-degree approximation.
A distribution has _𝗈𝗉 = 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 <Ref>, because 
there is not necessarily an orthonormal basis for our product distribution D^⊗ n that is a “stretched” basis for some other distribution over the Bloch sphere.

Instead, we compare the variance of the observable under D^⊗ n to the quantity _ρ∼ D^⊗ n[(^2 ρ)].
This allows us to use the boundedness of  to derive bounds for the contribution of the degree-d part to the variance of  under D^⊗ n.
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 D^⊗ n.



Let D be a distribution over the Bloch sphere.
Let U^† A U be the eigendecomposition of ρ = _D[ρ]. Let
    , ,  := U^† X U, U^† Y U, U^† Z U - (ρ U^† Z U) I/√(1 - (ρ U^† Z U)^2).
    
    Let B = {I, , , }^⊗ n.
    The degree of P ∈ B is the number of non-identity elements in the product. The degree of a linear combination ∑_P∈ Bα_P P of elements in B is the largest degree of P ∈ B such that α_P ≠ 0.


The fact that the degree is defined for any observable (which is equivalent to X̃, Ỹ, Z̃ forming a basis of the space of operators) is the content of <Ref>. The existence of low-degree approximation is guaranteed by the following lemma.


    
Let  be a bounded n-qubit observable and 
let D be a distribution over the Bloch sphere with mean μ⃗ and Pauli second moment matrix  such that ≤ 1-η for some η∈ (0,1).
Then there exists a degree-d observable ^≤ d and a constant η' ∈ (0,1) such that 

    _ρ∼ D^⊗ n [((ρ) - (^≤ dρ))^2] ≤ (1-η')^d,

where η' is a function of η.


Once <Ref> is established, <Ref> follows readily from an application of <Ref>.




Let 1-η be a known upper bound on _𝗈𝗉.
We assume the access model of <Ref>, where we get a set S of examples [(Pρ)] for 1-local P.
Our algorithm is as follows:

    
  * Compute η' as in the last line of <Ref>. Let d  O(log(1/)/log(1/(1-η')).
    
  * Draw a set S of size n^d·log (1/δ), and initialize S' to be empty.
    
  * For each x ∈ S, prepare a set T of log(|S| + 1/^2 + 1/δ) copies of the state ρ that matches the 1-local expectations of x. Let est(([ρ])) be the estimate of ([ρ]), where for each ρ∈ T, we measure with respect to {^†[], I - ^†[]}, and est(([ρ])) is the empirical probability of measuring the first outcome.
    
    Add 
    
    (x^⊗log(1/)/log(1/(1-η')), est(([ρ])))

    to the set S'.
    
  * Run linear regression on S' and output the returned hypothesis h.

By Hoeffding's inequality, each estimate of ([ρ]) is within  of its expectation with probability 1-exp(-Ω(|T| ^2)).
By union bound over the |S| estimates,
with probability ≥ 1 - δ, all estimates are within  of ([ρ]).

The time, sample, and error bounds follow from <Ref>, which guarantees that ^†[] is -close to some degree-d polynomial. This implies
the labels of our sample set are 2-close to such a polynomial.
The dimension of the linear regression problem is ≤ nd · 3^d ≤ n^O(d), as there are 3 choices for each non-identity component.


Then by <Ref>, linear regression has time and sample complexity 

    n^O(log(1/)/log(1/(1-η')))·log (1/δ)

and outputs a hypothesis h such that

    _ρ∼ D^⊗ n [(([ρ]) - (hρ))^2]    ≤ O() .




The proof of <Ref> follows from three technical Lemmas. The first gives, for any product distribution over n-qubit states, a (non-orthogonal) decomposition of any observable into operators which are centered and bounded in variance with respect to that distribution.



Let D be a distribution over the Bloch sphere.
Let U^† A U be the eigendecomposition of ρ = _D[ρ], and let 
, ,  := U^† X U, U^† Y U, U^† Z U - (ρ U^† Z U) I/√(1 - (ρ U^† Z U)^2).
Then {I, , , } is a basis for the set of 2× 2 unitary Hermitian matrices, and thus every n-qubit observable  can be written as 

    = ∑_P ∈ B(P) P

for B = {I, , , }^⊗ n.
Furthermore, each non-identity P ∈ B satisfies _ρ∼ D^⊗ n[(Pρ)] = 0 and _ρ∼ D^⊗ n[(Pρ)^2] ≤ 1.



It is clear that {I, , , } is linearly independent and thus B forms a basis for any n-qubit observable.
Note that (Pρ) = ∏_i=1^n (P_i ρ_i) as ρ is a product state, so we can restrict the analysis to single qubit states drawn from D.

For P = or , it is clear that _ρ∼ D[(Pρ)] = 0 and _ρ∼ D[(Pρ)^2] = 1.
For , we have

    _ρ∼ D[(ρ)]    = [ (ρ U^† Z U)] - (ρ U^† Z U)/√(1-(ρ U^† Z U)^2) = 0  .

Moreover,

    _ρ∼ D[(Z̃ρ)^2]    = [(ρ U^† Z U)]/1-(ρ U^† Z U)^2≤ 1  ,

because [(ρ U^† Z U)] + [(ρ U^† Z U)]^2 =  [(ρ U^† Z U)^2] ≤ 1.



Going forward, we will assume w.l.o.g. that the mean of the distribution _D[ρ] is diagonal because we can always transform the basis according to U.
Thus, we will assume that the mean state _D[ρ] = 1/2(I+μ Z) and the mean Bloch vector μ⃗ = (0,0,μ) for some μ∈ [-1,1],


We next prove two important components required in the proof of <Ref>.
The first lemma gives an eigenvalue lower bound on a Hermitian matrix that arises when we expand (^2 [ρ]).

 
Let μ∈ (-1,1) and

    M = [   1  iμ; -iμ   1 ].

Then λ_min(Re(M^⊗ k)) ≥ (1-μ^2)^k/2 for any k∈.


Note that M = I + μ Y and Y is imaginary. Thus,

    Re((I + μ Y)^⊗ k) = ∑_P∈{I,Y}^k: |P|  evenμ^|P|⊗_i=1^k P_i  .

Note also that the eigenvalues of the above remain the same if we replace the Y's with Z's.
Thus, the eigenvalues of the above can be indexed by x∈{±1}^k, and can be expressed as follows:

    λ(x) = ∑_S⊆ [k]: |S|  evenμ^|S| x^S  .


Let f: ^k → be the function f(x) = ∏_i=1^k (1+x_i) = ∑_S⊆[k] x^S. Then, we have λ(x) = 1/2(f(μ x) + f(-μ x)).
By the AM-GM inequality, 

    λ(x)    ≥√(f(μ x) f(-μ x)) = ∏_i=1^k √((1+μ x_i) (1-μ x_i)) = (1-μ^2)^k/2 .
































The next lemma gives an upper bound on the Pauli covariance matrix Σ (recall <Ref>) scaled by a specific diagonal matrix.



Let D be a distribution over the Bloch sphere with mean μ⃗ = (0,0,μ), Pauli second moment matrix  such that _𝗈𝗉≤ 1-η for some η∈ (0,1), and Pauli covariance matrix Σ.

Let = ((1-μ^2)^-1/4,(1-μ^2)^-1/4,(1-μ^2)^-1/2). 
Then there exists η' ∈ (0,1) such that Σ_𝗈𝗉≤ 1-η', where η' is a function of η.



We split into two cases based on whether μ^2 ≥η/2.
The case where μ^2 < η/2

is the simpler case: since Σ_ op≤_ op≤ 1-η and _ op^2 ≤ (1-μ^2)^-1, we have 

    Σ_ op≤Σ_ op/1 - μ^2≤1 - η/1 - μ^2≤1-η/1-η/2≤ 1-η/2  .


Now we consider the case where the inequality is not satisfied.
We note that Σ =  - μ⃗μ⃗^⊤ and μ⃗ = (0,0,μ), thus we have that
Σ has the following block structure:

    Σ = [ _2 × 2/√(1 - μ^2)                 b;               b^† _zz - μ^2/1 - μ^2 ] ,

where _2× 2 is the top left 2 × 2 block of , _zz is the bottom right entry, and b 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 [   A   b; b^†   c ]≽ 0 has operator norm at most A_ op + c.
We thus know that 

    Σ_ op≤_zz - μ^2/1 - μ^2 + _2 × 2_ op/√(1 - μ^2)≤_zz - μ^2/1 - μ^2 + (_2× 2)/√(1 - μ^2)≤_zz - μ^2/1 - μ^2 + 1 - _zz/√(1 - μ^2) ,

where we use the fact that 1 = () = (_2× 2) + _zz.
Then we have 

    Σ_ op   ≤_zz - μ^2/1 - μ^2 + 1 - _zz/√(1 - μ^2)
       = _zz(1/1-μ^2 - 1/√(1-μ^2)) + 1/√(1 - μ^2) - μ^2/1 - μ^2
       ≤ (1-η)(1/1-μ^2 - 1/√(1-μ^2)) + 1/√(1 - μ^2) - μ^2/1 - μ^2
       = 1 - η(1/1-μ^2-1/√(1-μ^2)) 
       ≤ 1 - η1 -√(1-η/2)/1-η/2 .

The third line is by the fact that _zz≤_𝗈𝗉≤ 1 - η,
and the last inequality is because the function 1/1-μ^2 - 1/√(1-μ^2) is 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 

    η'    ≥min{η1 -√(1-η/2)/1-η/2, η/2 } > 0  .




    As mentioned in <Ref>, our techniques can be extended to learn not just the mapping ρ↦(O[ρ]), but also the joint mapping (O,ρ)↦(O[ρ]). 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,…,ρ_N from , query the channel on each them, and for each of the output states [ρ_j], 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 [ρ_j], a randomized Pauli measurement will result in a stabilizer state |ψ^(j)⟩ = ⊗^n_i=1|s^(j)_i⟩∈{|0⟩,|1⟩,|+⟩,|-⟩,|y+⟩,|y-⟩}^⊗ n, and the expectation of ⊗^n_i=1 (3|s^(j)_i⟩⟨s^(j)_i| - I) is [ρ_j]. The classical description of the channel is given by the O(log(1/ϵ))-body reduced density matrices of the input states ρ_1,…,ρ_N, together with the classical encodings of |ψ^(1)⟩,…,|ψ^(N)⟩.

    Given an observable O, we can then perform regression to predict the labels (O⊗^n_i=1(3|s^(j)_i⟩⟨s^(j)_i|-I)) given the features {(Pρ_j)}_|P| ≤ O(log (1/ϵ)). Because the labels are unbiased estimates of (O[ρ_j]), the resulting estimator will be an accurate approximation to ρ↦(O[ρ]) for ρ∼. 
    
    In this work, we do not belabor these details as they are already investigated in depth in <cit.>. Instead, we focus on the single observable case as this is where the main difficulty lies in extending the results of <cit.> to more general input distributions.


Now we prove <Ref> which shows the existence of a low-degree approximator.


Assume w.l.o.g., as in <Ref>, that _D[ρ] = 1/2(I + μ Z) and μ⃗ = (0,0,μ).
Let  be expressed in the basis B = {I, X, Y, Z - μ I/√(1-μ^2)}^⊗ n as in <Ref>.
For a subset S ⊆ [n], we will denote by {P ∈ B: P ∼ S} the set of basis elements with non-identity components at indices in S and
identity components at indices in S.
We will also denote by |P| the number of non-identity components in P.


Let ^> d∑_|S| > d∑_P ∼ S(S)P.
We will show that ^>d satisfies _ρ∼ D^⊗ n[(^> dρ)^2] ≤ (1 - η')^d where η' ∈ (0,1) depends on η.

We first note a bound on the related quantity _ρ∼ D^⊗ n [(^2 ρ)]. 
Because _ op≤ 1 and ([ρ]) ≤ 1, (^2 [ρ]) ≤ 1 as well.
We will expand this quantity as a quadratic form.

    _ρ∼ D^⊗ n [(^2 ρ)]    = ∑_P,Q ∈ B(P) (Q)(PQ [ρ]) 
       =  ∑_P,Q ∈ B(P) (Q)(⊗_i=1^n P_iQ_i [ρ_i]) 
       =  ∑_P,Q ∈ B(P) (Q)∏_i=1^n( P_iQ_i [ρ_i])  .

Note that the product is 0 whenever exactly one of P_i, Q_i is I for any i ∈ [n] (as ((Z-μ I)· (I+μ Z)) = 0).
Therefore, we can partition the terms into groups that share a subset of identity variables: 

    _ρ∼ D^⊗ n [(^2 ρ)]    = ∑_S ⊆ [n]∑_P,Q ∼ S(P) (Q)∏_i=1^n( P_iQ_i [ρ_i]) 
       = ∑_S ⊆ [n]_S^† M^⊗ |S|_S  ,

where _S is the vector of coefficients for the set {P: P ∼ S}, and M is the 3 × 3 matrix such that M_P,Q = ( PQ _D[ρ]):

    M = [   1  iμ   0; -iμ   1   0;   0   0   1 ] .

Here, the entry iμ arises because XY = iZ and (XY ·1/2(I+μ Z)) = iμ.
Since M is positive semidefinite,
we have _S^† M^⊗ |S|_S ≥ 0 for all S,
and therefore we have 

    1 ≥_ρ∼ D^⊗ n [(^2 ρ)]
        = ∑_S ⊆ [n]_S^† M^⊗ |S|_S
        ≥∑_S ⊆ [n]:|S| > d_S^† M^⊗ |S|_S  .

Now we will write the desired quantity _ρ∼ D^⊗ n [(^> dρ)^2] as a quadratic form as well:

    _ρ∼ D^⊗ n [(^> dρ)^2]    = ∑_P,Q ⊆ B: |P|,|Q|>d(P) (Q) ∏_i ∈ [n][(P_i ρ) (Q_i ρ)]  .


Similarly, the product is 0 whenever exactly one of P_i and Q_i is identity (by the guarantee of <Ref> that [(P_iρ)] = 0 for P_i ≠ I), so we can make the same partition:


    _ρ∼ D^⊗ n [(^>dρ)^2]    = ∑_|S|>d_S^† M'^⊗ |S| .


Here M' is 3 × 3 matrix such that M'_PQ = _ρ∼ D[(Pρ)(Qρ)] for P,Q ∈{X,Y,Z-μ I/√(1-μ^2)}; in other words, it is the second moment matrix of the non-identity elements of our biased Pauli basis.
Below, we show the entries of M' in terms of the Pauli covariance matrix Σ:


    M' = [            Σ_xx            Σ_xy Σ_xz/√(1 - μ^2);            Σ_xy            Σ_yy Σ_yz/√(1 - μ^2); Σ_xz/√(1 - μ^2) Σ_yz/√(1 - μ^2)    Σ_zz/1 - μ^2 ] .

Our aim is to bound M' in terms of M in order to show the existence of some η' ∈ (0,1) such that  

    [(^> dρ)^2] ≤ (1 - η')^d ·((^> d)^2 [ρ]) ≤ (1-η')^d.

Comparing Eq. (<ref>) and (<ref>),
it suffices to show that 

    (1 - η')^|S|_S^† M^⊗ |S|_S ≥_S^† M'^⊗ |S|_S

for all vectors _S.
Crucially, since the Pauli coefficients _S must be real, it suffices to prove that

    M'^⊗ |S|≼
        (1-η')^|S|·Re(M^⊗ |S|)  .





Let M_2× 2 be the top left 2 × 2 block in M, which is exactly the matrix in <Ref>.
From <Ref>, we have λ_min(Re(M_2× 2^⊗ |S|)) ≥ (1- μ^2)^ |S|/2.
By the block structure of M, it follows that Re(M^⊗ |S|) ≽(√(1-μ^2), √(1-μ^2), 1)^⊗ |S|.
Thus, we can establish Eq. (<ref>) by proving that

    M' ≼ (1-η') ·( √(1-μ^2), √(1-μ^2), 1 )  .



Now, note that M' can be written as Σ, where Σ is the covariance matrix of D and = (1,1, (1-μ^2)^-1/2).
Letting = ((1 - μ^2)^-1/4, (1 - μ^2)^-1/4, (1 - μ^2)^-1/2) (which is the diagonal matrix defined in <Ref>), we can see that Eq. (<ref>) is equivalent to

    M'_𝗈𝗉≤ 1-η',


By <Ref>, this is true by our assumption that _𝗈𝗉≤ 1-η.
This establishes Eq. (<ref>) and thus Eq. (<ref>), and from Eq. (<ref>) and (<ref>), we have

    1    ≥_ρ∼ D^⊗ n [(^2 ρ)]
        ≥∑_|S| > d_S^† M^⊗ |S|_S 
       ≥ (1-η')^-d∑_|S| > d_S^† M'^⊗ |S|_S 
       = (1-η')^-d_ρ∼ D^⊗ n[(^>dρ)^2]  .

Therefore,

    _ρ∼ D^⊗ n[((ρ) - (^≤ dρ))^2] ≤ (1-η')^d  .

Hence, we have obtained the claimed result.



 
    In the proof of <Ref>, we relate the quantity _ρ∼ D^⊗ n[(^>dρ)^2] that we wish to bound to the related quantity _ρ∼ D^⊗ n [(^2 ρ)], which is at most 1 since _ op≤ 1.
    Due to the choice of our biased Pauli basis B = {I,X,Y, Z-μ I/√(1-μ^2)}^⊗ n, we may write both quantities as sums of _S^† M'^⊗ |S|_S and _S^† M^⊗ |S|_S
    (see Eq. (<ref>) and (<ref>)).

    Suppose ρ is a product of different distributions where each qubit has mean Bloch vector μ⃗_i = (0,0,μ_i) (after rotation; see <Ref>) and second moment bounded by 1-η.
    We will instead use the basis B = ⊗_i=1^n {I,X,Y, Z-μ_i I/√(1-μ_i^2)}.
    One can easily see that the above quantities are essentially the same, with M^⊗ |S| replaced by ⊗_i∈ S M_i and similarly for M'.
    Then, the next steps in the proof (establishing Eq. (<ref>) and (<ref>)) are exactly the same.


















§ LOWER BOUNDS



In this section, we show lower bounds in the classical case, which automatically imply hardness in the quantum case.
In <Ref>, we prove <Ref>, which shows hardness of learning without the product distribution assumption in <Ref>.
In <Ref>, we show that truncating in the unbiased basis fails when the distribution is not mean zero.



 §.§ Lower bounds for learning non-product distributions



In this section, we prove <Ref>. We show that if  is an arbitrary distribution, then even if  is supported on [-(1-η), (1-η)]^n (i.e., in the interior of the hypercube), there is no learning algorithm.

Let C be a code over ^n of size 2^Θ(n) and distance n/4.
The following fact is standard.

 
    For any constant > 0, any learning algorithm that can learn an arbitrary function f: {±1}^n →{±1} over C to  error requires 2^Ω(n) queries.









    Let η = 0.1.
    We set the distribution  to be the uniform distribution over (1-η)· C, which is supported in [-(1-η), (1-η)]^n.
    Let f: {±1}^n →{±1} be an arbitrary function.
    Since the code C has distance n/4, we can without loss of generality assume that f(x') = f(x) whenever d(x,x') ≤ n/8.

    Suppose for contradiction that there is an algorithm that, with only 2^o(n) queries to f, outputs a function g: [-1,1]^n → such that _x ∼[(g(x) - f(x))^2] ≤.
    Let p  1-η/2, and let Ber(p) be the distribution where we have +1 with probability p and -1 otherwise.
    Then, for any x∈{±1}^n, we have f((1-η)x) = _z∼Ber(p)^⊗ n[f(x ∘ z)], where ∘ denotes entry-wise product.

    We claim that for any x∈ C, |_z∼Ber(p)^⊗ n[f(x ∘ z)] - f(x)| ≤ o_n(1).
    The number of -1 coordinates in z is distributed as a Bin(n,η/2).
    By the Chernoff bound, [Bin(n,η/2) ≥ (1+δ)1/2η n] ≤ e^-O(δ^2 η n) = o_n(1).
    In particular, for η = 0.1, we have that [Bin(n,η/2) ≥ n/8] ≤ o_n(1).
    Thus, with probability 1-o_n(1), d(x∘ z, x) < n/8, which means that f(x∘ z) = f(x).
    This proves that |f((1-η)x) -f(x)| ≤ o_n(1) for all x∈ C.

    Then, let h(x) = g((1-η)x).
    
    _x∈ C(h(x) - f(x))^2   = _x∈ C(g((1-η)x) - f(x))^2
       ≤_x∈ C(g((1-η)x) - f((1-η)x))^2 + o_n(1) 
       = _x∼(g(x) - f(x))^2 + o_n(1)  
       ≤ + o_n(1)  .

    This means that h is an -approximation of f over C.
    This contradicts <Ref> thus completing the proof.





 §.§ Lower bounds for unbiased degree truncation



In <Ref>, if the product distribution  over [-(1-η), 1-η]^n has mean zero, then directly truncating f with respect to the standard monomial basis at degree O(log(1/)/log(1/(1-η))) (independent of n) suffices.
However, in this section, we will show that without the mean zero assumption, even truncating at Ω(n) 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: f is the multilinear extension of the Boolean majority function, and  is supported on a single nonzero point (which is in fact a product distribution).



[<cit.>]

Let f be the multilinear extension of the Boolean majority function. 
Then the ℓ_2 Fourier weight on terms of degree k is Θ(k^-3/2).


The following is a well-known fact in approximation theory.

[Chebyshev extremal polynomial inequality <cit.>]

    Let p be a degree-d univariate polynomial with leading coefficient 1.
    Then, max_x∈[-1,1] |p(x)| ≥ 2^-d+1.



    Let f: {±1}^n →{±1} be the majority function extended to the domain [-1,1]^n.
    Let 0 < a < b < 1 be fixed constants.
    Then, there exist δδ(a,b) ∈ (0,1) and t^*∈ [a,b] such that the degree-δ n truncation f^≤δ n has |f^≤δ n(t^* ·1⃗)| ≥ω_n(1).


    
    
    
    
    
    
    
    
    
    Let g(t)  f^≤ d(t·1⃗), which is a univariate polynomial of degree d, and consider the shifted polynomial g(t) = g(b-a/2t + a+b/2).
    
    The leading coefficient of g, denoted c_d, is c_d (b-a/2)^d, where c_d is the leading coefficient of g.
    Since g(t) = f^≤ d(t·1⃗), we have c_d = ∑_S: |S|=df(S).
    For the majority function, <Ref> implies that ndf(S)^2 = Θ(d^-3/2) for all S of size d, thus
    
    |c_d| = b-a/2^d nd^1/2Θ(d^-3/4)  .

    Then, by <Ref>, there must be a s^*∈[-1,1] such that
    
    |g(s^*)| ≥ 2^-d+1·b-a/2^d nd^1/2Θ(d^-3/4)  .

    If d = δ n, then nd≥ (1/δ)^d = e^dlog(1/δ).
    Thus, given 0 < a < b < 1, there exists a δ∈ (0,1) such that the above is exp(Ω(d)).
    Thus, there exists a t^*∈ [a,b] such that |f^≤ d(t^* ·1⃗)| ≥ω_n(1).






§ ACKNOWLEDGMENTS


SC and HH would like to thank Ryan O'Donnell for a helpful discussion at an early stage of this project. Much of this work was completed while JD and JL were interns at Microsoft Research.

alpha


