Fundamental questions on robustness and accuracy for classical and quantum learning algorithms Nana Liu Abstract This chapter introduces and investigates some fundamental questions on the relationship between accuracy and robustness in both classical and quantum classification algorithms under noisy and adversarial conditions. We introduce and clarify various definitions of robustness and accuracy, including corrupted-instance robustness accuracy and prediction-change robustness, distinguishing them from conventional accuracy and robustness measures. Through theoretical analysis and toy models, we establish conditions under which trade-offs between accuracy and robustness accuracy arise and identify scenarios where such trade-offs can be avoided. The framework developed highlights the nuanced interplay between model bias, noise characteristics, and perturbation types, including relevant and irrelevant perturbations. We explore the implications of some of these results for incompatible noise, adversarial quantum perturbations, the no free lunch theorem, and suggest future methods to examine these problems from the lens of dynamical systems. I Introduction Realizing the full potential of quantum-enhanced learning necessitates addressing a fundamental and pervasive challenge: the presence of noise and perturbations in both classical and quantum learning systems. Noise in machine learning arises from multiple sources. On one hand, environmental noise—such as hardware imperfections, decoherence, and stochastic fluctuations—can degrade the fidelity of quantum operations and corrupt input data. On the other hand, adversarial perturbations, often small but intentionally crafted changes to input examples, threaten the reliability and security of learning models by causing misclassifications. While noise is frequently viewed as a detrimental factor limiting performance, it can also play beneficial roles, including regularization to improve generalization, enhancement of privacy, and enabling compression when its parameters are carefully controlled. In the context of quantum machine learning, noise plays a dual role: it can be a disruptive influence that impedes algorithmic performance, but also a tool to enhance learning capabilities when harnessed appropriately. This duality raises essential questions about how to evaluate and quantify the robustness of quantum classifiers under realistic noisy conditions. Conventional accuracy measures, defined in noise-free scenarios, fail to capture the stability of model predictions when inputs or models themselves are subject to perturbations. This necessitates the introduction of robustness-specific performance metrics designed for both adversarial and non-adversarial noise environments. This chapter poses and explores some of these fundamental questions by focusing on classification problems under noisy conditions. We begin by systematically categorizing various notions of robustness, including corrupted-instance robustness accuracy, prediction-change robustness, and error-region robustness. We clarify how these definitions differ conceptually and mathematically, and how they relate to other accuracy measures. We also distinguish between relevant perturbations (which alter the true class of an example), and irrelevant perturbations, which do not change the underlying class but may affect model predictions. From some simple examples, we see the role of relevant and irrelevant perturbations trade-offs that can occur between accuracy and robustness accuracy. The central theme of the chapter is the exploration of the trade-off relations between accuracy and robustness accuracy. Through theoretical analysis and simplified illustrative models, we demonstrate conditions under which increasing robustness inevitably sacrifices accuracy, and conversely, when both can be simultaneously optimized without compromise. Key results include general relationships for unbiased and biased classifiers, showing how robustness accuracy depends jointly on accuracy and model robustness properties. We extend the discussion to quantum classification models, examining how quantum noise channels and measurement operators influence these trade-offs. Notably, we analyze noise models such as bit-flip, phase-flip, and depolarization, identifying scenarios where trade-offs appear or vanish. We also discuss adversarial perturbations modeled as quantum channels with bounded trace distance, establishing sufficient conditions for maximal trade-offs between accuracy and robustness accuracy. The chapter highlights how the intrinsic geometry of the data and the hypothesis class, rather than model-specific features alone, dictate these trade-offs. Beyond these core theoretical developments, we explore important practical and conceptual applications of the accuracy-robustness trade-off framework: • Incompatible Noise: We introduce the notion of incompatible noise, where training a model to be robust against one type of noise can reduce robustness against another. We provide explicit examples involving depolarization and bit-flip noise to illustrate this phenomenon, which has significant implications for model design and training strategies. • Adversarial Examples: We rigorously characterize adversarial perturbations in the quantum domain, specifying the conditions under which adversarial noise remains irrelevant (does not change true class) but induces prediction errors. This provides insight into the vulnerability of quantum classifiers and suggests avenues for robust training methods. • No Free Lunch Theorem: The chapter offers a new perspective on the no free lunch theorem by linking it to robustness accuracy. We interpret the theorem’s assertion—that no universally superior model exists—through the lens of perturbations inducing shifts in data distributions, clarifying the relationship between accuracy on one distribution and robustness accuracy on perturbed distributions. We also outline connections to dynamical systems theory, framing machine learning robustness as a question of stability and convergence under perturbations. We discuss the results and present the open questions in the last section. II Definition zoo In studying the performance of models in the presence of environmental as well as adversarial noise, there are many different characterisations of this performance and the sensitivity to these perturbations. We have various measures of robustness, so it is important to first become clear what these different definitions are, as the literature can often confuse these different definitions and this can even lead to contradictory claims, which are in fact not contradictory if one is careful. Table 1 : Classification of types of perturbations Irrelevant perturbation \mathcal{N}_{irr} Relevant perturbation \mathcal{N}_{rel} Small D(\sigma,\mathcal{N}(\sigma))<\epsilon Type I Type II Unrestricted D(\sigma,\mathcal{N}(\sigma)) Type III Type IV Table 2 : Different species of robustness and accuracy Corrupted-instance Prediction-change Error-region Robust loss \tilde{L} Definition 6 L^{*} Definition 7 \bar{L} Definition 8 Robustness accuracy \tilde{A} Definition 11 N/A \bar{A} Definition 13 Robustness N/A A^{*} Definition 12 N/A Robustness to adversarial perturbations \tilde{\Delta} Definition 14 \Delta^{*} Definition 15 \bar{\Delta} Definition 16 II.1 General definitions for classification problems Let \sigma\in\Sigma be input states, where the pair (\sigma,c) is sampled i.i.d from some distribution. The model or hypothesis function h_{\vec{\theta}}:\Sigma\rightarrow C makes the prediction for the classification of states \sigma\in\Sigma into K distinct classes, where C=\{1,...,K\} . We denote the ground truth (true class) of \sigma as c(\sigma) . If the model is deterministic, it means that h is a deterministic function. If the model is probabilistic, then h is a probabilistic function, which gives outputs in C with a certain probability. Definition 1 . (Loss function) A local loss function l_{h}(\sigma,c):(\Sigma,C)\rightarrow\real is a penalty function for the state \sigma when a model h is used. It outputs a small number if h gives the same prediction as c for \sigma , and a larger number number otherwise. A global loss function is the expected value of the local cost function over the distribution (\sigma,c)\sim\mathcal{D} \displaystyle L_{h,\mathcal{D}}=\textbf{E}_{(\sigma,c)\sim\mathcal{D}}l_{h}(\sigma,c) (1) If \mathcal{D}=\mathcal{D}_{train} corresponds only to the set of training data, then this global loss is called empirical loss. If \mathcal{D}=\mathcal{D}_{true} corresponds to the complete underlying distribution for \sigma states, then this global loss is the expected loss (population risk), but in most cases one does not have direct access to \mathcal{D}_{true} . Definition 2 . (Global loss minimisation) If one found the model that minimised the empirical loss (training process), one gets the training loss \min_{h}L_{h,\mathcal{D}_{train}} . The model obtained from this minimisation we denote h_{train} \displaystyle h_{train}=\text{argmin}_{h}L_{h,\mathcal{D}_{train}}. (2) One can also instead minimise the expected loss to get \min_{h}L_{h,\mathcal{D}_{true}} . The model obtained from this minimisation we denote h_{true} \displaystyle h_{true}=\text{argmin}_{h}L_{h,\mathcal{D}_{true}} (3) where h is optimised over some chosen hypothesis class of functions. Definition 3 . (Generalisation and approximation error) The generalisation error (estimation error) G_{L} is defined as the difference \displaystyle G_{L}=L_{h_{train},\mathcal{D}_{true}}-L_{h_{true},\mathcal{D}_{true}}. (4) Therefore, if the training set better approximates the true distribution (e.g. finite data versus infinite data setting), the the generalisation error should approach zero. Note that while it is not in general possible to access L_{h_{train},\mathcal{D}_{true}} directly since \mathcal{D}_{true} is generally unknown, it can be approximated by the testing loss L_{h_{train},\mathcal{D}_{test}} , where \mathcal{D}_{test} is the distribution corresponding to the testing set. The model minimising loss in classification is the Bayes classifier and we can call this value of loss the Bayes loss L_{h_{Bayes},\mathcal{D}_{true}} . Then the approximation error A_{L} refers to the difference \displaystyle A_{L}=L_{h_{true},\mathcal{D}_{true}}-L_{h_{Bayes},\mathcal{D}_{true}}. (5) The approximation error therefore captures how well the hypothesis class that the model is assumed to belong captures the true classification model. Definition 4 . Definition. (Excess risk) To assess how good the model h_{train} is, that is derived from the training process, we are interested then in the excess risk E_{L} \displaystyle E_{L}=L_{h_{train},\mathcal{D}_{true}}-L_{h_{Bayes},\mathcal{D}_{true}}=G_{L}+A_{L}. (6) Note that since \mathcal{D}_{true} is not generally accessible, so the above quantity is approximated by replacing it with a test distribution \mathcal{D}_{test} . II.2 Definitions in presence of perturbations In the following, we want to deal with loss functions in the presence of perturbations to the input states \sigma . There are many definitions which must be clearly distinguished and can potentially have very different behaviour. In the presence of a perturbation, the true class itself can change, depending on the type of perturbation on the test state. this leads us to the following definitions where we distinguish perturbations into two types. Definition 5 . (Relevant and irrelevant perturbations) A relevant perturbation \mathcal{N}_{rel,\sigma} and irrelevant perturbation \mathcal{N}_{irr,\sigma} for the state \sigma are changes to the state such that \displaystyle c(\mathcal{N}_{rel,\sigma}(\sigma))\neq c(\sigma) \displaystyle c(\mathcal{N}_{irr,\sigma}(\sigma))=c(\sigma). (7) We note that if the perturbation is artificially induced by an adversary, it is likely that there is \sigma- dependence in the noise \mathcal{N} . On the other hand, if the perturbations were induced as a result of the environment, it is more likely that the form of the perturbations themselves are independent of the state \sigma . With respect to a specified perturbation, we can also define robust loss, and we identify three kinds. Definition 6 . (Corrupted-instance robust loss) Let the perturbation occur so that \sigma\rightarrow\tilde{\sigma} for each state \sigma\in\Sigma . Then we define the corrupted-instance robust loss (CI-robust loss) as the global loss \tilde{L} \displaystyle\tilde{L}\equiv\textbf{E}_{(\sigma,c)\sim\mathcal{D}}l_{h}(\tilde{\sigma},c_{\sigma}) (8) Definition 7 . (Prediction-change robust loss) Let the perturbation occur so that \sigma\rightarrow\tilde{\sigma} for each state \sigma\in\Sigma . Then we define the prediction-change robust loss (PC-robust loss) as the global loss L^{*} \displaystyle L^{*}\equiv\textbf{E}_{(\sigma,c)\sim\mathcal{D}}l_{h}(\tilde{\sigma},h(\sigma)), (9) where we replace the true class c_{\sigma} with the model prediction h(\sigma) . Definition 8 . (Error-region robust loss) We define the error-region robust loss (ER-robust loss) as the global loss \bar{L} \displaystyle\bar{L}\equiv\textbf{E}_{(\sigma,c)\sim\mathcal{D}}l_{h}(\tilde{\sigma},c_{\tilde{\sigma}}) (10) where we also take into account the change to the true class if the perturbation \sigma\rightarrow\tilde{\sigma} occurs. However, since the true class is usually not accessible (at least those not in the training set), it is not convenient to work with the error-region robust loss, and instead it is more convenient to work with the corrupted-instance robust loss. II.2.1 1-0 loss: accuracy and robustness Here we can focus on the different definitions of robustness and accuracy when using 1-0 loss, which is an important loss function for classification problems. Here the local loss l(\sigma,c) is the identity function \mathbf{1}(h\neq c) , which takes the value of 1 if h(\sigma)\neq c and is equal to 0 otherwise. Definition 9 . The error region \mathcal{M} is defined as the set of samples \sigma\in\Sigma where h(\sigma)\neq c(\sigma) . Definition 10 . We define accuracy of the model h_{\vec{\theta}} as the probability \displaystyle A_{\vec{\theta},\mathcal{D}}\equiv P_{{(\sigma,c)\sim\mathcal{D}}}(h_{\vec{\theta}}(\sigma)=c(\sigma)). (11) We will often suppress the subscripts \{\vec{\theta},\mathcal{D}\} in the cases where our model and distribution do not change in our analysis. Definition 11 . We define corrupted-instance robustness accuracy by the probability \displaystyle\tilde{A}_{\vec{\theta},\mathcal{D}}\equiv P_{{(\sigma,c)\sim\mathcal{D}}}(h_{\vec{\theta}}(\tilde{\sigma})=c(\sigma)) (12) where \tilde{h} is a model modified by some perturbation \mathcal{N} . Definition 12 . We define prediction-change robustness by the probability \displaystyle A^{*}_{\vec{\theta},\mathcal{D}}\equiv P_{{(\sigma,c)\sim\mathcal{D}}}(h_{\vec{\theta}}(\tilde{\sigma})=h(\sigma)). (13) Although we will not be using the following definition in our analysis later – since corrupted-instance robustness accuracy and prediction-change robustness are more natural – for completeness we include also the error-region robustness accuracy. Definition 13 . We define error-region robustness accuracy by the probability \displaystyle\bar{A}_{\vec{\theta},\mathcal{D}}\equiv P_{{(\sigma,c)\sim\mathcal{D}}}(h_{\vec{\theta}}(\tilde{\sigma})=\tilde{c}(\sigma)). (14) In the rest of the chapter when using the terminology robustness accuracy, we use this to denote corrupted-instance robustness accuracy unless otherwise specified. II.2.2 Measures of robustness with respect to adversarial perturbations Note that all the above measures and definitions require a specification of what the perturbation is. However, in adversarial perturbations where by definition we do not necessarily have full information on the perturbation itself, and in addition these are usually ’small perturbations’ according to some definition of ’small’, it is important to characterise the robustness of a model. In this case, it is more convenient to specify some minimum distance – again different possible definitions of distance are possible – to perturb a test state whereby the relationship between the model prediction and the true prediction changes. Just as there are three types of robust loss, here we have three corresponding types of robustness with respect to adversarial perturbations. We note that depending on the definition of distance one chooses, for example l_{1} or quantum trace distance, we will also obtain different values and can even obtain different behaviour. Definition 14 . We define corrupted-instance robustness to adversarial perturbations by \displaystyle\tilde{\Delta}(h,\sigma)=\min{|\delta|}\quad,\quad h(\mathcal{N}_{\delta}(\sigma))\neq c(\sigma), (15) where |\delta| is some measure of distance between states \sigma and \mathcal{N}_{\delta}(\sigma) . We can also define the corresponding expected corrupted-instance robustness to adversarial perturbations by \displaystyle\langle\tilde{\Delta}(h)\rangle=\textbf{E}_{{(\sigma,c)\sim\mathcal{D}}}\Delta(h,\sigma) (16) Definition 15 . We define prediction-change robustness to adversarial perturbations by \displaystyle\Delta^{*}(h,\sigma)=\min{|\delta|}\quad,\quad h(\mathcal{N}_{\delta}(\sigma))\neq h(\sigma), (17) where |\delta| is some measure of distance between states \sigma and \mathcal{N}_{\delta}(\sigma) . We can also define the corresponding expected prediction-change robustness to adversarial perturbations by \displaystyle\langle\Delta^{*}(h)\rangle=\textbf{E}_{{(\sigma,c)\sim\mathcal{D}}}\Delta(h,x) (18) Definition 16 . We define error-region robustness to adversarial perturbations by \displaystyle\bar{\Delta}(h,\sigma)=\min{|\delta|}\quad,\quad h(\mathcal{N}_{\delta}(\sigma))\neq c(\mathcal{N}_{\delta}(\sigma)), (19) where |\delta| is some measure of distance between states \sigma and \mathcal{N}_{\delta}(\sigma) . We can also define the corresponding expected error-region robustness to adversarial perturbations by \displaystyle\langle\bar{\Delta}(h)\rangle=\textbf{E}_{{(\sigma,c)\sim\mathcal{D}}}\Delta(h,x) (20) III Trade-offs between accuracy and robustness accuracy In this section, we will examine more closely - through simple examples - the relationship between robustness and accuracy, and robustness accuracy from the point of view of classification algorithms at the testing stage. We will use some simplified toy models to illustrate some key observations and to show why it’s insufficient to study accuracy of a model on its own. We will see through some simple examples that trade-offs between accuracy and robustness accuracy can exist for both the 1-0 loss as well as linear loss. From simple examples as a starting point, we can ask fundamental questions about the requirements we should have for our model which could be subject to noisy perturbations and when we do and do not expect trade-offs between accuracy and robustness accuracy. For discussions on trade-offs between accuracy and robustness for classification of classical data (where both accuracy and robustness may be defined in various ways), see for example dobriban2023provable ; tsipras2018robustness ; xu2012robustness ; yang2020closer ; zhang2019theoretically . III.1 1-0 loss From our definition zoo in Section II.2.1 focusing on 1-0 loss, we see that the main players in characterising how good the classifier are: (i) accuracy A , (ii) corrupted-instance robustness accuracy \tilde{A} and (iii) prediction-change robustness A^{*} . A fundamental question is, what is the relationship between these key players? Briefly, the accuracy denotes the probability that the model h makes the correct description when we are sampling test states from the full distribution \mathcal{D} . However, accuracy may not be sufficient if the model is not trained under particular types of noise that is expected to corrupt incoming new states. The corrupted-instance robustness accuracy refers to the accuracy of the model when each test state \sigma is perturbed by some perturbation \mathcal{N} , and we refer this as robustness accuracy for short. Since this quantity itself must be related to properties of the model itself, we must also define prediction-change robustness — which we refer as robustness for short – which refers to the probability that the model prediction itself does not change when each test state is subject to the same perturbation \mathcal{N} . Here it is possible to identify a fundamental relationship between these quantities when considering K -class classification. Here we look at the simplest case where both the data and the model are unbiased, and we will make some simple observations. Theorem 17 . (Unbiased classifier) If the data and the model are both unbiased, in the sense that P(h=i)=1/K=P(c=j) for K -class classification and for any i,j=1,...,K , then the following holds: \displaystyle\tilde{A} \displaystyle=A(2A^{*}-1)+(1-A^{*}) (21) \displaystyle=A^{*}(2A-1)+(1-A). (22) Proof. See Appendix A for the proof. ∎ From this simple relationship, we can already make some important observations: (1) It is insufficient to only have a high accuracy A . The aim for a good model is to have high robustness accuracy \tilde{A} – which depends just as much on robustness A^{*} as on accuracy A . Here A and A^{*} are interchangeable in terms of their effect on \tilde{A} . (2) Trade-offs between \tilde{A} and A are possible. For example, if model has low robustness A^{*}<1/2 , higher accuracy leads to lower robustness accuracy, so training more won’t help if the model itself is badly chosen. So the choice of the model itself and having in-built invariances to obtain high A^{*} is very important. Similarly, if accuracy is low A<1/2 , increasing robustness alone cannot achieve high robustness accuracy: in fact increasing robustness decreases robustness accuracy. (3) Theorem 1 can be rewritten |\tilde{A}-A|=|(1-2A)(1-A^{*})| , where it can be seen that the difference between accuracy and robustness accuracy depends independently on A and A^{*} . In the above, it is clear that how well the model h is chosen and its own robustness properties is vital to the relationship between accuracy and robustness accuracy. We note that this relationship can also be modified from the above simplest form when different assumptions are included. A simple example we can show explicitly is when the model itself is biased. Theorem 18 . (Biased classifier)) If the data is unbiased, in the sense that 1/K=P(c=j) for K -class classification, but the model is biased. We look at the simplest setting where only one class is biased. Suppose it is class a that is biased, so then P(h=a)=\alpha , and the rest of the classes are unbiased, so P(h=i\neq a)=(1-\alpha)/(K-1) for any i\neq a . Then the following holds: \displaystyle\tilde{A}=\frac{(1-2A)(K-1)}{(1-\alpha)K}\left(A^{*}+\left(\frac{1-\alpha}{\alpha(K-1)}-1\right)P(\tilde{h}=h=a)\right)+(1-A) (23) Proof. See Appendix B for the proof. ∎ These simple observations show the importance of distinguishing robustness and robustness accuracy and accuracy as three independent considerations that must be studied in their own right, as well as their dependencies upon each other. The fact that trade-offs between these quantities can exist also points out applications of this to investigating whether it is possible to train models under ’incompatible noises’, where more training under one class of noise can actually adversely affect robustness with respect to another type of noise. Another application could be to the no free lunch theorem, which is based on the observation that for every distribution for which a model performs well, there should be some distribution for which the same model would perform badly. Although the free lunch theorem guarantees that these ’dual distributions’ should exist, what is the relationship between these distributions and how do we identify them? These questions are also intimately connected with the trade-off relationships between accuracy, robustness accuracy and robustness that we see here. III.1.1 Examples of trade-off between robustness accuracy and accuracy In this section, we provide some examples both in classical and quantum models where trade-offs between accuracy and robustness accuracy can exist. By this, we mean we are provided with two different models h_{1} and h_{2} and the test states are selected from an identical distribution \mathcal{D} . They have corresponding accuracies A_{1} , A_{2} , robustness accuracies \tilde{A}_{1} , \tilde{A}_{2} and robustness values A^{*}_{1} , A^{*}_{2} . A trade-off between robustness accuracy and accuracy is said to exist if when A_{1}0.5 , it is possible to have the tradeoff A_{1}\gg A_{2} and \tilde{A}_{1}\ll\tilde{A}_{2} , so a more accurate model H_{1} can lead to worse robustness accuracy. Example 2. We can generalise Example 1 to a more general example. Suppose we have two models \displaystyle H_{1}(x)=f(x_{1},x_{2},...,x_{d+1}) \displaystyle H_{2}(x)=g(x_{1}), (25) where the perturbation is only on x_{2},...,x_{d+1} , leaving x_{1} invariant, and they are selected from one of two distributions D_{\pm} coinciding with c(x)=\pm . The effect of the perturbation is to change D_{\pm}\rightarrow D_{\mp} . Here again we have A_{2}=p=\tilde{A}_{2} . Then if A_{1}>A_{2}=p , it is always true that \tilde{A}_{1}<\tilde{A}_{2} if p>1/2 . Example 3. Suppose we have two quantum models H_{1} and H_{2} and a Hamiltonian h\otimes\mathbf{1}^{\otimes d}+\mathbf{1}\otimes h\otimes\mathbf{1}^{\otimes d-1}+...+\mathbf{1}^{\otimes d}\otimes h with local operator h . Let the input state be of the form \sigma=\sigma_{1}\otimes...\otimes\sigma_{d+1} where \sigma_{i=1,...,d+1} are local states that h acts on and \displaystyle H_{1}(\sigma)=\frac{1}{d}\sum_{i=1}^{d}\text{Tr}(h\sigma_{i}) \displaystyle H_{2}(\sigma)=\text{Tr}(h\sigma_{d+1}) (26) and each -1\leq\text{Tr}(h\sigma_{i})\leq 1 . We can define the distribution from which we select \sigma as D . These models are related to the true class in the following way. Let h(\sigma)=\text{sign}(H(\sigma)) such that c(\sigma)=h_{2}(\sigma) with probability p . Also if c(\sigma)=\pm 1 , then the values \text{Tr}(h\sigma_{i})|_{i=1,...,d}\sim D_{\pm} Now we choose a noise model such that the effect of the perturbation is \text{Tr}(h\sigma_{i})|_{i=1,...,d}\rightarrow\text{Tr}(h\sigma^{\prime}_{i})|_{i=1,...,d}\sim D_{\mp} . Then it is possible to find a value p>0.5 where we have the trade-off situation that higher accuracy A_{1}>A_{2} implies less robustness accuracy \tilde{A}_{1}<\tilde{A}_{2} . Example 4. We can look at more general models of the following form. We first define \displaystyle f_{i}(\sigma)=\text{Tr}(\mathcal{O}_{i}\sigma) (27) as the i^{\text{th}} quantum feature with respect to \mathcal{O} of the state \sigma , where \{\mathcal{O}_{i}\}_{i=1}^{d+1} is a set of hermitian operators. Suppose the elements \alpha_{i}=0,1 for simplicity. Then we can compare two models \displaystyle H_{1}(\sigma)=f_{1}(\sigma) \displaystyle H_{2}(\sigma)=\sum_{i=1}^{d+1}\alpha_{i}f_{i}(\sigma) (28) and we are selecting states \sigma in a way such that f_{1}(\sigma)=\pm 1 and f_{2\leq i\leq d+1}(\sigma) has two distributions D_{\pm} corresponding to c(\sigma)=\pm . Suppose we choose perturbations where only f_{2},...,f_{d+1} can change and leave f_{1} invariant. Furthermore, the distributions change according to D_{\pm}\rightarrow D_{\mp} . We then define the accuracy A_{1} when P(c=1)=1/2=P(c=-1) to be A_{1}=P(h_{1}=c)\equiv p . A similar argument can be followed where when p>0.5 , one can achieve A_{2}>A_{1} while \tilde{A}_{2}<\tilde{A}_{1} . The above examples 1-4 focuses on deterministic classifiers. We can also examine examples with probabilistic classifiers. In the case of a probabilistic classifier, the predicted label h_{s}(\sigma) is a stochastic variable instead of a deterministic one given \sigma . For instance, we can consider this label as the outcome of a single-shot quantum measurement. We focus here on binary classifiers which can be straightforwardly generalised to the multiclass scenario. However, the true label c is still deterministic. This means we are sampling the non-stochastic pair \{\sigma_{i},c_{i}\}\sim\mathcal{D} from some underlying distribution \mathcal{D} , where i can also range over continuous values. For simplicity of notation, we consider discrete i and use the summation sign instead of integrals. Below we will distinguish between two types of probabilities. P_{s} is the probability associated with the stochastic variable getting a specific outcome given some \sigma , which we can model with a quantum expectation value as P_{s}(h_{s}(\sigma)=j)=\text{Tr}(\Pi_{j}\sigma) , where \{\Pi_{j}\} are quantum measurement operators, e.g. POVMs. On the other hand P is the probability associated with averaging over some distribution of input states, for instance P(c(\sigma)=1) is the probability of states sampled from \mathcal{D} as having the true label 1 . We can define then accuracy A_{s} of this stochastic classifier h_{s} as the probability it gives the same outcome as the true label \displaystyle A_{s}\equiv\sum_{(\sigma_{i},c_{i})}P(\sigma_{i},c_{i})P_{s}(h_{s}(\sigma_{i})=c_{i}). (29) Then we the following lemma for an unbiased binary stochastic classifier. Here we use the definition \sigma^{\pm}=\{\sigma|c(\sigma)=\pm 1\} and we can define the normalised quantum states \displaystyle\Sigma^{\pm}\equiv\frac{\sum_{\sigma_{i}^{\pm}}P(\sigma^{\pm}_{i})\sigma_{i}^{\pm}}{\sum_{\sigma_{j}^{\pm}}P(\sigma^{\pm}_{j})}. (30) Lemma 19 . We assume an unbiased dataset \sum_{\sigma_{j}^{\pm}}P(\sigma^{\pm}_{j})=1/2 . We assume a noise model that modifies the measurement \Pi_{1,-1}\rightarrow\tilde{\Pi}_{1,-1}=\sum_{l}E_{l}\Pi_{1,-1}E_{l}^{\dagger} where \{E_{l}\} are Kraus operators and \Pi_{1}=\mathbf{1}-\Pi_{-1} . Then the difference between the robustness accuracy and accuracy is given by \displaystyle|\tilde{A}_{s}-A_{s}|=\frac{1}{2}|\text{Tr}(\Pi_{1}(\tilde{\Sigma}^{+}-\Sigma^{+}+\Sigma^{-}-\tilde{\Sigma}^{-})|. (31) We can also provide an upper bound to this difference \displaystyle|\tilde{A}_{s}-A_{s}|\leq\tau(\Sigma_{A},\Sigma_{B}) (32) where \tau(\Sigma_{A},\Sigma_{B}) is the trace distance between states \Sigma_{A}\equiv(1/2)(\tilde{\Sigma}^{+}+\Sigma^{-}) and \Sigma_{B}\equiv(1/2)(\Sigma^{+}+\tilde{\Sigma}^{-}) . Proof. See Appendix D. ∎ Note that furthermore, the projector \Pi_{1} that maximises this upper bound between robustness accuracy and accuracy (for any distribution of states) is achieved by the Helstrom measurement corresponding to the optimal discriminator of \Sigma_{A} and \Sigma_{B} . We can now provide examples of cases where trade-offs between robustness accuracy and accuracy occur and when they do not. Example 5. In the case where the perturbation leaves the states \Sigma^{\pm} unchanged \tilde{\Sigma}^{\pm}=\Sigma^{\pm} , then \tilde{A}_{s}=A_{s} . However, if we have the transformation \tilde{\Sigma}^{\pm}\rightarrow\Sigma^{\mp} , then we have \displaystyle|\tilde{A}_{s}-A_{s}|=|1-2A_{s}|. (33) So for A_{s}>1/2 , this clearly implies a trade-off between \tilde{A}_{s} and A_{s} as A_{s} grows. We note that even a small perturbation is sufficient to achieve this outcome if the states \Sigma^{\pm} are near the true decision boundaries and while such a modification could be considered an adversarial example because of the small size of the perturbation. We will see this in the next example. For now, we can test this relation on two simple examples of noise: Pauli noise channel and depolarisation noise. (Pauli noise) Suppose we have the Pauli noise channel \mathcal{N}_{Pauli} for a single qubit \sigma_{i} where \displaystyle\mathcal{N}_{Pauli}(\sigma_{i})=p_{0}\sigma_{i}+p_{1}\sigma_{i}+p_{2}\sigma_{i}+p_{3}\sigma_{i} (34) and p_{0}+p_{1}+p_{2}+p_{3}=1 . Suppose we choose the simplest case where \Pi_{0}=|0\rangle\langle 0| . Then we can derive \displaystyle\tilde{\Sigma}^{\pm}=p_{0}\Sigma^{\pm}+p_{1}\sigma_{x}\Sigma^{\pm}\sigma_{x}+p_{2}\sigma_{y}\Sigma^{\pm}\sigma_{y}+p_{3}\sigma_{z}\Sigma^{\pm}\sigma_{z}. (35) It is straightforward to find \displaystyle\tilde{A}_{s}=(1-2(p_{1}+p_{2}))A_{s}+\frac{3}{2}(p_{1}+p_{2}). (36) Then we have a trade-off if d\tilde{A}_{s}/dA_{s}<0 , but not if \tilde{A}_{s}/dA_{s}\geq 0 . So we see that the trade-off condition is true when p_{1}+p_{2}>1/2 , but otherwise there is no trade-off. As special examples, for the case of bit-flip error (where only p_{0},p_{1}\neq 0 ), the trade-off condition corresponds to p_{2}>1/2 , whereas in the case of phase-flip (where p_{1}.p_{2}=0 ) we don’t have any trade-off between \tilde{A}_{s} and A_{s} . (Depolarisation noise) Another example is depolarisation noise \mathcal{N}_{dep} where \displaystyle\mathcal{N}_{dep}(\sigma_{i})=(1-p)\sigma_{i}+\frac{p}{d}\mathbf{1} (37) and \displaystyle\mathcal{N}_{dep}(\Sigma^{\pm})=(1-p)\Sigma^{\pm}+\frac{p}{d}\mathbf{1}. (38) This leads to \displaystyle\tilde{A}_{s}=(1-p)A_{s}+\frac{p}{2} (39) where d\tilde{A}_{s}/dA_{s}=1-p>0 , so there will never be a trade-off between robustness accuracy and accuracy for depolarisation noise. Example 6. We call quantum channels \mathcal{N}_{adv} acting on input quantum states \sigma adversarial perturbations if the trace distance is below some given constant \epsilon_{max}\ll 1 \displaystyle\tau(\sigma,\mathcal{N}_{adv}(\sigma))\leq\epsilon_{max} (40) for every input state \sigma\sim\mathcal{D} . Then it is possible to have a maximal trade-off between accuracy and robustness accuracy \tilde{A}_{s}=1-A_{s} for adversarial perturbations of the input states if the following sufficient condition is satisfied \displaystyle\min_{i}|\frac{p_{-,i}}{p_{+,i}}\text{Tr}(\sigma_{i}^{+}\sigma_{i}^{-})|\geq 1-\epsilon_{max} (41) where p_{\pm,i}\equiv P(\sigma^{\pm}_{i})/\sum_{\sigma_{j}^{\pm}}P(\sigma^{\pm}_{j}) . This is simple to show using \mathcal{N}_{Adv}(\Sigma^{\pm})=\Sigma^{\mp} , and more specifically \sigma_{i}^{\pm}\rightarrow\sigma_{i}^{\mp} with normalisation constants taken into account. Then using \tau(\sigma,\rho)\leq\sqrt{1-\mathcal{F}(\sigma,\rho)} , the result follows straightforwardly. However, we note that these perturbations are all due to relevant perturbations rather than irrelevant perturbations , since they change the true class of the states, so they belong to Type II perturbations, rather than Type I. From the above result, we see that the condition of a trade-off depends only on the distances between states of various classes, which is not a property of any particular model in itself, but rather an intrinsic feature of the problem. We can also look at more general classes of trade-offs between robustness accuracy and accuracy. A more general class of examples of trade-offs between \tilde{A}_{s} and A_{s} can come about if we consider small perturbations in the distribution \mathcal{D} itself. Let the initial distribution be \mathcal{D}_{1} and the distribution after perturbation be \mathcal{D}_{2} . We can define these distributions in the following way. For example, suppose we have an observable \mathcal{O}_{j} and we define F_{j}(\sigma_{i})=\text{Sign}\text{Tr}(\mathcal{O}_{j}\sigma_{i}) as the sign of the j^{th} quantum feature of the state \sigma_{i} . Then let us define the sign of one quantum feature F_{0} such that \displaystyle P(F_{0}(\sigma^{\pm}_{i})=\pm 1|c(\sigma_{i})=\pm 1)=f_{0} (42) \displaystyle P(F_{0}(\sigma^{\mp}_{i})=\pm 1|c(\sigma_{i})=\mp 1)=1-f_{0}. So if f_{0}>1/2 , then the feature F_{0} is positively correlated with the true label c . We define \sigma^{f_{0}^{\pm}}=\{\sigma|f_{0}(\sigma)=\pm 1\} and the following normalised quantum states \displaystyle\Sigma^{++}=\frac{\sum_{\sigma_{i}^{+}}P(\sigma_{i}^{+})\sigma^{f_{0}^{+}}_{i}}{\sum_{\sigma_{j}^{+}}P(\sigma_{j}^{+})} \displaystyle\Sigma^{+-}=\frac{\sum_{\sigma_{i}^{+}}P(\sigma_{i}^{+})\sigma^{f_{0}^{-}}_{i}}{\sum_{\sigma_{j}^{+}}P(\sigma_{j}^{+})} \displaystyle\Sigma^{-+}=\frac{\sum_{\sigma_{i}^{-}}P(\sigma_{i}^{-})\sigma^{f_{0}^{+}}_{i}}{\sum_{\sigma_{j}^{-}}P(\sigma_{j}^{-})} \displaystyle\Sigma^{--}=\frac{\sum_{\sigma_{i}^{-}}P(\sigma_{i}^{-})\sigma^{f_{0}^{-}}_{i}}{\sum_{\sigma_{j}^{-}}P(\sigma_{j}^{-})} Then we have the following general result on when to expect a trade-off between robustness accuracy and accuracy. Example 7. Now we study a class of perturbations such that \displaystyle\tilde{\Sigma}^{++}=\Sigma^{+-} \displaystyle\tilde{\Sigma}^{+-}=\Sigma^{++} \displaystyle\tilde{\Sigma}^{--}=\Sigma^{-+} \displaystyle\tilde{\Sigma}^{-+}=\Sigma^{--}. (44) Then it can be shown that for any f_{0}>1/2 we have the trade-off condition \displaystyle\tilde{A}_{s}\leq\frac{f_{0}}{1-f_{0}}(1-A_{s}). (45) From the definitions above, these perturbations occur if for instance we exchange the following \displaystyle\sigma^{f_{0}^{+}}_{i}\leftrightarrow\sigma^{f_{0}^{-}}_{i^{\prime}} (46) so long as the pair c_{i}=c_{i^{\prime}} . These are irrelevant perturbations. This means that we can always expect a trade-off between robustness accuracy and accuracy if the perturbations move the state labels according to a quantum feature that is strongly correlated with the true label. This analysis is a generalisation of example 5 where we simply exchange \displaystyle\sigma^{+}_{i}\leftrightarrow\sigma^{-}_{i^{\prime}}. (47) Furthermore, following straightforwardly from results in example 6, we see that the above trade-off between robustness accuracy and accuracy for irrelevant perturbations can occur if the following sufficient condition is satisfied \displaystyle\min_{i}\text{Tr}(\sigma_{i}^{f_{0}^{+}}\sigma_{i}^{f_{0}^{-}})\geq 1-\epsilon_{max}. (48) Taking into account non-trivial f_{0} , we can also similarly derive the bound \displaystyle|\tilde{A}_{s}-A_{s}|\leq(2f_{0}+1)\tau(\bar{\Sigma}_{A},\bar{\Sigma}_{B}) (49) where \displaystyle\bar{\Sigma}_{A}\equiv 4f_{0}(\tilde{\Sigma}^{++}+\tilde{\Sigma}^{-+}+\Sigma^{+-}+\Sigma^{--})+2(\tilde{\Sigma}^{+-}+\Sigma^{-+}) \displaystyle\bar{\Sigma}_{B}\equiv 4f_{0}(\tilde{\Sigma}^{+-}+\tilde{\Sigma}^{--}+\Sigma^{-+}+\Sigma^{++})+2(\tilde{\Sigma}^{-+}+\Sigma^{+-}). (50) III.1.2 Absence of trade-offs We know from Theorem 1 that A^{*}=1 is a sufficient condition for there to be no trade-off between \tilde{A} and A . For example, see yang . We can see that this can be a condition on both the input states themselves and a condition on the model h . Note that we only wish for robustness of our model against irrelevant perturbations , and we wish for non-robustness against relevant perturbations . We suppress indices to distinguish these types of perturbations since all robustness is defined with respect to irrelevant perturbations unless otherwise stated. To find the circumstances when the model H under a noisy perturbation gives A^{*}=1 , we assume that for all \sigma\sim D , we are given \min_{\sigma\sim D}p_{\sigma} , where p_{\sigma}=H_{k}(\sigma) (i.e. the probability that \sigma is assigned to the class that it’s in) and \sigma is in class k . Therefore \min_{\sigma\sim D}p_{\sigma} is a measure of the closest ‘distance’ of the dataset to the decision boundary for the model. Our purpose is to find a sufficient and necessary condition on the upper bound of \tau(\sigma,\rho) (where H(\rho)=\tilde{H}(\sigma) ), so that we have prediction-change robustness, i.e. H(\sigma)=H(\rho)=\tilde{H}(\sigma) for all states \sigma\sim D , which implies A^{*}=1 . Locally, i.e. for a specific \sigma where H(\sigma)|_{max}\equiv p_{\sigma} , we know that a necessary and sufficient condition for prediction-change robustness (i.e. \tilde{H}(\sigma)=H(\rho)=H(\sigma) ) is \displaystyle\tau(\sigma,\rho)<\delta_{\sigma}(1-\sqrt{1-\delta_{\sigma}^{2}})\equiv\tau_{\sigma} (51) where \delta_{\sigma}=\sqrt{1-4p_{\sigma}(1-p_{\sigma})}/2 . This is a statement about local prediction-change robustness. However, we care about global prediction change robustness to find the conditions under which A^{*}=1 . To change the above into a global statement for all \sigma\sim D , this means we need some upper bound of \tau(\sigma,\rho) for all \sigma\sim D . We know that a smaller p_{\sigma} should give rise to a larger upper bound to \tau(\sigma,\rho) , so we can define the state that gives this smallest probability \displaystyle\sigma_{min}\equiv\text{argmin}_{\sigma\sim D}p_{\sigma}. (52) Therefore, if we are given no information at all about which states in \sigma\sim D are chosen, then a necessary and sufficient condition for A^{*}=1 is for the perturbation \tau to be below the size \displaystyle\tau<\delta_{\sigma_{min}}(1-\sqrt{1-\delta_{\sigma_{min}}^{2}})\equiv\tau_{\sigma_{\min}}. (53) Later we can compute conditions for other values 0\leq A^{*}<1 . We can state this as our Proposition 1, which is a condition on the dataset for some given H . Theorem 20 . For the dataset \sigma\sim D and model H subject to noise where \tilde{H}(\sigma)=H(\rho) , then if the trace distance between \sigma and \rho satisfies the upper bound \displaystyle\tau(\sigma,\rho)<\delta_{\sigma_{min}}(1-\sqrt{1-\delta_{\sigma_{min}}^{2}}), (54) this is a sufficient condition for A^{*}=1 . We can illustrate this in the following example. We can look at a concrete example of a quantum clustering model where \displaystyle H_{k}(\sigma)=1-\tau(\sigma,C_{k}) (55) where C_{k} is the centroid state of the cluster K of states for \sigma\sim D . For instance, in the case where \sigma and all C_{k} are pure states, we have the simple model \displaystyle H_{k}(\sigma)=F(\sigma,C_{k})=\text{Tr}(|C_{k}\rangle\langle C_{k}|\sigma), (56) where the classifier is \displaystyle h(\sigma)=\text{argmax}_{k}H_{k}(\sigma). (57) Clearly, the largest H_{k}(\sigma) occurs for the state C_{k} that \sigma is closest to, hence \sigma is identified to belong to cluster K . In this case, it is easy to see how the distribution of the sizes of the clusters are sufficient for us to find p_{A} , since \displaystyle p_{A}(\sigma)=1-\tau(\sigma,C_{A}). (58) Therefore, if we are given the size of the largest cluster, then this gives us p_{\sigma_{\min}} , and hence \tau_{\sigma_{\min}} . Once inserted into Theorem 3, this would give us the sufficient condition for A^{*}=1 for this model. Aside from A^{*}=1 , we see from Theorem 1 that 1>A^{*}>1/2 is also sufficient for no trade-offs between robustness accuracy and accuracy. Sufficient conditions for this to be satisfied would also be helpful. From Theorem 3, we saw that for any case where \tau<\tau_{\sigma_{\min}} , then A^{*}=1 since h(\rho)=h(\sigma) for all \sigma\sim D . However, it may be that we require only h(\rho)=h(\sigma) for some percentage of \sigma\sim D instead of all cases. Suppose we fix A^{*}=a where 0\leq a<1 is some constant. For the distribution D , suppose we are given also the distribution of p_{\sigma} values (i.e. the maximum probability of \sigma being in a particular class, which will also be the class assigned to \sigma ). Let this distribution be labelled P_{\sigma}(p_{A}) , distributed over all p_{A} values for all \sigma\sim D . Then we have the following related results. A sufficient condition for the probability A^{*}=a to hold is when perturbations of any \sigma\in D satisfies \displaystyle\tau<\delta_{p_{a}}(1-\sqrt{1-\delta^{2}_{p_{a}}}) (59) where \displaystyle a=A^{*}=\int^{1}_{p_{a}}P_{\sigma}(p_{A})dp_{A}. (60) This means that either we can be given some upper bound to \tau where we calculate the corresponding p_{a} and hence the corresponding a value, or that we are given a and identify the corresponding upper bound to \tau . Either way, this requires access to the distribution P_{\sigma}(p_{A}) , which one may or not be able to access. III.1.3 Applications in studying trade-offs There are at least three main areas where the study of trade-offs between robustness accuracy and accuracy may be helpful for (1) Incompatible noise (2) Adversarial perturbations (3) No free lunch theorem and we will briefly discuss these and present open questions. Incompatible noise – We first present a definition of incompatible noise . Definition 21 . Let \tilde{A}^{(1)}_{s} be the robustness accuracy with respect to noise \mathcal{N}_{1} and \tilde{A}^{(2)}_{s} is the robustness accuracy with respect to noise \mathcal{N}_{2} . We call two noise perturbations \mathcal{N}_{1} and \mathcal{N}_{2} incompatible noise if \displaystyle\frac{d\tilde{A}^{(2)}_{s}}{d\tilde{A}^{(1)}_{s}}<0. (61) This means that if we train a model to be more accurate in presence of noise \mathcal{N}_{1} , it becomes less accurate when in presence of noise \mathcal{N}_{2} . We can show a simple example of this for a quantum classifier. Example 8. As an illustrative simple example for single-qubits with \Pi_{1}=|0\rangle\langle 0| , we let \mathcal{N}_{1} be depolarisation noise with noise parameter p_{1} and \mathcal{N}_{2} be bit-flip noise with noise parameter p_{2} , so \mathcal{N}_{2}(\Sigma^{\pm})=(1-p_{2})\Sigma^{\pm}+p_{2}\sigma_{x}\Sigma^{\pm}\sigma_{x} . Then we can derive \displaystyle\tilde{A}^{(1)}_{s}=(1-p_{1})A_{s}+\frac{p_{1}}{2} \displaystyle\tilde{A}^{(2)}_{s}=(1/2-p_{2})A_{s}+(1/2+p_{2})/2 (62) hence \displaystyle\frac{d\tilde{A}^{(2)}_{s}}{d\tilde{A}^{(1)}_{s}}=\frac{d\tilde{A}^{(2)}_{s}}{dA_{s}}\frac{dA_{s}}{d\tilde{A}^{(1)}_{s}}=\frac{1/2-p_{2}}{1-p_{1}} (63) In this case, since p_{1}<1 , depolarisation noise and bit-flip noise are incompatible if and only if p_{2}>1/2 . By understanding which perturbations are incompatible with each other, we can better understand the ultimate limitations of our model and to enable better model building. Adversarial examples – From Example 6, we saw that one way to consider adversarial perturbations are quantum channels \mathcal{N}_{adv} acting on input quantum states \sigma such that the trace distance is below some given constant \epsilon_{max}\ll 1 \displaystyle\tau(\sigma,\mathcal{N}_{adv}(\sigma))\leq\epsilon_{max} (64) for every input state \sigma\sim\mathcal{D} : these include both Type I and Type II perturbations. However, to get true adversarial examples for state \sigma , we specifically require three conditions: • \tau(\sigma,\mathcal{N}_{adv}(\sigma))\leq\epsilon_{max} , \epsilon\ll 1 • \mathcal{N}_{adv} acting on \sigma are also irrelevant perturbations , i.e., do not change the true label of \sigma : c(\sigma)=c(\mathcal{N}_{adv}(\sigma)) • h(\sigma)\neq h(\mathcal{N}_{adv}(\sigma)) Examples 1-6 all present cases of trade-offs between robustness accuracy and accuracy for relevant perturbations . However, in Example 7, we saw that we could also have these trade-offs for irrelevant perturbations , and Example 8 also allows the possibility for irrelevant perturbations. Thus trade-offs might also exist in the case of training to make models more robust to adversarial examples. For instance, in the above three conditions, the last deals with the corrupted-instance robustness of the model A^{*} , and we already know from Theorem 1 that a low robustness A^{*}<1/2 to \mathcal{N}_{adv} of Type I perturbations on \sigma is sufficient to guarantee that increasing accuracy A alone will only lead to worse and worse robustness accuracy. We will see examples of this type of behaviour in the next subsection with linear loss. No free lunch theorem – General trade-off behaviour between robustness acccuracy and accuracy, to both relevant and irrelevant perturbations, can also be considered from the perspective of the no free lunch theorem and also provide ways of constructing the best models. The no free lunch theorem is the observation that for every distribution \mathcal{D} of states for which a model h performs well (e.g. has high accuracy), there should be some distribution \tilde{\mathcal{D}} of states for which the same model h would perform badly. However, the no free lunch theorem doesn’t provide an explicit construction of these distributions for any model, since it’s only an existence theorem. We would like to understand what the relationship between one distribution where the particular model h works very well, versus a distribution for which the model has low accuracy. We can connect the setting of the no free lunch theorem to the relationship between accuracy and robustness accuracy in the following way. We first observe that when we make a perturbation \mathcal{N} on the input state \sigma for the original distribution \mathcal{D}_{1} , we note that we can instead consider this as the same scenario as when selecting \sigma from a modified distribution \mathcal{D}_{2} . This means we can rewrite the loss function for the perturbed states \tilde{\sigma}=\mathcal{N}(\sigma) where \sigma\sim\mathcal{D} as identical to the loss function of the unperturbed states selected from a different distribution \sigma\sim\mathcal{D}_{2} \displaystyle\tilde{L}_{\mathcal{D}_{1}}=\textbf{E}_{(\sigma,c)\sim\mathcal{D}_{1}}l_{h}(\tilde{\sigma},c_{\sigma})=\textbf{E}_{(\sigma,c_{\sigma})\sim\mathcal{D}_{2}}l_{h}(\sigma,c_{\sigma})=L_{\mathcal{D}_{2}}. (65) This simple rewriting leads to the following interpretation. In the context of 1-0 loss, the first quantity is the corrupted-instance robustness accuracy with respect to \mathcal{N} when selecting states from \mathcal{D}_{1} . The second quantity is accuracy, when selecting states from a different distribution \mathcal{D}_{2} , where \mathcal{D}_{2} is simply the selection of states in \mathcal{D}_{1} but all perturbed by \mathcal{N} . This means that it’s possible to consider the robustness accuracy of one model with respect to a distribution \mathcal{D}_{1} as identical to the accuracy of the same model with respect to another distribution \mathcal{D}_{2} . Thus we can write \tilde{A}_{1}=A_{2} . If A^{*} is the fraction of states \sigma that satisfy h(\sigma)=h(\mathcal{N}(\sigma)) , then from Theorem 1 we have \displaystyle A_{2}=A_{1}(2A^{*}-1)+(1-A^{*}). (66) Therefore a trade-off relationship between A_{1} and A_{2} denotes that the better a model h is with respect to one distribution \mathcal{D}_{1} , the worse the model h is with respect to distribution \mathcal{D}_{2} . We can find the relationship between \mathcal{D}_{1} and \mathcal{D}_{2} precisely when we identify the perturbation \mathcal{N} such that A^{*}<1/2 . As a worst-case example, when A^{*}=0 \displaystyle A_{2}=1-A_{1}, (67) and this means that for the set of states \sigma\sim\mathcal{D}_{1} and the model h where h(\sigma)\neq h(\mathcal{N}(\sigma)) for all states \sigma\sim\mathcal{D}_{1} , when h is the most accurate for \sigma\sim\mathcal{D}_{1} , the same model h is least accurate when the input states are selected from \mathcal{N}(\sigma) where \sigma\sim\mathcal{D}_{1} . Thus the trade-off relationship between robustness accuracy and accuray could also provide a window into more constructive ways of examining the no free lunch theorem and to be able to better pinpoint which models work more effectively for which distributions. III.2 Linear loss We can similarly consider models for classification based on linear loss instead of 1-0 loss, and examine the relationship between the global loss L and the corrupted-instance robust loss \tilde{L} . Note that in the previous section for the 1-0 loss function, the global loss is termed accuracy A and the corrupted-instance robust loss is termed the corrupted instance robustness accuracy \tilde{A} . For the linear loss model, we have \displaystyle l_{h}=-c_{i}H(\sigma_{i}) (68) where h(\sigma_{i})=\text{sign}H(\sigma_{i}) . Suppose we have M training states \{(\sigma_{i},c_{i})\}_{i=1}^{M} . Then we can write \displaystyle L_{\theta}=-\frac{1}{M}\sum_{i=1}^{M}c_{i}H_{\theta}(\sigma_{i}) \displaystyle\tilde{L}_{\theta}=-\frac{1}{M}\sum_{i=1}^{M}c_{i}H_{\theta}(\tilde{\sigma}_{i}) (69) The relationship between L and \tilde{L} can similarly be applied to identify incompatible noise , adversarial perturbations and example, and the no free lunch theorem. We will only provide a few examples here for illustration, since many similar examples already appeared for 1-0 loss that already motivated some of our fundamental questions. To understand the relationship between L and \tilde{L} , we first study an idealised case, where we assume that there are K_{\theta}=K states in the training set such that \displaystyle H(\tilde{\sigma}_{i})=H(\sigma_{i}), (70) and we denote these as ‘robust’ states \sigma_{i_{R}} . The rest of the M-K states satisfy \displaystyle H(\tilde{\sigma}_{i})=-H(\sigma_{i}) (71) and we denote these states by \sigma_{i_{\bar{R}}} . In this case, K/M=A^{*} . Then we can decompose the loss functions in the following way \displaystyle L=-\frac{1}{M}\left(\sum_{i_{R=1}}^{K}c_{i}H(\sigma_{i_{R}})+\sum_{i_{\bar{R}}=1}^{M-K}c_{i}H(\sigma_{i_{\bar{R}}})\right) \displaystyle=\frac{K}{M}L_{R}+\frac{M-K}{M}L_{\bar{R}} (72) where L_{R} and L_{\bar{R}} denote the ‘robust’ and ‘non-robust’ parts of the loss function and is defined as \displaystyle L_{R}=-\frac{1}{K}\sum_{i_{R=1}}^{K}c_{i}H(\sigma_{i_{R}}) (73) \displaystyle L_{\bar{R}}=-\frac{M-K}{M}\sum_{i_{\bar{R}}=1}^{M-K}c_{i}H(\sigma_{i_{\bar{R}}}). (74) Similarly we can rewrite \displaystyle\tilde{L}=-\frac{1}{M}\left(\sum_{i_{R=1}}^{K}c_{i}H(\tilde{\sigma}_{i_{R}})+\sum_{i_{\bar{R}}=1}^{M-K}c_{i}H(\tilde{\sigma}_{i_{\bar{R}}})\right) \displaystyle=\frac{K}{M}L_{R}-\frac{M-K}{M}L_{\bar{R}}. (75) Comparing L and \tilde{L} , it becomes clear where any possible trade-off between L and \tilde{L} comes from: the non-robust L_{\bar{R}} part of the cost function and a small A^{*} , since \displaystyle\frac{L-\tilde{L}}{2}=\frac{M-K}{M}L_{\bar{R}}. (76) We observe from the above expression that if the initial good performance of the model – measured according to L – is mostly due to the ‘non-robust’ parts L_{\bar{R}} , then when it comes to robustness training using \tilde{L} , the model will perform poorly. Although L_{\bar{R}} is not quite the prediction-change robust loss L^{*} , this case is still analogous to the case of 1-0 loss, where if robustness is poor A^{*}<1/2 , even if A is very high, \tilde{A} will be low. We can then examine the relationship between L and \tilde{L} for quantum models. Theorem 22 . Suppose we look at quantum models where \displaystyle H(\sigma)=\text{Tr}(\mathcal{M}\sigma). (77) Then for binary classification with unbiased data we have the difference \displaystyle L-\tilde{L}=\text{Tr}(\mathcal{M}(T^{-}-T^{+})) (78) where T^{\pm}\equiv(\Sigma^{\pm}+\tilde{\Sigma}^{\mp})/2 and \sigma_{i}^{\pm}=\{\sigma_{i}|c_{i}=\pm 1\} and \Sigma^{\pm}=(2/M)\sum_{i=1}^{M/2}\sigma_{i}^{\pm} , \tilde{\Sigma}^{\pm}=(2/M)\sum_{i=1}^{M/2}\tilde{\sigma}_{i}^{\pm} . Proof. This follows easily from the definitions \displaystyle L=-\frac{1}{M}\left(\sum_{i^{+}=1}^{M/2}\text{Tr}(\mathcal{M}\sigma_{i}^{+})-\sum_{i^{-}=1}^{M/2}\text{Tr}(\mathcal{M}\sigma_{i}^{-})\right)=-\frac{1}{2}(\text{Tr}(\mathcal{M}\Sigma^{+})-\text{Tr}(\mathcal{M}\Sigma^{-})), (79) \displaystyle\tilde{L}=-\frac{1}{2}(\text{Tr}(\mathcal{M}\tilde{\Sigma}^{+})-\text{Tr}(\mathcal{M}\tilde{\Sigma}^{-})). (80) ∎ Suppose we have two irrelevant perturbations \mathcal{N}_{1} and \mathcal{N}_{2} . In the idealised case there are K states that obey \displaystyle H(\mathcal{N}_{1}(\sigma_{i}))=H(\mathcal{N}_{2}(\sigma_{i})) (81) and M-K states obeying \displaystyle H(\mathcal{N}_{1}(\sigma_{i}))=-H(\mathcal{N}_{2}(\sigma_{i})), (82) where the former states are ‘robust’ states, whereas the latter are considered ‘non-robust’. Then the relationship between the L_{1} and L_{2} are given by \displaystyle L_{1}-L_{2}=2\frac{M-K}{M}L_{\bar{R}} (83) where \displaystyle L_{\bar{R}}=-\frac{1}{M}\sum_{i_{\bar{R}}}^{M-K}c_{i}H(\sigma_{i_{\bar{R}}}) (84) where \{\sigma_{i_{\bar{R}}}\} are the set of states of the non-robust states. In the more realistic quantum case, we have \displaystyle L_{1}-L_{2}=\text{Tr}(\mathcal{M}(N^{-}-N^{+})) (85) where N^{\pm}\equiv(\Omega_{1}^{\pm}+\Omega_{2}^{\mp})/2 with \Omega_{1}^{\pm}=(2/M)\sum_{i=1}^{M/2}\mathcal{N}_{1}(\sigma_{i}^{\pm}) and \Omega_{2}^{\pm}=(2/M)\sum_{i=1}^{M/2}\mathcal{N}_{2}(\sigma_{i}^{\pm}) . We see that it’s also possible to have trade-offs between robust loss and loss for those adversarial perturbations that are in addition irrelevant perturbations. Example 9. Here we have an explicit example for a single-qubit model where an irrelevant perturbation is gives rise to a trade-off between the loss and the perturbed loss. For instance, let us have the input states from the training set: \displaystyle\sigma^{+}_{1}=|0\rangle\langle 0| \displaystyle\sigma^{+}_{2}=|1\rangle\langle 1| \displaystyle\sigma^{-}_{1}=\frac{5}{6}|0\rangle\langle 0|+\frac{1}{6}|1\rangle\langle 1| \displaystyle\sigma^{-}_{2}=\frac{1}{3}|0\rangle\langle 0|+\frac{2}{3}|1\rangle\langle 1| Suppose under an irrelevant perturbation \mathcal{N}_{irr} we have the following transition \displaystyle\tilde{\sigma}^{+}_{1}=|1\rangle\langle 1| \displaystyle\tilde{\sigma}^{+}_{2}=\frac{1}{4}|0\rangle\langle 0|+\frac{3}{4}|1\rangle\langle 1| \displaystyle\tilde{\sigma}^{-}_{1}=\frac{5}{6}|0\rangle\langle 0|+\frac{1}{6}|1\rangle\langle 1| \displaystyle\tilde{\sigma}^{-}_{2}=\frac{4}{5}|0\rangle\langle 0|+\frac{1}{5}|1\rangle\langle 1| In this case we see that \displaystyle\Sigma^{+}=\frac{1}{2}(|0\rangle\langle 0|+|1\rangle\langle 1|) \displaystyle\Sigma^{-}=\frac{1}{36}(21|0\rangle\langle 0|+15|1\rangle\langle 1| \displaystyle\tilde{\Sigma}^{+}=\frac{1}{8}(|0\rangle\langle 0|+7|1\rangle\langle 1|) \displaystyle\tilde{\Sigma}^{-}=\frac{1}{60}(49|0\rangle\langle 0|+11|1\rangle\langle 1|) (88) Here we see that \displaystyle L=\frac{1}{12}\text{Tr}(\mathcal{M}(|0\rangle\langle 0|-|1\rangle\langle 1|)) \displaystyle\tilde{L}=-\frac{83}{120}\text{Tr}(\mathcal{M}(|0\rangle\langle 0|-|1\rangle\langle 1|)). (89) This means that L and \tilde{L} cannot be simultaneously minimised. In fact, minimising L leads to \mathcal{M}=|1\rangle\langle 1|-|0\rangle\langle 0| , which would in fact maximise \tilde{L} . We note that there are fundamental reasons why linear loss with linear quantum models are not always sufficient to contain the symmetries of the true underlying models. For instance, we know (from previous theorems [ ]) that if \tau(\sigma,\rho)0 but is not \gamma -robust for any \gamma\geq 0 . Note that the above robust feature definition can also be extended to be defined with respect to different loss functions and having different versions of robust features in the same way we have different robustnesses in Section 2. A working hypothesis is that, given \mathcal{D} and hypothesis class \mathcal{H} , if the (standard) accuracy relies heavily on k -useful but non-robust features, then the accuracy can be high while the robustness accuracy remains low. This would identify the cause of these trade-off relationships and provide a means to more efficiently resolve these, if possible. To express this mathematically, we have the following conjecture. Conjecture 1. Let the feature f_{\Lambda} be k- useful, so let \textbf{E}_{(\sigma,c)\sim\mathcal{D}}(c(\sigma)\cdot f_{\Lambda}(\sigma))\geq k_{\Lambda} and it is non-robust, so \textbf{E}_{(\sigma,c)\sim\mathcal{D}}(\inf_{\delta}c(\sigma)\cdot f_{\Lambda}(\mathcal{N}_{\delta}(\sigma)))\leq\gamma_{\Lambda} . Then if the hypothesis function h has high standard accuracy so A>a>1/2 , then it is possible to show that this provides an upper bound to the robustness accuracy \tilde{A}1-2\exp(-2N \zeta^2) where N is the number of samples we take from the quantum circuit and \zeta is the precision to which we determine the quantity \mathbf{\tilde{y}}_{0}(\sigma) . Therefore, we see that in the finite sampling limit, the accuracy in the presence of noise degrades as \displaystyle\tilde{A}>(1-2\exp(-2N \zeta^2))(2A-1)+(1-A) (127) where \tilde{A}\rightarrow A exponentially quickly as N grows, so accuracy in the presence of depolarisation noise is not in fact compromised very much. Thus, all effects of depolarisation noise on accuracy can be remedied by taking more measurements (efficiently). Appendix B: Proof of Theorem 2 The argument runs in the same way as for Theorem 1. Here we look at K -class classification where the data is unbiased, but the model is biased. However, we look at the simplest setting where only one class is biased. Suppose it is class A that is biased, so then P(h=a)=\alpha , and the rest of the classes are unbiased, so P(h=i\neq a)=(1-\alpha)/(K-1)\equiv\alpha^{\prime} . In this case, we just need the formula for \sum_{j}P_{jj}=P(\tilde{h}=1|h=1)+...+P(\tilde{h}=K|h=K) , since in the multiclass case we have derived: \displaystyle\tilde{A}=\frac{1}{K}(1-2A)\sum_{j}P_{jj}+(1-A). (128) So we begin with \displaystyle A^{*}=P(\tilde{h}=h=1)+...+P(\tilde{h}=h=K) \displaystyle=\alpha P(\tilde{h}=a|h=a)+\alpha^{\prime}\sum_{i\neq A}P(\tilde{h}=i|h=i) \displaystyle=\alpha\sum_{j}P_{jj}+(\alpha^{\prime}-\alpha)(\sum_{j}P_{jj}-P(\tilde{h}=a|h=a)) \displaystyle=\alpha^{\prime}\sum_{j}P_{jj}-(\alpha^{\prime}/\alpha-1)P(\tilde{h}=h=a). (129) We can rearrange to find \displaystyle\sum_{j}P_{jj}=\frac{1}{\alpha^{\prime}}(A^{*}+(\alpha^{\prime}/\alpha-1)P(\tilde{h}=h=a)) (130) where \alpha^{\prime}=(1-\alpha)/(K-1) . Finally we have the relation \displaystyle\tilde{A}=\frac{(1-2A)(K-1)}{(1-\alpha)K}\left(A^{*}+\left(\frac{1-\alpha}{\alpha(K-1)}-1\right)P(\tilde{h}=h=a)\right)+(1-A), (131) which reduces to the Theorem 1 expression when \alpha^{\prime}=\alpha=1/K . Appendix C: Details of examples Example 1 We now have a noise model where we have the perturbation x_{2},...,x_{d+1}\rightarrow x^{\prime}_{2},...,x^{\prime}_{d+1} , where if (x_{2},...,x_{d+1})\sim D_{\pm} then (x^{\prime}_{2},...,x^{\prime}_{d+1})\sim D_{\mp} . Under this noise model, we have the transformation \displaystyle\tilde{H}_{1}(x)=\frac{1}{d}(x^{\prime}_{2}+...+x^{\prime}_{d+1}) \displaystyle\tilde{H}_{2}(x)=H_{2}(x), (132) where we see that \tilde{H}_{2}=H_{2} but \tilde{H}_{1}\neq H_{1} . We can easily see that A_{2}=p and A^{*}_{2}=1 . Assuming that P(c=1)=1/2=P(c=-1) , A_{1} can be computed using \displaystyle A_{1}=\frac{1}{2}(P(h=1|c=1)+P(h=-1|c=-1)). (133) This accuracy can be increased to arbitrarily high values. For example, if D_{\pm} are Gaussian distributions centered on \pm\eta c for some \eta>0 with standard deviation 1 and for large enough d for the central limit theorem to apply, then A_{1}=P(h=c) corresponds to the probability that the value of a Gaussian distribution centered on \eta with standard deviation 1/d has a value larger than 0 . This means that so long as \eta is larger than 1/\sqrt{d} , we can have a high A_{1} . We also find that \displaystyle A^{*}_{1}=P_{x_{2},...x_{d+1}\sim D_{+}}(h_{1}(x)=\tilde{h}_{1}(x)) \displaystyle+P_{x_{2},...x_{d+1}\sim D_{-}}(h_{1}(x)=\tilde{h}_{1}(x))=0 (134) since we can imagine a perturbation where x_{i\geq 2}\rightarrow-x_{i\geq 2} to give D_{\pm}\rightarrow D_{\mp} . This means that h_{1}(x)=-\tilde{h}_{1}(x) for all x selected from the distribution D_{+}\bigcup D_{-} . To compute the robustness accuracy, we note that the noise perturbation makes the following change in distribution D_{\pm}\rightarrow D_{\mp} , which means that for the Gaussian distribution example we have \tilde{A}_{1}=1-A_{1} , which from Eq. ( 21 ) is also consistent with A^{*}_{1}=0 . In the special case of the Gaussian distributions, we have \displaystyle A_{1}=1-\text{Erf}(\eta\sqrt{d}),A^{*}_{1}=0,\tilde{A}_{1}=1-A_{1} \displaystyle A_{2}=p,A^{*}_{2}=1,\tilde{A}_{2}=A_{2}. (135) This means that we can have the trade-off scenario where A_{1}>>A_{2} and \tilde{A}_{1}=1-A_{1}<<1-A_{2}0.5 . Therefore, in the scenario p>0.5 , we have a trade-off condition where a better model in accuracy H_{2}\rightarrow H_{1} can lead to a less robust model. Example 2 This means we have the following relationships between probabilities: \displaystyle p_{++}\equiv P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{+}}(f=1|g=1) \displaystyle=P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{+}}(f=1|g=-1)\equiv p_{-+} \displaystyle p_{+-}\equiv P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{-}}(f=1|g=1) \displaystyle=P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{-}}(f=1|g=-1)\equiv p_{--} \displaystyle p^{\prime}_{++}\equiv P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{+}}(g=1|g=1) \displaystyle=P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{-}}(g=1|g=1)\equiv p^{\prime}_{+-}=1 \displaystyle p^{\prime}_{-+}\equiv P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{+}}(g=1|g=-1) \displaystyle=P_{\{x_{1},x_{2},...,x_{d+1}\}\sim D_{-}}(g=1|g=-1)\equiv p^{\prime}_{--}=0. (136) Then it is possible to compute \displaystyle A_{1}=1-\frac{1}{2}pa-\frac{1}{2}(1-p)b \displaystyle\tilde{A}_{1}=\frac{1}{2}(1-p)a+\frac{1}{2}pb, (137) where a\equiv 1-p_{++}+p_{--} and b\equiv 1-p_{-+}+p_{+-} . From this we can prove that if A_{1}>A_{2}=p , then it is always true that \tilde{A}_{1}<\tilde{A}_{2} if p>1/2 . We see that A_{1}>p implies 1/2pa<(1-p)(1-1/2b) . p>1/2 is equivalent to 1-p

p>0.5 , then we have a trade-off situation that A_{1}>A_{2} gives \tilde{A}_{1}<\tilde{A}_{2} . This means that if we are training a model \displaystyle H(\sigma)=\sum_{i=1}^{d+1}\text{Tr}(h\sigma_{i})=\alpha_{1}H_{1}(\sigma)+\alpha_{2}H_{2}(\sigma) (138) where we begin with \alpha_{1}=0,\alpha_{2}=1 and after more training we get \alpha_{0}=1,\alpha_{2}=0 . Example 4 Similarly to the classical scenario, we can make the following definitions for j=1,2 \displaystyle p^{(j)}_{++}\equiv P_{\{f_{2},...,f_{d+1}\}\sim D_{+}}(H_{j}=1|H_{1}=1) \displaystyle p^{(j)}_{+-}\equiv P_{\{f_{2},...,f_{d+1}\}\sim D_{-}}(H_{j}=1|H_{1}=1) \displaystyle p^{(j)}_{-+}\equiv P_{\{f_{2},...,f_{d+1}\}\sim D_{+}}(H_{j}=1|H_{1}=-1) \displaystyle p^{(j)}_{--}\equiv P_{\{f_{2},...,f_{d+1}\}\sim D_{-}}(H_{j}=1|H_{1}=-1) (139) We then define the accuracy A_{1} when P(c=1)=1/2=P(c=-1) to be \displaystyle A_{1}=P(h_{1}=c)\equiv p. (140) The accuracy for the second model is then \displaystyle A_{2}=1-\frac{1}{2}pa_{2}-\frac{1}{2}(1-p)b_{2} (141) where a_{2}=1-p^{(2)}_{++}+p^{(2)}_{--} and b_{2}=1-p^{(2)}_{-+}+p^{(2)}_{+-} . Suppose we choose perturbations where only f_{2},...,f_{d+1} can change and leave f_{1} invariant. Furthermore, the distributions change according to D_{\pm}\rightarrow D_{\mp} . Suppose the perturbation leaves H_{1} intact, so then \displaystyle\tilde{A}_{1}=A_{1}=p, (142) but model H_{2} has a robustness accuracy different to its accuracy \displaystyle\tilde{A}_{2}=\frac{1}{2}(1-p)a_{2}+\frac{1}{2}pb_{2} (143) Then a similar trade-off argument follows where if p>1/2 , then if we train values of \alpha_{i} beginning from \alpha_{1}=1,\alpha_{i\neq 0}=0 to more general \{\alpha_{i}\} we can achieve \displaystyle A_{2}>A_{1} (144) but this would lead to \displaystyle\tilde{A}_{2}<\tilde{A}_{1}. (145) Example 7 A more general class of examples of trade-offs between \tilde{A}_{s} and A_{s} can come about if we consider small perturbations in the distribution \mathcal{D} itself. Let the initial distribution be \mathcal{D}_{1} and the distribution after perturbation be \mathcal{D}_{2} . We can define these distributions in the following way. For example, suppose we have an observable \mathcal{M}_{j} and we define F_{j}(\sigma_{i})=\text{Sign}\text{Tr}(\mathcal{M}_{j}\sigma_{i}) as the sign of the j^{th} quantum feature of the state \sigma_{i} . Then let us define the sign of one quantum feature F_{0} such that \displaystyle P(F_{0}(\sigma^{\pm}_{i})=\pm 1|c(\sigma_{i})=\pm 1)=f_{0} \displaystyle P(F_{0}(\sigma^{\mp}_{i})=\pm 1|c(\sigma_{i})=\mp 1)=1-f_{0}. So if f_{0}>1/2 , then the feature F_{0} is positively correlated with the true label c . With this definition, we can write \displaystyle\sum_{\sigma^{+}_{i}}P_{s}(h_{s}(\sigma^{+}_{i})=1)=\sum_{\sigma_{i}}P_{s}(h_{s}(\sigma_{i})|c_{i}) \displaystyle=\sum_{\sigma_{i}}(P_{s}(h_{s}(\sigma_{i})=1|f_{0}(\sigma_{i})=1)\mathbf{1}(f_{0}(\sigma_{i})=c_{i}) \displaystyle+P_{s}(h_{s}(\sigma_{i})=1|f_{0}(\sigma_{i})=-1)\mathbf{1}(f_{0}(\sigma_{i})=-c_{i})). (146) This can be included in the definition of the accuracy where we define \sigma^{f_{0}^{\pm}}=\{\sigma|f_{0}(\sigma)=\pm 1\} . \displaystyle A_{s}=\sum_{\sigma_{i}}P(\sigma_{i},c_{i}=1)((\mathbf{1}(f_{0}(\sigma_{i})=c_{i})\text{Tr}(\Pi_{1}\sigma^{f_{0}^{+}}_{i})+\mathbf{1}(f_{0}(\sigma_{i})=-c_{i})\text{Tr}(\Pi_{1}\sigma^{f_{0}^{-}}_{i}))) \displaystyle+\sum_{\sigma_{i}}P(\sigma_{i},c_{i}=-1)((\mathbf{1}(f_{0}(\sigma_{i})=c_{i})\text{Tr}(\Pi_{-1}\sigma^{f_{0}^{-}}_{i})+\mathbf{1}(f_{0}(\sigma_{i})=-c_{i})\text{Tr}(\Pi_{-1}\sigma^{f_{0}^{-}}_{i}))) \displaystyle=\sum_{\sigma_{i}^{+}}\text{Tr}(\Pi_{1}\sigma^{f_{0}^{+}}_{i})P(\sigma^{+}_{i},f_{0}(\sigma_{i})=c_{i}=1)+\sum_{\sigma_{i}^{+}}\text{Tr}(\Pi_{1}\sigma^{f_{0}^{-}}_{i})P(\sigma^{+}_{i},f_{0}(\sigma_{i})=-c_{i}=-1) \displaystyle+\sum_{\sigma_{i}^{-}}\text{Tr}(\Pi_{-1}\sigma^{f_{0}^{-}}_{i})P(\sigma^{-}_{i},f_{0}(\sigma_{i})=c_{i}=-1)+\sum_{\sigma_{i}^{-}}\text{Tr}(\Pi_{-1}\sigma^{f_{0}^{+}}_{i})P(\sigma^{-}_{i},f_{0}(\sigma_{i})=-c_{i}=1). (147) We observe that \displaystyle P(\sigma^{\pm}_{i},f_{0}(\sigma_{i})=\pm 1)=P(f_{0}(\sigma_{i})=\pm 1|\sigma^{\pm}_{i})=f_{0}P(\sigma^{\pm}_{i}) \displaystyle P(\sigma^{\pm}_{i},f_{0}(\sigma_{i})=\mp 1)=P(f_{0}(\sigma_{i})=\mp 1|\sigma^{\pm}_{i})=(1-f_{0})P(\sigma^{\pm}_{i}). (148) Inserting this into the above expression for A_{s} gives \displaystyle A_{s}=\sum_{\sigma_{i}^{+}}\text{Tr}(\Pi_{1}\sigma^{f_{0}^{+}}_{i})P(\sigma^{+}_{i})f_{0}+\sum_{\sigma_{i}^{+}}\text{Tr}(\Pi_{1}\sigma^{f_{0}^{-}}_{i})P(\sigma^{+}_{i})(1-f_{0}) \displaystyle+\sum_{\sigma_{i}^{-}}(1-\text{Tr}(\Pi_{1}\sigma^{f_{0}^{-}}_{i}))P(\sigma^{-}_{i})f_{0}+\sum_{\sigma_{i}^{-}}(1-\text{Tr}(\Pi_{1}\sigma^{f_{0}^{+}}_{i}))P(\sigma^{-}_{i})(1-f_{0}). (149) We can define the normalised states \displaystyle\Sigma^{++}=\frac{\sum_{\sigma_{i}^{+}}P(\sigma_{i}^{+})\sigma^{f_{0}^{+}}_{i}}{\sum_{\sigma_{j}^{+}}P(\sigma_{j}^{+})} \displaystyle\Sigma^{+-}=\frac{\sum_{\sigma_{i}^{+}}P(\sigma_{i}^{+})\sigma^{f_{0}^{-}}_{i}}{\sum_{\sigma_{j}^{+}}P(\sigma_{j}^{+})} \displaystyle\Sigma^{-+}=\frac{\sum_{\sigma_{i}^{-}}P(\sigma_{i}^{-})\sigma^{f_{0}^{+}}_{i}}{\sum_{\sigma_{j}^{-}}P(\sigma_{j}^{-})} \displaystyle\Sigma^{--}=\frac{\sum_{\sigma_{i}^{-}}P(\sigma_{i}^{-})\sigma^{f_{0}^{-}}_{i}}{\sum_{\sigma_{j}^{-}}P(\sigma_{j}^{-})} If we use the unbiased dataset assumption, then we can simplify \displaystyle A_{s}=\frac{1}{2}f_{0}\text{Tr}(\Pi_{1}\Sigma^{++})+\frac{1}{2}(1-f_{0})\text{Tr}(\Pi_{1}\Sigma^{+-}) \displaystyle+\frac{1}{2}f_{0}(1-\text{Tr}(\Pi_{1}\Sigma^{--}))+\frac{1}{2}(1-f_{0})(1-\text{Tr}(\Pi_{1}\Sigma^{-+})). (151) Then a perturbed classifier leads to \displaystyle\tilde{A}_{s}=\frac{1}{2}f_{0}\text{Tr}(\Pi_{1}\tilde{\Sigma}^{++})+\frac{1}{2}(1-f_{0})\text{Tr}(\Pi_{1}\tilde{\Sigma}^{+-}) \displaystyle+\frac{1}{2}f_{0}(1-\text{Tr}(\Pi_{1}\tilde{\Sigma}^{--}))+\frac{1}{2}(1-f_{0})(1-\text{Tr}(\Pi_{1}\tilde{\Sigma}^{-+})). (152) Now we study a class of perturbations such that \displaystyle\tilde{\Sigma}^{++}=\Sigma^{+-} \displaystyle\tilde{\Sigma}^{+-}=\Sigma^{++} \displaystyle\tilde{\Sigma}^{--}=\Sigma^{-+} \displaystyle\tilde{\Sigma}^{-+}=\Sigma^{--}. (153) Then it is straightforward to show that for any f_{0}>1/2 we have the trade-off condition \displaystyle\tilde{A}_{s}\leq\frac{f_{0}}{1-f_{0}}(1-A_{s}). (154) Appendix D: Proof of Lemma 1 Below we will distinguish between two types of probabilities. P_{s} is the probability associated with the stochastic variable getting a specific outcome given some \sigma , which we can model with a quantum expectation value as P_{s}(h_{s}(\sigma)=j)=\text{Tr}(\Pi_{j}\sigma) . On the other hand P is the probability associated with averaging over some distribution of input states, for instance P(c(\sigma)=1) is the probability of states sampled from \mathcal{D} as having the true label 1 . We can define then accuracy A_{s} of this stochastic classifier h_{s} as the probability it gives the same outcome as the true label \displaystyle A_{s}\equiv\sum_{\sigma_{i}}\sum_{c_{i}}P(\sigma_{i},c_{i})P_{s}(h_{s}(\sigma_{i})=c_{i}) (155) Using the definition \sigma^{\pm}=\{\sigma|c(\sigma)=\pm 1\} we can then rewrite A_{s} \displaystyle A_{s}=\sum_{\sigma_{i}}\sum_{c_{i}}P(\sigma_{i},c_{i})P_{s}(h_{s}(\sigma_{i})=c_{i}) \displaystyle=\sum_{\sigma_{i}^{+}}P(\sigma^{+}_{i},c_{i}=1)P_{s}(h_{s}(\sigma^{+}_{i})=1)+\sum_{\sigma_{i}^{-}}P(\sigma^{-}_{i},c_{i}=-1)P_{s}(h_{s}(\sigma^{-}_{i})=-1) \displaystyle=\sum_{\sigma_{i}^{+}}P(\sigma^{+}_{i},c_{i}=1)\text{Tr}(\Pi_{1}\sigma_{i}^{+})+\sum_{\sigma_{i}^{-}}P(\sigma^{-}_{i},c_{i}=-1)\text{Tr}(\Pi_{-1}\sigma_{i}^{-}) \displaystyle=\text{Tr}(\Pi_{1}\sum_{\sigma_{i}^{+}}P(\sigma^{+}_{i})\sigma_{i}^{+})+\text{Tr}(\Pi_{-1}\sum_{\sigma_{i}^{-}}P(\sigma^{-}_{i})\sigma_{i}^{-}) \displaystyle=(\sum_{\sigma_{i}^{+}}P(\sigma^{+}_{i}))\text{Tr}(\Pi_{1}\Sigma^{+})+(\sum_{\sigma_{i}^{-}}P(\sigma^{-}_{i}))\text{Tr}(\Pi_{-1}\Sigma^{-}) where in the third equality we used P(\sigma^{\pm}_{i},c_{i}=\pm 1)=P(c_{i}=-\pm 1|\sigma^{\pm}_{i})P(\sigma^{\pm}_{i})=P(\sigma^{\pm}_{i}) and we define the normalised states \displaystyle\Sigma^{\pm}\equiv\frac{\sum_{\sigma_{i}^{\pm}}P(\sigma^{\pm}_{i})\sigma_{i}^{\pm}}{\sum_{\sigma_{j}^{\pm}}P(\sigma^{\pm}_{j})}. (157) For a unbiased dataset we have \sum_{\sigma_{j}^{\pm}}P(\sigma^{\pm}_{j})=1/2 . Then using the relation \Pi_{1}=\mathbf{1}-\Pi_{-1} we can write \displaystyle A_{s}=\frac{1}{2}\text{Tr}(\Pi_{1}(\Sigma^{+}-\Sigma^{-}))+\frac{1}{2}. (158) We will work using this unbiased assumption unless otherwise stated. Suppose we modify only the stochastic classifier, so we change the measurement \Pi\rightarrow\tilde{\Pi}=\sum_{l}E_{l}\Pi E_{l}^{\dagger} where \{E_{l}\} are Kraus operators. Then the robustness accuracy under this perturbation becomes \displaystyle\tilde{A}_{s}=\frac{1}{2}\text{Tr}(\tilde{\Pi}_{1}(\Sigma^{+}-\Sigma^{-}))+\frac{1}{2} \displaystyle=\frac{1}{2}\text{Tr}(\Pi_{1}(\tilde{\Sigma}^{+}-\tilde{\Sigma}^{-}))+\frac{1}{2} (159) where \tilde{\Sigma}^{\pm}=\sum_{l}E^{\dagger}_{l}\Sigma^{\pm}E_{l} . Then we can derive the difference \displaystyle|\tilde{A}_{s}-A_{s}|=\frac{1}{2}|\text{Tr}(\Pi_{1}(\tilde{\Sigma}^{+}-\Sigma^{+}+\Sigma^{-}-\tilde{\Sigma}^{-})|. (160) We can rearrange Eq. ( 160 ) to get \displaystyle|\tilde{A}_{s}-A_{s}|=\frac{1}{2}|\text{Tr}(\Pi_{1}(\tilde{\Sigma}^{+}+\Sigma^{-}-(\Sigma^{+}+\tilde{\Sigma}^{-})| \displaystyle=|\text{Tr}(\Pi_{1}(\Sigma_{A}-\Sigma_{B}))|\leq\tau(\Sigma_{A},\Sigma_{B}) (161) where \Sigma_{A}\equiv(1/2)(\tilde{\Sigma}^{+}+\Sigma^{-}) and \Sigma_{B}\equiv(1/2)(\Sigma^{+}+\tilde{\Sigma}^{-}) . As a very quick check, when the noise is the identity operation, we see that we see that the upper bound is saturated, since \tau(\Sigma_{A},\Sigma_{B}=\Sigma_{A})=0 .