High-dimensional quantum systems are vital for quantum technologies and are essential in demonstrating practical quantum advantage in quantum computing, simulation and sensing. Since dimensionality grows exponentially with the number of qubits, the potential power of noisy intermediatescale quantum (NISQ) devices over classical resources also stems from entangled states in high dimensions. An important family of quantum protocols that can take advantage of high-dimensional Hilbert space are classification tasks. These include quantum machine learning algorithms, witnesses in quantum information processing and certain decision problems. However, due to counter-intuitive geometrical properties emergent in high dimensions, classification problems are vulnerable to adversarial attacks. We demonstrate that the amount of perturbation needed for an adversary to induce a misclassification scales inversely with dimensionality. This is shown to be a fundamental feature independent of the details of the classification protocol. Furthermore, this leads to a trade-off between the security of the classification algorithm against adversarial attacks and quantum advantages we expect for high-dimensional problems. In fact, protection against these adversarial attacks require extra resources that scale at least polynomially with the Hilbert space dimension of the system, which can erase any significant quantum advantage that we might expect from a quantum protocol. This has wide-ranging implications in the use of both near-term and future quantum technologies for classification. Quantum technologies promise exciting advantages in quantum computation [1] , simulation [2] , metrology [3] and cryptography [4] . Even while large-scale and fault tolerant quantum technologies currently remain out of reach, noisy intermediate-scale quantum (NISQ) devices [5] hope to deliver advantages over classical systems in the near-term. Most of these protocols exploit not only unique quantum characteristics like entanglement and superposition, but also high-dimensional Hilbert spaces. Without the latter, no sizeable quantum advantages in either computation, simulation or sensing are expected. One important class of tasks where high-dimensional Hilbert spaces may be advantageous are classification problems. To correctly categorise an object belongs to one of the most common and basic questions asked in science. In the quantum setting, classification problems can appear mainly in one of two ways. Firstly, a quantum protocol can be used for classification problems with classical data in order to gain a quantum advantage in speed or precision. Many quantum-enhanced machine learning algorithms are of this type [6] . Alternatively, one can classify quantum states or processes themselves, in terms of entanglement [7] , phases [8] or other manybody behaviour. Quantum learning protocols also belong to the latter category [9] . From these examples, it therefore appears that advantages for classification tasks will become more pronounced as Hilbert-space dimension grows, at least in the absence of noise. However, as we will see, this is * Electronic address: nana.liu@quantumlah.org no longer true when the classification protocols are subject to adversarial perturbations. These are small, often hard-to-detect perturbations of the object to be classified which give rise to deliberate misclassification. This is highly relevant for many classification problems. In the machine learning context in particular, security breaches in the algorithm are not only desirable for adversarial parties, but also made possible as data used for classification are often shared amongst multiple, possibly untrusted parties [10] . Recent findings in machine learning suggests that even highly successful classification algorithms can be very vulnerable to adversarial perturbations if the dimension of the data is high enough, such as high-resolution image data [11] . Some quantum machine learning algorithms that resist certain kinds of adversarial attacks have also been recently developed [12] . However, it is yet unknown what the fundamental limits to adversarial robustness are for quantum classification problems in general. In this paper, we demonstrate that a perturbation by an amount scaling inversely with the dimension of the quantum system to be classified is sufficient to induce a misclassification. Amazingly, this is a fundamental feature of quantum classification originating from a purely geometrical property of high-dimensional spaces, known as the concentration of measure phenomenon [13] . It is independent of the specifics of any particular classification protocol. Furthermore, detection of these small perturbations by existing efficient certification protocols for quantum systems cannot be efficient. For classification problems, otherwise efficient certification protocols must now require resources scaling polynomially with dimensionality. This is an exponential resource cost in arXiv:1905.04286v1 [quant-ph] 10 May 2019 2 the corresponding number of qubits and can thus potentially erase any key quantum advantage from using high-dimensional quantum systems in the first place. This result presents a fundamental trade-off between the resources for preserving the security of the quantum system and resource advantages for classification protocols that exploit high-dimensional Hilbert space. Classification protocol that classify either raw quantum data or classical data embedded into quantum states will be subject to this limitation. Thus, this leads to widespread implications for many quantum classification tasks including, quantum machine learning algorithms, some witnesses in quantum information amongst others. To gain a more intuitive understanding of this result, we begin with examining what is special about classification problems, whose output belongs to a countable set. We compare this to quantum computational algorithms or other quantum protocols whose output can take on any continuous value. Suppose we have two parties, Alice and Bob. Alice wants to perform a classification task on an input quantum state σ, which is selected from the set Σ. The classification device Alice uses implements a function v : Σ → . This function can be written as v(σ) = Tr(OΛ(σ)), where Λ is a CPTP map performed by the device and O is an observable measured at the output of the device. For a classification problem, the final answer needs to be constrained to a discrete set of values and these are known as class labels. Thus v(σ) can be converted into discrete values h(σ) by using some thresholding function, e.g. h(σ) = sign(v(σ)) for binary classification. However, Bob may be a possibly adversarial party who can induce a small perturbation about σ that goes undetected by Alice. This means σ is modified into a state ρ where Alice is able to detect when F (σ, ρ) < 1 − χ but unable to detect when F (σ, ρ) ≥ 1 − χ. Then it can be shown, by applying Uhlmann's theorem, that |v(ρ)−v(σ)| is bounded above by a quantity proportional to √ χ (see Appendix A). Thus a small χ, which corresponds to a large overlap between σ and ρ, can result in a small difference O(χ) in the final real-number output of the quantum device. Although this might suggest that quantum protocols may in some cases be robust against perturbations of the input state, adversarial or otherwise, this inference does not necessarily hold for classification problems. Classification problems care about the discrete class label h(σ) rather than v(σ) itself. Thus if v(σ) lies very close to the decision boundary for h, even a small χ with corresponding small |v(ρ) − v(σ)| can mean ρ is classified differently to σ, i.e. h(σ) = h(ρ). This observation hints that, for classification problems, it is really the concentration of points near a decision boundary that matters, which can be mathematically captured by the concentration of measure phenomenon. Although already widely-used in quantum information in the context of quantifying average quantum behaviour of random quantum states [14] and related applications in cryptography [15] , it has not yet been employed for classification problems in the quantum setting. Notably, in many situations, this concentration of measure phenomenon predicts a growing concentration of points near such a decision boundary as the dimensionality of the problem increases. We will see that this implies that higher-dimensional quantum classification problems are more vulnerable to adversarial perturbations. To formalize our result, let us first introduce the following definitions. Definition 1. Suppose we want to assign classification labels s ∈ S to elements σ ∈ Σ where S is a countable set and σ can be either classical or quantum data. σ can refer to either states or processes. Functions c : Σ → S, belong to the set C known as ground truth if c(σ) gives the true classification label for any σ. These functions are not generally directly accessible. Functions belonging to H known as the hypothesis class are the accessible guesses to the ground truth. Definition 2. We select σ from Σ with respect to a probability measure µ and µ(Σ) = 1. Let M be the set of states that are misclassified by h ∈ H, i.e, M = {σ ∈ Σ|h(σ) = c(σ)}. Then we refer to µ(M) as the risk, which is the probability that the selected σ is misclassified by h. Definition 3. Let there be metric defined over Σ and the corresponding distance measure be denoted D. Then the −expansion of subsetΣ ⊆ Σ is defined as the set where D min (σ a ,Σ) is the infimum of the distance between σ and any element ofΣ. Then we call µ(M ) the adversarial risk under the perturbation of states σ by distance . This is equivalent to the probability that there is at least one state σ where D(σ, σ ) ≤ which is misclassified by h, i.e., h(σ ) = c(σ ). Definition 4. ForΣ ⊂ Σ with distance measure D and probability measure µ, we can define the concentration function α( ) as α( ) ≡ 1 − inf{µ(Σ )|µ(Σ) ≥ 1/2}. If Σ is also equipped with a vector space with dimension d and the corresponding space can be said to belong to the (l 1 , l 2 )-normal Levy family, where l 1 , l 2 > 0. Here α( ) quantifies the extent to which points in Σ concentrate about the boundary lines ofΣ ⊂ Σ. A small α( ) means a large concentration of points near such boundaries. For those spaces which belong to the normal Levy families, we see that this concentration near the boundary increase exponentially as the dimension d of the space increases. This is the concentration of measure phenomenon. We now focus our attention on Σ = SU (d) where SU (d) is the special unitary group. This choice will become clearer when we discuss our two scenarios. We can select σ ∈ SU (d) randomly according to the Haar probability measure and our goal is to classify σ where the risk is µ(M). Suppose h(σ) = c(σ). However, if σ is perturbed, for instance by an adversarial Bob, then the following theorem applies. Theorem 1. Suppose σ ∈ SU (d) and a perturbation σ → ρ occurs, where d HS (σ, ρ) ≤ and d HS is the Hilbert-Schmidt distance. If the adversarial risk is bounded above by R, then 2 must be bounded above by Proof. We only give the basic intuition behind the proof here, which is also based on recent classical machine learning results in [16] . Please refer to Appendix B for details. It is possible to show that having SU (d) equipped with the Haar probability measure and Hilbert-Schmidt metric belongs to the ( √ 2, 1/4)−normal Levy family, thus obeying Eq. (2). We choose Σ = SU (d). If the subset of misclassified points is denotedΣ = M, then Eq. (2) shows that more and more points tend to concentrate around the boundary of M as d increases. So if we select a point outside M, as d increases, the distance between the chosen point and the nearest point in M becomes smaller. This makes it more likely that only a small perturbation can result in misclassification. From theorem 1, we see that with large d, even a very small perturbation can result in a misclassification. As a result, it also becomes more and more difficult to certify whether or not σ has been adversarially perturbed. Furthermore, to certify whether a small perturbation has occurred requires extra resources in the quantum setting and these resources grow with increasing dimension. Thus a tension develops between the resources required to ensure robustness against misclassification and the quantum advantage expected as the dimension grows. Our aim is then to find fundamental limits to this tension that is independent of the details of any particular classification protocol. To describe this trade-off more precisely, in the following sections we examine two general scenarios, which we call untrusted state preparation and untrusted device preparation, depicted in Figure 1 . Untrusted state preparation-Alice wants to prepare and classify a d-dimensional pure quantum state σ, or equivalently a log 2 d-qubit state. Let σ = U |b b|U † , where U is Haar-randomly selected from SU (d) and |b is some given pure d-dimensional quantum state. Alice has a classical description of her σ, but does not have the quantum resources to create σ. She delegates to Bob the preparation of N copies of σ. However, Bob may be adversarial. He instead prepares a stateρ. This has the same dimensionality as σ ⊗N and ρ = σ ⊗N only when Bob is honest. So Alice assigns N state registers ofρ to certifying whether Bob could be an adversary. She can choose either state tomography or state certification for her test. Since state tomography demands more resources than state certification, it suffices to examine only the latter. In general, Bob has the capability of preparing anyρ where (i)ρ is some general entangled N register state with dimension 2 ⊗N . For our purpose here in finding a lower bound to N state , it is sufficient to consider case (iii). Thus Alice's certification task is to ascertain if F (ρ, σ) > 1 − χ to some high probability 1 − ∆ where χ small enough so that adversarial perturbations cannot be hidden. If this condition is not satisfied, then Alice rejects the state. Since (i) and (ii) require larger N state [34] our following results still hold for these cases. There are two main approaches to state certification. The first is the direct estimation of fidelity F (ρ, σ). To estimate the fidelity to precision η with failure probability ∆ requires the measurement of at least 1/(∆η 2 ) different Pauli observables. Hence at least this many copies of ρ are needed [17] . An alternative approach relies on a collection of binary-outcome measurements used to make the binary decision that the state satisfies either . However, since our aim is to find the minimal resource requirements for when F (ρ, σ) > 1 − χ, the fidelity estimation approach better suits our purpose. While improvements to state certification methods attempt to decrease the dependence of N state on d, the assumption is always of a constant η that is independent of d. The key difference in our scenario is that now it is η itself that carries a dimensional dependence. If Alice now sets R as the upper-bound to the adversarial risk she is willing to tolerate, the following statement holds true. Theorem 2a. Let Alice's quantum classification device implement the function h(σ) and let M be the set of states that h(σ) = c(σ). Alice needs N state copies of ρ to estimate the fidelity F(σ, ρ) to a precision that is necessary to guarantee that the adversarial risk is at most R with failure probability ∆. Then she requires at least copies of ρ, where g(µ(M), R) = 2 ln(2/(µ(M)(1 − R))). Proof. We sketch the basic ideas behind the proof here and refer the reader to Appendix C for details. Alice's selection of state σ is equivalent to her selecting U Haarrandomly from SU (d) [36] . Thus we can use Eq. (3) in Theorem 1. Next we need to change the HilbertSchmidt distance into the corresponding quantum fidelity, used for Alice's state certification scheme. Then Eq. (3) can be shown to be equivalent to This means that the error in estimating the fidelity must satisfy η < g(µ(M), R)/d 2 . Using the fidelity estimation approach [17] , N state > 1/(∆η 2 ). Thus In the absence of an adversarial Bob, Alice performs her classification task in three steps. First she prepares her input quantum state σ. She then inputs σ into her classification device which outputs a real number v(σ). Then Alice computes the corresponding class label by applying some thresholding function v(σ) → h(σ) and obtains the correct class label hcorrect. However, in many situations, Alice would want to delegate either her state preparation of σ or the preparation of her classification device to Bob. Even if Alice can certify the state or the device after receiving it from an adversarial Bob, she can still misclassify the input state if the dimension of σ is high. Untrusted state preparation (bottom left): Alice asks Bob for state σ and Bob instead returns the state ρ. Alice certifies that ρ is close to σ in fidelity and gets the output v(ρ) = v(σ) + δv(σ) from her device. Even when δv is small, once mapped to h, there can be a misclassification hincorrect. Untrusted device preparation (bottom right): Similarly, suppose Bob prepares the device implementing Λ instead of U and gives it to Alice. She is able to certify the device to some precision, and obtains the output v + δv where δv is small. However, small δv can still result in a misclassified label hincorrect if the dimension of σ is high enough. It is crucial to note that now N has a polynomial dependence on the dimension, which derives from the polynomial dependence of η on dimensionality. This has significant implications for the robustness of classification protocols against adversarial perturbations. Theorem 2a states that the minimum certification cost is exponential in the size of the quantum system, even when the certification protocol is considered otherwise efficient. For example, in quantum-enhanced machine learning algorithms, there are claims of quadratic and even up to exponential quantum speedups in d compared to the corresponding classical machine learning algorithms [6] . However, it is often assumed that the state preparation for converting classical data into quantum input states is delegated to an oracle, otherwise the resources for state preparation itself can over-ride resources potentially saved by employing a quantum algorithm [18] . This could be made possible for instance by delegating quantumrandom-access memory (QRAM) capabilities to Bob [6] . Yet, we saw that, even in the presence of such an oracle, Alice's certification requirements are of order at least d 4 . This would then still overwhelm any claimed exponential speedup and many quadratic speedup advantages afforded by these algorithms. From this we see a tradeoff between security and speedup as dimensionality increases. Untrusted device preparation-Suppose Alice now delegates only the preparation of the unitary part U of her classification device to a possibly adversarial Bob. Bob has no other power than the device preparation. If Bob is honest, he returns the prepared U to Alice, she inputs the quantum states |Ψ whose source she trusts. She then makes the final measurement on her device to obtain the classification of those states. If Bob is adversarial, then he may prepare a device that implements the CPTP map Λ instead. Given that Alice knows the classical description of U , she is able to perform device certification, by estimating the average channel-fidelity avg {|Ψ } Tr(Λ(|Ψ Ψ|)U |Ψ Ψ|U † ) [17] , where |Ψ is selected Haar-randomly. Then by using at least N device > 1/(∆ δ 2 ) calls to the device, Alice can estimate this fidelity to precision δ with failure probability ∆ . Similarly to the case in untrusted state preparation, if Alice wants to classify the states |Ψ selected like in Theorem 2a, the following result holds. Theorem 2b. Let U be the unitary that Alice wants to implement, which is used in a classification device that misclassifies inputs states with probability µ(M). Suppose Bob prepares, instead of U , the circuit implementing a CPTP map Λ. Then Alice requires at least calls to her device to estimate the average channel-fidelity to guarantee that that her adversarial risk is bounded above by R with failure probability ∆ . Proof. The ideas behind the proof are very similar to Theorem 2a. Let δ now be the error in estimating the average channel-fidelity with failure probability ∆ . The channel estimation protocol [17] requires that N device > 1/(∆ δ 2 ). Again employing Theorem 1 and converting the Hilbert-Schmidt distance to that of average channel-fidelity, we find δ < g(µ(M), R )/d 2 . Thus 5 the number of extra certification resources required where adversarial risk is bounded above by R is For details see Appendix D. An important example is in the context of quantum learning, where we wish to classify states that we do not have the classical descriptions of. These include for instance quantum-template matching [19] and quantum anomaly detection [20] , where the control-SWAP gate serves as the key component to the classification device. Since control-SWAP gates, especially for large dimensional systems, are difficult to experimentally realise [21] , these would be the gates delegated to Bob to prepare. However, certifying the control-SWAP gates to a constant precision η is insufficient and the minimum η to be robust against adversarial attacks must grow with scaling at least d 2 [37]. Other applications-It is also possible to apply our results to cases where machine learning is used to identify witnesses of physical properties like non-local correlations or the presence of phase transitions. Our results depend on a crucial requirement that the misclassification probability µ(M) > 0. This is almost always true when the classification function is learned from examples rather than derived from first principles. For instance, in [7, 22] , machine learning algorithms and training data are used to learn the decision boundary to determine whether a quantum state is entangled or separable and here µ(M) > 0. Other examples include learning decision boundaries for classifying phases [8] . These scenarios are all vulnerable to adversarial perturbations described in this paper. Discussion-While high-dimensional Hilbert spaces are often considered beneficial for quantum information processing, its vulnerabilities apart from sensitivity to decoherence are almost entirely unexplored. In this paper we examine one important instance. For classification problems involving quantum states or processes, we demonstrate a fundamental bound showing how higherdimensional quantum systems are more sensitive to adversarial perturbations than lower-dimensional systems. This phenomenon is independent of any decoherence effects or details of any particular classification protocol. Furthermore, any exponential quantum advantages in classification are erased by this behaviour. Our results so far come from finding bounds to the minimum distance between Alice's original datum σ and the nearest element in the originally misclassified set M. However, these nearest elements to σ might have zero measure, thus cannot be reached if Bob perturbs σ in random directions. These cases are significant to consider, because it means that these misclassified points can only be reached from σ by adversarial perturbations, i.e., Bob deliberately moving σ to an element in M. Thus, an important future direction is to examine the differences between the resources required for Alice to remain robust against adversarial perturbations to that of random perturbations or perturbations induced by noise, for instance in [23] . This is particularly poignant in the NISQ-era of quantum technologies. To further understand the effects of highdimensionality, it is important to go to the extreme case of continuous-variable quantum information, with potentially infinite degrees of freedom. It is then compelling to investigate whether these quantum systems possess some maximal sensitivity to adversaries and if this power can be harnessed to devise novel detection methods. We are now only unravelling the beginnings of how high-dimensional quantum systems behave under adversarial perturbations. This has both practical and foundational ramifications. Its relevance will increasingly grow as quantum devices are networked together in a future quantum internet [24] and adversarial considerations become inevitable.
Recently, it has been indicated that this phenomenon is also present in the case of quantum classifiers REF , where the dimension plays a very important role: the higher the dimension the easier to carry out those adversarial attacks.
Vulnerability of quantum classification to adversarial perturbations
arXiv: Quantum Physics
Physics Mathematics