content_image/385111.jpg content_image/385112.jpg content_image/385113.jpg content_image/385116.jpg
〈 Y$_{1}$, . . . , Y$_{m}$ 〉 be a random vector of C ’s sampled uniformly without replacement. 

We are mainly interested in the case where C is a finite set of Hermitian matrices with some additional properties: We assume the set is centered GLYPH<BX> [ X$_{i}$ ] = 0 and that there are con- stants c, σ$_{0}$ ∈ GLYPH<CA> bounding the operator norm ‖ X$_{i}$ ‖ ≤ c and the variance ‖ GLYPH<BX> [ X 2 $_{i}$] ‖ ≤ σ 2 0 of the random variables. Then: 

Theorem 1 (Operator-Bernstein inequality) . With the defini- tions above, let S$_{X}$ = ∑ m i $_{=1}$X$_{i}$ and S$_{Y}$ = ∑ m i $_{=1}$Y$_{i}$ . Let V = mσ 2 $_{0}$. Then for both S = S$_{X}$ and S = S$_{Y}$ it holds that 

for t ≤ 2 V/c , and 

for larger values of t . 

The version involving S$_{X}$ has been proved in [1] as a minor variation of the operator-Chernoff bound from [11]. In the proof, the failure probability is bounded from above in terms of the “operator moment-generating function” 

To establish the more general statement, it would be sufficie nt to show that M$_{Y}$ ≤ M$_{X}$ . In fact, this relation is well-known to hold for real-valued random variables. One popular way of proving it involves the notion of negative association [12, 13]. Indeed, the author of [1] tried to generalize this concept to the case of matrix-valued random variables, but failed to over- come its apparent dependency on the total order of the real numbers. However, he overlooked a much older and more el- ementary argument given in [14], which only relies on certain convexity properties and applies without change to the matrix- valued case (see below). 

As a consequence of Theorem 1, the analysis in Section II.C of [1] can be simplified and improved, by setting the constant C equal to one. The remark at the end of that section applies. In particular, in the rest of that paper, one may assume that ‖ Δ$_{T}$ ‖ 2 < n 1 / $^{2}$‖ Δ ⊥ T ‖ $_{2}$. Thus, the conditions on the certificate Y in Section II.E may be relaxed to ‖P $_{T}$Y − sgn ρ ‖ 2 ≤ 1 2 n 1 / $_{2}$. This implies that l , the number of iterations of the “golfing scheme”, may be reduced to l = ⌈ log$_{2}$(2 n 1 / 2 √$_{r}$$_{)}$ ⌉ . The esti- mates on | Ω | in Theorems 1, 2, and 3 therefore all improve by a factor of log$_{2}$ n 2 log$_{2}$ n 1 / 2 = 4 . 

In [9], Proposition 3.3 becomes superfluous. The final bounds improve accordingly. 

The consequences are more pronounced for an upcoming detailed analysis [15] of noise resilience (in the spirit of [16]) of quantum mechanical applications. 

<img src='content_image/385111.jpg'>

<img src='content_image/385112.jpg'>

<img src='content_image/385113.jpg'>

## C. Implications 

The present note makes no statements about approaches which either rely on the Bernoulli model, or use the non- commutative Kintchine inequality instead of the operator Chernoff bound [3, 4, 10]. 

Finally, note that the “golfing scheme” employed in [1, 8] demands that l independent batches of coefficients be sam- pled. As a consequence of Theorem 1, every single batch may be assumed to be drawn without replacement. However, for technical reasons, it is still necessary that the batches remain independent. This does not constitute a problem. Indeed, let Ω be the set of distinct coefficients used by the golfing scheme. It is shown that, with high probability, there exists a “dual certificate” in the space spanned by the basis elements corre - sponding to the coefficients in Ω . Since Ω is just a random subset of cardinality | Ω | ≤ m , the probability that there is a dual certificate in the space spanned by m distinct random ba- sis elements (obtained from sampling without replacing) can only be higher. A very similar argument has recently been given in [10], where the golfing scheme has been modified to work with the Bernoulli model. 

In this section, we repeat an argument from [14] which im- plies that for all λ ∈ GLYPH<CA> the inequality M$_{Y}$ ( λ ) ≤ M$_{X}$ ( λ ) holds. We emphasize that the proof of [14] does not need to be modified in order to apply matrix-valued random variables . However, the version given below makes some steps explicit which were omitted in the original paper. 

For now, let C be any finite set; let X , Y be as above. The central observation is that one can generate the dis- tribution of X by first sampling y = 〈 y$_{1}$, . . . , y$_{m}$ 〉 with- out replacement, and then drawing the x$_{1}$, . . . , x$_{m}$ from { y$_{1}$, . . . , y$_{m}$ } in a certain (unfortunately not completely triv- ial) way. 

To make that second step precise, we introduce a random partial function Z from C m to C $^{m}$. The domain of f is the set of vectors y ∈ C m with pairwise different components ( y$_{i}$ ̸ = y$_{j}$ ). Given such a vector y , we sequentially assign values to the components Z$_{1}$, . . . , Z$_{m}$ of Z ( y ) by sampling from { y$_{1}$, . . . , y$_{m}$ } according to the following recipe. At the k th step, let D$_{k}$ be the subset of { y$_{1}$, . . . , y$_{m}$ } of values which have already been drawn in a previous step. To get Z$_{k}$ : 

1. with probability | D$_{k}$ | | C | take a random element from D$_{k}$ , 

and 

2. with probability 1 − | D$_{k}$ | | C | take a random element from the { y$_{1}$, . . . , y$_{m}$ } not contained in D$_{k}$ . 

(Here, by a “random” element, we mean one sampled uni- formly at random from the indicated set). Then 

Lemma 2. With the definitions above, X and Z ( Y ) are iden- tically distributed. 

What is more, if C is a subset of a vector space, then 

<img src='content_image/385116.jpg'>

## D. Proof 

