domain: phys sdv sdv.aen

text:
Jeanne Kergomard

Frédéric Carrière

Maeva Subileau

Lauriane Chonchon

Gilles Paboeuf

Nathalie Barouh

Claire Bourlieu-Lacanal
email: claire.bourlieu-lacanal@inrae.fr

Véronique Vié
email: veronique.vie@univ-rennes.fr

Journées Chevreul

Claire Bourlieu

Interfacial adsorption and lipolysis behavior of gPLRP2 onto natural lipid membrane extracts from microalgae Chlorella vulgaris, walnuts, and almonds

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Results

Results

Results

Conclusion

The organisation of lipid extracts was observed by AFM and showed phase separation related to the FA composition. The interaction with the gPLRP2 was followed by ellipsometry and tensiometry, both signals allow to discriminate between adsorption, adsorption and insertion, adsorption and digestion. The lipolytic activity on galactolipids is clearly observed for the chlorella vulgaris extract.

  Photosynthetic plant membranes


Sungwoo Choi

Brigitte D'andr Éa-Novel

Michel Fliess

Hugues Mounier

Jorge Villagra

Model-free control of automotive engine and brake for Stop-and-Go scenarios

Keywords: Stop-and-Go, model-free control, inteligent PID controllers, numerical differentiation, robustness

In this paper we propose a complete strategy for the longitudinal control of automotive vehicles in Stop-and-Go situations. Firstly, a upper level grey-box torque control is proposed to compensate for neglected dynamics at chassis level (due for example to road slopes, aerodynamic forces, rolling resistance forces, etc.). Secondly, to obtain the desired torque, we have considered a model-free approach to elaborate the suitable low level engine or braking torque. Convincing simulation results are presented to validate our method.

I. INTRODUCTION

Driving assistance systems like Adaptive Cruise Control (ACC) and Stop-and-Go have been extensively studied in recent years [START_REF] Vahidi | Research advances in intelligent collision avoidance and adaptive cruise control[END_REF]. The former is devoted to inter-distance control in highways where the vehicle velocity remains quasi constant, whereas the latter is appropriate for vehicles driving in towns with frequent and sometimes hard stops and accelerations. The constraints of these two situations are quite different in terms of comfort, so they have often been treated as two distinct approaches. The authors of [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF] propose a unique non-linear reference model and controller for both ACC and Stop-and-Go scenarios. However, their feedback terms are not sufficiently robust to tackle external disturbances such as road characteristics and aerodynamic forces. A grey-box control strategy was therefore proposed in [START_REF] Villagra | Robust grey-box closed-loop stop-and-go control[END_REF] in order to compensate all the neglected dynamics.

In [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF] the authors suppose that the reference acceleration generated by the model can be instantaneously applied to the following vehicle. However, the corresponding braking and accelerating torques are often difficult to obtain because of the uncertainty of the engine/brake models. Different approaches have been proposed to handle the nonlinear dynamics of engine and brake: input/output linearization [START_REF] Swaroop | Comparison of spacing and headway control laws for automatically controlled vehicles[END_REF], [START_REF] Raza | Modeling and control design for a computer-controlled brake system[END_REF], fuzzy logic ( [START_REF] Naranjo | ACC+Stop&Go Maneuvers With Throttle and Brake Fuzzy Control[END_REF], [START_REF] Germann | Nonlinear distance and cruise control for passenger cars[END_REF]) and sliding mode ( [START_REF] Gerdes | Vehicle speed and spacing control via coordinated throttle and brake actuation[END_REF], [START_REF] Yi | Nonlinear Brake Control for Vehicle CW/CA Systems[END_REF], [START_REF] Nouvelière | Experimental vehicle longitudinal control using a second order sliding mode technique[END_REF]) have been proposed for engine and brake control.

S. Choi Hugues.Mounier@ief.u-psud.fr J. Villagra is at Departamento de Ingenieria de Sistemas y Automatica, Universidad Carlos III, 28911 Leganes (Madrid), Spain. jvillagr@ing.uc3m.es Most of these methods use fixed gains, whereas the model parameters vary during the lifetime of the vehicle. In addition to this, off-line identification for an engine/brake modeling is often complex. We here propose a so called model-free control approach developed in [START_REF] Fliess | Commande sans modèle et commande à modèle restreint[END_REF], [START_REF] Fliess | Model-free control and intelligent PID controllers: towards a possible trivialization of nonlinear control?[END_REF], which is inherently robust to the very poorly known engine and brake dynamics. 1The remainder of the paper is organized as follows. The general control scheme is presented in Section II. In Section III we explain the model-free control setting. Section IV presents upper level control with the compensation of unmodeled dynamics using the so-called intelligent PID controllers [START_REF] Fliess | Commande sans modèle et commande à modèle restreint[END_REF], [START_REF] Fliess | Model-free control and intelligent PID controllers: towards a possible trivialization of nonlinear control?[END_REF]. Section V is devoted to lower level engine/brake control and to associated simulations. A robustness study will be presented in Section VI.

II. CONTROL SCHEME

The whole control scheme is graphically summarized in Figure 1. The longitudinal control system architecture for the Stop-and-Go is designed to be hierarchical, with an upper level controller and a lower level controller. The upper level controller determines the desired torque for the vehicle using longitudinal velocities, wheel angular velocities and inter-distance measurements by radar. An intelligent PID compensation is developed at this level to deal with the chassis dynamics uncertainties. The lower level controller determines the throttle angle input or the braking pressure input required to track the desired torque generated by the upper level controller. For the model-free control design, measured engine and brake torques are required as an input to this level. For the simulation, a 14 degree-of-freedom vehicle representation with tire models as well as a radar model have been used.

III. MODEL-FREE CONTROL 2

We only assume that the plant behavior is well approximated in its operational range by a system of ordinary differential equations. The input/output equation looks like for a SISO system: E(t, y, ẏ, . . . , y (ι) , u, u, . . . , u (κ) ) = 0 where E is a sufficiently smooth function of its arguments. Assume that for some integer n, 0 < n ≤ ι, ∂ E ∂ y (n) ≡ 0. The implicit function theorem yields then locally y (n) = E(t, y, ẏ, . . . , y (n-1) , y (n+1) , . . . , y (ι) , u, u, . . . , u (κ) )

This equation becomes by setting E = F + αu:

y (n) = F + αu (1)
where

• α ∈ R is a non-physical constant parameter, such that F and αu are of the same magnitude; • the numerical value of F, which contains the whole "structural information", is determined thanks to the knowledge of u, α, and of the estimate of the derivative y (n) (see remark 1 below).

In all the numerous known examples it was possible to set n = 1 or 2. If n = 2, we close the loop via the intelligent PID controller, or i-PID controller,

u = - F α + ÿ * α + K P e + K I e + K D ė (2)
where

• y * is the output reference trajectory, which is determined via the rules of flatness-based control; • e = yy * is the tracking error; • K P , K I , K D are the usual tuning gains.

Remark 1:

The numerical derivation of noisy signals, which is necessary to implement the feedback loop (2) is borrowed from [START_REF] Fliess | Non-linear estimation is easy[END_REF] and already plays an important role in model-based control (see [START_REF] Mboup | Numerical differentiation with annihiators in noisy environment[END_REF] for further important theoretical developments, and, also, [START_REF] Choi | Robust Algebraic Approach for Radar Signal Processing: Noise filtering, time-derivative estimation and perturbation estimation[END_REF] for some applications). This approach obviously necessitates derivatives estimation 2 See [START_REF] Fliess | Commande sans modèle et commande à modèle restreint[END_REF], [START_REF] Fliess | Model-free control and intelligent PID controllers: towards a possible trivialization of nonlinear control?[END_REF] for more details. of noisy signals. The estimate of the 1 st order derivative of a noisy measured signal y can be expressed as follows:

ŷ = - 3! T 3 T 0 (T -2t)y(t)dt, (3)
where [0,T] is a quite "short" time window. Moreover, a filtered version of the noisy measured signal y yields:

ŷ = 2! T 2 T 0 (2T -3t)y(t)dt. (4)
The global structure of our scheme is the following:

-the upper level uses an i-PD controller of the form (2) to handle external disturbances (road slope, aerodynamic forces, ... see ( 12)). Equation (3) will also be used to estimate the time derivative of the inter-distance d which is necessary to obtain the leader vehicle velocity. -The lower level uses the other i-PD controllers (20) and ( 22) to handle the unknown engine and brake dynamics.

IV. UPPER LEVEL CONTROLLER

First of all, a short summary of the control law for the upper level controller is given and then the resulting engine/brake torque is elaborated.

A. Feedforward control

An inter-distance reference model proposed by [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF] will act as a feedforward control law for the upper level controller. The inter-distance reference model describes a virtual vehicle dynamics which is positioned at a distance d r (reference distance) from the leader vehicle. The reference model dynamics is given by dr = ẍlẍr f [START_REF] Fliess | Correcteurs proportionnels-intégraux généralisés[END_REF] where ẍl is the leader vehicle acceleration and the follower vehicle acceleration

ẍr f = u r (d r , ḋr ) (6)
is a nonlinear function of the inter-distance reference d r and of its time derivative ḋr . Introducing d d 0 -d r in [START_REF] Gerdes | Vehicle speed and spacing control via coordinated throttle and brake actuation[END_REF], where d 0 is the safe nominal inter-distance, the control problem consists in finding a suitable control when d 0 so that all the solutions of the dynamics (5) fulfill the following comfort and safety constraints:

• d r d c , with d c the minimal inter-distance, will guarantee collision avoidance.

• ẍr B max , where B max is the maximum attainable longitudinal acceleration, depending on the driver, the vehicle and the infrastructure, will have an effect on security and comfort.

• ... x r
J max , where J max is a bound on the driver desired jerk, which directly affects the comfort performances. The work by [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF] proposed to use a nonlinear damper model: The previous equation can be analytically integrated and expressed in terms of d r , assuming that ẋl (0) = 0:

ḋr = c 2 (d 0 -d r ) 2 + ẋl (t) -β , β = ẋr f (0) + c 2 (d 0 -d r (0)) 2 .
(7) From ( 6), the feedforward control law is then obtained:

u r = ẍr = c|d 0 -d r | ḋr (8)
where the reference inter-distance evolution comes from numerical integration of [START_REF] Germann | Nonlinear distance and cruise control for passenger cars[END_REF]. Note that the parameters c and d 0 are algebraic functions of comfort and safety parameters (see [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF] for details).

Remark 2: The leader vehicle velocity ẋl is estimated using ẋl = ḋ + ẋ f where ḋ is estimated by (3) from the measured distance d.

B. Upper level closed loop control

The feedforward control should be corrected with feedback terms which can compensate errors induced by measurement noises and external disturbances. We use an algebraic PD compensator 3 , so that the corrected acceleration of (8) is given by:

u(= γ x ) = u r + K P e + K D ė (9)
where e represents the error between the real inter-distance and the reference inter-distance ( e = dd r ), and its time derivative will be estimated using (3).

C. Engine/Brake torque generation

The wheel rotation dynamics can be written as follows:

I ω = -rF x + τ e a -τ b a ( 10
)
where I is the rotation inertia moment, ω is the wheel angular velocity, r is the tire radius, F x is the longitudinal tire force, τ e a is the applied engine torque, and τ b a is the applied brake torque, both of them applied at the wheel center. The sum of the 4 wheels rotation dynamics equations and of the vehicle longitudinal dynamic equation Mγ x = ∑ 4 i=1 F x i yields

τ g = I 4 ∑ i=1 ωi + rMγ x ( 11
)
where

τ g = τ e -τ b = ∑ 4 i=1 (τ e a i -τ b a i
) is the generalized total torque, M is the total weight of vehicle and γ x is the longitudinal acceleration. ω is computed once more with (3) from the measured wheel angular velocities.

Our final reference torque τ g can be obtained using (11) where γ x = u is given by [START_REF] Martinez | A Safe Longitudinal Control for Adaptive Cruise Control and Stop-and-Go Scenarios[END_REF], and an intelligent PID compensation is applied to handle unmodeled external disturbances γ 0 (due to road slope, rolling resistance, wind, etc.): 4

3 See [START_REF] Fliess | Correcteurs proportionnels-intégraux généralisés[END_REF] for details. 4 See [START_REF] Villagra | Robust grey-box closed-loop stop-and-go control[END_REF] for details.

τ g = I 4 ∑ i=1 ωi + rM(u -γ0 ). (12)
V. LOW LEVEL CONTROLLER

In the lower level controller, the throttle angle input and the brake pressure input are calculated in order to track the desired torque determined by the upper level controller. For this study, an engine model and a brake model have been used.

A. Engine model

The engine model we use in this study was derived by Powell et al. [START_REF] Powel | Optimal idle speed control of an automotive engine[END_REF] from steady-state engine maps. The model represents a 1.6 liter, 4-cylinder fuel injected engine. The dynamic equations of the model are:

Ṗad = k p ( ṁac e -ṁac s ) (13) ẇm = k n (T m -T ch ) ṁac e = (1 + a 1 α p + a 2 α p 2 )g(P ad ) (14)
g(P ad ) =

m a s = ṁac s 120w m ( 16
)
T ch = ( w m 263.17

) 2 + T ch pert . ( 17
)
All the quantities in those equations are explained in Table I and we will use all the coefficients (a i , i = 1, ..., 12) proposed in [START_REF] Nouvelière | Commandes robustes appliquées au contrôle assisté d'un véhicule à basse vitesse[END_REF]. T m is related to τ g through the transmission chain which we will not detail here.

B. Brake model

We will use a simple brake model proposed in [START_REF] Yi | Nonlinear Brake Control for Vehicle CW/CA Systems[END_REF] where the brake hydraulic dynamics have been approximated by a linear second-order system. The dynamic equations for the brake pressure is:

ż1 = z 2 ż2 = -b 1 z 1 -b 1 z 2 + b 3 P m ( 18
)
P ω = z 1
where P m is the input to the solenoid valve and P ω is the brake pressure at the wheel. The brake torque τ b is considered to be proportional to the brake pressure at the wheel:

τ b = K b P ω .
where K b is the lumped gain for the entire brake system.

C. Model-free feedback control

Inspired by [START_REF] Choi | Robust Algebraic Approach for Radar Signal Processing: Noise filtering, time-derivative estimation and perturbation estimation[END_REF] with n = 0, we assume that there is locally a linear relation between the measured engine torque and the throttle angle:

τ e = k a α p + G(t) ( 19
)
where k a is a constant and G(t) represents neglected dynamics of the engine.

If we use as a throttle input:

α p = 1 k a (a( τe -τg ) + τ g -Ĝ), (20)
where a ∈ R -, τ e is the measured engine torque, and Ĝ is the estimate of G(t) which can be obtained from [START_REF] Yi | Nonlinear Brake Control for Vehicle CW/CA Systems[END_REF] in discrete time form:

G k = τ ek -k a α k-1 ,
this control law leads to the following torque error dynamics:

a( τe -τg ) -(τ e -τ g ) = 0.
Therefore τ e will converge exponentially to τ g .

The brake torque can also be expressed by:

τ b = k b P m + D(t) (21)
where k b is a constant and D(t) represents neglected dynamics of the brake. And the same technique can be applied for the brake input too:

P m = 1 k b (b( τb -τg ) + τ g -D), (22)
where b ∈ R -, τ b is the measured brake torque and D is the estimate of D(t).

Remark 3: In (20) and ( 22), we need torque measurements. From a practical point of view, the torque measurement is not an easy task. Instead, it could be estimated using [START_REF] Naranjo | ACC+Stop&Go Maneuvers With Throttle and Brake Fuzzy Control[END_REF]. In order to test this, realistic noises have been added on both angular wheel velocities ω and longitudinal accelerations γ x . To attenuate the perturbation due to these measurement noises, α p and P m are finally filtered using [START_REF] Fliess | Non-linear estimation is easy[END_REF]. Let us also notice that the time derivative terms in (20) and ( 22) are obtained using (3). Finally we have implemented our resulting control law which does not need any torque measurement but in absence of external dynamic disturbances on a typical Stop-and-Go scenario where several accelerations/decelerations are applied on a flat road. Figure 2 shows that the desired torque is pretty well tracked.

The same scenario is tested once more, with several external disturbances (road slope, rolling resistance and aerodynamic force) which are detailed for example in [START_REF] Villagra | Robust grey-box closed-loop stop-and-go control[END_REF]. Thanks to the grey-box compensation on the upper level controller, external disturbances are efficiently compensated and the desired torque is well tracked too (see Figure 3). Indeed, in that case, we cannot obviously estimate γ 0 from [START_REF] Nouvelière | Experimental vehicle longitudinal control using a second order sliding mode technique[END_REF] if we suppose that the torque τ g is not itself measured. These simulation results show that our control strategy exhibits good robustness properties with respect to the external disturbances, if the torque is supposed to be measured.

VI. ROBUSTNESS STUDY OF THE MODEL-FREE CONTROL AGAINST PARAMETER VARIATIONS

In order to show the robustness of our model-free control approach which does not rely on any parametric model, we can compare it with an analytical solution of the engine/brake models presented in Section V.

A. Analytical input solutions of the engine/brake models

Introducing m a s of ( 16) into [START_REF] Raza | Modeling and control design for a computer-controlled brake system[END_REF] yields

T m = A ṁac s + B A = a 10 120w m , B = a 9 + a 11 w m + a 12 w 2 m . (23)
In a similar way, (23) can be rewritten using ṁac s from (13):

T m = A( ṁac e - Ṗad k p ) + B. ( 24
)
If we rearrange (24) in terms of ṁac e and we compare it with [START_REF] Powel | Optimal idle speed control of an automotive engine[END_REF]:

ṁac e = 1 A (T m -B + A Ṗad k p ) = (1 + a 1 α p + a 2 α p 2 )g(P ad )
then, the following second order equation in α p can be written: Finally, we solve (25) and obtain a throttle angle input which is a function of T m, P ad and ω m (the positive root will be taken because physically α p ≥ 0):

aα p 2 + bα p + c = 0 a = a 2 , b = a 1 , c = 1 - T m -B+A Ṗad kp Ag(P ad ) . (25)
α p = f(T m , P ad , w m ) = -b + √ b 2 -4ac 2a . (26)
For the brake input, we can express easily P m from (18):

P m = 1 b 3 ( Pω + b 2 Ṗω + b 1 P ω ) (27)
using algebraic estimates of Pω and Ṗω . Reference Real Fig. 3. Torques, external disturbances and inter-distance when the torque is supposed to be measured

B. Influence of parameter uncertainties

We assume that parameters are not well known. We will increase a 9 and a 10 up to 20 % in the engine model and b 3 up to 20 % in the brake model. And then, we will compare the model-free control performance using [(20), ( 22)] with the analytical solution performance using [(26), ( 27)].

As the analytical solutions are obtained from (26) and (27), they are very sensitive to any parameter variation, and therefore torque tracking quality is quite poor (see Figure 4). On the contrary, the model-free control strategy shows good performances (see Figure 5). The model-free control approach has been applied to develop controllers in Stop-and-Go scenarios. Our control laws are naturally robust not only to unmodeled low level dynamics but also to external disturbances applied to the chassis. It should be pointed out that engine/brake torque measurements are no more needed and can be estimated using algebraic techniques in the disturbance free case.

Fig. 1 .

 1 Fig. 1. General Stop-and-Go control scheme

  u r = -c| d| ḋ, ∀ d 0 which leads to the following equation: d = -c| d| ḋẍl .

Fig. 2 .

 2 Fig. 2. Torques, inter-distances and velocities in a typical Stop-and-Go scenario

Fig. 4 .

 4 Fig. 4. Influence of the parameter changes on the analytical solutions

Fig. 5 .

 5 Fig. 5. Robustness of the model-free control against parameter changes

  and B. d'Andréa-Novel are at Mines ParisTech, CAOR-Centre de Robotique, Mathématiques et Systèmes, 60 bd. Saint Michel,

	75272 Paris Cedex 06, France. sung-woo.choi@ensmp.fr,
	dandrea@ensmp.fr
	M.	Fliess	is	at	INRIA-ALIEN	&	LIX	(CNRS,
	UMR 7161),	École polytechnique, 91128 Palaiseau, France.
	Michel.Fliess@polytechnique.edu
	H.	Mounier	is	at	Institut	d' Électronique	Fondamentale
	(CNRS, UMR 8622), Université Paris-Sud, 91405 Orsay, France.

TABLE I ENGINE

 I

		MODEL VARIABLES AND PARAMETERS
	ṁace	Mass air flow rate into the manifold (kg/s)
	ṁacs	Mass air flow rate out of the manifold (kg/s)
	P ad α p	Manifold pressure (P a ) Throttle angle ( • )
	w m	Engine speed (tr/min)
	T m	Internally developed torque (Nm)
	T ch	Load torque (Nm)
	T chpert	Shaft torque (Nm)
	k p	Manifold dynamic constant
	k n	Rotational dynamics constant

  (a 4 P ad -P 2 ad ), P ad > 50.66 ṁac s = a 5 w m + a 6 P ad + a 7 w m P ad + a 8 w m P 2 ad T m = a 9 + a 10 m a s + a 11 w m + a 12 w 2

	1, a 3	P ad ≤ 50.66

m

[START_REF] Raza | Modeling and control design for a computer-controlled brake system[END_REF]

See [8] for another application to the automotive industry, i.e., to the control of throttles.


Omar Fawzi

Aadil Oufkir

Daniel Stilck Franca

Daniel Stilck

Franca Lower Bounds

Daniel Stilck França

Lower Bounds on Learning Pauli Channels

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In spite of their impressive progress over the last few years [START_REF] Arute | Quantum supremacy using a programmable superconducting processor[END_REF]; [START_REF] Ebadi | Quantum phases of matter on a 256-atom programmable quantum simulator[END_REF]; [START_REF] Scholl | Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms[END_REF]; Zhong et al. (2020), the scaling and effective employment of quantum technologies still face many challenges. One of the most significant ones is how to tame the noise affecting such devices. For that, more effective tools are required to characterize and learn noisy quantum channels [START_REF] Eisert | Quantum certification and benchmarking[END_REF]. As the number of parameters required to describe a quantum channel scales exponentially in the size of the device, it is challenging to learn the noise beyond a few qubits.

A class of quantum channels that deserves particular attention is that of Pauli channels (Watrous, 2018, Sec. 4.1.2). The reasons for that are manifold. First, Pauli channels provide a simple and effective model of incoherent noise, admitting a representation in terms of a probability distribution corresponding to different Pauli errors and inheriting the rich structure of the Pauli matrices. Second, they are a physically relevant noise model and the noise affecting a device can always be mapped into a Pauli channel by using randomized compiling [START_REF] Wallman | Noise tailoring for scalable quantum computation via randomized compiling[END_REF] techniques without incurring a loss in fidelity. These properties make the problem of Pauli tomography, i.e. learning a Pauli channel, particularly relevant. Finally, Pauli channel tomography is also known to be a problem for which quantum resources provide an advantage [START_REF] Chen | Quantum advantages for pauli channel estimation[END_REF].

Furthermore, reliable protocols to learn quantum channels face the additional hurdle that there might be errors both in the initial state preparation and measurements (SPAM errors). Thus, it is desirable to design protocols that are robust to such errors. And, of course, practical protocols should not rely on the preparation of complex states or measurements. A popular and widely used protocol to learn Pauli channels that fulfills these desiderata is that of randomized benchmarking and its variations [START_REF] Flammia | Efficient estimation of pauli channels[END_REF]; [START_REF] França | Approximate randomized benchmarking for finite groups[END_REF]; [START_REF] Helsen | General framework for randomized benchmarking[END_REF]; [START_REF] Helsen | A new class of efficient randomized benchmarking protocols[END_REF]; [START_REF] Magesan | Characterizing quantum gates via randomized benchmarking[END_REF]. Finally, Pauli noise model reflects experiments that are actually done in practice (see e.g., [START_REF] Harper | Efficient learning of quantum noise[END_REF] which includes an experimental implementation). It is thus natural to ask to what extent it is optimal or whether we could hope for better protocols to learn Pauli noise.

Contributions We provide lower bounds on the number of measurements or channel uses for learning a Pauli quantum channel in diamond norm using incoherent measurements and no auxiliary systems in both non-adaptive and adaptive settings (see Table 1 for a summary). Let d = 2 n the dimension of the input and output of the unknown Pauli channel on n qubits and ε > 0 the precision parameter.

• Non-adaptive setting: We show that any non-adaptive learning algorithm of a Pauli channel should, at the worst case, use at least Ω(d 3 /ε 2 ) measurements or a total number Ω(d 4 /ε 6 ) of

Model

Lower bound Upper bound

Non-adaptive, 1 -distance N = Ω(d 3 /ε 2 ) or N = Õ(d 3 /ε 2 ) N t=1 m t = Ω(d 4 /ε 6 ) [this work] Flammia and Wallman (2020) Non-adaptive, ∞ -distance N = Ω(1/ε 2 ) N = Õ(1/ε 2 ) Flammia and O'Donnell (2021) [START_REF] Flammia | Pauli error estimation via population recovery[END_REF] Adaptive, 1 -distance N = Ω(d 2 /ε 2 ) [this work] N = Õ(d 3 /ε 2 ) Flammia and Wallman (2020) Adaptive, 1 -distance N = Ω(d 2.5 /ε 2 ) [this work] N = Õ(d 3 /ε 2 ) ε ≤ 1/(20d), ∀t ∈ [N ] : m t = 1 [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] Table 1: Lower and upper bounds for Pauli channel tomography using incoherent measurements. N is the total number of steps or measurements. At each step t ∈ [N ], m t denotes the total number of channel uses between the (t -1) th and t th measurements.

channel uses. In particular, this shows that the randomized benchmarking algorithm of (Flammia & Wallman, 2020, Result 1) is almost optimal since the channels we consider in our construction have a spectral gap ∆ ≥ 1 -4ε and thus the total number of channel uses is at most twice the number of measurements. This result is stated in Theorem 4.1. For the proof, we construct an εseparated family of Pauli channels close to the maximally depolarizing channel and use it to encode a message from [e Ω(d 2 ) ]. A learning algorithm can be used to decode this message with the same success probability. Hence, the encoder and decoder should share at least Ω(d 2 ) nats of information.

On the other hand, after each step, we show that the correlation between the encoder and decoder can only increase by at most O(ε 2 /d) nats if the channel is used at most 2 times. Moreover, if the channel is used m ≥ 3 times, we show in this case that the correlation between the encoder and decoder can only increase by at most O(mε 6 /d 2 ) nats. Note that the naive upper bound on this correlation is O(ε 2 ), we obtain an improvement by a factor d or d 2 /m by exploiting the randomness in the construction of the Pauli channel.

• Adaptive setting: We show that in general, any learning algorithm of a Pauli channel should use at least Ω(d 2 /ε 2 ) measurements no matter how many times the channel is applied and intertwined with other unital operations before each measurement. For the proof, we can use the same construction to encode a message in [e Ω (d 2 ) ]. In order to decode this message with high probability, a learner needs to share at least Ω(d 2 ) nats of information with the uniform encoder. Then, we need to show that, for a Pauli channel close to the maximally depolarizing channel, at each step, reapplying the channel m ≥ 1 times even intertwined with unital operations can only add a noise and doesn't help to extract useful information: the amount of correlation between the encoder and decoder increases by at most O(ε 2m ) nats. This result is stated in Theorem 3.1. Furthermore, if the (adaptive) algorithm could only apply the Pauli channel once per step, it should use at least Ω(d 2.5 /ε 2 ) measurements if ε ≤ 1/(20d). This result is stated in Theorem 5.1. The strategy of the proof is the same as in the non-adaptive case. When the learner can adapt its choices of input and measurement device depending on the previous observations, we expect that its correlations with the uniform encoder will increase by more than O(ε 2 /d) nats per step. Besides the naive upper bound of O(ε 2 ) on this correlation, we show that if the learner uses the channel once per step, it can only increase its correlation with the encoder by at most O(kε 4 /d 3 ) nats at step k.

For this, we change the previous construction and use normalized Gaussian random variables in the Pauli channel's coefficients. The Gaussian variables allow us to break the dependency between the probability of measurements at different steps by applying Gaussian integration by parts on an upper bound of the mutual information.

Related work

Learning Pauli channels has been considered in different settings. [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] provides an algorithm for learning Pauli channels in 2 -norm using Õ(d/ε 2 ) measurements. This implies an upper bound of Õ(d 3 /ε 2 ) for learning Pauli channel in 1 -norm. For completeness, we reproduce this argument in App. B. In this article, we address an open question posed in Flammia and Wallman (2020) about a lower bound for learning Pauli channels. In particular we show that the algorithm of [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] is optimal up to logarithmic factors. Moreover, learning a Pauli channel in ∞ -norm was shown to be solved with Θ(1/ε 2 ) measurements in [START_REF] Flammia | Pauli error estimation via population recovery[END_REF] and this is optimal up to logarithmic factors. The previous settings did not allow for ancillas. The work

Preliminaries

Let d = 2 n be the dimension of an n-qubit system. We use the notation [d] := {1, . . . , d}. We adopt the bra-ket notation: a column vector is denoted |φ and its adjoint is denoted φ| = |φ † . With this notation, φ|ψ is the dot product of the vectors φ and ψ and, for a unit vector |φ ∈ S d , |φ φ| is the rank-1 projector on the space spanned by the vector φ. The canonical basis {e

i } i∈[d] is denoted {|i } i∈[d] := {|e i } i∈[d] .
A quantum state is a positive semi-definite Hermitian matrix of trace 1. We will denote the identity matrix by I d ∈ C d×d and by id d : C d×d → C d×d the identity map. We will omit the the d subscript if the dimension is clear from context. A quantum channel is a map N :

C d×d → C d×d of the form N (ρ) = k A k ρA † k where the Kraus operators {A k } k satisfy k A † k A k = I.
A map N is a quantum channel if, and only if, it is:

• completely positive: for all ρ ∈ C d 2 ×d 2 , ρ 0, id d ⊗ N (ρ) 0 and

• trace preserving: for all ρ ∈ C d×d , tr(N (ρ)) = tr(ρ).

If the quantum channel N satisfies further N (I) = I, it is called unital.

We define the diamond distance between two quantum channels N and M as the diamond norm of their difference:

N -M = max φ: φ|φ =1 id d ⊗ (N -M)(|φ φ|) 1
where the the Schatten 1-norm of a matrix M is defined as

M 1 = tr √ M † M .
Pauli channels are a special quantum channel whose Kraus operators are weighted Pauli operators. Formally, a Pauli quantum channel P can be written as follows:

P(ρ) = P ∈{I,X,Y,Z} ⊗n p(P )P ρP (1)
where the Pauli matrices

I = 1 0 0 1 , X = 0 1 1 0 , Y = 0 -i i 0
and Z = 1 0 0 -1 and {p(P )} P ∈{I,X,Y,Z} ⊗n is a probability distribution. Let P n = {I, X, Y, Z} ⊗n be the set of Pauli operators. The elements of P n either commute or anti commute. Let P and Q be two Pauli operators, we have P Q = (-1) P.Q QP where P.Q = 0 if [P, Q] = 0 and P.Q = 1 otherwise. We consider the Pauli channel tomography problem which consists of learning a Pauli channel in the diamond norm. Given a precision parameter ε > 0, the goal is to construct a Pauli channel P satisfying with at least a probability 2/3:

P -P ≤ ε.
An algorithm A is 1/3-correct for this problem if it outputs a Pauli channel ε-close to P with a probability of error at most 1/3. We choose to learn in the diamond norm because it characterizes the minimal error probability to distinguish between two quantum channels when auxiliary systems are allowed [START_REF] Watrous | The theory of quantum information[END_REF]. Since the diamond norm between two Pauli channels is exactly twice the TV-distance between their corresponding probability distributions [START_REF] Magesan | Characterizing quantum gates via randomized benchmarking[END_REF], approximating the Pauli channel P in diamond norm is equivalent to approximating the probability distribution p in TV-distance. The latter is defined for two probability distributions p and q on [d] as follows:

TV(p, q) = 1 2 d i=1 |p i -q i |.
The learner can only extract classical information from the unknown Pauli channel P by performing a measurement on the output state. Throughout the paper, we only consider unentangled or incoherent measurements. That is, the learner can only measure with an n-qubit measurement device and auxilliary qubits or measuring multiple copies at once is not allowed. This restriction is natural for the problem at hand, given that performing measurements on multiple copies requires a quantum memory.

More precisely, an n-qubit measurement is defined by a POVM (positive operator-valued measure) with a finite number of elements: this is a set of positive semi-definite matrices M = {M i } i acting on the Hilbert space C 2 n and satisfying i M i = I. Each element M i in the POVM M is associated with the outcome i. The tuple {tr(ρM i )} i is non-negative and sums to 1: it thus defines a probability. Born's rule [START_REF] Born | Zur Quantenmechanik der Stoßvorgänge[END_REF] says that the probability that the measurement on a quantum state ρ using the POVM M will output i is exactly tr(ρM i ).

For an integer t ≥ 1, we say that the learner is at step t if it has already performed t-1 measurements. With this definition, the total number of steps is exactly the total number of measurements. However, depending on the setting, the total number of channel uses could be different than the total number of steps. The goal of the paper is to show lower bounds on the total number of steps as well as the total number of the channel uses.

A simple example we can propose to see the effect of reusing the channel is the following test:

H 0 : P(ρ) = ρ vs H 1 : P(ρ) = (1 -ε)ρ + εtr(ρ) I d .
We can choose as input the rank one state ρ = |0 0|. Under the null hypothesis H 0 , the channel does not affect the state |0 0|. On the other hand, under H 1 , if we apply the channel P a number m ∈ N * times the resulting quantum state is

P (m) (ρ) = (1-ε) m |0 0|+(1 -(1 -ε) m ) I d .
Hence, if we measure with the POVM M = {|0 0| , I-|0 0|} of outcomes 0 and 1 respectively, under H 0 we will always see 0 while under H 1 , we will see 0 with probability roughly (1 -ε) m . Therefore, we can achieve a confidence δ with only one measurement but the channel is reused log(1/δ)/ε-times 1 . However, if we don't allow reusing the channel, then the number of measurements needed is approximately log(1/δ)/ε.

A general lower bound on the number of steps required for Pauli channel tomography

In this section, we consider the problem of learning a Pauli quantum channel using incoherent measurements. Unlike the usual state tomography problem for which at each step the learner can only choose the measurement device, for quantum channels, the learner has additional choices. First, in every setting, the learner can choose the input quantum state at each step. This choice can be done in an adaptive fashion: the input quantum state at a given step can be chosen depending on the previous observations (and of course the previous input states and POVMs). Second, the learner has the ability to reuse the Pauli quantum channel as much as it wants before performing the measurement. This is specific to quantum process tomography too since for state tomography using incoherent measurements, once a measurement is performed, the post-measurement quantum state is usually useless. Finally, the learner can intertwine arbitrary unital quantum channels and the unknown Pauli quantum channel before measuring the output of this (possibly long) sequence of quantum channels. We propose a lower bound on the number of steps required for the Pauli channel tomography problem in this general setting.

Recall that Pauli channel tomography problem is equivalent to learning the probability p in the TVdistance. Mainly, the learner would like to construct a probability distribution p on the set of Pauli operators P n satisfying with at least a probability 2/3: TV(p, p) ≤ ε 1 all the logs are taken in base e so the information is measured in "nats".

. . .

M 1 ρ 1 P N 1 P P N m1-1 P I 1  (I 1 ) . . . M I1 2 ρ I1 2 P N I1 1 P P N I1 m2-1 P I 2  . . . . . . M I <N -1 N -1 ρ I <N -1 N -1 P N I <N -1 1 P P N I <N -1 m N -1 -1 P I N -1  I <N = (I 1 , . . . , I N -1 )
. . . with as few steps as possible.

M I <N N ρ I <N N P N I <N 1 P P N I <N m N -1 P I N
Let N be a sufficient number of steps to learn P as defined in Eq. (1). At step t ∈ [N ], the learner has the ability to choose an input quantum state ρ t , the number m t ≥ 1 of uses of the quantum channel P, the unital quantum channels applied in between N 1 , . . . , N mt-1 and the POVM M t for measuring the output quantum state ρ output t :

ρ output t = P • N mt-1 • P • • • • • P • N 1 • P(ρ t ) mt times .
All these elements can be chosen adaptively: the choice of m t , ρ t , N 1 , . . . , N mt-1 and M t can depend on the previous observations I 1 , . . . , I t-1 (see Fig. 1 for an illustration). However, to not overload the expressions we don't add the subscript I 1 , . . . , I t-1 on m t , ρ t , N 1 , . . . , N mt-1 or M t . By Born's rule, performing a measurement on the output quantum state ρ output t using the POVM M t = {M t i } i∈I is equivalent to sampling from the probability distribution

x ∼ {tr(ρ output t M t i )} i∈I .
Note that unital operations cannot be used to prepare a new state and thus have a free step. In fact, applying a unital operation after a noisy Pauli channel cannot prepare a rank-1 state for example. We propose the following lower bound on the number of steps N .

Theorem 3.1. The problem of Pauli channel tomography using incoherent measurements requires a number of steps satisfying:

N = Ω d 2 ε 2 .
This Theorem shows that no matter how often the learner reuses the quantum Pauli channel intertwined with other unital quantum channels on each step, the global number of steps should be exponential in the number of qubits. This can be explained by the fact that a Pauli channel adds noise to the input state, so reapplying it makes the input state more noisy and can't help to extract more information. Although, as we remark later, this lower bound is weaker in the dependency on the dimension d compared to the non-adaptive case, it has the particularity of not depending on the number of uses of the Pauli channel.

Proof. We will break down the proof into several steps.

Construction of the family F We start by describing a general construction of a big family F = {P x } x∈ 1,M constituted of quantum Pauli channels satisfying for all x = y ∈ 1, M : TV(p x , p y ) ≥ ε, we say that the family F is ε-separated. These quantum channels have the form for x ∈ 1, M :

P x (ρ) = P ∈{I,X,Y,Z} ⊗n p x (P )P ρP = P ∈{I,X,Y,Z} ⊗n 1 + 4α x (P )ε d 2 P ρP (2)
where α x (P ) = ±1 to be chosen randomly so that α x (P ) = -α x (σ(P )) for some matching σ of {I, X, Y, Z} ⊗n2 . Suppose that we have already constructed an ε-separated family of Pauli quantum channels F = {P x } x of cardinality M . We show that we can add another element to this family as long as M < e cd 2 for some sufficiently small constant c. For this, we choose α(P ) = -α(σ(P )) = ±1 with probability 1/2 each. This α leads to a quantum channel P(ρ) = P ∈{I,X,Y,Z} ⊗n 1+4α(P )ε d 2 P ρP . Then, we control the probability that the corresponding Pauli quantum channel isn't ε-far from the family F. By the union bound and Chernoff-Hoeffding inequality [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]:

P (∃P x ∈ F : TV(p, p x ) < ε) ≤ M x=1 P P ∈Pn |p(P ) -p x (P )| < 2ε = M x=1 P P ∈Pn 4|α(P ) -α x (P )| < 2d 2 = M x=1 P P ∈Pn 1 α(P ) =αx(P ) < d 2 4 = M x=1 P   2 d 2 P ∈Pn/σ 1 α(P ) =αx(P ) -E 1 α(P ) =αx(P ) < - 1 4   = M x=1 exp(-2(d 2 /2)(1/4) 2 ) = M exp(-d 2 /16)
which is strictly smaller than 1 if M < e d 2 /16 . So far, we have proven the following lemma:

Lemma 3.2. There exists an ε-separated family of quantum Pauli channels of the form 2 and size at least e d 2 /16 .

Hence, we can use this family to encode a message X ∼ Unif 1, M to a quantum Pauli channel P = P X in the family constructed above. The decoder receives this unknown quantum Pauli channel, chooses its inputs states and performs incoherent measurements possibly after many uses of the channel intertwined with arbitrary unital quantum channels, and learns it to within a precision ε/2. It thus produces a Pauli quantum channel P corresponding to a probability distribution p satisfying, with a probability at least 2/3, TV(p, p X ) ≤ ε/2. Since the family of probability distributions {p x } x∈[M ] is εseparated, there is only one X such that TV(p, p X ) ≤ ε/2. Therefore a 1/3-correct algorithm can decode with a probability of failure at most 1/3. By Fano's inequality, the encoder and decoder should share at least Ω(log(M )) = Ω(d 2 ) nats of information.

Lemma 3.3 [START_REF] Fano | Transmission of information: A statistical theory of communications[END_REF]). The mutual information between the index of the actual channel X and the estimated index X is at least

I(X : X) ≥ 2/3 log(M ) -log(2) = Ω(d 2 ).
Then we show that no algorithm can extract more than O(ε 2 ) nats of information at each step. For this, recall that X is the uniform random variable on the set 1, M representing the encoder and denote by I 1 , . . . , I N the observations of the decoder or the 1/3-correct algorithm. The Data-Processing inequality implies:

I(X : X) ≤ I(X : I 1 , . . . , I N ).
Moreover, if we denote by I ≤k-1 := (I 1 , . . . , I k-1 ) for all 1 ≤ k ≤ N , the chain rule of mutual information guves:

I(X : I 1 , . . . , I N ) = N k=1 I(X : I k |I ≤k-1 )
where I(X : I k |I ≤k-1 ) denotes the conditional mutual information between X and I k giving I ≤k-1 . We claim that every conditional mutual information I(X : I k |I ≤k-1 ) can be upper bounded by O(ε 2 ). To prove this claim, we prove first a general upper bound on the conditional mutual information.

At step t ∈ [N ] , the 1/3-correct algorithm used by the decoder chooses the input state ρ t , uses the unknown quantum Pauli channel P m t ≥ 1 times, eventually intertwines the P with unital quantum channels N t 1 , N t 2 , . . . , N t mt-1 and finally measures the output with a POVM

M t = {λ t i |φ t i φ t i |} i∈It where φ t i |φ t i = 1 and i λ t i |φ t i φ t i | = I. Note that this implies i λ t i = d.
Observe that we can always reduce the measurement with a general POVM M to the measurement with such a POVM by taking the projectors on the eigenvectors of each element of the POVM M weighted by the corresponding eigenvalues. We denote by

P mt (ρ t ) = P • N t mt-1 • P . . . P • N t 1 • P(ρ t ) mt times
the quantum channel applied to the input quantum state ρ t . We denote by q the joint distribution of (X, I 1 , . . . , I N ):

q(x, i 1 , . . . , i N ) = 1 M N t=1 λ t it φ t it P mt x (ρ t ) φ t it .
We use the usual notation of marginals by ignoring the indices on which we marginalize. For instance, for all adaptive algorithms, for all 1 ≤ k ≤ N , we have:

q ≤k (x, i 1 , . . . , i k ) = i k+1 ,...,i N 1 M N t=1 λ t it φ t it P mt x (ρ t ) φ t it = 1 M k t=1 λ t it φ t it P mt x (ρ t ) φ t it N t=k+1 it λ t it φ t it P mt x (ρ t ) φ t it = 1 M k t=1 λ t it φ t it P mt x (ρ t ) φ t it N t=k+1 tr(P mt x (ρ t )) = 1 M k t=1 λ t it φ t it P mt x (ρ t ) φ t it .
We sometimes abuse the notation and use q instead of q ≤k when it is clear from the context. In order to simplify the expressions, we introduce the notation

u k,x i k = φ k i k dP m k x (ρ k ) -I φ k i k . Note that for adaptive strategies the vectors φ k i k = φ t i k (i <k ) and the states ρ k = ρ k (i <k ) depend on the previous observations i <k = (i 1 , . . . , i k-1 ) for all k ∈ [N ].
Then the general upper bound on the conditional mutual information is:

Lemma 3.4. Let 1 ≤ k ≤ N and u k,x i k = φ k i k (i <k ) dP m k x (ρ k (i <k )) -I φ k i k (i <k ) .
We have for adaptive strategies:

I(X : I k |I ≤k-1 ) ≤ 3E x E i∼q ≤k-1 i k λ k i k d (u k,x i k ) 2 .
Moreover, for non-adaptive strategies

u k,x i k = φ k i k dP m k x (ρ k ) -I φ k i k and: I(X : I k |I ≤k-1 ) ≤ 3E x i k λ k i k d (u k,x i k ) 2 .
Proof. We can remark that, for all 1

≤ k ≤ N , q(x, i ≤k ) = λ k i k 1+u k,x i k d q(x, i ≤k-1 ) thus q(x, i k |i ≤k-1 ) q(x|i ≤k-1 )q(i k |i ≤k-1 ) = q(x, i ≤k )q(i ≤k-1 ) q(x, i ≤k-1 )q(i ≤k ) = λ k i k 1+u k,x i k d q(x, i ≤k-1 )q(i ≤k-1 ) q(x, i ≤k-1 ) y q(y, i ≤k ) = λ k i k 1+u k,x i k d q(i ≤k-1 ) y q(y, i ≤k ) = λ k i k 1+u k,x i k d q(i ≤k-1 ) y q(y, i ≤k-1 )λ k i k 1+u k,y i k d = (1 + u k,x i k )q(i ≤k-1 ) y q(y, i ≤k-1 )(1 + u k,y i k ) = (1 + u k,x i k ) y q(y|i ≤k-1 )(1 + u k,y i k )
.

Therefore by Jensen's inequality:

I(X : I k |I ≤k-1 ) = E log q(x, i k |i ≤k-1 ) q(x|i ≤k-1 )q(i k |i ≤k-1 ) = E log (1 + u k,x i k ) y q(y|i ≤k-1 )(1 + u k,y i k ) ≤ E log(1 + u k,x i k ) - y q(y|i ≤k-1 ) log(1 + u k,y i k ) = E log(1 + u k,x i k ) - y E q(y|i ≤k-1 ) log(1 + u k,y i k ) .
The first term can be upper bounded using the inequality log(1 + x) ≤ x verified for all x ∈ (-1, +∞):

E log(1 + u k,x i k ) = E x,i∼q log(1 + u k,x i k ) ≤ E x,i∼q u k,x i k = E x,i∼q ≤k u k,x i k = E x,i∼q ≤k-1 i k λ k i k d (1 + u k,x i k )u k,x i k = E x,i∼q ≤k-1 i k λ k i k d (u k,x i k ) 2 because i k λ k i k d u k,x i k = tr(dP mt x (ρ t ) -I) = 0.
The second term can be upper bounded using the inequality -log(1 + x) ≤ -x + x 2 /2 verified for all x ∈ (-1/2, +∞):

E - y q(y|i ≤k-1 ) log(1 + u k,y i k ) = - y E x,i∼q q(y|i ≤k-1 ) log(1 + u k,y i k ) = - y E x,i∼q ≤k-1 q(y|i ≤k-1 ) i k λ k i k d (1 + u k,x i k ) log(1 + u k,y i k ) ≤ y E x,i∼q ≤k-1 q(y|i ≤k-1 ) i k λ k i k d (1 + u k,x i k )(-u k,y i k + (u k,y i k ) 2 /2) = y E x,i∼q ≤k-1 q(y|i ≤k-1 ) i k λ k i k d (-u k,y i k -u k,y i k u k,x i k + (u k,y i k ) 2 /2 + u k,x i k (u k,y i k ) 2 /2) ≤ y E x,i∼q ≤k-1 q(y|i ≤k-1 ) i k λ k i k d ((u k,x i k ) 2 + (u k,y i k ) 2 ) = 2 y E x,i∼q ≤k-1 q(y|i ≤k-1 ) i k λ k i k d (u k,x i k ) 2 = 2E x,i∼q ≤k-1 i k λ k i k d (u k,x i k ) 2 .
Since the conditional mutual is upper bounded by the sum of these two terms, the upper bound on the conditional mutual information follows.

The following Lemma permits to conclude the upper bound on the conditional mutual information and thus the upper bound on the mutual information.

Lemma 3.5. Let m ≥ 1, N 1 , . . . , N m-1 be unital quantum channels and P be a Pauli quantum channel in the family F. We have for all quantum states ρ and vectors |φ ∈ S d :

| φ| dPN m-1 P . . . PN 1 P(ρ) |φ -1| ≤ (4ε) m .
Proof. For x ∈ 1, M , we define the map M x verifying the following equality:

M x (ρ) = P x (ρ) -tr(ρ) I d = P ∈{I,X,Y,Z} ⊗n 4α x (P )ε d 2 P ρP,
where we have used the fact (see Lemma A.2) that for all ρ:

P ∈{I,X,Y,Z} ⊗n P ρP = dtr(ρ)I.

Note that tr(M x (ρ)) = tr(P x (ρ)) -tr(ρ)tr( I d ) = tr(ρ) -tr(ρ) = 0. Applying a unital quantum channel N between two quantum channels P x can be seen as :

P x N P x (ρ) = P x N tr(ρ) I d + M x (ρ) = P x tr(ρ) I d + N M x (ρ) = tr(ρ) I d + M x ( I d + N M x (ρ)) = tr(ρ) I d + M x N M x (ρ) because tr(N M x (ρ)) = tr(M x (ρ)) = 0 and M x (I) = P ∈{I,X,Y,Z} ⊗n 4α x (P )ε d 2 I = P ∈{I,X,Y,Z} ⊗n /σ 4α x (P )ε d 2 I + 4α x (σ(P ))ε d 2 I = 0.
By induction, we generalize this equality to m applications of the Pauli channel P x :

P x N m-1 P x . . . P x N 1 P x (ρ) m times = tr(ρ) I d + M x N m-1 M x . . . M x N 1 M x (ρ) m times Therefore φ| dPN m-1 P . . . PN 1 P(ρ) |φ = φ| I + dMN m-1 M . . . MN 1 M(ρ) |φ = 1 + d φ| MN m-1 M . . . MN 1 M(ρ) |φ .
On the other hand, for all vectors |φ ∈ S d and Hermitian matrices

X = i λ i |φ i φ i | we have: | φ| X |φ | = | i λ i | φ|φ i | 2 | ≤ i |λ i || φ|φ i | 2 = φ| |X| |φ therefore using Lemma A.2: | φ| M(X) |φ | = φ| P ∈Pn 4α(P )ε d 2 P XP |φ ≤ 4ε d 2 P ∈Pn | φ| P XP |φ | ≤ 4ε d 2 P ∈Pn φ| P |X|P |φ = 4ε d 2 φ| dtr|X|I |φ = 4ε d tr|X|,
moreover we can also obtain:

tr|M(X)| = P ∈Pn 4α(P )ε d 2 P XP 1 ≤ P ∈Pn 4ε d 2 P XP 1 = P ∈Pn 4ε d 2 tr|X| = 4εtr|X|,
and for a quantum channel N j :

tr|N j (X)| = N j (X) 1 = i λ i N j (|φ i φ i |) 1 ≤ i λ i N j (|φ i φ i |) 1 = i |λ i | = tr|X|.
Therefore by induction we can prove:

| φ| dPN m-1 P . . . PN 1 P(ρ) |φ -1| = d| φ| MN m-1 M . . . MN 1 M(ρ) |φ | ≤ d 4ε d tr|N m-1 M . . . MN 1 M(ρ)| = 4εtr|M . . . MN 1 M(ρ)| ≤ (4ε) 2 tr|N m-2 . . . MN 1 M(ρ)| ≤ (4ε) m .
(3)

Now we can finally upper bound the mutual information between X and (I 1 , . . . , I N ):

Lemma 3.6. The mutual information can be upper bounded as follows:

I(X : I 1 , . . . , I N ) = O(N ε 2 ).
Proof. For all 1 ≤ t ≤ N , we remark that u t,x it = φ t it dP mt x (ρ t )-I φ t it = ( φ| dP x N mt-1 P x . . . P x N 1 P(ρ t ) |φ -1), so by Lemma 3.4 and Lemma 3.5:

I(X : I t |I ≤t-1 ) ≤ 3E x,i∼q ≤t-1 it λ t it d (u t,x it ) 2 ≤ 3E x,i∼q ≤k-1 it λ t it d 16ε 2 = 48ε 2
because it λ t it = d. Finally:

I(X : I 1 , . . . , I N ) = N t=1 I(X : I t |I ≤t-1 ) = O(N ε 2 ).
Using Lemma 3.3 and Lemma 3.6 we obtain:

Ω(d 2 ) ≤ I ≤ O(N ε 2 ),
which yields the lower bound N = Ω(d 2 /ε 2 ).

To assess a lower bound, we need to compare it with upper bounds. The algorithm of Flammia and Wallman (2020) implies an upper bound of O d 3 log(d) ε 2 (see App. B for a self contained proof), so there is a gap between our lower bound and this upper bound. However, note that the algorithm of Flammia and Wallman (2020) (and in fact most channel learning protocols we are aware of) use non-adaptive strategies. We will now show that indeed [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] is optimal if we restrict to non-adaptive protocols.

Optimal Pauli channel tomography with non-adaptive strategies

The main difference between non-adaptive and adaptive strategies is that the former should choose the set of inputs, number of repetition, unital channels applied in between and the measurement devices before starting the learning procedure so that they cannot depend on the actual observations of the algorithm. Concretely, besides fixing the total number of steps N and the total number of channels uses at each step {m t } t∈[N ] , the non-adaptive algorithm is asked to choose also the inputs {ρ t } t∈[N ] , the unital channels Hence, when the algorithm performs a measurement on the output state ρ output t using the POVM M t = {λ t i |φ t i φ t i |} i∈It , it observes i t ∈ I t with probability:

{{N j } j∈[mt-1] } t∈[N ] and
ρ output t = P • N mt-1 • P • • • • • P • N 1 • P(ρ t ) mt times . . . . M 1 ρ 1 P N 1 P P N m1-1 P I 1  . . . M 2 ρ 2 P N 1 P P N m2-1 P I 2  . . . . . . M N ρ N P N 1 P P N m N -1 P I N
tr λ t it φ t it φ t it ρ output t = λ t it φ t it P • N mt-1 • P • • • • • P • N 1 • P(ρ t ) φ t it .
We refer to Fig. 2 for an illustration. We prove the following lower bound on the total number of measurements and steps:

Theorem 4.1. The problem of Pauli channel tomography using non-adaptive incoherent measurements requires a total number of channel uses verifying:

N t=1 m t = Ω d 4 ε 6
or a total number of steps verifying:

N = Ω d 3 ε 2 .
At a first sight we can think that this Theorem is not comparable to Theorem 3.1 since we give lower bounds on different parameters. However, if we ask the algorithm to only apply the channel once per step, we obtain an improved lower bound on the number of steps required for Pauli channel tomography using non-adaptive strategies. Moreover, it shows that the upper bound of [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] is almost optimal especially if we know that the additional uses of channels at each step are only required to make the algorithm resilient to errors in SPAM. Finally, the optimal complexity Θ d 3 ε 2 for Pauli channel tomography is quite surprising: We are ultimately interested in learning a classical distribution on P n [d 2 ] in TV-distance which requires a complexity of Θ d 2 ε 2 in the usual sampling access model, so our model is strictly weaker than the usual sampling access model. Furthermore, the quantum state tomography problem has also an optimal copy complexity of Θ d 3 ε 2 : this shows that adding an additional structure to the channel can make the optimal complexity of channel tomography smaller.

Proof. The construction on the family F is similar to the construction in the proof of Theorem 3.1. We only need to add some constraints about the concentration of the means 1 M M x=1 g(α x ) around their expectations for every function g ∈ G. To see what are the functions we need to consider in the set G, let us simplify the mutual information between X and I 1 , . . . , I N in the non-adaptive setting. Recall from Lemma 3.4 that the mutual information can be upper bounded as follows:

I(X : I 1 , . . . , I N ) = N t=1 I(X : I t |I ≤t-1 ) ≤ 3 N t=1 E x,i∼q ≤t-1 it λ t it d (u t,x it ) 2 .
Since now we consider non-adaptive algorithms, this upper bound can be simplified:

3E x,i∼q ≤t-1 it λ t it d (u t,x it ) 2 = 3 1 M M x=1 it∈It λ t it d (u t,x it ) 2 .
We remark that we only need to approximate

1 M M x=1 N t=1 i∈It λ t i d φ t i dP mt x (ρ t ) φ t i -1 2 .
Note that ( φ| dP mt (ρ t ) |φ -1) 2 ∈ [0, (4ε) 2 ] for every |φ ∈ S d and ε ≤ 1/4 (see ( 3)). Also, we have for

all t ∈ [N ], i∈It λ t i d = 1 so N t=1 i∈It λ t i d φ t i dP mt x (ρ t ) φ t i -1 2 ∈ [0, 16N ε 2 ].
Therefore by Hoeffding's inequality [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] for s = (16N ε 2 ) 2 log(10

) 2M P 1 M M x=1 N t=1 i∈It λ t i d φ t i dP mt x (ρ t ) φ t i -1 2 -E α N t=1 i∈It λ t i d φ t i dP mt α (ρ t ) φ t i -1 2 > s ≤ exp - 2M s 2 (16N ε 2 ) 2 = exp - 2M (16N ε 2 ) 2 log(10) 2M (16N ε 2 ) 2 = 1 10
.

By a union bound, this error probability 1/10 can be absorbed in the error probability of the construction by choosing a small enough constant c in the cardinality of the family M = exp(cd 2 ). To recapitulate, we have proven so far that we can construct the family of quantum Pauli channels F so that the mutual information satisfies:

Ω(d 2 ) ≤ I ≤ I(X : I 1 , . . . , I N ) ≤ 3 t it∈It λ t it d E α φ t it dP mt α (ρ t ) φ t it -1 2 + 52N ε 2 exp(-Ω(d 2 )). (4)
We claim that the RHS can be upper bounded for m t = 1 as follows:

Lemma 4.2. For all t ∈ [N ], for all unit vectors |φ ∈ S d :

E α ( φ| dP α (ρ t ) |φ -1) 2 ≤ 32ε 2 d .
If the claim is true, the inequalities 4 imply using the fact that for all t ≤ N , it∈It λ t it = d:

Ω(d 2 ) ≤ I ≤ 3 N t=1 it∈It λ t it d ε 2 d + 52N ε 2 exp(-Ω(d 2 )) ≤ O N ε 2 d
and the lower bound of N = Ω(d 3 /ε 2 ) yields for strategies using only one channel per step.

Proof. Let t ∈ [N ] and |φ ∈ S d . We have:

E α ( φ| dP α (ρ t ) |φ -1) 2 = E α P ∈Pn 4α(P )ε d φ| P ρ t P † |φ 2 = E α P,Q∈Pn 16α(P )α(Q)ε 2 d 2 φ| P ρ t P † |φ φ| Qρ t Q † |φ = P ∈Pn
16ε 2 d 2 ( φ| P ρ t P † |φ φ| P ρ t P † |φ -φ| P ρ t P † |φ φ| σ(P )ρ t σ(P ) † |φ )

≤ P ∈Pn 32ε 2 d 2 φ| P ρ t P † |φ 2 ≤ P ∈Pn 32ε 2 d 2 φ| P ρ 2 t P † |φ = 32ε 2 d 2 φ| dtr(ρ 2 t )I |φ ≤ 32ε 2 d ,
where we used the Cauchy-Schwartz inequality.

Now, if we allow multiple uses of the channel at each step, we obtain the following upper bound depending on the number m ≥ 2 of channel uses:

Lemma 4.3. For all t ∈ [N ], m ≥ 2 and unit vectors |φ ∈ S d : E α ( φ| dP m α (ρ t ) |φ -1) 2 ≤ 4m (4ε) 2m d min{2,m-1} .
Proof. Recall that for a Pauli channel P α , we can define M α = P α -tr() I d so that after m applications of the Pauli channel P α intertwined by the unital quantum channels N 1 , . . . , N m-1 , we have the following identity:

P α N m-1 P α . . . P α N 1 P α (ρ) m times = tr(ρ) I d + M α N m-1 M α . . . M α N 1 M α (ρ) m times
.

The definition of P α implies:

M α (ρ) = P α (ρ) -tr(ρ) I d = P ∈Pn 4α(P )ε d 2 P ρP = P ∈Pn 4α(P )ε d 2 N P (ρ)
where we use the notation for the unital quantum channel N P (ρ) = P ρP for all P ∈ P n . So, using the notation N Pm,m-1,...,1,P1 = N Pm N m-1 N Pm-1 . . . N P2 N 1 N P1 , we can develop the quantity we want to upper bound as follows:

E α ( φ| dP m α (ρ) |φ -1) 2 = d 2 E α ( φ| M α N m-1 M α . . . M α N 1 M α (ρ) |φ ) 2 = d 2 E α   P1,...,Pm 4α(P 1 )ε d 2 • • • 4α(P m )ε d 2 φ| N Pm N m-1 N Pm-1 . . . N P2 N 1 N P1 (ρ) |φ   2 = (4ε) 2m d 4m-2 P,Q∈Pn E α (α(P 1 ) • • • α(P m )α(Q 1 ) • • • α(Q m )) φ| N Pm,m-1,...,1,P1 (ρ) |φ φ| N Qm,m-1,...,1,Q1 (ρ) |φ . If Q 1 , σ(Q 1 ) / ∈ {P 1 , . . . , P m , Q 2 , . . . , Q m } the expected value E α (α(P 1 ) • • • α(P m )α(Q 1 ) • • • α(Q m )
) is 0, otherwise, we can upper bound each term inside the sum by 1 and we count the number of these terms. Moreover we can gain two factors d by using the properties of Pauli group for m ≥ 3. For example, suppose that Q 1 = P 1 , we have P ∈Pn N P (ρ) = P ∈Pn P ρP = dtr(ρ)I hence for m ≥ 3:

(4ε) 2m d 4m-2 P,Q:Q1=P1 E α (α(P 1 ) • • • α(P m )α(Q 1 ) • • • α(Q m )) φ| N Pm,m-1,...,1,P1 (ρ) |φ φ| N Qm,m-1,...,1,Q1 (ρ) |φ ≤ (4ε) 2m d 4m-2 P,Q:Q1=P1 φ| N Pm,m-1,...,1,P1 (ρ) |φ φ| N Qm,m-1,...,1,Q1 (ρ) |φ = (4ε) 2m d 4m-2 P,Q<m:Q1=P1 φ| Pm N Pm,m-1,...,1,P1 (ρ) |φ φ| Qm N Qm,m-1,...,1,Q1 (ρ) |φ = (4ε) 2m d 4m-2 P,Q<m:Q1=P1 φ| dtr(N m-1,...,1,P1 (ρ))I |φ φ| dtr(N m-1,...,1,Q1 (ρ))I |φ = (4ε) 2m d 4m-2 P,Q<m:Q1=P1 d 2 = (4ε) 2m d 4m-2 (d 2 ) 2m-3 d 2 = (4ε) 2m d 2 .
Since we have 2(2m -1) possibilities for Q 1 , σ(Q 1 ) ∈ {P 1 , . . . , P m , Q 2 , . . . , Q m }, we conclude that:

E α ( φ| dP m α (ρ) |φ -1) 2 ≤ 2(2m -1) (4ε) 2m d 2 ≤ 4m (4ε) 2m d 2 .
Now, if m = 2, we can have Q 1 = Q 2 and therefore we can't gain a factor d when summing over Q 2 . In this case, we obtain instead an upper bound: Using the inequalities 4 and the fact that for all t ∈ [N ], it∈It λ t it = d, we deduce:

E α φ| dP 2 α (ρ) |φ -1 2 ≤ 6 (4ε) 4 d . M 1 ρ 1 P I 1 I 1 -→ M I1 2 ρ I1 2 P I 2 ... I <N -→ M I<N N ρ I<N N P I N
2 10 t:mt≤2 ε 2 d + 4 t:mt≥3 m t (4ε) 2mt d 2 = Ω(d 2 ).
Therefore we have either t:mt≤2

ε 2 d = Ω(d 2 ) or 4 t:mt≥3 m t (4ε) 2m t d 2
= Ω(d 2 ). Finally, we have either

N = Ω d 3 ε 2 or N t=1 m t = Ω d 4 ε 6 .
This proof relies crucially on the non-adaptiveness of the strategy. This can be seen clearly when simplifying the upper bound of the conditional mutual information in Lemma 3.4. For an adaptive strategy, this upper bound contains large products for which the expectation (under α) can only upper bounded by O(ε 2 ) which implies a lower bound on N similar to Theorem 3.1. In the next section, we explore how to overcome this difficulty in some regime of ε and improve the general lower bound N = Ω(d 2 /ε 2 ).

A lower bound for Pauli channel tomography with adaptive strategies in the high precision regime

In this section, we improve the general lower bound of quantum Pauli channel tomography in Theorem 3.1 for adaptive strategies with one use of the channel each step. In the adaptive setting, a learner could adapt its choices depending on the previous observations. It can prepare a large set of inputs and measurements and thus it potentially has more power to extract information much earlier than its nonadaptive counterpart. With this intuition, we expect that lower bounds for adaptive strategies should be harder to establish. Moreover, in this section, we only consider one use of the channel for each step, i.e., m t = 1. After observing I 1 , . . . , I t at steps 1 to t, the learner would choose an input ρ ≤t t+1 := ρ I1,...,It where the rank one matrices are projectors and the coefficients sum to 1. So, the adaptive algorithm extracts classical information at step t + 1 from the unknown Pauli quantum channel P by first applying P to the input ρ I1,...,It t+1 and then performing a measurement using the POVM M I1,...,It t+1 (see Fig. 3 for an illustration). In this case, it observes i t+1 ∈ I I1,...,It t+1 with a probability given by Born's rule: We prove the following lower bound on the number of steps. Note that because of the assumption m t = 1 for all steps t, the number of steps is the same as the number of channel uses.

Theorem 5.1. Let ε ≤ 1/(20d). Adaptive strategies for the problem of Pauli channel tomography using incoherent measurements require a number of steps satisfying:

N = Ω d 5/2 ε 2 .
Furthermore, any adaptive strategy that uses O(d 2 /ε 2 ) memory requires a number of steps N satisfying

N = Ω d 3 ε 2 . ( 5
)
In this Theorem, we show that we can improve on the general lower bound of Theorem 3.1 by an exponential factor of number of qubits if the precision parameter ε is small enough. However, this lower bound could be as well not optimal so it remains either to improve it to match the non-adaptive upper bound of [START_REF] Flammia | Efficient estimation of pauli channels[END_REF] or to propose an adaptive algorithm with a number of steps matching this lower bound. With the same proof, we can generalize this lower bound to adaptive algorithms with limited memory. Any strategy that adapts on at most H ε 2 previous observations for the problem of Pauli channel tomography using incoherent measurements requires a number of steps N = Ω min

d 4 √ Hε 2 , d 5 Hε 2 , d 3 ε 2
. For instance, if the algorithm can only adapt its input state and measurement device on the previous d 2 ε 2 observations then it requires N = Ω d 3 ε 2 steps to correctly approximate the unknown Pauli channel. The remaining of this Section is reserved to the proof of this Theorem.

Construction of the family F We start by constructing a family of Pauli quantum channels that is Ω(ε)-separated. The elements of this family would have the following form, for all x ∈ F = 1, M : Q∈Pn α(Q) and {α(P )} P are d 2 random variables i.i.d. as N (0, 1) and p x (P ) = 1+2 αx(P )εd/ αx 2 d 2

. It is not difficult to check that {p x } x are valid probabilities for ε ≤ 1/4d. Indeed, for all P ∈ P n we have |α(P )| ≤ 2 α 2 so for ε ≤ 1/4d we have 1 + 2α x (P )εd/ α x 2 ∈ [0, 2] thus p x (P ) ∈ [0, 2/d 2 ] ⊂ [0, 1) for d ≥ 2. Moreover, we claim that: Lemma 5.2. Let β be an independent and identically distributed copy of α. We have:

P (TV(p α , p β ) < ε/5) ≤ e -Ω(d 2 ) .
If this claim is true, then a union bound permits to show the existence of the family with the property M = exp(Ω(d 2 )). Let us prove first a lower bound on the expected TV distance between p α and p β .

Lemma 5.3. Let β be an independent and identically distributed copy of α. We have:

E (TV(p α , p β )) ≥ 7ε 20 .
Proof. We start by writing:

TV(p α , p β ) = ε d P ∈Pn α(P ) α 2 - β(P ) β 2 ≥ ε d P ∈Pn α(P ) α 2 - β(P ) β 2 - ε d Q∈Pn α(Q) α 2 - Q∈Pn β(Q) β 2
where we use the triangle inequality. We can upper bound the expectation of the second difference using the fact that α 2 is independent of {α(P )/ α 2 } P :

E ε d Q∈Pn α(Q) α 2 - Q∈Pn β(Q) β 2 ≤ 2E ε d P ∈Pn α(P ) α 2 = 2ε d E P ∈Pn α(P ) E ( α 2 ) ≤ 4ε d .
Indeed, by the Cauchy-Schwartz inequality:

E P ∈Pn α(P ) ≤ E   P ∈Pn α(P ) 2   = d
and by the Hölder's inequality:

E ( α 2 ) ≥ E ( α 2 2 ) 3 E ( α 4 2 ) = (d 2 ) 3 d 2 (d 2 -1) + 3d 2 ≥ d 2 .
We move to lower bound the expectation of the first difference using Hölder's inequality:

E ε d P ∈Pn α(P ) α 2 - β(P ) β 2 = εdE α(P ) α 2 - β(P ) β 2 ≥ εd E α(P ) α 2 -β(P ) β 2 2 3 E α(P ) α 2 -β(P ) β 2 4 ≥ εd 8/d 6 48/d 4 ≥ 2ε 5 .
because we can compute the numerator using the fact that α 2 is independent of {α(P )/ α 2 } P :

E α(P ) α 2 - β(P ) β 2 2 = 2E α(P ) 2 α 2 2 -2E α(P )β(P ) α 2 β 2 = 2 E α(P ) 2 E ( α 2 2 ) = 2 d 2 .
Moreover, we can bound the denominator by Hölder's inequality and the fact that α 2 is independent of {α(P )/ α 2 } P :

E α(P ) α 2 - β(P ) β 2 4 ≤ 16E α(P ) 4 α 4 2 = 16 E α(P ) 4 E ( α 4 2 ) = 48 d 2 (d 2 -1) + 3d 2 ≤ 48 d 4 .
Therefore the expected value of the TV-distance satisfies:

E (TV(p α , p β )) ≥ 2ε 5 - 4ε d ≥ 7ε 20 .
Once we have a lower bound on the expected value of TV(p α , p β ), we can proceed to prove Lemma 5.2.

Proof. We want to show that the function TV(p α , p β ) concentrates around its mean. Let (α, γ) and (β, δ) be two couples of standard Gaussian vectors. By the reverse triangle inequality we have:

| TV(p α , p γ ) -TV(p β , p δ )| ≤ | TV(p α , p γ ) -TV(p γ , p β )| + | TV(p γ , p β ) -TV(p β , p δ )| ≤ TV(p α , p β ) + TV(p γ , p δ ).
On the set

E 2 = {(α, β) : α 2 , β 2 > d/4} we have TV(p α , p β ) ≤ ε d P ∈Pn α(P ) α 2 - β(P ) β 2 + ε d P ∈Pn α(P ) α 2 - β(P ) β 2 ≤ 2ε d P ∈Pn α(P ) α 2 - β(P ) β 2 ≤ 2ε d P ∈Pn α(P ) α 2 - α(P ) β 2 + 2ε d P ∈Pn α(P ) β 2 - β(P ) β 2 ≤ 2ε d P ∈Pn |α(P )| α 2 -β 2 α 2 β 2 + 2ε d P ∈Pn α(P ) -β(P ) β 2 = 2ε d α 1 α 2 -β 2 α 2 β 2 + 2ε d α -β 1 β 2 ≤ 2ε α 2 α -β 2 α 2 β 2 + 2ε α -β 2 β 2 ≤ 2ε 4 d α -β 2 + 2ε α -β 2 4 d = 16ε d α -β 2 .
Here we used that α 1 ≤ d α 2 , as α is a vector with d 2 entries, and our assumption on the norms in the last line. Hence, on the set E 4 , by using the inequality

x + y ≤ √ 2 x 2 + y 2 : | TV(p α , p γ ) -TV(p β , p δ )| ≤ TV(p α , p β ) + TV(p γ , p δ ) ≤ 16ε d α -β 2 + 16ε d γ -δ 2 ≤ 16 √ 2ε d α -β 2 2 + γ -δ 2 2 =: L (α, γ) -(β, δ) 2 .
Moreover, the function TV(p α , p β ) can be extended to an L-Lipschitz function on the whole set R d 2 ×R d 2 using the following definition for every (α, β) ∈ R d 2 × R d 2 (Kirszbraun theorem, see e.g. [START_REF] Mattila | Geometry of sets and measures in euclidean spaces: fractals and rectifiability[END_REF]):

f (α, β) = inf (γ,δ)∈E 2 {TV(p γ , p δ ) + L (α, β) -(γ, δ) 2 }.
We can control the expected value of f using the lower bound on the expected value of TV(p α , p β ) (Lemma 5.3) as follows:

E (f ) = E (f 1 E 2 ) + E f 1 (E 2 ) c ≥ E (f 1 E 2 ) ≥ 7ε 20 -8ε exp(-Ω(d 2 )) ≥ 3ε 10 because |E (f (α, β)1 E 2 ) -E (TV(p α , p β )) | = E TV(p α , p β )1 (E 2 ) c ≤ 8εP (E c ) ≤ 8ε exp(-Ω(d 2 ))
where we have used the fact that TV(p α , p β ) ≤ 4ε and P (E c ) = P ( α 2 ≤ d/4) ≤ exp(-Ω(d 2 )). Indeed, we can apply the concentration of Lipschitz functions of Gaussian random variables (Wainwright, 2019, Theorem 2.26) for the function α → α 2 which is 1-Lipschitz by the triangle inequality:

| α 2 -β 2 | ≤ α -β 2
and its expectation satisfies E ( α 2 ) ≥ d/2, thus:

P (E c ) = P ( α 2 ≤ d/4) = P ( α 2 -E ( α 2 ) ≤ -d/4) ≤ exp(-Ω(d 2 )).
We proceed with the same strategy for the function f which is L-Lipschitz where L = 16 √ 2ε

d . By the concentration of Lipschitz functions of Gaussian random variables (Wainwright, 2019, Theorem 2.26), we obtain for all s ≥ 0 :

P (|f -E (f ) | > s) ≤ exp - cd 2 s 2 ε 2
with c > 0 a constant. Then, we can deduce the upper bound on the probability:

P (TV(p α , p β ) < ε/5) = P TV(p α , p β ) < ε/5, (α, β) ∈ E 2 + P TV(p α , p β ) < ε/5, (α, β) / ∈ E 2 ≤ P f (α, β) < ε/5, (α, β) ∈ E 2 + P (α, β) / ∈ E 2 ≤ P f (α, β) -E (f ) < ε/5 -3ε/10, (α, β) ∈ E 2 + 2P (α / ∈ E) ≤ P (f (α, β) -E (f ) < -ε/10) + 2P (α / ∈ E) ≤ 3 exp(-Ω(d 2 )) ≤ exp(-Ω(d 2 )).
Hence we construct an ε/5-separated family F of cardinal Ω(d 2 ). By changing ε ↔ 5ε in the definition of {P x } x∈F , the family becomes ε-separated for ε ≤ 1/(20d).

Once the family F is constructed, we can use it to encode a message in 1, M to a quantum Pauli channel P = P x in the family F. The decoder receives this unknown quantum Pauli channel, chooses its inputs states and performs adaptive incoherent measurements and learns it. Therefore a 1/3-correct algorithm can decode with a probability of failure at most 1/3 by finding the closest quantum Pauli channel in the family F to the channel approximated by the algorithm. By Fano's inequality, the encoder and decoder should share at least Ω(log(M )) = Ω(d 2 ) nats of information.

Lemma 5.4 [START_REF] Fano | Transmission of information: A statistical theory of communications[END_REF]). The mutual information between the encoder and the decoder is at least

I ≥ 2/3 log(M ) -log(2) ≥ Ω(d 2 ).
Upper bound on the mutual information Since we have a lower bound on the mutual information, it remains to prove an upper bound depending on the number of steps N and the precision ε. For this, let us denote by X the uniform random variable on the set 1, M representing the encoder and I 1 , . . . , I N the observations of the decoder or the 1/3-correct algorithm. The Data-Processing inequality implies:

I ≤ I(X : I 1 , . . . , I N ).
By upper bounding the mutual information between X and I 1 , . . . , I N and using a contradiction argument, we prove Theorem 5.1 which we recall:

Theorem. Let ε ≤ 1/(20d). Adaptive strategies for the problem of Pauli channel tomography using incoherent measurements requires a number of steps satisfying:

N = Ω d 5/2 ε 2 .
Proof. Recall that we can write the mutual information as: I(X :

I 1 , . . . , I N ) = N k=1 I(X : I k |I ≤k-1 ). Fix k ∈ [N ]
, by Lemma 3.4, we can upper bound the conditional mutual information:

I(X : I k |I ≤k-1 ) ≤ 3E x E i∼q ≤k-1 i k λ k i k d (u k,x i k ) 2
where we use the notation:

u k,x i k = φ k i k (dP x (ρ k ) -I) φ k i k = φ k i k P ∈Pn 2α x (P )ε α x 2 P ρ k P φ k i k = P ∈Pn 2α x (P )ε α x 2 φ k i k P ρ k P φ k i k - P,Q∈Pn 2α x (Q)ε d 2 α x 2 φ k i k P ρ k P φ k i k = P ∈Pn 2α x (P )ε α x 2 φ k i k P ρ k P φ k i k - P ∈Pn 2α x (P )ε d α x 2 .
Note that for adaptive strategies the vectors

φ k i k = φ k i k (i 1 , . . . , i k-1
) and the states ρ k = ρ k (i 1 , . . . , i k-1 ) depend on the previous observations (i 1 , . . . , i k-1 ) for all k ∈ [N ]. Similarly, we denote:

u k,α i k = P ∈Pn 2α(P )ε α 2 φ k i k P ρ k P φ k i k - P ∈Pn 2α(P )ε d α 2 = 2 α 2 P ∈Pn α(P )ε φ k i k P (ρ k -I/d)P φ k i k . We have i k λ k i k u k,x i k = tr (dP x (ρ k ) -I) = 0 as i k λ k i k u k,α i k = P ∈Pn 2α x (P )ε α x 2 tr(P ρ k P ) - P ∈Pn 2α x (P )ε α x 2 = P ∈Pn 2α x (P )ε α x 2 - P ∈Pn 2α x (P )ε α x 2 = 0.
Note that the cardinal of the constructed family M = |F| is of order exp(Ω(d 2 )), so every mean in x can be approximated by the expected value for α following the distribution explained in the construction, the difference will be, by Hoeffding's inequality, of order exp(-Ω(d 2 )) so negligible (see the proof of Proposition C.1 for a detailed justification of this claim, note that the error probability can be absorbed in the total error probability by adding these inequalities in the construction of the family F). Therefore we obtain the upper bound on the mutual information:

N k=1 I(X : I k |I ≤k-1 ) ≤ 3 N k=1 E x,i∼q ≤k-1 i k λ k i k d (u k,x i k ) 2 = 3 N k=1 1 M M x=1 i1,...,i k-1 k-1 t=1 λ t it 1 + u t,x it d i k λ k i k d (u k,x i k ) 2 ≤ 3 N k=1 E α i1,...,i k-1 k-1 t=1 λ t it 1 + u t,α it d i k λ k i k d (u k,α i k ) 2 + 3N ε 2 exp(-Cd 2 ) (6) = 3 N k=1 E ≤k E α k-1 t=1 1 + u t,α it (u k,α i k ) 2 + 3N ε 2 exp(-Cd 2 )
where we use the notation

E ≤k [X(i 1 , . . . , i k )] := 1 d k i1,...,i k k t=1 λ k i k X(i 1 , . . . , i k ).
Observe that for non-adaptive strategies, we can simplify these large products using the fact u t,α it does not depend on (i 1 , i 2 , . . . , i t-1 ). We obtain in this case an upper bound on the mutual information:

I(X : I 1 , . . . , I N ) ≤ 3 N k=1 E k E α (u k,α i k ) 2 + 3N ε 2 exp(-Cd 2 ).
For this expression, using methods similar to the proof of Theorem 4.1, one can obtain a bound of the form

E k E α (u k,α i k ) 2 = O( ε 2 d
) which would lead to a lower bound of Ω( d 3 ε 2 ) as in Theorem 4.1. However, for adaptive strategies, we can not simplify the terms (1 + u t,α it ) for t < k because (u k,α i k ) 2 depends on the previous observations (i 1 , . . . , i k-1 ). For this reason, we use Gaussian integration by parts (see Theorem A.3) to break the dependency between the variables in the last expectation. Recall that for all t, i t , ρt = ρ t -I/d and:

u t,α it = 2 α 2 P ∈Pn α(P )ε φ t it P ρt P φ t it .
Using the fact that α 2 is independent of {α(P )/ α 2 } P , we can write:

E α 2 2 E k-1 t=1 1 + u t,α it (u k,α i k ) 2 = 2ε P ∈Pn φ k i k P ρk P φ k i k E α 2 2 E α(P ) α 2 u k,α i k k-1 t=1 1 + u t,α it = 2ε P ∈Pn φ k i k P ρk P φ k i k E α(P ) α 2 u k,α i k k-1 t=1 1 + u t,α it = 2ε P ∈Pn φ k i k P ρk P φ k i k E (α(P )F (α)) ,
where

F (α) = α 2 u k,α i k k-1 t=1 1 + u t,α it .
Gaussian integration by parts (see Theorem A.3) implies:

E (α(P )F (α)) = E (∂ P F (α)) = 2ε φ k i k P ρk P φ k i k E k-1 t=1 1 + u t,α it + k-1 s=1 E   α 2 u k,α i k ∂ P u s,α is t∈[k-1]\s 1 + u t,α it  
Moreover, we have

α 2 ∂ P u s,α is = 2 φ s is P ρs P φ s is ε α 2 -∂ P α 2 P ∈Pn α(P ) φ s is P ρs P φ s is ε α 2 = 2 φ s is P ρs P φ s is ε - 1 α 2 α(P )u s,α
is hence:

E ≤k E k-1 t=1 1 + u t,α it (u k,α i k ) 2 = E ≤k 2ε d 2 P ∈Pn φ k i k P ρk P φ k i k E (α(P )F (α)) = E ≤k 4ε 2 d 2 P ∈Pn φ k i k P ρk P φ k i k 2 E k-1 t=1 1 + u t,α it (L1) + E ≤k 4ε 2 d 2 P ∈Pn k-1 s=1 φ k i k P ρk P φ k i k φ s is P ρs P φ s is E   u k,α i k t∈[k-1]\s 1 + u t,α it   (L2) -E ≤k 2ε d 2 P ∈Pn φ k i k P ρk P φ k i k k-1 s=1 E   α(P ) α 2 u k,α i k u s,α is t∈[k-1]\s 1 + u t,α it   . (L3)
We analyze the latter expressions line by line. Our goal is to upper bound these terms better with some expression improving the naive upper bound O(ε 2 ) on the conditional mutual information. Let us start by line (L1), we have

P ∈Pn 1 d i k λ k i k φ k i k P ρk P φ k i k 2 ≤ P ∈Pn 1 d • tr(P ρ2 k P ) = P ∈Pn 1 d • tr(ρ 2 k ) ≤ d, so using 1 d it λ k i k (1 + u t,α
it ) = 1 we can upper bound the line (L1) as follows:

(L1) ≤ E ≤k-1 4ε 2 d E k-1 t=1 1 + u t,α it = 4ε 2 d .
This upper bound has the same order as for non-adaptive strategies. So we expect that the contribution of line (L1) will not affect much the overall upper bound on the conditional mutual information. Next we move to line (L3), first we show a useful inequality:

Lemma 5.5. Let t ∈ [N ]. Recall that u t,α it = 2 α 2
P ∈Pn α(P )ε φ t it P ρt P φ t it . We have:

1 d it λ t it (u t,α it ) 2 ≤ 16ε 2 .
Observe that if we apply this upper bound directly on the expression of the conditional mutual information (Lemma 3.4) we obtain an upper bound I = O(N ε 2 ) which leads to a lower bound N = Ω(d 2 /ε 2 ) similar to Theorem 3.1. Still this Lemma will be useful for controlling intermediate expressions appearing for the upper bound of line (L3).

Proof. We use the fact that every M can be written as

α(P ) 2 = 16dε 2 .
In the previous inequality, we used that for all R ∈ P n : we can write R = i λ i |φ i φ i | where the eigenvalues {λ i } i have absolute values 1, then by the triangle inequality:

|tr(Rρ)| = i λ i tr(|φ i φ i | ρ) ≤ i |λ i tr(|φ i φ i | ρ)| ≤ i |tr(|φ i φ i | (ρ -I/d))| ≤ i |tr(|φ i φ i | ρ)| + i |tr(|φ i φ i | I/d))| = tr(ρ) + tr(I/d) = 2.
Observe that the condition ε ≤ 1/(4d) implies that for all t ∈ [N ] and i t ∈ I t we have 1 + u t,α it ≥ 1/16

and recall that

E k (1 + u t,α it ) = 1 d it λ t it (1 + u t,α it ) = 1.
Therefore, (L3) can be controlled as follows:

(L3) = -E ≤k 1 d 2 k-1 s=1 E   u k,α i k 2 u s,α is t∈[k-1]\s 1 + u t,α it   = 1 d 2 E ≤k   -E   s<k u s,α is (u k,α i k ) 2 t∈[k-1]\s 1 + u t,α it     ≤ 1 d 2 E ≤k   E   s<k u s,α is (u k,α i k ) 2 t∈[k-1]\s 1 + u t,α it     ≤ 16ε 2 d 2 E <k E s<k u s,α is (1 + u s,α is ) t<k 1 + u t,α it (Lemma. 5.5) ≤ 16ε 2 d 2 E α E <k s<k u s,α is (1 + u s,α is ) 2 t<k 1 + u t,α it E α E <k t<k 1 + u t,α it (Cauchy-Schwartz) ≤ 16ε 2 d 2 E α E <k s,r<k u s,α is (1 + u s,α is ) • u r,α ir (1 + u r,α ir ) t<k 1 + u t,α it E <k t<k 1 + u t,α it = ≤ 16ε 2 d 2 E α E <k s<k (u s,α is ) 2 (1 + u s,α is ) 2 t<k 1 + u t,α it (E ≤max{s,r} u s,α is u r,α ir = 0 if s = r) ≤ 64ε 2 d 2 E α E <k s<k (u s,α is ) 2 t∈[k-1]\s 1 + u t,α it ≤ √ k 256ε 3 d 2 , (1 + u t,α it ≥ 1/16 ⇐ ε ≤ 1/4d)
where we use also Lemma 5.5 for the last inequality. Indeed, we can simplify the expectation as follows

E <k s<k (u s,α is ) 2 t∈[k-1]\s 1 + u t,α it = s<k E <k (u s,α is ) 2 t∈[k-1]\s 1 + u t,α it = s<k E ≤s (u s,α is ) 2 t∈[s-1] 1 + u t,α it ≤ s<k E ≤s-1 16ε 2 t∈[s-1] 1 + u t,α it (Lemma 5.5) = s<k 16ε 2 ≤ 16ε 2 k.
Finally, we control the line (L2) which is more involved. Let us adopt the notation for s, k ∈ [N ]:

M s,k = P ∈Pn P ρk P φ s is P ρs P φ s is = 1 d 2 P,Q,R∈Pn tr(ρ k Q)tr(ρ s R)P QP φ s is P RP φ s is = 1 d 2 P,Q,R∈Pn tr(ρ k Q)tr(ρ s R)(-1) P.(QR) Q φ s is R φ s is = Q∈Pn tr(ρ k Q)tr(ρ s Q) φ s is Q φ s is Q (Lemma A.1)
so that we can write P ∈Pn φ k

i k P ρk P φ k i k φ s is P ρs P φ s is = tr( φ k i k φ k i k M s,k ). Also we use the notation Ψ k = E ≤k E u k,α i k 2 t<k 1 + u t,α
it so that we have the (in)equalities:

(L2) = 4ε 2 d 2 E ≤k E   k-1 s=1 tr( φ k i k φ k i k M s,k )u k,α i k t∈[k-1]\s 1 + u t,α it   = 4ε 2 d 2 E ≤k E   tr φ k i k φ k i k k-1 s=1 M s,k (1 + u s,α is ) u k,α i k t≤k-1 1 + u t,α it   ≤ 4ε 2 d 2 E ≤k E   tr φ k i k φ k i k k-1 s=1 M s,k (1 + u s,α is ) 2 t≤k-1 1 + u t,α it   Ψ k (Cauchy-Schwartz) ≤ 4ε 2 d 2 E ≤k E   tr   φ k i k φ k i k k-1 s=1 M s,k (1 + u s,α is ) 2   t≤k-1 1 + u t,α it   Ψ k (Cauchy-Schwartz) = 4ε 2 d 2 1 d E ≤k-1 E   tr   k-1 s=1 M s,k (1 + u s,α is ) 2   t≤k-1 1 + u t,α it   Ψ k .
From the definition of M s,k we can write that for s, t < k

tr(M s,k M t,k ) = d Q∈Pn tr(ρ k Q) 2 tr(ρ s Q)tr(ρ t Q) φ s is Q φ s is φ t it Q φ t it . Hence tr k-1 s=1 M s,k (1 + u s,α is ) 2 = s,t<k d Q∈Pn tr(ρ k Q) 2 tr(ρ s Q)tr(ρ t Q) φ s is Q φ s is φ t it Q φ t it (1 + u s,α is )(1 + u t,α it ) = d Q∈Pn tr(ρ k Q) 2 s<k tr(ρ s Q) φ s is Q φ s is (1 + u s,α is ) 2 ≤ 4d Q∈Pn s<k tr(ρ s Q) φ s is Q φ s is (1 + u s,α is ) 2
note that this step is crucial because ρ k depends on (i 1 , . . . , i k-1 ) so we need to avoid it in order to simplify with the expectations E t for t < k. When we want to simplify the expectation

E ≤k-1 E tr k-1 s=1 M s,k (1+u s,α is ) 2 t≤k-1 1 + u t,α it
and we expand the square of the latter expression, we can see that if s 1 < s 2 (or s 1 > s 2 ), we'll get 0 because we can simplify the terms (1 + u t,α it ) in the product for t > s 2 , the term (1 + u s2,α is 2

) is simplified with the denominator so we can take safely the expectation under E s2 :

E s2 tr(ρ s2 Q) φ s2 is 2 Q φ s2 is 2 = 1 d is 2 tr(ρ s2 Q)λ s2 is 2 φ s2 is 2 Q φ s2 is 2 = tr(ρ s2 Q)tr(Q) = 0 because tr(Q) = 0 unless Q = I for which tr(ρ s2 Q) = tr(ρ s2 ) = tr(ρ s2 -I/d) = 0. Therefore (L2) ≤ 4ε 2 d 2 1 d E ≤k-1 E   tr k-1 s=1 M s,k (1 + u s,α is ) 2 t≤k-1 1 + u t,α it   Ψ k ≤ 4ε 2 d 2 1 d E ≤k-1 E   4d Q∈Pn s<k tr(ρ s Q) φ s is Q φ s is (1 + u s,α is ) 2 t≤k-1 1 + u t,α it   Ψ k ≤ 4ε 2 d 2 s<k 16 Q∈Pn E ≤s tr(ρ s Q) 2 φ s is Q φ s is 2 E   t≤s-1 1 + u t,α it   Ψ k (1 + u s,α is ) ≥ 1 16 ≤ 4ε 2 d 2 s<k 64E ≤s Q∈Pn φ s is Q φ s is φ s is Q φ s is E   t≤s-1 1 + u t,α it   Ψ k (|tr(ρ s Q)| ≤ 2) = 4ε 2 d 2 s<k 64E ≤s φ s is dtr( φ s is φ s is )I φ s is E   t≤s-1 1 + u t,α it   Ψ k (Lemma A.2) ≤ 32ε 2 d √ d √ k Ψ k .
We have proven so far, for all k ≤ N :

Ψ k ≤ 4ε 2 d + 256 √ k ε 3 d 2 + 32ε 2 d √ d √ k Ψ k . (7)
The first term of the upper bound can be seen as a non-adaptive contribution. The second one can be thought as a geometric mean of the first and third terms. The last term represents essentially the contribution of the adaptivity. Our final stage of the proof is to use these recurrence inequalities to prove the lower bound by a contradiction argument.

Recall that

Ψ k = E ≤k E u k,α i k 2 t<k 1 + u t,α it and N k=1 I(X : I k |I <k ) ≤ 3 N k=1 Ψ k + 3N ε 2 exp(-Cd 2
). We suppose that N ≤ c d 5/2 ε 2 for sufficiently small c > 0. We know that from Lemma 5.4 and Lemma 3.4

c 0 d 2 ≤ I(X : Y ) ≤ 3 k≤N Ψ k + 3N ε 2 exp(-Cd 2 ).
So k≤N Ψ k ≥ c d 2 (for example c = c 0 /4), on the other hand the inequality (7) implies:

k Ψ k ≤ k 4ε 2 d + 256 ε 3 d 2 √ k + 32 ε 2 √ k d √ d Ψ k ≤ 4 N ε 2 d + 256 N ε 3 d 2 √ N + 32 k ε 2 √ k d √ d Ψ k ≤ 4 N ε 2 √ c d 2 k≤N Ψ k + 256 N ε 2 d 2 cd 5/2 + 32 ε 2 d √ d k k k Ψ k (Cauchy-Schwartz) ≤ 8 √ c d + 512 √ c d 1/4 + 32 ε 2 d √ d k k k Ψ k ≤ C ε 2 d √ d N k Ψ k
where C is a universal constant. Therefore:

k Ψ k ≤ C 2 N 2 ε 4 d 3 ≤ C 2 c 2 d 2 Hence c 0 d 2 ≤ I(X : Y ) ≤ k≤N 3Ψ k + 3N ε 2 exp(-Cd 2 ) ≤ 6C 2 c 2 d 2
which gives the contradiction for c √ c 0 /C . Finally we deduce N = Ω(d 5/2 /ε 2 ) and we conclude the proof of Theorem 5.1. If the adaptive algorithm has a memory of O(H/ε 2 ), the previous inequalities imply for all 1 ≤ k ≤ N :

k Ψ k ≤ k 4ε 2 d + 256 √ H ε 2 d 2 + 32ε d √ d √ H Ψ k ≤ k 4ε 2 d + 256 √ H ε 2 d 2 + (32ε) 2 H d 3 + Ψ k 2
where we use AM-GM inequality, hence we deduce:

c 0 d 2 ≤ I(X : Y ) ≤ k 3Ψ k + 3N ε 2 exp(-Cd 2 ) ≤ 30ε 2 N d + 6 • 256 √ H ε 2 N d 2 + 6 • (32ε) 2 HN d 3
and finally we obtain:

N = Ω min d 4 √ Hε 2 , d 5 Hε 2 , d 3 ε 2 .
For H = O(d 2 ), this gives Eq. ( 5).

Conclusion and open problems

We have provided lower bounds for Pauli channel tomography in the diamond norm using independent strategies for both adaptive and non-adaptive strategies. In particular, we have shown that the number of measurements should be at least Ω(d 3 /ε 2 ) in the non-adaptive setting and Ω(d 2.5 /ε 2 ) in the adaptive setting. We would like to finish with three interesting directions. Finding the optimal complexity of Pauli channel tomography using adaptive incoherent measurements remains an open question. We conjecture this complexity to be Θ(d 3 /ε 2 ) since we remark that in many situations the adaptive strategies cannot overcome the non-adaptive ones. Furthermore, we already obtained a Θ(d 3 /ε 2 ) bound for adaptive strategies in the high precision and sub-exponential memory regime, further evidence of this bound. Moreover, since [START_REF] Chen | Quantum advantages for pauli channel estimation[END_REF] established the optimal complexity for estimating the eigenvalues of a Pauli channel in the l ∞ -norm using ancilla-assisted non-adaptive independent strategies, it would be interesting to find the optimal complexity to learn a Pauli channel in the diamond norm when the algorithm can use k-qubit ancilla for k ≤ n. measurements in Theorem 4.1 with one use per step, this algorithm is thus optimal up to a logarithmic factor. Note that we only add this part for completeness and we don't claim any new contribution, all the proofs are similar to those in the mentioned references.

Recall the set of Pauli operators P n = {I, X, Y, Z} ⊗n . Let S be a subset of P n , we define the commutant of S as the set of Pauli operators that commute with every element in S: C S = {P ∈ P n : ∀Q ∈ S, P Q = QP }.

Before stating the algorithm, we start by some important Lemmas we need:

Lemma B.1. P n can be covered by d + 1 stabilizer (Abelian) groups G 1 , . . . , G d+1 satisfying for all i = j:

• |G i | = d, • C Gi = G i , • G i ∩ G j = {I}.
The proof is taken from [START_REF] Bandyopadhyay | A new proof for the existence of mutually unbiased bases[END_REF] and [START_REF] Wootters | Optimal state-determination by mutually unbiased[END_REF].

Proof. Here we use the correspondence between P n and Z 2 2 n Z 2n 2 . We can encode:

I → (0, 0) ∈ Z 2 2 , X → (1, 0) ∈ Z 2 2 , Y → (1, 1) ∈ Z 2
2 , Z → (0, 1) ∈ Z 2 2 and we generalize to P n by concatenating the encoding of each tensor. We define the inner product of a = (a 1 , a 2 ), b = (b 1 , b 2 ) ∈ Z 2 2 as follows:

a × b = a 1 b 2 + a 2 b 1 mod (2).

We generalize to a, b ∈ Z 2 2 n :

a × b = a 1 × b 1 + • • • + a n × b n mod (2).
It is not difficult to see that P and Q commute iff their corresponding images a and b have inner product 0. We group the first coordinates together then the second coordinates by using the isomorphism Z 2 2 n (Z n 2 ) 2 : a → (α|β) = (((a 1 ) 1 , . . . (a n ) 1 )|((a 1 ) 2 , . . . (a n ) 2 ). Moreover, by specifying an n × (2n) matrix (A|B) we can construct the corresponding set of Pauli operators as the preimage of the linear combinations of {(A i |B i )} i where M i denotes the i th row of the matrix M . For instance, the corresponding set of (0 n |I n ) is the Z only Pauli operators. The partition we are looking for will be given by {G i } d+1 i=1 = {{1} ∪ C i } d+1 i=1 [START_REF] Bandyopadhyay | A new proof for the existence of mutually unbiased bases[END_REF] where {C i } d+1 i=1 are the sets of non identity Pauli operators corresponding to matrices of the form: (0 n |I n ), (I n |A 1 ), . . . , (I n |A d ).

It can be shown that in order to have G i a stabilizer group, it is sufficient to have A i a symmetric matrix and |C i | = d -1. The former condition implies that for all k, l ∈ [n], the preimages of (I n |A i ) k and (I n |A i ) l commute. Indeed, (I n |A i ) k × (I n |A i ) l = (A i ) k,l + (A i ) l,k = 0 mod (2). The latter condition is satisfied since the matrix (I n |A i ) has rank n and thus generates 2 n -1 non identity Pauli operators (the preimages of n j=1 α j (I n |A i ) j where {α j } j∈[n] ∈ {0, 1} n \ {0} ). Also, the condition of |C i | = d -1 implies that G i = {1} ∪ C i is a group, since the maximal cardinal of a stabilizer set is d [START_REF] Bandyopadhyay | A new proof for the existence of mutually unbiased bases[END_REF]. The same argument shows that the commutant of G i is itself. for each P ∈ G. We repeat this procedure for each G ∈ {G 1 , . . . , G d+1 } to estimate all {p(P )} P ∈Pn to within ε/d. The total complexity is thus N = d+1 i=1 N Gi = O d 3 log(d)/ε 2 . Let {q(P )} P ∈Pn the approximations of {p(P )} P ∈Pn given by the empirical means. We can define {q(P )} P ∈Pn as follows:

q(P ) = 1 d 2

Q∈Pn

(-1) Q.P q(Q) so that we have by the Parseval-Plancherel identity: d q -p 2 = q -p 2 = P ∈Pn (q -p) 2 ≤ P ∈Pn (ε/d) 2 = ε.

However, q is not necessarily a probability distribution. The set of probability distributions on P n is convex, hence if we define r as the orthogonal projection on this set, we have:

r -p 2 ≤ q -p 2 ≤ ε/d.
We conclude by the Cauchy-Schwartz inequality that r is a good approximation of p: r -p 1 ≤ d r -p 2 ≤ ε.

C Proof of Ineq. (6)

In this Section, we give the proof of an approximation used in the proof of Theorem 5.1, more precisely in Ineq. ( 6), where we showed that the empirical average over the ensemble of a certain function is well-approximated by its mean.

Proposition C.1. There is a universal constant C > 0 such that with probability at least 9/10 we have: Proof. Let k ∈ [N ]. For x ∈ [M ], let f k (x) be the function:

f k (x) = i1,...,i k-1 k-1 t=1 λ t it 1 + u t,x it d i k λ k i k d (u k,x i k ) 2 .
Similarly we define:

f k (α) = i1,...,i k-1 k-1 t=1 λ t it 1 + u t,α it d i k λ k i k d (u k,α i k ) 2 .
Since for all k ∈ [N ],

x ∈ [M ] and i k ∈ I k , we have (u k,x i k ) 2 ≤ 1,

M

-bounded. Hence Hoeffding's inequality [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] writes:

P N k=1 1 M M x=1 f k (x) -E N k=1 1 M M x=1 f k (x) > s ≤ 2 exp   - 2s 2 M j=1 32N ε 2 M 2   .
Since for all x ∈ [M ] we have E (f k (x)) = E α (f k (α)), we deduce:

P N k=1 1 M M x=1 f k (x) - N k=1 E α (f k (α)) > s ≤ 2 exp - s 2 M 512N 2 ε 4 .
Finally, by taking s = 25N ε 2 log(20)

M , with probability at least 9/10, we have: where C > 0 is a universal constant and we used the fact that M = exp(Ω(d 2 )).

Figure 1 :

 1 Figure 1: Illustration of an adaptive strategy for learning Pauli channel.

Figure 2 :

 2 Figure 2: Illustration of a non-adaptive strategy for learning Pauli channel.

Figure 3 :

 3 Figure 3: Illustration of an adaptive strategy for learning Pauli channel using one channel per step.

t+1

  and a measurement device represented by a POVM M ≤t t+1 := λ I1,..

  because for Q ∈ A G , we have: P1.Q p(P 2 )tr(P 1 P 2 P 3 P 2 ) Therefore if Q ∼ p G and P ∈ G, then:E (-1) Q.P = Q∈A G p G (Q)(-1) Q.P = Q∈A G R∈C G p(R + Q)(-1) (Q+R).P = S∈Pn p(S)(-1) S.P = p(P ) because P ∈ G thus P commutes with R ∈ C G and P n = C G ⊕ A G . Therefore, by Hoeffding's inequality Hoeffding (1963), we can estimates {p(P ) = E Q∼p G (-1) Q.P } P ∈G to within ε/d with N G = log(2d(d + 1))/(2(ε/d) 2 ) = O d 2 log(d)/ε 2 samples to have a probability of error at most δ/(d(d + 1))

  ,α i k ) 2 + N ε 2 exp(-Cd 2 ).

  f k (x) ∈ [0, 16ε 2 ]. Therefore the function

  i k ) 2 + N ε 2 exp(-Cd 2 )

  the POVMs {M t } t∈[N ] which we suppose without loss of generality have the form M t = {λ t

	i |φ t i φ t i |} i∈It where φ t i |φ t i = 1 and i∈It λ t i = d. The output state at step t ∈ [N ] has
	the form:

  M = R∈Pn

																			tr(M R) d	R and Lemma A.1
	it	λ t it (u t,α it ) 2 =	4ε 2 α 2 2 it	λ t it φ t it	P ∈Pn	α(P )P ρt P φ t it	2 ≤	2 α 2 4ε 2	tr	P ∈Pn	α(P )P ρt P	2
		=	4ε 2 α 2 2	tr	P ∈Pn	α(P )	1 d	R∈Pn	tr(R ρt )P RP	2	=	α 2 2 4ε 2	tr	P ∈Pn	α(P )	1 d	R∈Pn	tr(R ρt )(-1) R.P R	2
		=	4ε 2 α 2 2 P,P ,R,R ∈Pn	α(P )α(P )	1 d 2 tr(R ρt )tr(R ρt )(-1) R.P (-1) R .P tr(RR )
		=	4ε 2 α 2 2 P,P ,R∈Pn	α(P )α(P )	1 d	• tr(R ρt ) 2 (-1) R.P (-1) R.P
		=	4ε 2 α 2 2 R∈Pn P ∈Pn	α(P )(-1) R.P	2	1 d	• tr(R ρt ) 2 ≤	16ε 2 α 2 2 P,P ,R∈Pn	α(P )α(P )	1 d	(-1) R.(P P )
		=	16ε 2 α 2 2 P,P ∈Pn	α(P )α(P ) • d • 1 P P =I =	16dε 2 α 2 2 P =P ∈Pn

  Finally, it should be noted that all of the channel constructions used in this work have a very large spectral gap, i.e. are very noisy. It would be interesting to study the sample complexity of Pauli channel tomography in terms of the spectral gap as well. measurements. Annals of Physics, 191 (2), 363-381. Zhong, H. S., Wang, H., Deng, Y. H., Chen, M. C., Peng, L. C., Luo, Y. H., . . . Pan, J. W. (2020, dec). Quantum computational advantage using photons. Science, 370 (6523), 1460-1463. DOI: 10.1126/science.abe8770 B Optimal non-adaptive algorithm for learning a Pauli channel with incoherent measurements In this section, we simplify the algorithm of Flammia and Wallman (2020), and consider only the learning algorithm. In particular, we show that, if we don't have errors in SPAM, only one copy per step is needed. Hence, this algorithm can learn a Pauli channel to within ε in the diamond norm with only O d 3 log(d)

	ε 2
	measurements/steps. Since we have proved the lower bound of Ω d 3 ε 2

in order to have P ∈Pn αx(P ) = 0 and thus a quantum channel for ε ≤ 1/4.

Acknowledgments

Aadil Oufkir thanks Guillaume Aubrun for helpful discussions. This work is part of HQI initiative (www.hqi.fr) and is supported by France 2030 under the French National Research Agency award number "ANR-22-PNCQ-0002". We also acknowledge support from the European Research Council (ERC Grant AlgoQIP, Agreement No. 851716).

A Technical tools A.1 Pauli group properties

In this section, we group some useful properties about the Pauli operators that we need for the proofs in this article.

Lemma A.1. We have for all Q ∈ {I, X, Y, Z} ⊗n :

Proof. It is clear that for Q = I, Q commutes with every P ∈ P n and thus the equality holds. Now, let Q ∈ P n \ {I} and we write Q = Q 1 ⊗ • • • ⊗ Q n where for all i ∈ [n], Q i ∈ {I, X, Y, Z} is a Pauli matrix. By the same decomposition for P ∈ P n , we can write:

where we have used in the third equality the fact that every non identity Pauli matrix Q i commutes only with the identity and itself (so it anti-commutes with the two other Pauli matrices) thus the sum Pi∈{I,X,Y,Z} (-1) Pi.Qi = 0. Lemma A.2. We have for all matrices ρ: Therefore we can simplify the LHS by using the identity P Q = (-1) P.Q QP for all P, Q ∈ P n :

where we have used Lemma A.1 to obtain the fourth equality.

A.2 Gaussian integration by parts

Gaussian integration by parts (see e.g. [START_REF] Van Handel | Probability in high dimension[END_REF]) is a generalization of Isserlis' formula [START_REF] Isserlis | On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables[END_REF].

Theorem A.3. Let (X 1 , . . . , X d ) be a Gaussian vector and f : R d → R be a smooth function. We have:

Now, we want to have

So in order to avoid this situation, we would like to have for all i = j, det(A i -A j ) = 0. Let B 1 , . . . , B n ∈ Z n×n 2 be n symmetric matrices. If we have for all α ∈ Z n 2 \ {0}:

is the expansion of i in the binary basis. These {A i } 2 n i=1 have the wanted conditions. Such construction of {B i } n i=1 can be found in [START_REF] Wootters | Optimal state-determination by mutually unbiased[END_REF]. Let f 1 , . . . , f n be a basis of F 2 n as a vector space over Z 2 . Then we can write for all i, j ∈ [n]:

satisfy the wanted condition [START_REF] Wootters | Optimal state-determination by mutually unbiased[END_REF]. We can verify this, let α ∈ Z n 2 \ {0}, we have:

.

Suppose that det (

i,j x j = 0 therefore:

On the other hand, the definition of y implies j,k,i

i,j x j = 0 finally α = 0 which is a contradiction.

Lemma B.2. Let G ∈ {G 1 , . . . , G d+1 }. Denote by A G = P n /C G , we have P n = G ⊕ P n /G, C A G = P n /G, and

Proof. It is clear that when Q ∈ C G , the identity holds since for all P ∈ G, P.Q = 0. Let Q / ∈ C G , so we can find P ∈ G such that Q.P = 1 i.e. QP = -P Q. Let C (resp. A) be the set of elements of G that commutes (resp. anti commutes) with Q. By the action of P , we have the isomorphism C → A : R → P R. Hence G can be partitioned into two sets C and A of the same size. Therefore:

We have G ∩ P n /G = {I}. Let P ∈ P n and Q ∈ P n /G the class of P . So, P -Q ∈ G and P can be written as

We have

Proof. Since G is an Abelian group we have for all Q ∈ G:

thus it is a rank 1 quantum state. For the second point, we'll show that each term of M G is a rank one projector and their sum is

G is a rank 1 projector. Moreover, by using the fact that

Finally, these two conditions imply that M G is a POVM. Now, we can state a simplified version of the algorithm proposed by [START_REF] Flammia | Efficient estimation of pauli channels[END_REF].

i=1 (-1) Qi.P . end for Define for P ∈ P n , q(P ) = 1 d 2 Q∈Pn (-1) Q.P q(Q). Let r be the orthogonal projection of q on the set of probability distributions on P n . return the Pauli channel R(ρ) = P ∈Pn r(P )P ρP .

Theorem B.4. Algorithm 1 performs O d 3 log(d)/ε 2 ) measurements to learn a Pauli channel to within ε in diamond norm with at least a probability 2/3. The proof is taken from [START_REF] Flammia | Efficient estimation of pauli channels[END_REF].

Proof. If we choose the input ρ G for some stabilizer group G, apply the Pauli channel P and perform the measurement using the POVM M G , the induced probability distribution is given by: