February 04, 2026
Standard approaches to quantum statistical inference rely on measurements that induce a collapse of the wave function, effectively consuming the quantum state to extract information. In this work, we investigate the fundamental limits of locally-gentle quantum state certification, where the learning algorithm is constrained to perturb the state by at most \(\alpha\) in trace norm, thereby allowing for the reuse of samples. We analyze the hypothesis testing problem of distinguishing whether an unknown state \(\rho\) is equal to a reference \(\rho_0\) or \(\epsilon\)-far from it. We derive the minimax sample complexity for this problem, quantifying the information-theoretic price of non-destructive measurements. Specifically, by constructing explicit measurement operators, we show that the constraint of \(\alpha\)-gentleness imposes a sample size penalty of \(\frac{d}{\alpha^2}\), yielding a total sample complexity of \(n = \Theta(\frac{d^3}{\epsilon^2 \alpha^2})\). Our results clarify the trade-off between information extraction and state disturbance, and highlight deep connections between physical measurement constraints and privacy mechanisms in quantum learning. Crucially, we find that the sample size penalty incurred by enforcing \(\alpha\)-gentleness scales linearly with the Hilbert-space dimension \(d\) rather than the number of parameters \(d^2-1\) typical for high-dimensional private estimation.
A central postulate of quantum mechanics dictates that observation inevitably alters the observed system. In the standard regime of projective measurements, this disturbance is maximal, resulting in the "collapse of the wave function". Consequently, the quantum state is effectively consumed upon measurement, preventing any further extraction of information from that specific copy. While this destructive nature is assumed in most quantum testing algorithms, it is not an absolute necessity.
In this work, we depart from the destructive paradigm and investigate the challenge of locally-gentle quantum state certification. Here, the learning algorithm is constrained to perform measurements that are minimally invasive. Formally, we aim to learn an unknown quantum state \(\rho \in \mathbb{C}^{d \times d}\) given access to n copies. We consider the hypothesis testing task: \[\label{eqn::state95certification95problem} H_0: \rho = \rho_0\text{vs}H_1: \norm{\rho - \rho_0}_{Tr} > \epsilon,\tag{1}\] where \(\norm{\cdot}_{Tr}\) denotes the trace norm. Crucially, we enforce that the measurements are \(\alpha\)-gentle. That is, for a gentleness parameter \(\alpha\), the measurement ensures that the distance between the pre-measurement state \(\rho\) and the post-measurement state \(\rho_{M \to y}\) is bounded by \(\norm{\rho - \rho_{M \to y}}_{Tr} \leq \alpha\).
Unlike the standard setting where the state collapses to an eigenstate, this constraint ensures the state is only altered \(\alpha\)-minimally and can therefore be reused for subsequent information extraction. It has been suggested ([1]) that this preservation of quantum information is essential for the efficient implementation of quantum backpropagation algorithms. The central objective of this paper is to determine the information-theoretic price of this preservation, aiming to answer the question:
What is the sample complexity penalty incurred by enforcing \(\alpha\)-gentleness?
Prior to recent developments, the literature on the statistical properties of gentle measurements was sparse, extending little beyond the rudimentary bounds provided by the gentle measurement lemma [2]. A significant shift occurred when [3] established a connection between gentleness and differential privacy, proposing a gentle algorithm for shadow tomography—a task distinct from ours where the goal is to learn only some "basic properties" of the state rather than the state itself. Recently, [4] analyzed locally-gentle state tomography and certification specifically for qubits. They established that for these single-qubit tasks, gentleness incurs a multiplicative penalty of \(\frac{1}{\alpha^2}\), resulting in a sample optimal rate of \(n = \Theta(\frac{1}{\epsilon^2 \alpha^2})\).
Quantum state certification is a special task of quantum property testing ([5]) in which one aims to learn properties of a quantum state by means of quantum measurements. This field of research has seen a great amount of interest in recent years with the works of [6]–[9] and [10]. While [6] and [7] consider the theoretically more efficient regime of entangled measurements, given their current experimental unfeasibility ([11]), the focus has shifted in recent years to develop sample optimal algorithms for unentangled (product) measurements. [8] showed that for unentangled randomized measurements, a total of \(n = \Theta(\frac{d^{3/2}}{\epsilon^2})\) copies of \(\rho\) are needed to distinguish it from the maximally mixed state. Later, [9] provided an algorithm using mutually unbiased bases that achieves state certification using \(n = O(\frac{d^2}{\epsilon^2})\) copies with fixed measurements. [10] subsequently proved the corresponding lower bound \(n = \Omega(\frac{d^2}{\epsilon^2})\) for fixed unentangled measurements. Furthermore, their proof technique recovered the lower bound from [8] as a corollary. They also provided a generalized upper bound algorithm utilizing 2-designs, which coincides with that of [9] when d is a prime power.
It was observed by [3] that a global gentle measurement can be constructed such that the resulting statistics follow the Laplace mechanism known from classical differential privacy [12]. While [3] discussed approximate implementations of the aforementioned mechanism, [4] constructed an implementable physical measurement, gentle on each system component, where the outcomes follow the label switching privacy mechanism ([13]). Given the prominence of differential privacy in statistical inference [14]–[16], a major challenge lies in upgrading classical privacy mechanisms into gentle measurements that preserve the quantum state while providing optimal guarantees for the inference problem at hand.
We now state our main result, which establishes the fundamental limit for quantum state certification under local gentleness constraints and give a short description of the main technical difficulties of our contributions. The following Theorem synthesizes the upper bound (Theorem 3) and the matching lower bound (Theorem 4).
Theorem 1 (Minimax Sample Complexity). Consider the testing task \(H_0: \rho = \rho_0\) versus \(H_1: \norm{\rho - \rho_0}_{\mathrm{tr}} > \epsilon\), where \(\rho_0 = \frac{1}{d}\text{\usefont{U}{bbm}{m}{n}1}\) is the maximally mixed state. Then, a total number of \[n = \Theta\left( \frac{d^3}{\alpha^2 \epsilon^2} \right)\] copies are needed and sufficient to achieve a success probability of at least \(2/3\) when restricting ourselves to fixed, unentangled, locally \(\alpha\)-gentle measurements,.
Comparing our result to the standard unentangled setting, where \(n = \Theta(d^2/\epsilon^2)\) is sufficient for fixed measurements ([9]), we observe that enforcing \(\alpha\)-gentleness incurs a multiplicative penalty of \(d/\alpha^2\). This scaling highlights a surprising efficiency in quantum gentle learning. The parameter space of a \(d\)-dimensional quantum state has dimension \(d^2-1\). In classical differential privacy, the sample complexity penalty typically scales linearly with the dimension of the parameter space (i.e., one might expect a penalty of order \(d^2\)). However, we find that the quantum “price of gentleness” scales only as \(d\). This separation suggests that “lifting” classical privacy mechanisms to the quantum regime, that is converting stochastic maps into physical measurement operators, yields fundamentally different statistical behaviors due to the specific geometric properties of quantum state space.
A major challenge in gentle learning is “lifting” classical private mechanisms (which act on probability distributions) into valid quantum instruments (which act on density matrices). We propose an explicit construction of measurement operators that satisfy the gentleness constraint while preserving statistical utility. Our construction utilizes quantum \(2\)-designs, which are finite sets of unit vectors related to the Haar-measure on the unitary group. Aiming at generalizing the classical RAPPOR mechanism for high-dimensional private testing ([16]), we define a “noisy” measurement operator that is both gentle and statistically optimal. For a proper \(2\)-design comprised of vectors \((\ket{v_m})_{m = 1}^D\), a vector \(z \in \{0,1\}^D\), and a noise parameter \(\delta > 0\), we define the operator: \[E_{\delta, z} = \left( \frac{e^{\delta/2}}{e^{\delta/2} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D e^{-\frac{\delta}{2} \norm{z - e_m}_1} \ket{v_m}\bra{v_m},\] where \(e_m \in \{0,1\}^D\) is the standard basis vector for the \(m\)-th entry. We prove that for appropriate \(\delta\), the collection \(\{E_{\delta, z}\}_z\) forms a valid POVM that is \(\alpha\)-gentle. Furthermore, we show that classical post-processing of the outcomes of this POVM achieves the upper bound.
To establish optimality, we extend the lower bound framework of [10]. A critical technical obstacle arises from the nature of gentleness: as noted in [4], gentle measurements must be full-rank. Otherwise, input states near the operator’s null space would suffer total collapse. Consequently, we cannot rely on standard techniques that assume rank-one POVMs.
We overcome this by analyzing the specific structure of the information loss. For a gentle measurement defined by POVM elements \((E_y)_{y \in \mathcal{Y}}\), we characterize the \(\chi^2\)-fluctuation around the distribution induced by \(\rho_0\) via the linear super-operator \(\mathcal{H}: \mathbb{C}^{d \times d} \to \mathbb{C}^{d \times d}\), defined as: \[\require{physics} \label{eqn::defn95linear95superoperator} \mathcal{H}(A) := \sum_{y \in \mathcal{Y}} \frac{\Tr[ A E_{y} ]}{\Tr[E_{y}]} E_{y}.\tag{2}\] We show that \(\mathcal{H}\) captures the relevant statistical properties of general (non-rank-one) measurements, serving as a generalization of the analysis of the Lüders channel. By proving that \(\mathcal{H}\) is self-adjoint, we can identify the least sensitive directions in the state space along which to perturb \(\rho_0\) corresponding to the smallest eigenvalues of \(\mathcal{H}\). Constructing local perturbations along these directions yields the matching lower bound.
| non-gentle | gentle | |
|---|---|---|
| Bound | ([9]) | (Theorem [thm::upper95bound]) |
| Bound | ([10]) | (Theorem [thm::lower95bound]) |
A \(d\)-dimensional quantum system is based on the Hilbert space \(\mathbb{C}^d\) with the standard complex inner product. A state of the system is given by a positive self-adjoint matrix (positive for short) \(\rho \in \mathbb{C}^{d \times d}\) with trace one, i.e. \(\require{physics} \Tr[\rho] = 1\). A state \(\rho\) of the system is said to be pure if it has rank one, i.e. \(\rank(\rho) = 1\). In that case we can write \(\rho = \ket{\psi}\bra{\psi}\) for a normalized vector \(\ket{\psi} \in \mathbb{C}^d\). As such, we often identify pure states with one of their representational vectors \(\ket{\psi}\). We denote by \(\mathcal{S}(\mathbb{C}^d)\) the convex set of all quantum states and by \(\mathcal{S}_{pure}(\mathbb{C}^d)\) the set of pure quantum states. Composite quantum systems are described by the tensor product of the individual parts. The product state of \(n\) identical and independent states \(\rho\) is given by \(\rho^{\otimes n} := \rho \otimes ... \otimes \rho \in \mathcal{S}((\mathbb{C}^d)^{\otimes n})\).
There are several notions of measurements in quantum mechanics that are more or less general. The one we chose here is as in [17] and is the most general one that allows us to define the notion of post-measurement states which will be essential for gentleness. A quantum measurement is given by a set of measurement operators \(M = (M_y)_{y \in \mathcal{Y}} \subseteq \mathbb{C}^{d \times d}\) such that \[\label{eqn::resolution95of95identity} \sum_{y \in \mathcal{Y}} M_y^* M_y = \text{\usefont{U}{bbm}{m}{n}1},\tag{3}\] where \(\text{\usefont{U}{bbm}{m}{n}1}\) denotes the \(d \times d\) identity matrix. The outcome of a quantum measurement is random and alters the state of the system. Measuring the states \(\rho\) or \(\ket{\psi}\) one obtains the outcome \(y \in \mathcal{Y}\) with probability \[\require{physics} \begin{align} \mathbb{P}_{\rho}\left( R^M = y \right) = \Tr\left[ \rho M_y^*M_y \right]&\text{and}\mathbb{P}_{\ket{\psi}}\left( R^M = y \right) = \left| \bra{\psi}M_y^*M_y\ket{\psi} \right| = \norm{M_y \ket{\psi}}^2 \intertext{respectively. The state of the system after the measurement (the post-measurement state) is given by} \rho_{M \to y} = \frac{1}{\sqrt{\mathbb{P}_{\rho}\left( R^M = y \right)}} M_y\rho M_y^*&\text{and}\ket{\psi}_{M \to y} = \frac{1}{\sqrt{\mathbb{P}_{\ket{\psi}}\left( R^M = y \right)}} M_y \ket{\psi} = \frac{M_y \ket{\psi}}{\norm{M_y \ket{\psi}}} \end{align}\] respectively. A measurement \(M\) on a composite system \((\mathbb{C}^d)^{\otimes n}\) is said to be product if it acts independently on each state of the joint system and can be written as \(M = M^{(1)} \otimes .... \otimes M^{(n)}\) given by measurement operators \(M_y = M_{y_1}^{(1)} \otimes ... \otimes M_{y_n}^{(n)}\) for \(y \in \mathcal{Y}_1 \times ... \times \mathcal{Y}_n\). If \(M^{(1)} = ... = M^{(n)}\) we write \(M = (M^{(1)})^{\otimes n}\) for short. The outcome of a product measurement on a product state are independent random variables.
A (proper) 2-design is a finite set of \(D\) normalized-vectors \((\ket{v_m})_{m = 1}^D\) such that \[\label{eqn::295design95definition} \frac{1}{D} \sum_{m = 1}^D (\ket{v_m}\bra{v_m})^{\otimes 2} = \int \ket{\psi}\bra{\psi}^{\otimes 2} d\mu(\psi)\tag{4}\] where \(\mu\) is the Haar-measure on the unit sphere in \(\mathbb{C}^d\). For a proper 2-design \((\ket{v_m})_{m = 1}^D\), the operators \((\sqrt{\frac{d}{D}} \ket{v_m}\bra{v_m})_{m = 1}^D\) define a quantum measurement and for any self-adjoint matrix \(M\) it holds (see [10]) \[\require{physics} \label{eqn::property95295design} \frac{1}{D} \sum_{m = 1}^D \bra{v_m}M\ket{v_m} = \frac{1}{d(d+1)} \left( \Tr[M^2] + \Tr[M]^2 \right).\tag{5}\] Their importance arises from the fact that they are highly symmetric, preserving the second moment of the Haar-measure ([18]). Given that the optimal randomized measurement for state certification samples a Haar-random unitary ([8]), 2-designs are a natural way to define fixed, non-random measurements. This property has already successfully been applied to quantum state tomography ([19]) and state certification ([10]). Although their properties in general dimension \(d\) remain an open field of study it has been shown ([20]) that a collection of mutually unbiased bases forms a proper 2-design. For \(d = p^q\) being a prime power, it is known, that there are \(q+1\) mutually unbiased bases such that \(D = d(d+1)\). However, as the measurement operators defined by a quantum 2-design are rank-one they cannot be gentle ([4]). In order to define a gentle measurement based on 2-designs we must therefore be more careful in constructing the measurement operators for our state certification algorithm.
The quantum analogues of the total variation and the \(\mathbb{L}_2\) distances between likelihoods are the trace-norm distance and the Frobenius-norm distance, respectively, between quantum states. These distances between the states \(\rho_1\) and \(\rho_2\) are defined as \[\require{physics} \norm{\rho_1 - \rho_2}_{Tr} = \frac{1}{2} \Tr\left[ |\rho_1 - \rho_2| \right]\text{and}\norm{\rho_1 - \rho_2}_F = \Tr\left[ (\rho_1 - \rho_2)^2 \right]^{\frac{1}{2}}\] respectively. Here, for \(A \in \mathbb{C}^{d \times d}\), \(|A| = \sqrt{A^*A}\) denotes its matrix absolute value. Note that, since \(\rho_1 - \rho_2\) is a self-adjoint operator, it admits a spectral decomposition \(\rho_1 - \rho_2 = \sum_{j = 1}^d \mu_j \ket{\psi_j}\bra{\psi_j}\) for an orthonormal basis \((\ket{\psi}_j)_{j = 1,...,d}\) of \(\mathbb{C}^d\). Then it holds \[\norm{\rho_1 - \rho_2}_{Tr} = \frac{1}{2} \sum_{j = 1}^d |\mu_j|\text{and}\norm{\rho_1 - \rho_2}_F = \left(\sum_{j = 1}^d |\mu_j|^2\right)^{\frac{1}{2}},\] i.e. the Trace-norm and Frobenius-norm are equivalent to the Schatten-1 and -2-norms respectively. Note that the Frobenius-norm is the norm induced by the inner product \(\require{physics} \langle A, B \rangle = \Tr\left[ A^* B \right]\) on \(\mathbb{C}^{d \times d}\). Both of the above norms have simpler forms for pure states.
Lemma 1. ([21]) Let \(\rho_1 = \ket{\psi_1}\bra{\psi_1}, \rho_2 = \ket{\psi_2}\bra{\psi_2}\) be two pure states. Then the trace-norm and Frobenius-norm distance between the two is given by \[\norm{\rho_1 - \rho_2}_{Tr} = \sqrt{1 - |\bra{\psi_1}\ket{\psi_2}|^2}\text{and}\norm{\rho_1 - \rho_2}_{F} = \sqrt{2(1 - |\bra{\psi_1}\ket{\psi_2}|^2)}.\]
We can define the Trace- and Frobenius-norm for a super-operator \(\mathcal{H}\) as the Schatten-1 and 2-norms of \(\mathcal{H}\) on the Hilbert-space \(\mathbb{C}^{d \times d}\) endowed with the inner product \(\require{physics} \langle A, B \rangle = \Tr\left[ A^* B \right]\) on \(\mathbb{C}^{d \times d}\). That is, for an orthonormal basis \((V_j)_{j = 1,...,d^2}\) of \(\mathbb{C}^{d \times d}\) we define \[\norm{\mathcal{H}}_{Tr} = \frac{1}{2} \sum_{j = 1}^{d^2} \left| \langle V_j, \mathcal{H}(V_j)\rangle \right| \text{and}\norm{\mathcal{H}}_F = \left( \sum_{j = 1}^{d^2} \left|\langle V_j, \mathcal{H}(V_j) \rangle \right|^2 \right)^{\frac{1}{2}}.\]
In order to asses the quality of our tests we make use of metrics on the space of probability distributions. Notably the total-variation-distance that is intimately related to the optimal error of a test and the \(\chi^2\)-distance that allows us to bound the test error using properties that behave nicely for our set of local alternatives. The total-variation- and \(\chi^2\)-distances for mutually absolutely continuous probability distributions \(\mathbb{P}_0, \mathbb{P}_1\) on \((\mathcal{Y}, \mathcal{P}(\mathcal{Y}))\) with probability mass functions \(p\) and \(q\) are define as \[\norm{\mathbb{P}_1 - \mathbb{P}_0}_{TV} = \frac{1}{2} \sum_{y \in \mathcal{Y}} \left| p_1(y) - p_0(y) \right|\text{and}d_{\chi^2}(\mathbb{P}_1, \mathbb{P}_0) = \sum_{y \in \mathcal{Y}} \frac{p_1(y)^2}{p_0(y)} -1\] respectively. Let \(H_0: \mathbb{P} = \mathbb{P}_0\) vs. \(H_1: \mathbb{P} = \mathbb{P}_1\). Then for the error of the test \(\Delta^*\) that distinguishes optimally between the two hypotheses \(H_0\) and \(H_1\), it holds \[\mathbb{P}_0(\Delta^* = 1) + \mathbb{P}_1(\Delta^* = 0) = 1 - \norm{\mathbb{P}_0 - \mathbb{P}_1}_{TV}.\] Together with the inequality \(\norm{\mathbb{P}_1 - \mathbb{P}_0}_{TV} \leq \sqrt{d_{\chi^2}(\mathbb{P}_1, \mathbb{P}_0)}\) (see [22]), we can bound the optimal testing by controlling the \(\chi^2\)-distance. The following result will prove useful for our lower bounds as it evaluates the \(\chi^2\)-distance between a product distribution \(\mathbb{P}_0=\mathbb{P}\) and an average \(\mathbb{P}_1 = \mathbb{E}_{\nu}\left[ \mathbb{Q}_{\nu} \right]\) of product distributions \(\mathbb{Q}_{\nu}\) with respect to a prior measure over the parameters \(\nu\).
Theorem 1. (Lemma 8 in [23]) Let \(\mathbb{P} = \mathbb{P}^{(1)} \otimes ... \otimes \mathbb{P}^{(n)}\) be a fixed probability distribution and \(\mathbb{Q}_{\nu} = \mathbb{Q}_{\nu}^{(1)} \otimes ... \otimes \mathbb{Q}_{\nu}^{(n)}\) be another mutually absolutely continuous probability distribution indexed by a random parameter \(\nu \in \mathcal{V}\) on a space \((\prod_{i = 1}^n \mathcal{Y}_i, \bigotimes_{i = 1}^n \mathscr{Y}_i)\) with densities \(p(y) = \prod_{i = 1}^n p_i(y_i)\) and \(q_{\nu}(y) = \prod_{i = 1}^n q_{\nu}^{(i)}(y_i)\) with respect to a common measure. Then it holds \[d_{\chi^2}\left( \mathbb{E}_{\nu}\left[ \mathbb{Q}_{\nu} \right], \mathbb{P} \right) = \mathbb{E}_{\nu_1, \nu_2} \left[ \prod_{i = 1}^n \left( 1 + H_i(\nu_1, \nu_2) \right) \right] - 1,\] where \(\nu_1, \nu_2\) are two independent copies of \(\nu\) and \[H_i(\nu_1, \nu_2) = \mathbb{E}_{y_i \sim \mathbb{P}^{(i)}}\left[ \delta_{\nu_1}^{(i)}(y_i) \delta_{\nu_2}^{(i)}(y_i) \right]\text{and}\delta_{\nu}^{(i)}(y_i) = \frac{q_{\nu}^{(i)}(y_i) - p^{(i)}(y_i)}{p^{(i)}(y_i)}.\]
Quantum measurements generally alter the state that they measure. The idea of gentleness is to limit the amount of alteration by the measurement. This renders the post-measurement states useful for further application. We achieve this by limiting the distance between the states before and after the measurements.
Definition 1. For a given gentleness parameter \(\alpha \in [0,1]\), a measurement \(M\) is \(\alpha\)-gentle on a set \(\mathcal{S}\) of quantum states if for all possible measurement outcomes \(y\) \[\norm{\rho - \rho_{M \to y}}_{Tr} \leq \alpha\text{for all } \rho \in \mathcal{S}.\]
If \(\rho = \rho_1 \otimes ... \otimes \rho_n\) is a product state belonging to \(\mathcal{S}_1 \otimes ... \otimes \mathcal{S}_n =: \mathcal{S}^n\), we say that a measurement \(M\) is locally-\(\alpha\)-gentle if it is a product measurement \(M = M_1 \otimes ... \otimes M_n\) and \(M_i\) is \(\alpha\)-gentle on \(\mathcal{S}_i\) for all \(i\).
Note that the notion of locally \(\alpha\)-gentle product measurements is different to that of (possibly coherent) \(\alpha\)-gentle measurements \(M\) on product states in \(\mathcal{S}^n\). An example of the latter is given by the Laplace mechanism from [3] which is not locally-\(\alpha\)-gentle.
A concept that has been shown (by [3]) to be closely related to gentleness is that of quantum differential privacy. In contrast to gentleness, quantum differential privacy is only concerned with the probability of the measurement outcomes.
Definition 2. A measurement \(M\) is said to be \(\delta\)-quantum-differentially-private (\(\delta\)-qDP) for \(\delta>0\) on a set \(\mathcal{S}\) of quantum states, if for the outcome probabilities of any two states \(\rho_1, \rho_2\) in \(\mathcal{S}\) under \(M\) it holds \[\label{eqn::quantum95privacy95equation} \mathbb{P}_{1}(R^{M} = y) \leq e^{\delta} \mathbb{P}_2(R^{M} = y)\text{for all } y \in \mathcal{Y}.\qquad{(1)}\] We call a product measurement \(M = M_1 \otimes ... \otimes M_n\) locally-\(\delta\)-quantum-differentially private on \(\mathcal{S}_1 \otimes ... \otimes \mathcal{S}_n =: \mathcal{S}^n\) if each \(M_i\) is \(\delta\)-quantum-differentially private on \(\mathcal{S}_i\).
We see that, as with gentleness, the locality of the quantum differential privacy for product measurements can be verified by checking the property on each register separately. One of the main results from [3] was the fact gentleness and quantum differential privacy represent two sides of the same coin. Note however that for any measurement \(M = (M_y)_{y \in \mathcal{Y}}\) the quantum differential privacy of \(M\) is only dependent on the operators \(E_y = M_y^*M_y\) while the gentleness of \(M\) is dependent on the operators \(M_y\) themselves. Since for any family \(U = (U_y)_{y \in \mathcal{Y}}\) of unitaries on \(\mathbb{C}^d\), the operators \(UM = (U_y M_y)_{y \in \mathcal{Y}}\) also define a quantum measurement with a possibly different gentleness value. However, since \((M_y U_y)^* (U_y M_y) = M_y^* M_y\), the outcome distributions of both measurements are the same, which means that their quantum differential privacy parameter is also the same. When talking about gentle measurements we must therefore always consider which implementation of \(M\) we are working with. The following theorem gives an overview on the relation between the gentleness and quantum differential privacy. Its proof can be found in Appendix 7.
Theorem 2. Let \(M = (M_y)_{y \in \mathcal{Y}}\) be a quantum measurement. Then the following two results hold
If \(M\) is locally-\(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^d)^{\otimes n}\), then there exists an implementation of \(M\) such that \(M\) is \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)^{\otimes n}\) for \(\alpha = (e^{\frac{\delta}{2}} -1)/(e^{\frac{\delta}{2}} +1) = \tanh(\delta/4)\). The implementation is given by the positive definite operators \((|M_y|)_{y \in \mathcal{Y}}\).
If \(M\) is locally-\(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)^{\otimes n}\) for \(\alpha < 1/2\), then \(M\) is locally-\(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^d)^{\otimes n}\) for \(\delta = 2\log((1+2\alpha)/(1-2\alpha)) = 4 \mathop{\mathrm{arctanh}}(2 \alpha)\).
[4] have shown that the relation from gentleness to quantum differential privacy can be improved for positive-definite operators. For positive-definite operators, a locally-\(\alpha\)-gentle measurement is locally-\(\delta\)-quantum-differentially-private for \(\delta = 2\log((1+\alpha)/(1-\alpha)) = 4 \mathop{\mathrm{arctanh}}(\alpha)\) (see Lemma 2). This result, together with Theorem 2, establishes a one-to-one correspondence between gentle and quantum differentially private measurements for positive-definite operators with optimal constants relating the two.
Another useful result for both gentleness as well as quantum differential privacy is the fact that it suffices to verify them on the set of pure quantum states. Proposition 7 assures that it is enough to calculate the gentleness of a measurement on pure states most of the time to show gentleness on all states. Furthermore, Proposition 5 assures that a measurement is locally-\(\delta\)-quantum-differentially-private on mixed states if and only if it is locally-\(\delta\)-quantum-differentially-private on pure states. Furthermore, in order to verify quantum differential privacy of a measurement \(M = (M_y)_{y \in \mathcal{Y}}\) it suffices to check that \(\lambda_{max}(E_{y}) \leq e^{\delta} \lambda_{min}(E_{y})\) for all \(y \in \mathcal{Y}\), where \(E_{y} = M_{y}^*M_{y}\).
Let us now demonstrate how to construct a locally-\(\alpha\)-gentle state certification algorithm. The construction of our measurement is based on proper 2-designs which have already proven of great value for quantum learning of high-dimensional states ([19], [10]). For simplicity, we will assume in this section that \(d = p^q\) is a prime power. In that case, the existence of a proper 2-design is guaranteed through mutually unbiased bases ([20]). The measurement we propose randomizes the projectors of the 2-design in such a way that prevents the state from collapsing such that is far from the pre-measurement state. Let \((\ket{v_m})_{m = 1}^D\) be a proper quantum 2-design and set \(\delta = 4 \mathop{\mathrm{arctanh}}(\alpha)\). For \(e_m \in \{0,1\}^D\) being the vector that is zero everywhere except in the m-th entry, let us now define \[\label{eqn::measurement95definion} E_{\delta, z} = \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D e^{-\frac{\delta}{2} \norm{z - e_m}_1} \ket{v_m}\bra{v_m}\text{and}M_{\delta, z} = \sqrt{E_{\delta, z}}\tag{6}\] for every \(z \in \{0,1\}^D\) and set \(M_{\delta} = (M_{\delta, z})_{z \in \{0,1\}^D}\). Note that the matrices \(E_{\delta, z}\) are not diagonal as the vectors \(\ket{v_m}\) are not pairwise orthogonal. This so-defined measurement is a gentle-ized version of measuring the 2-design \((\sqrt{\frac{d}{D}} \ket{v_m}\bra{v_m})_{m = 1}^D\) directly and Lemma 3 shows that \(M_{\delta}^{\otimes n}\) is in fact a locally-\(\alpha\)-gentle measurement on \(\mathcal{S}((\mathbb{C}^d)^{\otimes n})\). When applying the product measurement \(M_{\delta}^{\otimes n}\) to the state \(\rho^{\otimes n}\) we obtain \(n\) independent and identically distributed random variables \(R^{M_{\delta}}_i \in \{0,1\}^D\). Based on these outcomes, we define \[N_m = \sum_{i = 1}^n \text{\usefont{U}{bbm}{m}{n}1}_{\{ (R^{M_{\delta}})_m = 1 \}}\] which counts the occurrences of each entry being measured. In order to now test between the two hypotheses \[\label{eqn::testing95problem} H_0: \rho = \rho_0vs.H_1: \norm{\rho - \rho_0}_{Tr}> \epsilon\tag{7}\] we compare \(N_m\) to the expected outcome \(p_{\rho}(m) = \frac{d}{D} \bra{v_m} \rho \ket{v_m}\) without gentleness while correcting for the biased introduced by measuring the state gently. More precisely, for \(p_{\rho_0}(m) = \frac{d}{D}\bra{v_m}\rho_0\ket{v_m}\) and \(\beta = (e^{\frac{\delta}{2}} + 1)^{-1}\) we calculate \[T_n = \sum_{m = 1}^D \left( (N_m - (n-1) (\alpha p_{\rho_0}(m) + \beta))^2 - N_m + (n-1)(\alpha p_{\rho_0}(m) + \beta)^2 \right)\] based on which we define the test \[\label{eqn::test95definition} \Delta_n = \text{\usefont{U}{bbm}{m}{n}1}_{\{T_n > c\}}\text{ for }c = \frac{1}{2} \frac{n(n-1)\alpha^2 \epsilon^2}{Dd}.\tag{8}\] For this test procedure, we have the following result.
Theorem 3. Consider the testing task 7 and assume \(n = O( \frac{d^3}{\epsilon^2 \alpha^2} )\). Then, for the test \(\Delta_n\) defined in 8 it holds \[\begin{align} \mathbb{P}_{0}(\Delta_n = 1) + \sup_{\rho \,:\, \norm{\rho - \rho_0} > \epsilon} \mathbb{P}_{\rho}(\Delta_n = 0) \leq \frac{1}{3}. \end{align}\]
Proof. In order to show the sample complexity of our algorithm, we relate the properties of the measurement 6 to the RAPPOR mechanism. To see this, let \[\require{physics} p_{\rho}(m) = \Tr\left[ \frac{d}{D} \ket{v_m}\bra{v_m} \rho \right] = \frac{d}{D} \bra{v_m}\rho\ket{v_m}\] be the probability of measuring the state \(\rho\) non-gently using the 2-design \((\ket{v_m})_{m = 1}^D\) directly (that is, using the measurement \(M_{2-\text{design}} = (\sqrt{\frac{d}{D}} \ket{v_m}\bra{v_m})_{m = 1,...,D}\)). The crucial result of our proof is now that the outcome probabilities of the measurement 6 are equal to the the outcomes of applying the RAPPOR mechanism to the probability distribution \(p_{\rho}\). To see this equality, consider the privatization mechanism described by, where, depending on the outputs of \(R^{M_{2-\text{design}}}\), we independently draw \(D\) elements \(z_j \in \{0,1\}\) according to \[\begin{align} Q_j(Z_j = z_j | R^{M_{2-\text{design}}} = m) &= \frac{1}{e^{\frac{\delta}{2}}+1} \begin{cases} z_j e^{\frac{\delta}{2}} + (1-z_j) & j = m \\ (1-z_j) e^{\frac{\delta}{2}} + z_j & j \neq m \end{cases}.\label{eqn::privacy95kernel95multinomial} \end{align}\tag{9}\] We let \(Z = (Z_1,...,Z_D)\). Then \[\begin{align} Q(Z = z |R^{M_{2-\text{design}}} = m) &= \prod_{j = 1}^D Q_j(Z_j = z_j | R^{M_C} = m) \\ &= \left( \frac{1}{e^{\frac{\delta}{2}} +1} \right)^DQ_k(Z_m = z_m | R^{M_C} = m) \prod_{j \neq m}^D Q_j(Z_j = z_j | R^{M_C} = m) \\ &= \left( \frac{1}{e^{\frac{\delta}{2}} +1} \right)^d\left( e^{\frac{\delta}{2}} \right)^{(z - e_k)_k} \prod_{j \neq k} \left( e^{\frac{\delta}{2}} \right)^{(z - e_k)_j}= \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} +1} \right)^De^{-\frac{\delta}{2} \norm{z - e_m}_1}. \end{align}\] This shows \[\require{physics} \begin{align} \mathbb{P}_{\rho}(Z = z) &= \sum_{m = 1}^D Q(Z = z | R^{M_{2-\text{design}}} = m) \mathbb{P}_{\rho}(R^{M_{2-\text{design}}} = m) \\ &= \sum_{m = 1}^D \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} +1} \right)^D e^{-\frac{\delta}{2} \norm{z - e_m}_1} \frac{d}{D} \Tr[\ket{v_m}\bra{v_m} \rho] \\ &= \Tr\left[ \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} +1} \right)^D \frac{d}{D} \sum_{m = 1}^D e^{-\frac{\delta}{2} \norm{z - e_m}_1} \ket{v_m}\bra{v_m} \rho \right] = \mathbb{P}_{\rho}(M_{\delta} = z). \end{align}\] Having established this equality allows us to now apply results from differential privacy. Any statistic based on the results of our gentle measurement 6 has the same properties as applied to the privatized version of the outcome distribution of the non-gentle 2-design measurement. In particular, applying [24] Lemma III.3 and III.4 to \(T_n\), we obtain \[\mathbb{E}_{\rho}[T_n] = n (n-1) \alpha^2 \norm{p_{\rho} - p_{\rho_0}}_2^2 = n (n-1) \frac{d^2}{D^2} \alpha^2 \norm{\rho - \rho_0}_{F}^2 \geq n (n-1) \frac{d^2}{D^2d} \alpha^2 \norm{\rho - \rho_0}_{Tr}^2\] and \[\mathop{\mathrm{Var}}_{\rho}[T_n] \leq 2 D n^2 + 5 n^3 \alpha^2 \norm{p_{\rho} - p_{\rho_0}}_2^2 = 2Dn^2 + 4n\mathbb{E}_{\rho}[T] = 2Dn^2 + 5n^3 \alpha^2 \frac{d^2}{D^2} \norm{\rho - \rho_0}_{F}^2,\] where we used 5 in order to relate the \(\ell_2\) distance of the probability distributions \(p_{\rho}\) and \(p_{\rho_0}\) to the Frobenius-norm between the two states \(\rho\) and \(\rho_0\). Recall that if the 2-design is given by a set of mutually unbiased bases for \(d = p^q\), we have \(D = d(d+1)\) and under the null, we obtain \[\mathbb{P}_{\rho_0}(T_n \geq c) \leq \frac{1}{c^2}\mathop{\mathrm{Var}}_{\rho_0}[T_n] = \frac{2}{d^2} \frac{d^6}{n^2 \alpha^4 \epsilon^4}\] while under the alternative, that is for \(\rho\) with \(\norm{\rho - \rho_0}_{Tr}> \epsilon\), it follows that \[\begin{align} \mathbb{P}_{\rho}(T_n \leq c) &\leq \mathbb{P}_{\rho}\left(T_n \leq \frac{1}{2} \mathbb{E}_{\rho}[T_n] \frac{D}{d^2} \right) \leq \frac{4\mathop{\mathrm{Var}}_{\rho}[T_n]}{\mathbb{E}_{\rho}[T_n]} = \frac{8Dn^2}{\mathbb{E}_{\rho}[T_n]} + \frac{16n}{\mathbb{E}_{\rho}[T_n]} \leq \frac{8d^6}{n^2\alpha^4\epsilon^4} + \frac{16d^3}{n \alpha^2 \epsilon^2}. \end{align}\] As such, for the sum of error probabilities we have \[\begin{align} \mathbb{P}_{0}(\Delta = 1) + \sup_{\rho \in H_1} \mathbb{P}_{\rho}(\Delta = 0) \leq \frac{d^4r^2}{n^2\alpha^4\epsilon^4} \left( \frac{2}{d^2} + 8 \right) + \frac{16d^2r}{n \alpha^2 \epsilon^2} \leq \frac{10d^4r^2}{n^2\alpha^4\epsilon^4} + \frac{16d^2r}{n \alpha^2 \epsilon^2}. \end{align}\] We see that the last term is smaller than \(\frac{1}{3}\) for \(n = O(\frac{d^3}{\epsilon^2 \alpha^2})\). ◻
The assumption that \(d\) is a prime power is less restricting in practice than it would seem at first. Most \(d\)-dimensional quantum systems of interest are in fact prime powers. In particular, such systems include \(q\) joint qubits which form a \(d = 2^q\)-dimensional quantum system. Such ensembles of qubits are the basis of moderns quantum computers. Furthermore, another source of 2-designs are symmetric-informationally complete POVMs (SIC-POVMs). Such measurements also form 2-designs ([25]) and they are known to exist up to \(d = 39604\) ([26]) with their existence being conjectured for all dimensions \(d\) ([25]). Part of this conjecture is that such SIC-POVMs consist of \(D = d^2\) vectors which would generalize our result to arbitrary \(d\).
Let us now shortly outline how to show that the algorithm in Section 5 is in fact sample optimal for locally-\(\alpha\)-gentle quantum state certification. For an in-depth analysis of this lower bound, see Appendix 8.
Theorem 4. Consider the testing task 7 for \(\rho_0 = \frac{1}{d}\text{\usefont{U}{bbm}{m}{n}1}\) and assume \(n = O(\frac{d^3}{\epsilon^2 \alpha^2})\). Then, for the minimal testing error it holds \[\label{eqn::test95error} \inf_{(M, \Delta)} \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \sup_{\rho: \norm{\rho - \rho_0}_{Tr} > \epsilon} \mathbb{P}_{\rho^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 0 \right) \geq \frac{1}{3}.\qquad{(2)}\] Here the infimum is taken over over all locally-\(\alpha\)-gentle measurements \(M\) and subsequent tests \(\Delta\).
Proof. We start by constructing local alternatives around the maximally mixed state \(\rho_0 = \frac{1}{d} \text{\usefont{U}{bbm}{m}{n}1}\) based on random perturbations along directions of trace-zero. Let \((V_j)_{j = 1}^{d^2}\) be an orthonormal basis of \(\mathbb{H}_d\) with \(V_{d^2} = \frac{1}{\sqrt{d}} \text{\usefont{U}{bbm}{m}{n}1}\). The exact choice of the \(V_j\) will depend on the measurement and will be chosen later in the proof. For some \(d/2 \leq D \leq d^2 - 1\) and \(\nu \in \mathcal{V} = \{-1,1\}^D\) we will now define the states \[\label{eqn::defn95alternative95states} \rho_{\nu} = \rho_0 + \Delta_{\nu} = \rho_0 + \frac{c \epsilon}{\sqrt{dD}} \sum_{i = 1}^D \nu_i V_i.\tag{10}\] Let us now consider \(\require{physics} \mathcal{V}_{\mathcal{S}} := \left\{ \nu \in \mathcal{V} \middle| \rho_{\nu} \in \mathcal{S}(\mathbb{C}) \text{ and } \norm{\rho_{\nu} - \rho_0}_{\Tr} > \epsilon \right\}\) which is the set of admissible states, i.e. those that define valid alternative states. Lemma 4 assures us that for a suitable \(c > 0\) a state is admissible with high probability, meaning we have \(|\mathcal{V}_{\mathcal{S}}|/|\mathcal{V}| \geq 1 - 2e^{-d}\). We can then reduce the minimax risk to a Bayesian risk, which we further bound in terms of the chi-squared distance to an average over the alternatives. For the locally-\(\alpha\)-gentle measurement \(M = (M_1 \otimes ... \otimes M_n)\) that is given by measurement operators \(M_y = M_{y_1} \otimes ... \otimes M_{y_n}\), we set \(E_{y_i} = M_{y_i}^*M_{y_i}\) and define \[\require{physics} \begin{align} \label{eqn::Kraus95channel} \mathcal{H}_i: \mathbb{C}^{d \times d} \to \mathbb{C}^{d \times d}\text{with}&\mathcal{H}_i(A) := \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i}\text{and}\bar{\mathcal{H}} = \frac{1}{n} \sum_{i = 1}^n \mathcal{H}_i. \end{align}\tag{11}\] We show that these linear super-operators can be related to the chi-squared distance in the following way \[d_{\chi^2}\left( \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}, \mathbb{E}_{\nu} \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \right) \leq \left( \frac{e^d}{e^d -2} \right)^2 \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V})} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right].\] By Proposition 9, we know that the properties of the operator \(\bar{\mathcal{H}}\) are highly related to the gentleness of the measurement \(M\). In particular \(\bar{\mathcal{H}}\) is self-adjoint with an orthonormal basis of eigenvectors \((V_i)_{i = 1}^{d^2}\) where \(V_{d^2} = \frac{1}{d} \text{\usefont{U}{bbm}{m}{n}1}\) and \(V_i\) are traceless, hermitian for \(i = 1,...,d^2-1\). For the corresponding eigenvalues \(\mu_i\) it holds \[\sum_{i = 1}^{d^2-1} \mu_i \leq \frac{16\alpha^2}{(1-4\alpha^2)^2}.\] When the measurement \(M\) is assumed to be fixed we can chose the \(V_i\) in 10 such that they correspond to the eigenvectors of \(\bar{\mathcal{H}}\) with the smallest eigenvalues. Using properties of the Rademacher random variables \(\nu\), we further bound the last term by the sum of the square of the first \(D\) smallest eigenvalues of \(\bar{\mathcal{H}}\) \[\label{eqn::inequalities95lower95bound} \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V})} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right] \leq \exp\left(\frac{1}{2} \frac{n^2 c^4 \epsilon^4}{D^2} \sum_{i = 1}^D \mu_i^2 \right) \leq \exp\left( 512 \frac{n^2 c^4 \epsilon^4 \alpha^4}{2D^2 d^2} \right).\tag{12}\] Since \(D \geq \frac{d^2}{2}\), the last term upper bounds the chi-squared distance from above, which in turn lower bounds the test error. As such, if \(n \geq \Omega(\frac{d^3}{\epsilon^2 \alpha^2})\) the optimal testing error is larger than \(\frac{1}{3}\). ◻
For randomized measurements in the non-gentle case, [8] has shown an optimal rate of \(n = \Theta(\frac{d^{3/2}}{\epsilon^2})\). It turns out that our proof technique allows to show lower bounds for randomized measurements in the gentle case. If the measurements we perform are random, we cannot chose \(\Delta_{\nu}\) in 10 according to the direction of least sensitivity of the measurement. This is because these directions are unknown to us due to the randomness of the measurement. Mathematically, this corresponds to the fact that we cannot assume the eigenvalues in 12 to be ordered, resulting in a larger upper bound. In that case, for \(D = d^2-1\), we have \[\label{eqn::HS95norm95M95D95randomized} \sum_{i = 1}^{D} \mu_i^2 \leq \frac{16 \alpha^2}{(1+4\alpha^2)^2} \sum_{i = 1}^{D} \mu_i \leq \left(\frac{16 \alpha^2}{(1+4\alpha^2)^2}\right)^2 = \frac{256 \alpha^4}{(1-4\alpha)^4}\tag{13}\] which gives the following lower bound for randomized measurement schemes. We believe it to be an interesting open question to identify whether this lower bound is optimal.
Corollary 1. A total of \(n = \Omega\left( \frac{d^2}{\epsilon^2 \alpha^2} \right)\) copies of the state \(\rho\) are needed to verify whether \(\rho\) is the maximally mixed state \(\rho_0 = \frac{1}{d} \text{\usefont{U}{bbm}{m}{n}1}\) or \(\norm{\rho - \rho_0}_{Tr} > \epsilon\) with high probability using randomized locally-\(\alpha\)-gentle measurements.
This section is split into a first part in which we prove (i) in Theorem 2 while the second part of this section is concerned with (ii) in Theorem 2 and the improvement on the constants appearing for positive-definite measurement operators. Note that, since we work exclusively with locally-gentle measurements, it suffices to show the results on each register independently. For a brief overview on the differences between locally- and globally-gentle measurement, see [4].
Proposition 5. Let \(M = (M_{y})_{y \in \mathcal{Y}}\) be a quantum measurement. Then the following are equivalent:
\(M\) is a \(\delta\)-quantum-differentially-private measurement on \(\mathcal{S}(\mathbb{C}^d)\).
\(M\) is a \(\delta\)-quantum-differentially-private measurement on \(\mathcal{S}_{pure}(\mathbb{C}^d)\).
\(\lambda_{max}(E_{y}) \leq e^{\delta} \lambda_{min}(E_{y})\) for all \(y \in \mathcal{Y}\), where \(E_{y} = M_{y}^*M_{y}\).
Proof.
Since \(\mathcal{S}_{pure}(\mathbb{C}^d) \subseteq \mathcal{S}(\mathbb{C}^d)\).
Let \(M\) be \(\delta\)-quantum-differentially-private on pure states. For any \(y \in \mathcal{Y}\) we define \(E_{y} = M_{y}^*M_{y}\). Then for \(\rho = \ket{\psi}\bra{\psi}, \rho' = \ket{\psi'}\bra{\psi'}\) it holds \[\bra{\psi}E_{y}\ket{\psi} = \mathbb{P}_{\ket{\psi}}(R^M = y) \leq e^{\delta}\mathbb{P}_{\ket{\psi'}}(R^M = y) = e^{\delta} \bra{\psi'}E_{y}\ket{\psi'}\] Now, let \(\ket{\psi}\) and \(\ket{\psi'}\) be eigenvectors of \(E_y\) associated to eigenvalue \(\lambda_{max}(E_{y})\) and \(\lambda_{min}(E_{y})\) respectively. Then we have \[\begin{align} \lambda_{max}(E_{y}) = \bra{\psi}E_{y}\ket{\psi} &= \mathbb{P}_{\ket{\psi}}(R^M = y) \\ &\leq e^{\delta}\mathbb{P}_{\ket{\psi'}}(R^M = y) \\ &= e^{\delta} \bra{\psi'}E_{y}\ket{\psi'} = e^{\delta} \lambda_{min}(E_{y}). \end{align}\]
Note that we can write any quantum state as \(\rho = \sum_{n = 1}^{d} \lambda_n \ket{\psi_n}\bra{\psi_n}\). The outcome probability for \(y \in \mathcal{Y}\) is then given by \[\require{physics} \mathbb{P}_{\rho}\left( R^M = y \right) = \Tr\left[ \rho E_{y} \right] = \sum_{n = 1}^{d} \lambda_k \Tr\left[ \ket{\psi_k}\bra{\psi_k} E_{y} \right] = \sum_{n = 1}^{d} \lambda_k \bra{\psi_k}E_{y}\ket{\psi_k}.\] By definition of \(\lambda_{max}(E_{y})\) and \(\lambda_{min}(E_{y})\), since \(\sum_{k = 1}^{d} \lambda_k = 1\), we have \[\lambda_{min}(E_{y}) \leq \mathbb{P}_{\rho}\left( R^M = y \right) \leq \lambda_{max}(E_{y})\] for any \(\rho \in \mathcal{S}(\mathbb{C}^d)\) . Therefore we have \[\mathbb{P}_{\rho}\left( R^M = y \right) \leq \lambda_{max}(E_{y}) \leq e^{\delta} \lambda_{min}(E_{y}) \leq e^{\delta} \mathbb{P}_{\rho'}\left( R^M = y \right)\] for all \(\rho, \rho' \in \mathcal{S}(\mathbb{C}^d), y \in \mathcal{Y}\).
◻
Proposition 6. Let \(M = (M_y)_{y \in \mathcal{Y}}\) be a quantum measurement and \(E_y = M_y^*M_y\). If \(M\) is \(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^{d})\), then there exists an implementation \(\tilde{M}\) of \(M\) such that \(\tilde{M}\) is \(\alpha\)-gentle on \(\mathcal{S}_{pure}(\mathbb{C}^{d})\) for \[\alpha = \frac{e^{\frac{\delta}{2}} -1}{e^{\frac{\delta}{2}} +1} = \tanh\left( \frac{\delta}{4} \right).\]
Proof. Note that, by Proposition 5, we have \(\lambda_{max}(E_{y}) \leq e^{\delta} \lambda_{min}(E_{y})\) for all \(y \in \mathcal{Y}\), where \(E_{y} = M_{y}^*M_{y}\). Let \(|M_y| = \sqrt{E_y}\) be the unique positive square root of \(E_y\). Then \(\tilde{M} = (|M_y|)_{y |\in \mathcal{Y}}\) does define a quantum measurement that has the same outcome probabilities as \(M_y\). Given \(|M_y|\), there exists an orthonormal basis \(\ket{v_{y,1}},...,\ket{v_{y,d}}\) of \(\mathbb{C}^d\) and \(\lambda_{y,1},...,\lambda_{y,d} > 0\) such that \[|M_y| = \sum_{i = 1}^d \lambda_{y, i} \ket{v_{y, i}}\bra{v_{y, i}},\] where \(\lambda_{y,1} = \sqrt{\lambda_{min}(E_y)}\) and \(\lambda_{y,d} = \sqrt{\lambda_{max}(E_y)}\). Any pure state \(\ket{\psi} \in \mathcal{S}_{pure}(\mathbb{C}^d)\) can be written as \[\ket{\psi} = \sum_{i = 1}^d \mu_i \ket{v_{y,i}},\text{for } \sum_{i = 1}^d |\mu_i|^2 = 1.\] Then, for \(\rho = \ket{\psi}\bra{\psi}\) we have \[\begin{align} \norm{\rho - \rho_{|M| \to y}}_{Tr}^2 = 1 - \frac{\left|\bra{\psi}|M_y|\ket{\psi}\right|^2}{\bra{\psi}|M_y|^2\ket{\psi}}\leq 1 - \frac{4 \lambda_1 \lambda_d}{(\lambda_d+ \lambda_1)^2} = \left(\frac{\lambda_d - \lambda_1}{\lambda_d + \lambda_1}\right)^2 \leq \left(\frac{e^{\frac{\delta}{2}} -1}{e^{\frac{\delta}{2}} +1}\right)^2, \end{align}\] where the first inequality is due to the Kantorovich inequality ([27]) and the second inequality is due to the fact that the eigenvalues of \(E_y\) are given by the square of the eigenvalues of \(|M_y|\). This shows that \(\tilde{M}\) is \(\alpha\)-gentle on pure states. ◻
Proposition 7. Let \(M = (M_{y})_{y \in \mathcal{Y}}\) be an \(\alpha\)-gentle measurement on \(\mathcal{S}_{pure}(\mathbb{C}^d)\) such that \(M_{y}\) is positive and self-adjoint. Then, \(M\) is \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)\).
Proof. Let \(\rho = \sum_{k = 1}^{d}\lambda_k \ket{\psi_k}\bra{\psi_k} \in \mathcal{S}(\mathbb{C}^d)\) be any quantum state and \(M\) a \(\alpha\)-gentle measurement on \(\mathcal{S}_{pure}(\mathbb{C}^d)\). Define \[\ket{\Psi} = \sum_{k = 1}^{d} \sqrt{\lambda_k} \ket{\psi_k} \otimes \ket{\psi_k} \in \mathcal{S}_{pure}(\mathbb{C}^d \otimes \mathbb{C}^d).\] Then it holds \(\require{physics} \rho = \Tr_2[\ket{\Psi}\bra{\Psi}]\), where \(\require{physics} \Tr_2\) is the partial trace over the seconds Hilbert space \(\mathbb{C}^d\). Furthermore, for the measurement \(M \otimes I = (M_{y} \otimes I)_{y \in \mathcal{Y}}\) it holds \[\require{physics} \begin{align} \mathbb{P}_{\rho}\left( R^M = y \right) = \Tr\left[ \rho M_{y}^* M_{y} \right] &= \Tr\left[ \Tr_2[\ket{\Psi}\bra{\Psi}] M_{y}^* M_{y} \right] \\ &= \Tr\left[ \ket{\Psi}\bra{\Psi} (M_{y}^*M_{y} \otimes I) \right] \\ &= \Tr\left[ \ket{\Psi}\bra{\Psi} (M_{y}^* \otimes I) (M_{y} \otimes I) \right] \\ &= \Tr\left[ \ket{\Psi}\bra{\Psi} (M_{y} \otimes I)^* (M_{y} \otimes I) \right] = \mathbb{P}_{\ket{\Psi}}\left( R^{M\otimes I} = y \right). \end{align}\] Furthermore, we have \[\require{physics} \begin{align} M_{y} \rho M_{y}^* = M_{y} \Tr_2[\ket{\Psi}\bra{\Psi}] M_{y}^* = \Tr_2 \left[ (M_{y} \otimes I) \ket{\Psi}\bra{\Psi} (M_{y}^* \otimes I) \right]. \end{align}\] This shows that \[\require{physics} \begin{align} \rho_{M \to y} &= \frac{1}{\mathbb{P}_{\rho}\left( R^M = y \right)} M_{y}\rho M_{y}^* \\ &= \frac{1}{\mathbb{P}_{\ket{\Psi}}\left( R^{M\otimes I} = y \right)} \Tr_2 \left[ (M_{y} \otimes I) \ket{\Psi}\bra{\Psi} (M_{y}^* \otimes I) \right] \\ &= \Tr_2 \left[ \frac{1}{\sqrt{\mathbb{P}_{\ket{\Psi}}\left( R^{M\otimes I} = y \right)}} (M_{y} \otimes I) \ket{\Psi}\bra{\Psi} (M_{y}^* \otimes I) \frac{1}{\sqrt{\mathbb{P}_{\ket{\Psi}}\left( R^{M\otimes I} = y \right)}} \right] \\ &= \Tr_2\left[ \ket{\Psi_{M \otimes I \to y}}\bra{\Psi_{M \otimes I \to y}} \right]. \end{align}\] Since the trace norm is contractive under quantum channels such as the partial trace, we have \[\require{physics} \begin{align} \norm{\rho - \rho_{M \to y}}_{Tr} &= \norm{\Tr_2[\ket{\Psi}\bra{\Psi}] - \Tr_2\left[ \ket{\Psi_{M \otimes I \to y}}\bra{\Psi_{M \otimes I \to y}} \right]}_{Tr} \\ &\leq \norm{\ket{\Psi}\bra{\Psi} - \ket{\Psi_{M \otimes I \to y}}\bra{\Psi_{M \otimes I \to y}}}_{Tr}. \end{align}\] Therefore, the gentleness of \(M\) on \(\mathcal{S}(\mathbb{C}^d)\) is bounded by the gentleness of \(M \otimes I\) on \(\mathcal{S}_{pure}(\mathbb{C}^d \otimes \mathbb{C}^d)\). By Lemma 2, \(M\) is \(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^d)\) for \(\delta = 4 \mathop{\mathrm{arctanh}}(\alpha)\). Then, \[\lambda_{max}(M_{y}^*M_{y} \otimes I) = \lambda_{max}(M_{y}^*M_{y}) \leq e^{\delta} \lambda_{min}(M_{y}^*M_{y}) = e^{\delta} \lambda_{min}(M_{y}^*M_{y} \otimes I)\] which shows that \(M \otimes I\) is also \(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^d \otimes \mathbb{C}^d)\). Proposition 6 then shows, that \(M \otimes I\) is \(\alpha\)-gentle on \(\mathcal{S}_{pure}(\mathbb{C}^d \otimes \mathbb{C}^d)\) from which we get \[\begin{align} \norm{\rho - \rho_{M \to y}}_{Tr} \leq \norm{\ket{\Psi}\bra{\Psi} - \ket{\Psi_{M \otimes I \to y}}\bra{\Psi_{M \otimes I \to y}}}_{Tr} \leq \alpha. \end{align}\] ◻
Corollary 2. Let \(M = (M_y)_{y \in \mathcal{Y}}\) be a quantum measurement and \(E_y = M_y^*M_y\). If \(M\) is \(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^{d})\), then there exists an implementation \(\tilde{M}\) of \(M\) such that \(\tilde{M}\) is \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^{d})\) for \[\alpha = \frac{e^{\frac{\delta}{2}} -1}{e^{\frac{\delta}{2}} +1} = \tanh\left( \frac{\delta}{4} \right).\]
Proof. For the implementation \(\tilde{M} = (|M_{y}|)_{y \in \mathcal{Y}}\) we chose in the proof of Proposition 6, we have that the measurement operators are positive and self-adjoint. Thus, by Proposition 7, we have that the same implementation \(\tilde{M}\) is \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)\). ◻
This concludes the proof of part (i) of Theorem 2 which shows that quantum-differentially-private measurements have a gentle implementation. The following two results are now concerned with the opposite direction showing that gentle measurements are always quantum-differentially-private.
Proposition 8. Let \(\alpha\) in \([0, \frac{1}{2})\) and \(M\) be \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)\) with measurement operators \(M_{y}\). Then \(M\) is \(\delta\) quantum differentially-private on \(\mathcal{S}(\mathbb{C}^d)\) for \(\delta = 2\log(\frac{1+2\alpha}{1-2\alpha})\).
Proof. Assume that \(M = (M_{y})_{y \in \mathcal{Y}}\) is an \(\alpha\)-gentle measurement on \(\mathcal{S}(\mathbb{C}^d)\). Define \(E_{y} := M_{y}^*M_{y}\). Let \(\rho_1, \rho_2 \in \mathcal{S}(\mathbb{C}^d)\) s.t. \(\norm{\rho_1 - \rho_2}_{Tr} = 1\). Let us further denote by \(p_1\) (respectively \(p_2\)) the probability of obtaining outcome \(y\) under \(\rho_1\) (respectively \(\rho_2\)). That is \[p_1 = \mathbb{P}_{\rho_1}\left(R^M = y \right)\text{and}p_2 = \mathbb{P}_{\rho_2}\left(R^M = y \right)\] Without loss of generality we assume that \(p_1 > p_2 \geq 0\). Now, let \[\rho_{\lambda} = \lambda \rho_1 + (1-\lambda) \rho_2\text{for all } \lambda \in (0,1).\] The probability of obtaining the outcome \(y\) when measuring \(\rho_{\lambda}\) is \[\require{physics} p_{\lambda} = \mathcal{P}_{\rho_{\lambda}}(R^M = y) = \Tr\left( \rho_{\lambda} E_y \right) = \lambda \Tr\left( \rho_1 E_y \right) + (1 - \lambda) \Tr\left( \rho_2 E_y \right) = \lambda p_1 + (1 - \lambda) p_2.\] The post-measurement state of \(\rho_{\lambda}\) is then given by \[(\rho_{\lambda})_{M \to y} = \frac{1}{p_{\lambda}} M_y \rho_{\lambda} M_y^* = \frac{\lambda p_1 (\rho_1)_{M \to y} + (1-\lambda) p_2 (\rho_2)_{M \to y}}{\lambda p_1 + (1-\lambda) p_2}.\] Now if we define \(\delta = \frac{\lambda p_1}{\lambda p_1 + (1-\lambda) p_2} - \lambda > 0\), we get \[\begin{align} \rho_{\lambda} - (\rho_{\lambda})_{M \to y} = \frac{\lambda p_1}{p_{\lambda}} \left((\rho_1 - (\rho_1)_{M \to y}\right) + \frac{(1-\lambda) p_2}{p_{\lambda}} \left(\rho_2 - (\rho_2)_{M \to y}\right) + \delta \left(\rho_2 - \rho_1\right)). \end{align}\] By the triangle inequality and gentleness we now have \[\begin{align} \delta \norm{\rho_2 - \rho_1}_{Tr} \leq \frac{\lambda p_1}{p_{\lambda}} \alpha + \frac{(1-\lambda) p_2}{p_{\lambda}} \alpha + \alpha = 2 \alpha \end{align}\] Since we further assumed \(\norm{\rho_2 - \rho_1}_{Tr} = 1\), we get \(\delta \leq 2 \alpha\). This allows us to write \[\begin{align} p_1 = \frac{\lambda - \lambda^2 + \delta (1-\lambda)}{\lambda - \lambda^2 - \delta \lambda} p_2 \leq \frac{\lambda - \lambda^2 + 2\alpha (1-\lambda)}{\lambda - \lambda^2 - 2 \alpha \lambda} p_2\text{for all } \lambda \in (0,1 - 2 \alpha). \end{align}\] The last inequality only holds as long as the denominator is positive which is the case for \(\lambda < 1 - 2 \alpha\). As such, for \(\lambda_0 = \frac{1 - 2 \alpha}{2} < 1 - 2 \alpha\), we obtain \[p_1 \leq \frac{\lambda_0 - \lambda_0^2 + 2\alpha (1-\lambda_0)}{\lambda_0 - \lambda_0^2 - 2 \alpha \lambda_0} p_2 = \left( \frac{1 + 2\alpha}{1 - 2\alpha} \right)^2 p_2.\] Now, since we started with \(\rho_1, \rho_2\) such that \(\norm{\rho_1 - \rho_2}_{Tr} = 1\), the last relation holds for every pure state. As such \(M\) is \(2 \log\left( \frac{1 + 2\alpha}{1 - 2\alpha} \right)\)-quantum-differentially-private on pure states. Proposition 5 then proves that \(M\) is \(2 \log\left( \frac{1 + 2\alpha}{1 - 2\alpha} \right)\)-quantum-differentially-private on the whole space. ◻
While Proposition 8 shows that an arbitrary gentle measurement is quantum differentially private, showing part (ii) of Theorem 2, we can show that the constant relating the two can be improved for measurements with positive-definite measurement operators.
Lemma 2. Let \(\alpha\) in \([0, 1)\) and \(M\) be \(\alpha\)-gentle on \(\mathcal{S}(\mathbb{C}^d)\) with positive-definite measurement operators \(M_y\). Then \(M\) is \(\delta\) quantum differentially-private on \(\mathcal{S}(\mathbb{C}^d)\) for \(\delta = 2\log(\frac{1+\alpha}{1-\alpha}) = 4 \mathop{\mathrm{arctanh}}(\alpha)\).
Proof. Let \(M_y = \sum_{i = 1}^d \lambda_i \ket{v_i}\bra{v_i}\) be positive-definite with maximal and minimal eigenvalue \(\lambda_d\) and \(\lambda_1\) respectively. Consider the gentleness of \(M_y\) on the pure state \(\ket{\psi} = \frac{1}{\sqrt{\lambda_1 + \lambda_d}} (\sqrt{\lambda_d} \ket{v_1} + \sqrt{\lambda_1} \ket{v_d})\). Lemma 1 then shows that, due to the gentleness of \(M\) on \(\rho = \ket{\psi}\bra{\psi}\), we have \[\begin{align} \alpha^2 \geq \norm{\rho - \rho_{M \to y}}_{Tr}^2 = 1- \frac{\left| \bra{\psi} M_y \ket{\psi} \right|^2}{\bra{\psi} M_y^2 \ket{\psi}}. \end{align}\] For the numerator and denominator we have \[\begin{align} \left|\bra{\psi} M_y \ket{\psi}\right|^2 &= \frac{1}{(\lambda_1 + \lambda_d)^2} \left( \lambda_d \lambda_1 + \lambda_d \lambda_1 \right)^2 = \frac{4 \lambda_1^2 \lambda_d^2}{(\lambda_1+ \lambda_d)^2} \\ \bra{\psi} M_y^2 \ket{\psi} &= \frac{1}{\lambda_1 + \lambda_d} \left( \lambda_d \lambda_1^2 + \lambda_d^2 \lambda_1 \right) = \lambda_1 \lambda_d. \end{align}\] from which we obtain \[\frac{\left| \bra{\psi} M_y \ket{\psi} \right|^2}{\bra{\psi} M_y^2 \ket{\psi}} = \frac{4 \lambda_1 \lambda_d}{(\lambda_1 + \lambda_d)^2}\] This gives \[\alpha^2 \geq \frac{(\lambda_d - \lambda_1)^2}{(\lambda_d + \lambda_1)^2}\text{or equivalently}\alpha \geq \frac{\lambda_d - \lambda_1}{\lambda_d + \lambda_1} = \frac{\frac{\lambda_d}{\lambda_1} - 1}{\frac{\lambda_d}{\lambda_1} +1 }\] Using the fact that for \(E_{y} = M_y^2\) we have \(\lambda_{max}(E_{y}) = \lambda_d^2\) and \(\lambda_{min}(E_{y}) = \lambda_1^2\), we get \[\begin{align} \alpha \geq \frac{e^{2 \frac{1}{4}\log\left( \frac{\lambda_{max}(E_{y})}{\lambda_{min}(E_{y})} \right)} - 1}{e^{2 \frac{1}{4}\log\left( \frac{\lambda_{max}(E_{y})}{\lambda_{min}(E_{y})} \right)} + 1} = \tanh\left( \frac{1}{4} \log\left( \frac{\lambda_{max}(E_{y})}{\lambda_{min}(E_{y})} \right) \right). \end{align}\] Finally, using the monotonicity of \(\tanh\), we get \[\frac{\lambda_{max}(E_{y})}{\lambda_{min}(E_{y})} \leq e^{4 \mathop{\mathrm{arctanh}}(\alpha)}\] which together with Proposition 5 shows that \(M\) is \(\delta\)-quantum-differentially-private on \(\mathcal{S}(\mathbb{C}^d)\) for \[\delta = 4 \mathop{\mathrm{arctanh}}(\alpha).\] ◻
Let us now show that the measurement defined trough the operators in 6 does in fact constitute a valid locally-\(\alpha\)-gentle measurement.
Lemma 3. Let \((\ket{v_m})_{m = 1}^D\) be a quantum 2-design. For \(e_m \in \{0,1\}^D\) being the vector that is zero everywhere except in the m-th entry, define \[E_{\delta, z} = \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D e^{-\frac{\delta}{2} \norm{z - e_m}_1} \ket{v_m}\bra{v_m},\] for every \(z \in \{0,1\}^D\) and \(\delta = 4 \mathop{\mathrm{arctanh}}(\alpha)\) and set \(M_{\delta} = (M_{\delta, z})_{z \in \{0,1\}^D}\). Then \(M_{\delta}^{\otimes n}\) is in fact a locally-\(\alpha\)-gentle measurement on \(\mathcal{S}((\mathbb{C}^d)^{\otimes n})\).
Proof. We will make use of Theorem 2 to show the results. As we have already seen, due to the locality of the measurements, it suffices to consider its impact on a single register. As such, we first assure that the operators \(M_{\delta} = (M_{\delta, z})_{z \in \{0,1\}^D}\) do define a quantum measurement on each register. Due to the definition of product measurements, their product \(M_{\delta}^{\otimes n}\) then also defines a valid quantum measurement. Finally, by showing the gentleness of the \(M_{\delta}\) on a single register, we have shown the local gentleness of \(M_{\delta}^{\otimes n}\). Let \((\ket{v_m})_{m = 1}^D\) a quantum 2-design. In particular, we have \[\sum_{m = 1}^D \ket{v_m}\bra{v_m} = \frac{D}{d} \text{\usefont{U}{bbm}{m}{n}1}.\] Since each \(E_{\delta, z}\) is a sum of positive operators, \(E_{\delta, z}\) is itself positive and we can take the operator square root \(M_{\delta, z} = \sqrt{E_{\delta, z}}\). In order to assure that \(M_{\delta} = (M_{\delta, z})_{z \in \{0,1\}^D}\) indeed defines a quantum measurement we must assure that it fulfills the completeness relation. We have \[\begin{align} \sum_{z \in \{0,1\}^D} E_{\delta, z} &= \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D \ket{v_m}\bra{v_m} \sum_{z \in \{0,1\}^D} e^{-\frac{\delta}{2} \norm{z - e_m}_1} \\ &= \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D \ket{v_m}\bra{v_m} \left[ \sum_{z | z_m = 1} e^{-\frac{\delta}{2} \norm{z - e_m}_1} + \sum_{z | z_m = 0} e^{-\frac{\delta}{2} \norm{z - e_m}_1}\right] \\ &= \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D \ket{v_m}\bra{v_m} \left[ \sum_{j = 0}^{D-1} \binom{D-1}{j} e^{-\frac{\delta}{2} j } + \sum_{j = 0}^{D-1} \binom{D-1}{j} e^{-\frac{\delta}{2} (j+1)} \right] \\ &= \left( \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \right)^D \frac{d}{D} \sum_{m = 1}^D \ket{v_m}\bra{v_m} \left( (e^{-\frac{\delta}{2}} + 1)^{D-1} + (e^{-\frac{\delta}{2}} +1)^{D-1} e^{-\frac{\delta}{2}} \right) \\ &= \frac{e^{\frac{\delta}{2}}}{e^{\frac{\delta}{2}} + 1} \left( 1 + e^{-\frac{\delta}{2}} \right) \text{\usefont{U}{bbm}{m}{n}1} \\ &= \text{\usefont{U}{bbm}{m}{n}1}. \end{align}\] Therefore, taking \(M_{\delta, z} = \sqrt{E_{\delta, z}}\), the operators \(M_{\delta} = (M_{\delta, z})_{z \in \{0,1\}^D}\) do indeed define a quantum measurement. Now, let \(z \in \{0,1\}^D\) with \(\norm{z} = k\) be fixed. We have \[e^{-\frac{\delta}{2} (k+1)} \leq e^{-\frac{\delta}{2} \norm{z - e_m}} \leq e^{-\frac{\delta}{2} (k-1)}\] for all \(m\) from which we obtain \[\frac{\text{\usefont{U}{bbm}{m}{n}P}_{\ket{\psi}}(R^{M_{\delta}})}{\text{\usefont{U}{bbm}{m}{n}P}_{\ket{\psi'}}(R^{M_{\delta}})} \leq e^{\frac{\delta}{2}((k+1)-(k-1))} \leq e^{\delta}\] for any \(\ket{\psi}, \ket{\psi'}\) which. Together with Theorem 2 this shows the local \(\alpha\)-gentleness of \(M_{\delta}^{^\otimes n}\). ◻
Let us first recall the following result from [10] which we will prove again for the readers convenience.
Lemma 4 (Proposition 3 in [10]). Let \(d^2/2 \leq D \leq d^2-1\) and \(\nu\) be drawn uniformly from \(\mathcal{V} = \{-1,1\}^D\). Let \(\Delta_{\nu}\) and \(\sigma_{\nu}\) as in 10 . Then there exists a universal constant \(c \leq 10\sqrt{2}\) such that for \(\epsilon < 1/c^2\) we have \[\mathbb{P}_{\nu}\left( \norm{\Delta_{\nu}}_{op} \leq \frac{1}{d} \text{ and } \norm{\rho_{\nu} - \rho_{0}} \geq \epsilon \right) \geq 1 - 2e^{-d}.\]
Proof. The Hölder inequality for matrices gives \[\norm{\Delta_{\nu}}_{F}^2 \leq \norm{\Delta_{\nu}}_{op} \norm{\Delta_{\nu}}_{1}.\] Applying Theorem 15 in [10] to \(\Delta_{\nu} = \frac{c\epsilon}{\sqrt{Dd}} W\) with \(\norm{\Delta_{\nu}}_F = \frac{c \epsilon}{\sqrt{d}}\) gives \[\mathbb{P}_{\nu}\left( \norm{\Delta_{\nu}}_{op} \leq \frac{c \epsilon}{\sqrt{Dd}} 10 \sqrt{d}\right) = \mathbb{P}_{\nu}\left( \norm{W}_{op} \leq 10 \sqrt{d} \right) \geq 1 - 2e^{-d}.\] As such, we also have \[\begin{align} \mathbb{P}_{\nu} \left( \norm{\Delta_{\nu}}_1 \geq \frac{c\epsilon \sqrt{D}}{10d} \right) \geq \mathbb{P}_{\nu}\left( \norm{\Delta_{\nu}}_{op} \leq \norm{\Delta_{\nu}}_F^2 \frac{10d}{c\epsilon\sqrt{D}} \right) = \mathbb{P}_{\nu}\left( \norm{W}_{op} \leq 10 \sqrt{d} \right) \geq 1 - 2e^{-d}. \end{align}\] Since \(D \geq \frac{d^2}{2}\), for \(c = 10\sqrt{2}\), for all \(\epsilon< \frac{1}{c^2}\) we have \[\mathbb{P}_{\nu}\left( \norm{\Delta_{\nu}}_{op} \leq \frac{1}{d} \text{ and } \norm{\rho_{\nu} - \rho_{0}} \geq \epsilon \right) \geq 1 - 2e^{-d}.\] ◻
With the the result of the Lemma 4 we can now turn to the proof of Theorem 4. Suppose we are given a \(n\)-copies of the unknown state \(\rho\), that is \(\rho^{\otimes n}\) on which we perform a locally-\(\alpha\)-gentle measurement \(M^{\otimes n}\). The error of any subsequent test in then given by \[\mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \sup_{\rho: \norm{\rho - \rho_0}_{Tr} > \epsilon} \mathbb{P}_{\rho^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 0 \right)\] We will reduce the supremum over the alternative to the maximum over a well suited finite set of alternatives. Let us denote by \(\mathbb{H}_d\) the real vector space of \(d \times d\) hermitian matrices with inner product given by \(\require{physics} \langle A , B \rangle = \Tr\left[ A^* B \right]\). Let \((V_j)_{j = 1}^{d^2}\) be an orthonormal basis of \(\mathbb{H}_d\) with \(V_{d^2} = \frac{1}{\sqrt{d}} \text{\usefont{U}{bbm}{m}{n}1}\). The exact choice of the \(V_j\) will depend on the measurement and will be given later in the proof. For some \(d/2 \leq D \leq d^2 - 1\) we will now define the states as in 10 by \[\label{eqn::defn95alternative95states952} \rho_{\nu} = \rho_0 + \Delta_{\nu} = \rho_0 + \frac{c \epsilon}{\sqrt{dD}} \sum_{i = 1}^D \nu_i V_i\tag{14}\] for \(\nu \in \mathcal{V} = \{-1,1\}^D\). Let us now consider \(\require{physics} \mathcal{V}_{\mathcal{S}} := \left\{ \nu \in \mathcal{V} \middle| \rho_{\nu} \in \mathcal{S}(\mathbb{C}) \text{ and } \norm{\rho_{\nu} - \rho_0}_{\Tr} > \epsilon \right\}\). The set \(\mathcal{V}_{\mathcal{S}}\) indexes those operators \(\rho_{\nu}\) that actually define quantum states (in that they are positive) that are at least \(\epsilon\) far away from \(\rho_0\) in trace-norm. Lemma 4 assures us that for a suitable \(c > 0\), we have \(|\mathcal{V}_{\mathcal{S}}|/|\mathcal{V}| \geq 1 - 2e^{-d}\) which we will later use to work with the whole set \(\mathcal{V}\). We can now lower bound the testing error as follows \[\begin{align} \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \sup_{\rho: \norm{\rho - \rho_0}_{Tr} > \epsilon} \mathbb{P}_{\rho^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 0 \right) &\geq \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \max_{\nu \in \mathcal{V}_{\mathcal{S}}} \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 0 \right) \\ &\geq \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \frac{1}{|\mathcal{V}_{\mathcal{S}}|} \sum_{\nu \in \mathcal{V}_{\mathcal{S}}} \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 0 \right) \\ &\geq \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}\left( \Delta = 1 \right) + \mathbb{E}_{\nu} \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \left( \Delta = 0 \right) \\ &\geq 1 - \sqrt{d_{\chi^2}\left( \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}, \mathbb{E}_{\nu \sim \mathcal{V}_{\mathcal{S}} } \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \right)}. \end{align}\] We now bound this using the decoupled \(\chi^2\) fluctuation using Theorem 1. As such, we need to calculate \[H_i(\nu_1, \nu_2) = \mathbb{E}_{y_i \sim \mathbb{P}^{(i)}}\left[ \delta_{\nu_1}^{(i)}(y_i) \delta_{\nu_2}^{(i)}(y_i) \right]\text{and}\delta_{\nu}^{(i)}(y_i) = \frac{q_{\nu}^{(i)}(y_i) - p^{(i)}(y_i)}{p^{(i)}(y_i)}.\] in our particular setup. We have \[\require{physics} \label{eqn::defn95p95and95q} p^{(i)}(y_i) = \Tr(\rho_{0} E_{y_i})\text{and}q_{\nu}^{(i)}(y_i) = \Tr(\rho_{\nu} E_{y_i}),\tag{15}\] where \(\nu\) is drawn uniform at random from \(\mathcal{V}_{\mathcal{S}}\) and \(\rho_{mm}\) and \(\rho_{\nu} = \rho_{mm} + \Delta_{\nu}\). This gives \[\require{physics} \begin{align} H_i(\nu_1, \nu_2) &= d \sum_{y_i \in \mathcal{Y}_i} \frac{\Tr\left[ \Delta_{\nu_1} E_{y_i} \right] \Tr\left[ \Delta_{\nu_2} E_{y_i} \right]}{\Tr[E_{y_i}]} \notag \\ &= d \Tr\left[ \Delta_{\nu_1} \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ \Delta_{\nu_2} E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} \right] = d \Tr\left[ \Delta_{\nu_1} \mathcal{H}_i(\Delta_{\nu_2}) \right], \label{eqn:relation95H95i95Lüders95channel} \end{align}\tag{16}\] where \[\require{physics} \begin{align} \tag{17} \mathcal{H}_i: \mathbb{C}^{d \times d} \to \mathbb{C}^{d \times d}\text{with}&\mathcal{H}_i(A) := \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} \intertext{and} \tag{18} &\bar{\mathcal{H}} = \frac{1}{n} \sum_{i = 1}^n \mathcal{H}_i \end{align}\] are linear super-operators (see Lemma 5). This allows us to bound \[\require{physics} \begin{align} d_{\chi^2}\left( \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}, \mathbb{E}_{\nu} \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \right) &= \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V}_{\mathcal{S}})} \left[ \prod_{i = 1}^n \left( 1 + H_i(\nu_1, \nu_2) \right) \right] - 1 \\ &= \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V}_{\mathcal{S}})} \left[\exp\left(d \sum_{i = 1}^n \Tr\left[ \Delta_{\nu_1} \mathcal{H}_i(\Delta_{\nu_2}) \right] \right) \right] - 1 \\ &= \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V}_{\mathcal{S}})} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right] - 1. \end{align}\] Now, we use the fact that the probability of an alternative state not being a valid quantum states is exponentially small (see Lemma 4) in order to further bound \[\mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V}_{\mathcal{S}})} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right] \leq \left( \frac{e^d}{e^d -2} \right)^2 \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V})} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right]\] where we will write \(\mathbb{E}_{\nu_1, \nu_2} := \mathbb{E}_{\nu_1, \nu_2 \sim U(\mathcal{V})}\) in short from now on. For \(D \leq d^2 - 1\), let \(\mathcal{V}_D = \left( V_i \right)_{i = 1,...,D}\), where the \(V_i\) are the eigenvectors of \(\Bar{\mathcal{H}}\). Then, for \(\nu \in \{-1,1\}^D\), we have \[\Delta_{\nu} = \frac{c \epsilon}{\sqrt{dD}} \sum_{i = 1}^D \nu_i V_i \in \mathop{\mathrm{span}}(\mathcal{V}_D).\] Let \(\Phi_{\mathcal{V}_D}^{-1}(\Delta_\nu) = \left( \frac{c \epsilon}{\sqrt{dD}} \nu_i \right)_i = \frac{c \epsilon}{\sqrt{dD}} \nu\) be the coefficient vector of \(\Delta_{\nu}\) with respect to the basis \(\mathcal{V}_D\) of \(\mathop{\mathrm{span}}(\mathcal{V}_D)\). Furthermore, let \(M_D =\mathcal{M}_{\mathcal{V}_D}^{\mathcal{V}_D}(\Bar{\mathcal{H}}|_{\mathop{\mathrm{span}}(\mathcal{V}_D)}) = \mathop{\mathrm{diag}}\left( \mu_1,...,\mu_D \right)\) be the transformation matrix of \(\Bar{\mathcal{H}}|_{\mathop{\mathrm{span}}( \mathcal{V}_D)}\) with respect to the basis \(\mathcal{V}_D\). Then it holds \[\begin{align} \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle &= \left(\Phi_{\mathcal{V}_D}^{-1}(\Delta_{\nu_1})\right)^t \mathcal{M}_{\mathcal{V}_D}^{\mathcal{V}_D}(\Bar{\mathcal{H}}|_{\mathop{\mathrm{span}}( \mathcal{V}_D )}) \Phi_{\mathcal{V}_D}^{-1}(\Delta_{\nu_2}) \\ &= \frac{c^2 \epsilon^2}{dD} {\nu_1}^t M_D \nu_2 \\ &= \frac{c^2 \epsilon^2}{dD} \sum_{i = 1}^D \mu_i \nu_{1,i} \nu_{2,i}. \end{align}\] This now allows us to further bound the \(\chi^2\) distance as. \[\begin{align} d_{\chi^2}\left( \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}, \mathbb{E}_{\nu} \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \right) &\leq \left( \frac{e^d}{e^d -2} \right)^2 \mathbb{E}_{\nu_1, \nu_2} \left[ \exp\left(nd \langle \Delta_{\nu_1}, \bar{\mathcal{H}}(\Delta_{\nu_2}) \rangle \right) \right] - 1 \\ &= \left( \frac{e^d}{e^d -2} \right)^2 \mathbb{E}_{\nu_1, \nu_2} \left[ \exp\left(\frac{d c^2 \epsilon^2}{D} \sum_{i = 1}^D \mu_i \nu_{1,i} \nu_{2,i}\right) \right] - 1. \end{align}\] Using the tower property of the conditional expectation, we write \[\begin{align} \mathbb{E}_{\nu_1, \nu_2} \left[ \exp\left(\frac{d c^2 \epsilon^2}{D} \sum_{i = 1}^D \mu_i \nu_{1,i} \nu_{2,i}\right) \right] &= \mathbb{E}_{\nu_1, \nu_2} \left[ \mathbb{E}_{\nu_1, \nu_2}\left[ \exp\left(\frac{d c^2 \epsilon^2}{D} \sum_{i = 1}^D \mu_i \nu_{1,i} \nu_{2,i}\right) \middle| \nu_1 \right] \right] \\ &\leq \mathbb{E}_{\nu_1, \nu_2}\left[ \exp\left(\frac{1}{2} \frac{n^2 c^4 \epsilon^4}{D^2} \sum_{i = 1}^D \mu_i^2 \nu_{1,i}^2 \right) \right] \\ &= \exp\left(\frac{1}{2} \frac{n^2 c^4 \epsilon^4}{D^2} \sum_{i = 1}^D \mu_i^2 \right) \\ &= \exp\left( \frac{n^2 c^4 \epsilon^4}{2 D^2} \norm{M_D}_{HS}^2 \right) \end{align}\] using the fact that the Rademacher random variables \(\nu_{1,i}, \nu_{2,i}\) are iid. sub-gaussian and applying Theorem 7.27 in [28]. The main result of this proof is the fact that all the necessary information of the gentle measurement is encoded in the matrix \(M_D\) together with the parameter vectors \(\Phi_{\mathcal{V}_D}^{-1}(\Delta_\nu)\). For gentle measurements, the results from Proposition 9 give us a bound on the eigenvalues of \(\bar{\mathcal{H}}\), which are the diagonal entries of \(M_D\), in terms of the gentleness of the measurement. When choosing \(D = \frac{d^2}{2}\) we can now further bound \[\begin{align} \label{eqn::HS95norm95M95D95fixed} \norm{M_D}_{HS}^2 = \sum_{i = 1}^D \mu_i^2 \leq D \mu_D^2 \leq D \left(\frac{\sum_{i = D}^{d^2 - 1} \mu_i}{d^2 -1 - (D-1)} \right)^2 \leq \frac{512 \alpha^4}{(1-2\alpha)^8 d^2} \end{align}\tag{19}\] where we used the fact that assume the eigenvalues \(\mu_i\) to be ordered from smallest to largest and the results of Proposition 9. This gives \[\begin{align} d_{\chi^2}\left( \mathbb{P}_{\rho_0^{\otimes n}}^{R^{M^{\otimes n}}}, \mathbb{E}_{\nu} \left[ \mathbb{P}_{\rho_{\nu}^{\otimes n}}^{R^{M^{\otimes n}}} \right] \right) &\leq \left( \frac{e^d}{e^d -2} \right)^2 \exp\left( 512 \frac{n^2 c^4 \epsilon^4 \alpha^4}{2D^2 d^2} \right) - 1 \\ &\leq \left( \frac{e^d}{e^d -2} \right)^2 \exp\left( 1024 c^4 \frac{n^2 \epsilon^4 \alpha^4}{d^6} \right) - 1 \end{align}\] showing that the error of any locally-\(\alpha\)-gentle test is bounded from below from 0 as long as \(n \geq \Omega\left( \frac{d^3}{\epsilon^2 \alpha^2} \right)\), completing the proof of Theorem 4.
Note that the proof is not exclusively valid for \(\rho_0\) being the maximally mixed state. Suppose that \(\rho_0\) is a full rank quantum state belonging to some class \(\mathcal{S}_{c_{min}} = \left\{ \rho \in \mathcal{S}(\mathbb{C}^d) \; \middle| \; \lambda_{min}(\rho) \geq \frac{c_{min}}{d}\right\}\) for some fixed \(c_{min} > 0\). Then the results of Lemma 4 still hold for \(c = 10\sqrt{2}\) and \(\epsilon < \frac{c_{min}}{c^2}\) showing that the construction in equation 14 are valid alternative states with high probability, even in the case that \(\rho_0\) is not the maximally mixed state. Furthermore, using the properties of gentle measurements, for the probability mass functions defined in 15 , which we insert in 16 , we have \[\require{physics} \frac{1}{p^{(i)}(y_i)} = \frac{1}{\Tr[\rho_0 E_{y_i}]} \leq \frac{1}{\lambda_{min}(E_{y_i})} \leq \frac{e^{\delta}}{\lambda_{max}(E_{y_i})} \leq \frac{d e^{\delta}}{\Tr[E_{y_i}]}.\] Therefore, the linear super-operator we end up with in this case is the same as in 18 with an additional factor of \(e^{\delta}\). For \(\alpha\) bounded away from \(\frac{1}{2}\), we have \(\delta\) bounded away from \(\infty\) which does not alter the rate in terms of \(d, n, \epsilon\) and \(\alpha\).
The next two results are concerned with the properties of the super-operators define in 17 and 18 .
Lemma 5. Let \(\mathcal{H}_i\) and \(\bar{\mathcal{H}}\) be defined as in 17 and 18 . Then
\(\mathcal{H}_i\) and \(\bar{\mathcal{H}}\) are hermitian and positive.
\(\mathcal{H}_i\) and \(\bar{\mathcal{H}}\) are Hermiticity-preserving.
\(\mathcal{H}_i\) and \(\bar{\mathcal{H}}\) are Trace-preserving.
\(\mathcal{H}_i\) and \(\bar{\mathcal{H}}\) are unital.
Proof.
Let \(A \in \mathbb{C}^{d \times d}\). Then \[\require{physics} \begin{align} \Tr\left[ A^* \mathcal{H}_i(A) \right] &= \Tr\left[ A^* \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} \right] \\ &= \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A^* E_{y_i} \right] \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} \\ &= \sum_{{y_i} \in \mathcal{Y}_i} |\Tr\left[ A E_{y_i} \right]|^2 \frac{1}{\Tr[E_{y_i}]} \geq 0 \end{align}\] using the fact that \(\require{physics} \Tr[A^*E_{y_i}] = \Tr\left[(E_{y_i} A)^*\right] = \overline{\Tr\left[E_{y_i} A\right]}\). As such \(\mathcal{H}_i\) is hermitian and positive and with it \(\bar{\mathcal{H}}\).
Let \(A \in \mathbb{H}_d\) be hermitian. Then \[\require{physics} \begin{align} \mathcal{H}_i(A)^* &= \left(\sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i}\right)^* \\ &= \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A^* E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} = \mathcal{H}_i(A^*) = \mathcal{H}_i(A). \end{align}\] By linearity, \(\bar{\mathcal{H}}(A)^* = \bar{\mathcal{H}}(A)\).
Let \(A \in \mathbb{C}^{d \times d}\). Then \[\require{physics} \begin{align} \Tr\left[ \mathcal{H}_i(A) \right] &= \Tr\left[ \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} \right] \\ &= \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ A E_{y_i} \right] = \Tr\left[ A \sum_{{y_i} \in \mathcal{Y}_i} E_{y_i} \right] = \Tr[A]. \end{align}\] By linearity, \(\bar{\mathcal{H}}\) is also trace-preserving.
We have \[\require{physics} \mathcal{H}_i(\text{\usefont{U}{bbm}{m}{n}1}) = \sum_{{y_i} \in \mathcal{Y}_i} \Tr\left[ \text{\usefont{U}{bbm}{m}{n}1} E_{y_i} \right] \frac{1}{\Tr[E_{y_i}]} E_{y_i} = \sum_{{y_i} \in \mathcal{Y}_i} E_{y_i} = \text{\usefont{U}{bbm}{m}{n}1}.\] By linearity, \(\bar{\mathcal{H}}\) is also unital.
◻
With these results we can prove some further properties of the operator \(\bar{\mathcal{H}}\) that we state in the following proposition.
Proposition 9. Let \(M_i = (M_{y_i})_{y_i \in \mathcal{Y}_i}\) be \(\alpha\) gentle measurements for \(i = 1,...,n\), \(\alpha \in [0, 1/2)\) and \(E_{y_i} = M_{y_i}^*M_{y_i}\). Furthermore, let \(\bar{\mathcal{H}}\) be as in 18 where the \(\mathcal{H}_i\) are defined with respect to the gentle measurements \(M_i\). Then
There exists an orthonormal basis \(V_1,...V_{d^2} \in \mathbb{H}_d\) of eigenvectors of \(\bar{\mathcal{H}}\) with eigenvalues \(\mu_1, ...,\mu_{d^2} > 0\) such that \[\require{physics} \bar{\mathcal{H}}(A) = \sum_{i = 1}^{d^2} \mu_i \Tr\left[V_i A \right] V_i\]
\(\text{\usefont{U}{bbm}{m}{n}1}/\sqrt{d} = V_{d^2}\) is an eigenvector of \(\bar{\mathcal{H}}\) with eigenvalue \(1\).
We have \(\require{physics} \Tr\left[ V_i \right] = 0\) for \(i = 1,...,d^2-1\).
We have \(\sum_{i = 1}^{d^2-1} \mu_i \leq \frac{16\alpha^2}{(1-4\alpha^2)^2}\).
Proof.
By Lemma 5, we know that \(\bar{\mathcal{H}}\) is a positive \(\mathbb{C}\)-linear operator on the \(\mathbb{C}\)-vector space \(\mathbb{C}^{d \times d}\). Since it is also Hermiticity-preserving, its restriction \(\bar{\mathcal{H}}|_{\mathbb{H}_d}\) to the space of hermitian matrices \(\mathbb{H}_d\) is also a self-adjoint and positive \(\mathbb{R}\)-linear operator on the \(\mathbb{R}\)-vector space \(\mathbb{H}_d\). As such, there exist an orthonormal basis \(V_1,...,V_{d^2} \in \mathbb{H}_d\) of eigenvectors of \(\bar{\mathcal{H}}|_{\mathbb{H}_d}\) with eigenvalues \(\tilde{\mu}_1,...,\tilde{\mu}_{d^2} > 0\) such that \[\require{physics} \bar{\mathcal{H}}|_{\mathbb{H}_d}(A) = \sum_{i = 1}^{d^2} \tilde{\mu}_i \Tr[V_i A] V_i.\] Since \(\bar{\mathcal{H}}\) is a positive \(\mathbb{C}\)-linear operator on \(\mathbb{C}^{d \times d}\), there exist an orthonormal basis of vectors \(W_1,...,W_{d^2} \in \mathbb{C}^{d \times d}\) with eigenvalues \(\mu_1,...,\mu_{d^2} > 0\) such that \[\require{physics} \bar{\mathcal{H}}(A) = \sum_{i = 1}^{d^2} \mu_i \Tr[W_i A] W_i.\] Obviously, the vectors \(V_i\) are eigenvectors of \(\bar{\mathcal{H}}\) as well and they remain linear independent in the larger \(\mathbb{C}\)-vector space \(\mathbb{C}^{d \times d}\) due to them remaining orthogonal. Therefore, it must hold \(W_i = V_i\) and \(\tilde{\mu}_i = \mu_i\) for all \(i\).
Since \(\bar{\mathcal{H}}\) is unital, \(\text{\usefont{U}{bbm}{m}{n}1}\) is an eigenvector of \(\bar{\mathcal{H}}\) with eigenvalue \(1\) and therefore its renormalization \(\text{\usefont{U}{bbm}{m}{n}1}/\sqrt{d} = V_{d^2}\) as well.
Since the \(V_i\) are orthogonal, we have \[\require{physics} 0 = \Tr\left[ V_{d^2} V_i \right] = \Tr\left[ \text{\usefont{U}{bbm}{m}{n}1} V_i \right] = \Tr\left[ V_i \right]\] for all \(i = 1,...,d^2-1\).
Since the measurements \(M_i\) are \(\alpha\)-gentle, by Theorem 2, they are \(\delta\)-quantum-differentially-private for \(\delta = 2\log(\frac{1+2\alpha}{1-2\alpha})\). Then each channel \(\mathcal{H}_j\) has a basis of eigenvectors \(V_i^{(j)}\) with eigenvalues \(\mu_i^{(j)}\), where \(V_{d^2}^{(j)} = \frac{1}{\sqrt{d}} \text{\usefont{U}{bbm}{m}{n}1}\). We know that the matrices \(V_i^{(j)}\) are traceless and as such we have \[\require{physics} \begin{align} \sum_{i = 1}^{d^2 -1} \mu_i^{(j)} &= \sum_{i = 1}^{d^2 -1} \Tr\left[ V_i^{(j)} \Bar{\mathcal{H}_j}(V_i^{(j)}) \right] \\ &= \sum_{i = 1}^{d^2 -1} \sum_{y_j \in \mathcal{Y}_j} \Tr\left[ V_i^{(j)} E_{y_j} \right]^2 \frac{1}{\Tr[E_{y_j}]} \intertext{Now, using the fact that \Tr[E_{y_j}] \geq d \lambda_{min}(E_{y_j}) we get} &\leq \frac{1}{d} \sum_{i = 1}^{d^2 -1} \sum_{y_j \in \mathcal{Y}_j} \Tr\left[ V_i^{(j)} E_{y_j} \right]^2 \frac{1}{\lambda_{min}(E_{y_j})} \\ &= \frac{1}{d} \sum_{i = 1}^{d^2 -1} \sum_{y_j \in \mathcal{Y}_j} \Tr\left[ V_i^{(j)} \left( \frac{E_{y_j}}{\lambda_{min}(E_{y_j})} - \text{\usefont{U}{bbm}{m}{n}1} \right) \right]^2 \lambda_{min}(E_{y_j}) \\ &= \frac{(e^{\delta} -1)^2}{d} \sum_{y_j \in \mathcal{Y}_j} \sum_{i = 1}^{d^2 -1} \Tr\left[ V_i^{(j)} A_{y_j} \right]^2 \lambda_{min}(E_{y_j}) \intertext{where A_{y_j} := \frac{1}{e^{\delta}-1} \left(\frac{E_{y_j}}{\lambda_{min}(E_{y_j})} - \text{\usefont{U}{bbm}{m}{n}1}\right) has maximal eigenvalue 1 due to Proposition~\ref{prop::equalities95qDP}. Since (V_i^{(j)})_{i = 1,...,d^2} forms an orthonormal basis of \mathbb{C}^{d \times d}, we may bound} &\sum_{i = 1}^{d^2 -1} \Tr\left[ V_i^{(j)} A_{y_j} \right]^2 \leq \norm{A_{y_j}}_{HS}^2 \leq d. \intertext{Finally, this gives the bound} \sum_{i = 1}^{d^2 -1} \mu_i^{(j)} &\leq \frac{(e^{\delta} -1)^2}{d} \sum_{y_j \in \mathcal{Y}_j} d \lambda_{min}(E_{y_j}) \leq (e^{\delta} -1)^2. \end{align}\] Therefore, using the fact that \(\frac{1}{\sqrt{d}} \text{\usefont{U}{bbm}{m}{n}1}\) is an eigenvector for all \(\mathcal{H}_j\) and \(\Bar{\mathcal{H}}\) with eigenvalue 1, it holds \[\require{physics} \begin{align} \sum_{i = 1}^{d^2 -1} \mu_i &= \Tr\left[ \Bar{\mathcal{H}} \right] - 1 = \frac{1}{n} \sum_{j = 1}^n \Tr\left[ \mathcal{H}_j \right] - 1 = \frac{1}{n} \sum_{j = 1}^n \sum_{i = 1}^{d^2} \mu_i^{(j)} -1 \\ &\leq \frac{1}{n} \sum_{j = 1}^n \left((e^{\delta} -1)^2 + 1\right) - 1 = (e^{\delta} -1)^2 = \frac{16 \alpha^2}{(1-4\alpha^2)^2}. \end{align}\]
◻