# The suboptimality ratio of projective measurements restricted to low-rank subspaces

Albert Senen-Cerda

► To cite this version:

Albert Senen-Cerda. The suboptimality ratio of projective measurements restricted to low-rank subspaces. 2024. hal-04834816

HAL Id: hal-04834816

https://hal.science/hal-04834816v1

Preprint submitted on 12 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The suboptimality ratio of projective measurements restricted to low-rank subspaces

Albert Senen-Cerda

IRIT, LAAS-CNRS, and Université Toulouse Paul Sabatier, France

albert.senen-cerda@irit.fr

## Abstract

Limitations in measurement instruments can hinder the implementation of some quantum algorithms. Understanding the suboptimality of such measurements with restrictions may then lead to more efficient measurement policies. In this paper, we theoretically examine the suboptimality arising from a Procrustes problem for minimizing the average distance between two fixed quantum states when one of the states has been measured by a Projective Measurement (PM). Specifically, we compare optima when we can only use PMs that are aligned with a low-rank subspace supported by the quantum states, and the case that we can measure with the full set of PMs. For this problem, we show that the suboptimality ratio is independent of the dimension of the full space, and is at most polylogarithmic in the dimension of the low-rank subspace. In the proof of this result, we use a probabilistic approach and the main techniques include trace inequalities related to projective measurements, and operator norm bounds for equipartitions of Parseval frames, which are of independent interest.

## 1 Introduction

Projective Measurements (PMs), and the larger set of Positive Operator Valued Measures (POVMs) play a key role in quantum tomography [7], state discrimination [11], quantum key distribution [18, 24], and measurement-based quantum computing [9]. In practical applications, however, due to restrictions in measurement instruments and resources, not all optimal PMs or POVMs can be accurately implemented. For example, this occurs when only a limited selection of high-fidelity PMs are available to the practitioner or when no ancilla states are possible; those typically used to implement POVMs. From a theoretical perspective, these restrictions are circumvented by using a smaller set of measurements plus additional resources, e.g., POVMs can be instead simulated from PMs with additional postselection [25].

If we focus on optimization problems with measurements, it is unclear which problems have PMs as optima, and more precisely how suboptimal they become if additional restrictions exist. In this paper, we focus on this latter issue and bound the suboptimality arising from a Procrustes problem with PMs that are aligned with a low-rank structure of the measured states.

Upon measuring a quantum state with an observable on an ambient space $\mathcal{H}$, the probability that a certain outcome is observed depends on the alignment between the measured state and the state that would correspond to that outcome. A projective measurement $\mathcal{P} = \{P_1, \dots, P_n\}$ consists of $n$ orthogonal projectors that characterize the outcomes of a measurement. After measurement of a mixed quantum state $\rho$ by $\mathcal{P}$, the random outcome of the measurement $X$ is $P_i$ with probability $\text{Tr}[\rho P_i] \ge 0$ for all $i \in [n]$. The Procrustes problem for PMs can be formulated as finding a PM $\mathcal{P}$ of $\rho$ that in expectation brings the random outcome state $X = X(\mathcal{P}, \rho)$ closest to another mixed quantum state $\tau$. In Frobenius norm, the problem is equivalent to finding

$$ \min_{\mathcal{P} \in \mathcal{P}(\mathcal{H})} \mathbb{E} \left[ \| \tau - X(\mathcal{P}, \rho) \|_{\text{F}}^2 \right], \qquad (1) $$
where $P(\mathcal{H})$ is the set of PMs. Up to constants, (1) is equal to the following maximization problem over PMs

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \sum_{i=1}^{n} \mathrm{Tr}[\tau P_i \rho P_i]. \qquad (2) $$

This optimization problem is nonconvex, and for our setting we consider additional restrictions. Firstly, we assume that $\tau$, and $\rho$ have a low rank structure and are only composed of states supported in a subspace $\mathcal{S} \subset \mathcal{H}$ of dimension $r \ll n$. Secondly, we model constraints of the measurement instrument by considering only PMs $\mathcal{Q}$ that are aligned with this subspace $\mathcal{S}$. Formally, this means that $r$ out of $n$ orthogonal projectors generate also a projective measurement on $\mathcal{S}$. The set of such PMs will generate a strict subset $P(\mathcal{S}) \subset P(\mathcal{H})$, and we can thus also define a constrained maximization problem analogous to (2). A relevant question is how suboptimal is the restriction to measurements over the low-rank structure compared to using the full set of PMs. We can define the suboptimality ratio as the smallest constant $K_{n,r} \ge 1$ such that for any quantum states $\rho$ and $\tau$ with support in a subspace $\mathcal{S} \subset \mathcal{H}$ of dimension $r$,

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \sum_{i=1}^{n} \mathrm{Tr}[\tau P_i \rho P_i] \le K_{n,r} \max_{\mathcal{Q} \in P(\mathcal{S})} \sum_{i=1}^{r} \mathrm{Tr}[\tau Q_i \rho Q_i]. \qquad (3) $$

The constant $K_{n,r}$ encodes the suboptimality of restricting to measurements in the low-rank subspace, and a low value would imply that we can use the smaller set of measurements aligned with the subspace of quantum states to approximate (2). Constants that encode information on maximal suboptimality are common in quantum information. We can namely mention Tsirelson's bound that is perhaps the most well-known and is fundamental in bounding violations of Bell's inequalities [12]. For the maximization in (2), there are some results in the context of quantum control [26]. In particular, for the constant $K_{n,r}$, when $\tau$ and $\rho$ are pure states ($r=2$) then it is known that $K_{n,2}=1$ for all $n \ge 2$ [36]. For general mixed states ($r \ge 2$), the magnitude of $K_{n,r}$ is however unknown.

Our main contribution is to show that there exists $c > 0$ such that for any $n \ge r \ge 2$,

$$ K_{n,r} \le c \log(r)^4. \qquad (4) $$

The bound (4) indicates that the suboptimality does not depend on the dimension $n$ of the ambient space $\mathcal{H}$ and is at most polylogarithmic in the dimension $r$ of the low-rank subspace $\mathcal{S}$. As a consequence, we may approximate the solution of (2) up to a polylogarithmic factor by optimizing over the smaller space $\mathcal{S}$ where both $\rho$ and $\tau$ are supported.

Our second contribution is technical and relates to the methods used in the proof of (4). We use a probabilistic approach to upper bound the trace of certain Kraus maps by randomized operators while preserving their PM structure. Restricted to $\mathcal{S}$, the projectors $P_i$ induce vectors $|v_i\rangle \in \mathcal{S}$ that generate a Parseval frame and satisfy

$$ \sum_{i=1}^{n} |v_i\rangle\langle v_i| = 1_S. \qquad (5) $$

The measurement $\mathcal{P} \in P(\mathcal{H})$ in (2) can be understood on $\mathcal{S}$ as sum of a PM $\mathcal{Q} \in P(\mathcal{S})$ that is weighted by $T = [n/r]$ matrices $L_t$ obtained from some equipartition of the frame vectors

$$ \sum_{t=1}^{T} \mathrm{Tr}[\tau L_t \mathcal{Q}[L_t^\dagger \rho L_t] L_t^\dagger] \quad \text{where} \quad \mathcal{Q}[a] = \sum_{i=1}^{r} Q_i a Q_i. \qquad (6) $$

Similar to (5), the weight matrices satisfy

$$ \sum_{t=1}^{T} L_t L_t^\dagger = 1_S. \qquad (7) $$

The difficulty of the analysis lies in decoupling the dimension $n$ from (6) while preserving the PMs structure of the measurements involved. To tackle this problem we use a probabilistic approach and
find a single random measurement that in expectation behaves as the sum of the measurements in (6). Specifically, we consider Gaussian random weight matrices of the type

$$ \hat{L} = \sum_{t=1}^{T} g_t L_t, \quad \text{where} \quad g_t \sim \text{N}(0, 1) \quad \text{are i.i.d. for all } t \in [T]. \qquad (8) $$

By using this random weight in a measurement, we transfer the dependence on the dimension $n$ from the sum of weighted PM in (6) to the variance of (8).

Additional key steps in the proof include showing the existence of a partition $\pi$ of the frames that satisfies variance constraints independent of $n$. The probabilistic method from combinatorics is used in this step to bound the operator norm of a frame variance matrix. In this way, with high probability we obtain

$$ \|\hat{L}\|_{\text{op}} < c \log(r). \qquad (9) $$

We also introduce new trace inequalities to extract the weights $L_t$ from the traces in (6) while preserving the PMs structure of the measurements. These inequalities are based on complex interpolation results.

Remarkably, our proof method directly relates the polylogarithmic term in (4) with the additional dimensional factor that appears in well-known random matrix concentration inequalities [34] compared to their univariate counterparts. This fact suggests that our method cannot be further improved without using additional information about the optima of (2).

## 1.1 Related Literature

Procrustes problems have been previously studied in the literature. We can namely mention Procrustes problems for orthogonal matrices [30], weighted versions with quadratic constraints [16], conic constraints [4, 14], and problems with manifold constraints [6, 1].

The maximization problem in (2) appears in the context of quantum control with nonselective measurements in [26], and for general Kraus maps in [27]. Special cases are studied in [36], including the case $r = 2$ and $n \ge 2$. In particular $K_{n,2} = 1$ is shown using the first order stationary conditions; see (16) in Section 2.1. By relaxing in (2) the optimization to general Kraus maps, no local maxima exist for $n = 2$ [27], but this may not be the case for projective measurements.

From a theoretical perspective, the analysis of the suboptimality in optimization problems is commonly conducted to approximate solutions of computationally hard problems. Related to the quantum setting, for example, we can mention semi-definite program relaxations for generalized orthogonal Procrustes problems [5, 37] that are related to the well-known Grothendieck's inequality [8]. Grothendieck's constant [19] characterizes maximal inequality bounds and can be interpreted as a suboptimality ratio between optimization problems with different constraints on the dimensions [10], which is similar to (3). We remark, however, that these constants are universally bounded and do not grow indefinitely with the intrinsic dimension of the problem—the dimension of $\mathcal{S}$ in our setting—except if there are additional constraints, such as those induced by a graph structure [3].

We use key properties of Parseval frames [35] such as (5). In particular, we partition the frame into equal-sized sets and try to impose an orthogonal structure on each partition. Orthogonalization has been studied before in [13] for POVMs, where it is shown that if a POVM is close to being orthogonal, then there exists a PM that is actually close to the POVM. Differently in our problem, the frame in (5) may be far from orthogonal, and we have additional constraints such as the dimension of the PMs that we seek.

In the proof of (4), we use the probabilistic method [2] to prove the existence of operators with certain properties by showing that they occur with positive probability. In quantum information, for example, this method can be used to find low-rank approximations of Kraus maps [21] by using random Kraus operators. In our case, we use the random matrix (8) to randomize, and upper bound (6) while preserving the PM structure of the operators. Concentration inequalities for Gaussian random matrices from [34] are then used to estimate the operator norm provided that its variance can be controlled. Operator norm bounds for random matrices have been used in the quantum setting to understand quantum expanders [20, 17], and other random quantum channels [15, 22]. In our setting, to show that the variance of (8) is small we consider a random partition
$\pi$ and bound the operator norm of a random variance matrix of $\hat{L}$ induced by this partition. We use the method of moments to estimate the operator norm [33], but differently from the typical concentration bounds that assume independence, in our case the entries of the matrix have strong dependencies induced by the frame.

Finally, we also use operator trace inequalities such as trace convexity [23], and in Section 4.5 we show new trace inequalities involving projective measurements using complex interpolation techniques. We can mention [32] where interpolation inequalities for traces of matrix products are shown using a similar approach.

## 2 Preliminaries

Let $\mathcal{H}$ be a complex finite-dimensional Hilbert space with inner product $\langle \cdot | \cdot \rangle : \mathcal{H} \times \mathcal{H} \to \mathbb{C}$, and such that $\dim(\mathcal{H}) = n$. Let $B(\mathcal{H})$ be the space of linear maps of $\mathcal{H}$, and let

$$B^{\text{sa}}(\mathcal{H}) = \{A \in B(\mathcal{H}) \mid A = A^{\dagger}\},$$

be the set of self-adjoint operators of $\mathcal{H}$. We also let $B_{\ge}^{\text{sa}}(\mathcal{H})$, and $B_{>}^{\text{sa}}(\mathcal{H})$ be the sets of nonnegative selfadjoint, and positive selfadjoint operators, respectively. The set of density matrices of $\mathcal{H}$ is defined by

$$D(\mathcal{H}) = \{\rho \in B_{\ge}^{\text{sa}}(\mathcal{H}), \text{Tr}[\rho] = 1\}. \qquad (10)$$

The set of (nondegenerate) PMs in $\mathcal{H}$ is composed of sets of $n$ orthogonal rank-one projectors

$$P(\mathcal{H}) = \{(P_1, \dots, P_n) \in B(\mathcal{H})^{\times n} : P_i = P_i^{\dagger}, P_i P_j = \delta_{ij} P_i, \text{rk}(P_i) = 1 \text{ for } i \in [n]\}. \qquad (11)$$

For any $\mathcal{P} \in P(\mathcal{H})$, the following partition of unity property for the identity operator $1_{\mathcal{H}} \in B(\mathcal{H})$ holds

$$\sum_{i=1}^{n} P_i = 1_{\mathcal{H}}. \qquad (12)$$

When a mixed quantum state encoded by a density matrix $\rho \in D(\mathcal{H})$ is measured by a PM $\mathcal{P} \in P(\mathcal{H})$, the outcome state $X$ is $P_i \in D(\mathcal{H})$ with probability $\text{Tr}[P_i\rho] \ge 0$. Let $\mu(\rho, \mathcal{P})$ be the distribution of the random density matrix $X$ describing the outcome state after measuring $\rho$ with $\mathcal{P} \in P(\mathcal{H})$. The expected state after measurement is then given by

$$\mathcal{P}[\rho] = \mathbb{E}_{X \sim \mu(\rho, \mathcal{P})}[X] = \sum_{i=1}^{n} \text{Tr}[\rho P_i] P_i = \sum_{i=1}^{n} P_i \rho P_i. \qquad (13)$$

### 2.1 Procrustes problem for projective measurements

Given a target quantum state $\tau \in D(\mathcal{H})$, we can ask what is the expected distance between $\tau$, and the outcome state of the measurement of $\rho$ by $\mathcal{P}$. The Procrustes problem for PM consists of finding for which measurement $\mathcal{P} \in P(\mathcal{H})$ the expected distance is minimized. In the Frobenious norm, $\|A\|_{\text{F}}^2 = \text{Tr}[AA^{\dagger}]$, the Procrustes problem is

$$\begin{aligned} \min_{\mathcal{P} \in P(\mathcal{H})} \mathbb{E}_{X \sim \mu(\rho, \mathcal{P})} \left[ \|\tau - X\|_{\text{F}}^2 \right] &= \min_{\mathcal{P} \in P(\mathcal{H})} \sum_{i=1}^{n} \text{Tr}[P_i \rho] \|\tau - P_i\|_{\text{F}}^2 \\ &= \min_{\mathcal{P} \in P(\mathcal{H})} -\sum_{i=1}^{n} 2 \text{Tr}[P_i \rho] \text{Tr}[P_i \tau] + C(\rho, \tau) \\ &= -2 \max_{\mathcal{P} \in P(\mathcal{H})} \text{Tr}[\rho \mathcal{P}[\tau]] + C(\rho, \tau), \end{aligned} \qquad (14)$$

where the last equality holds since projectors are rank-one and so for all $i \in [n]$, $\text{Tr}[P_i\rho]\text{Tr}[P_i\tau] = \text{Tr}[P_i\rho P_i\tau]$. Both $\tau$ and $\rho$ are fixed, so both (14) and (2) are equivalent up to a constant.

The maximization problem (2) is symmetric over $\rho$ and $\tau$, and can be posed as an optimization over the unitary group $U(\mathcal{H}) = \{U \in B(\mathcal{H}) : UU^{\dagger} = UU^{\dagger} = 1_{\mathcal{H}}\}$. We let the measurement
$\tilde{P}(U) = \{U\tilde{P}_1U^\dagger, \dots, U\tilde{P}_nU^\dagger\}$ be dependent on $U \in U(\mathcal{H})$ for some $\tilde{P} \in P(\mathcal{H})$ fixed. Then we can consider the equivalent maximization problem

$$ \max_{U \in U(\mathcal{H})} \mathrm{Tr}[\rho \tilde{P}(U)[\tau]]. \qquad (15) $$

In [36], the first order stationary conditions for critical points of (15) were computed: a critical point $U^*$ with measurement $\mathcal{P}^* = \mathcal{P}(U^*)$ must satisfy

$$ [\rho, \mathcal{P}^*[\tau]] = [\mathcal{P}^*[\rho], \tau], \qquad (16) $$

where $[A, B] = AB - BA$ is the commutator. This problem (15) is nonconvex, and to our knowledge it is unknown how complex the optimization landscape is, e.g., how many critical points exist satisfying (16). In Section 5, we will use manifold optimization [1] to try to numerically find (15).

## 2.2 Restriction to aligned projective measurements

For the maximization problem in (2), we impose some restrictions in the set of measurements as well as some additional structure that we can exploit. To model the limitations of measurement instruments, we assume that we can only use projective measurements aligned with a subspace smaller than $\mathcal{H}$. Furthermore, we assume there is an additional low-rank structure in the quantum states that is also aligned with the aforementioned subspace. We formalize these ideas as follows.

Firstly, we assume that both $\tau$ and $\rho$ belong to a low-rank subspace $S \subset \mathcal{H}$ with $\dim(S) = r$. Specifically, for any vector $|v\rangle \in S^{\perp}$—the orthogonal subspace in $\mathcal{H}$ of $S - \rho|v\rangle = \tau|v\rangle = 0$, and all eigenvectors with positive eigenvalue of $\rho$ and $\tau$ belong to $S$. Secondly, to model the restriction of certain measurements, we will consider the maximization only over a subset of PMs that commute with the unique orthogonal projector $\Pi_S: \mathcal{H} \to S$ from $\mathcal{H}$ onto $S$ and is related to the set of PMs of $S$. As in (11), we define

$$ P(S) = \{(Q_1, \dots, Q_r) \in B(S)^{\times r} : Q_i = Q_i^\dagger, Q_i Q_j = \delta_{ij} Q_i, \mathrm{rk}(Q_i) = 1 \text{ for } i \in [r]\}. \qquad (17) $$

There is an injective map $\iota: P(S) \to P(\mathcal{H})$ given by completing the set of $r$ orthogonal projectors of $Q \in P(S)$ in $\mathcal{H}$ with orthogonal projectors from a fixed $Q^{\perp} \in P(S^{\perp})$. Since $\rho$, and $\tau \in D(S)$ are invariant under $\Pi_S$, we have the equality

$$ \mathrm{Tr}[\tau Q[\rho]] = \mathrm{Tr}[\tau \iota(Q)[\rho]] \quad \text{for any } Q \in P(S). \qquad (18) $$

We consider then the set of restricted measurements to be $P(S)$, which is independent of $\mathcal{H}$, and define the restricted optimization problem as the maximization

$$ \max_{Q \in P(S)} \mathrm{Tr}[\tau Q[\rho]]. \qquad (19) $$

## 3 Suboptimality ratio of projective measurements

On the Hilbert space $\mathcal{H}$ with $\dim(\mathcal{H}) = n$, the suboptimality ratio $K_{n,r}$ is defined as the smallest constant such that for any $\rho$, and $\tau$ supported on the subspace $S \subset \mathcal{H}$ of fixed dimension $r \le n$, we have

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \mathrm{Tr}[\tau \mathcal{P}[\rho]] \le K_{n,r} \max_{Q \in P(S)} \mathrm{Tr}[\tau Q[\rho]]. \qquad (20) $$

The constant $K_{n,r} \ge 1$ encodes how suboptimal restricted measurements are when there is an aligned low-rank structure present in the quantum states compared to using a larger set of PMs.

Our main result in Theorem 1 bounds the suboptimality ratio $K_{n,r}$ when the quantum states $\tau$, and $\rho$ are supported in $S$, and the measurements are also restricted to this subspace. Its proof can be found in Section 4.

**Theorem 1.** Let $\mathcal{H}$ be a complex Hilbert space with $\dim(\mathcal{H}) = n$, and let $S \subset \mathcal{H}$ be a Hilbert subspace with $\dim(S) = r \le n$. There exists $c > 0$ such that for any $n \ge r \ge 2$, and any $\rho$, $\tau \in D(S)$,

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \mathrm{Tr}[\tau \mathcal{P}[\rho]] \le c \log(r)^4 \max_{Q \in P(S)} \mathrm{Tr}[\tau Q[\rho]]. \qquad (21) $$
From Theorem 1, we obtain that the bound of $K_{n,r}$ is independent of the dimension of the ambient Hilbert space $\mathcal{H}$, and at most polylogarithmic in the dimension of the subspace $\mathcal{S}$. By choosing restricted measurements in $\mathcal{S}$, we lose at most a polylogarithmic factor in (20). Remarkably, as can be seen in the proof of Theorem 1, the polylogarithmic dependence in the bound of $K_{n,r}$ arises from a connection to random matrix theory. Specifically, in random matrix concentration results there is typically an additional dimensional factor—the matrix size $r$—that appears compared to their counterparts in univariate concentration inequalities. In our case, this factor determines the logarithmic dependence and is a consequence of our probabilistic approach to showing the result; see Remark 3 in Section 4.4.

For the Procrustes problem in (1) we can approximate the optimum by restricting to the subspace $\mathcal{S}$. Theorem 1, and (14) immediately yield a rough approximation inequality in Corollary 1.

**Corollary 1.** Suppose $\tau, \rho \in D(\mathcal{S}) \subset D(\mathcal{H})$, where $\mathcal{S} \subset \mathcal{H}$ is a $r$-dimensional subspace of $\mathcal{H}$. Then, there exists a universal constant $c > 0$ such that

$$ \min_{Q \in P(\mathcal{S})} \mathbb{E}_{X \sim \mu(\rho, \mathcal{Q})} \left[ \|\tau - X\|_{\text{F}}^2 \right] - (c \log(r)^4 - 1) \text{Tr}[\tau \mathcal{Q}[\rho]] \le \min_{P \in P(\mathcal{H})} \mathbb{E}_{X \sim \mu(\rho, P)} \left[ \|\tau - X\|_{\text{F}}^2 \right]. \quad (22) $$

We remark that Corollary 1 is not sharp since the bound of $K_{n,r}$ does not include information about the relationship between absolute values in (20), only their relative values. In particular, there may be cases when the inequality in (22) is trivial since the left-hand side may be negative. This fact raises the question if the bound of $K_{n,r}$ in Theorem 1 can be further improved.

In Section 5, we use numerical simulations to examine the constant $K_{n,r}$ for different values of $r$, and $n$. The simulations suggest that $K_{n,r} \approx 1$ for small values of $r$, but a more complex behavior cannot be ruled out.

# 4 Proof of Theorem 1

We present a sketch of the proof of Theorem 1 in the following steps (i)–(vi), each one corresponding to Sections 4.1–4.6, respectively.

(i) **Reduction to weighted PMs.** In Section 4.1, we fix a PM $\mathcal{P} \in P(\mathcal{H})$ and we examine the effect that the measurement has restricted to the subspace $\mathcal{S}$ where $\rho$ and $\tau$ are supported. We show that the restriction of $\mathcal{P}$ can be decomposed as $T = \lceil n/r \rceil$ ‘weighted’ measurements over $\mathcal{S}$

$$ \mathrm{Tr}[\rho \mathcal{P}[\tau]] = \sum_{i=1}^{T} \mathrm{Tr}[\rho \mathcal{Q}_{L_i^{\pi}}[\tau]]. \quad (23) $$

The matrices $\{L_t^\pi\}_{t=1}^T$ are composed of some equipartition of vectors $|v_i\rangle_i^n$ from a Parseval frame induced by the orthogonal projectors in $\mathcal{P}$. Moreover, the equipartition of the vectors can be chosen with a permutation $\pi$ of their labels.

(ii) **A good partition of Parseval frames exists.** In Section 4.2, we find a partition of the Parseval frame from the previous decomposition such that not only the matrices $\{L_t^\pi\}_{t=1}^T$ satisfy the normalization condition corresponding to frames

$$ \sum_{t=1}^{T} L_t^{\pi} (L_t^{\pi})^{\dagger} = 1_S, \quad (24) $$

but also

$$ \mathcal{L}^{\pi} = \sum_{t=1}^{T} (L_t^{\pi})^{\dagger} L_t^{\pi} \approx 1_S, \quad (25) $$

as much as possible. We use the probabilistic method from combinatorics with $\mathcal{L}^\pi$, and the method of moments from random matrix theory to bound the operator norm $\|\mathcal{L}^\pi\|_{\text{op}} = \sup_{|x|=1} |\mathcal{L}^\pi x|$. We show that there exists a permutation $\pi$ of the vectors, and its corresponding equipartition such that $\|\mathcal{L}^\pi\|_{\text{op}} \le c \log(r)$.
(iii) Randomization. In order to avoid the fact that we have $T = \lceil n/r \rceil$ summands in (23), in Section 4.3 we use a random weight matrix

$$ \hat{L} = \sum_{t=1}^{T} g_t L_t^{\pi}, \qquad (26) $$

with $g_t$ for $t \in [T]$ i.i.d. $N(0, 1)$ Gaussian random variables. Moreover, we show using operator trace inequalities that

$$ \sum_{i=1}^{T} \mathrm{Tr}[\rho Q_{L_i^{\pi}}[\tau]] \le 3\mathbb{E}[\mathrm{Tr}[\rho Q_{\hat{L}}[\tau]]], \qquad (27) $$

where $Q_{\hat{L}}$ is a random measurement on $\mathcal{S}$ weighted by $\hat{L}$.

(iv) Concentration. In Section 4.4 we use well-known concentration inequalities for Gaussian random matrices to show concentration of the operator norm $\|\hat{L}\|_{\mathrm{op}}$. The variance of $\hat{L}$ crucially becomes independent of $n$ due to (24), and (25).

(v) Interpolation. We extract the weights from the weighted measurement $Q_{\hat{L}}$ in (27). Specifically, in Section 4.5 we show by using complex interpolation inequalities that for any weighted measurement $Q_L$ with $L \in B(\mathcal{H})$, there exists $\mathcal{Z} \in P(\mathcal{S})$ such that

$$ \mathrm{Tr}[\rho Q_L[\tau]] \le \|L\|_{\mathrm{op}}^4 \mathrm{Tr}[\rho \mathcal{Z}[\tau]]. \qquad (28) $$

(vi) Combining all steps. Finally, in Section 4.6 the previous interpolation inequality implies that there exists a constant $C > 0$ and $\mathcal{Y} \in P(\mathcal{S})$ such that

$$ \mathbb{E}[\mathrm{Tr}[\rho Q_{\hat{L}}[\tau]]] \le C \mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4] \mathrm{Tr}[\rho \mathcal{Y}[\tau]], \qquad (29) $$

where $\hat{L}$ is the random matrix in (26). A polylogarithmic bound in $r$ for $\mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4]$ is obtained by using the concentration properties from step (iv). Finally, from (23), (27), and (29), the claim of Theorem 1 follows.

## 4.1 Reduction to weighted PMs

We first show that the projections of a fixed measurement $\mathcal{P} \in P(\mathcal{H})$ in (14) to $\mathcal{S}$ is equivalent to a sum over weighted PMs in $P(\mathcal{S})$.

**Definition 2 (Weighted PMs).** Let $Q = (Q_1, \dots, Q_r) \in P(\mathcal{S})$ and $L \in B(\mathcal{S})$. A weighted PM is a map $Q_L : D(\mathcal{S}) \to B(\mathcal{S})$ defined for any $\rho \in D(\mathcal{S})$ as

$$ Q_L[\rho] = \sum_{i=1}^{r} L Q_i L^\dagger \rho L Q_i L^\dagger = L Q[L^\dagger \tau L] L^\dagger. \qquad (30) $$

From Definition 2, given $Q \in P(\mathcal{S})$ and $L \in B(\mathcal{S})$ we can write for $\tau, \rho \in D(\mathcal{H})$

$$ \mathrm{Tr}[\rho Q_L[\tau]] = \mathrm{Tr}[\rho L Q[L^\dagger \tau L] L^\dagger]. \qquad (31) $$

The following lemma poses the optimization problem in (2) as a maximum over a sum of weighted PMs in $\mathcal{S}$ that are dependent. This is a special case of the well-known Naimark dilation theorem.

**Lemma 1.** Let $\mathcal{S} \subseteq \mathcal{H}$ be an inclusion of finite-dimensional Hilbert spaces with $\mathrm{dim}(\mathcal{S}) = r$, and $\mathrm{dim}(\mathcal{H}) = n$. Let $\rho, \tau \in D(\mathcal{S}) \subseteq D(\mathcal{H})$ and $\mathcal{P} \in P(\mathcal{H})$. There exists $Q \in P(\mathcal{S})$, and $L_1, \dots, L_T \in B(\mathcal{S})$ with $T = \lceil n/r \rceil$ such that

$$ \mathrm{Tr}[\rho \mathcal{P}[\tau]] = \sum_{i=1}^{T} \mathrm{Tr}[\rho Q_{L_i}[\tau]], \qquad (32) $$
and

$$ \sum_{t=1}^{T} L_t L_t^{\dagger} = \mathbb{1}_{\mathcal{S}}. \qquad (33) $$

*Proof.* We have $\mathcal{P} = (P_1, \dots, P_n) \in P(\mathcal{H})$ with $P_i = |u_i\rangle\langle u_i|$ for $i \in [n]$, and $\{|u_i\rangle\rangle_{i=1}^n$ is an Orthonormal Basis (ONB) of $\mathcal{H}$. Denote the orthogonal projection from $\mathcal{H}$ to $\mathcal{S}$ by $\Pi_{\mathcal{S}}: \mathcal{H} \to \mathcal{S}$, and define $|v_i\rangle = \Pi_{\mathcal{S}}|u_i\rangle \in \mathcal{S}$ for all $i \in [n]$. By using the fact that (i) $\rho = \Pi_{\mathcal{S}}\rho\Pi_{\mathcal{S}}^{\dagger}$ and similarly for $\tau$, the following equality holds,

$$ \begin{aligned} \mathrm{Tr}[\rho\mathcal{P}[\tau]] &= \sum_{i=1}^{n} \mathrm{Tr}[\rho P_i \tau P_i] \\ &\stackrel{(i)}{=} \sum_{i=1}^{n} \mathrm{Tr}[\rho \Pi_S P_i \Pi_S^{\dagger} \tau \Pi_S P_i \Pi_S^{\dagger}], \\ &= \sum_{i=1}^{n} \mathrm{Tr}[\rho|v_i\rangle\langle v_i|\tau|v_i\rangle\langle v_i|]. \end{aligned} \qquad (34) $$

Out of the $n$ vectors, we consider $T$ disjoint sets of $r$ vectors, where we complete with the null vector if necessary. If $m = \lceil n/r \rceil r$ is the total number of vectors, we may choose the equipartition $\{|v_i\rangle\rangle_{i=1}^r, \{|v_i\rangle\rangle_{i=r+1}^{2r}, \dots, \{|v_i\rangle\rangle_{i=T(r-1)+1}^{Tr}\}$. Let $\{|e_i\rangle\rangle_{i=1}^r$ be a ONB of $\mathcal{S}$ and let $\mathcal{E} = (E_1, \dots, E_r) \in P(\mathcal{S})$ be the PM in this basis, that is, $E_i = |e_i\rangle\langle e_i|$ for $i \in [r]$. We define the operators

$$ L_t = |v_{r(t-1)+1}\rangle\langle e_1| + \dots + |v_{rt}\rangle\langle e_r| = \sum_{l=1}^{r} |v_{r(t-1)+l}\rangle\langle e_l| \in B(\mathcal{S}) \text{ for } t \in [T], \qquad (35) $$

and note that $L_t E_l L_t^{\dagger} = |v_{r(t-1)+l}\rangle\langle v_{r(t-1)+l}|$ for all $l \in [r]$, and $t \in [T]$. In the notation of (31), we have now

$$ \begin{aligned} \sum_{i=1}^{n} \mathrm{Tr}[\rho P_i \tau P_i] &= \sum_{t=1}^{T} \sum_{i=1}^{r} \mathrm{Tr}[\rho L_t E_i L_t^{\dagger} \tau L_t E_i L_t^{\dagger}] \\ &= \sum_{t=1}^{T} \mathrm{Tr}[\rho \mathcal{E}_{L_t}[\tau]]. \end{aligned} \qquad (36) $$

Moreover, from the condition that $\sum_{i=1}^n P_i = \mathbb{1}_{\mathcal{H}}$, and $\sum_{l=1}^r E_l = \mathbb{1}_{\mathcal{S}} = \Pi_{\mathcal{S}}$ we obtain that

$$ \mathbb{1}_{\mathcal{S}} = \Pi_{\mathcal{S}} \mathbb{1}_{\mathcal{H}} \Pi_{\mathcal{S}}^{\dagger} = \sum_{i=1}^{n} \Pi_{\mathcal{S}} P_i \Pi_{\mathcal{S}}^{\dagger} = \sum_{i=1}^{m} |v_i\rangle\langle v_i| = \sum_{t=1}^{T} \sum_{i=1}^{r} L_t E_i L_t^{\dagger} = \sum_{t=1}^{T} L_t L_t^{\dagger}. \qquad (37) $$

□

The vectors $\{|v_i\rangle\rangle_{i=1}^m$ in the proof of Lemma 1 constitute a Parseval frame of $\mathcal{S}$, since

$$ \sum_{i=1}^{m} |v_i\rangle\langle v_i| = \mathbb{1}_{\mathcal{S}}, \qquad (38) $$

which implies that $|v_i| \le 1$, and

$$ \sum_{i=1}^{m} |v_i|^2 = r. \qquad (39) $$

## 4.2 Equipartitions of Parseval frames

In Section 4.1 we have restricted a PM $\mathcal{P} \in P(\mathcal{H})$ to $\mathcal{S}$, and we have shown in Lemma 1 that it is equivalent to a sum over weighted PMs in $\mathcal{S}$. To later introduce randomization in Section 4.3
without adding a large variance, we additionally need the weight matrices to be approximately symmetric. In particular, while we have the partition of unity property in (33), its counterpart

$$ \mathcal{L} = L_1^\dagger L_1 + \dots + L_T^\dagger L_T, \quad \text{where} \\ (\mathcal{L})_{ij} = \sum_{t=1}^T \langle v_{r(t-1)+i} | v_{r(t-1)+j} \rangle \tag{40} $$

can be very far away from the identity $1_S$. To overcome this issue, we will exploit two invariant properties of the decomposition that we have not used in the definition of $\{L_t\}_{t \in [T]}$ and Lemma 1. Without loss of generality, we will assume that $T = n/r \in \mathbb{N}$, since we can always complete the frame with the null vector to satisfy the constraint.

* For any permutation $\pi \in S_n$, we can define similar matrices $\{L_t^\pi\}_{t \in [T]}$ by using the permuted set of vectors $\{|v_{\pi(i)}\rangle\}_{i \in m}$ which satisfy Lemma 1, but do not leave (40) invariant.

* We can add a phase modifier $\Theta = (\theta_1, \dots, \theta_n) \in \mathbb{R}^n$ to the frame $\{|v_i\rangle\}_{i=1}^n$ by defining for $j \in [n]$, $|v_j\rangle(\Theta) = \exp(i\theta_j)|v_j\rangle$ such that Lemma 1 also holds for this frame, but (40) is not invariant.

For a permutation $\pi \in S_n$, and a frame modifier $\Theta = (\theta_1, \dots, \theta_n) \in \mathbb{R}^n$, we define for $t \in [T]$

$$ L_t^\pi(\Theta) = e^{i\theta_{\pi(r(t-1)+1)}} |v_{\pi(r(t-1)+1)}\rangle\langle e_1| + \dots + e^{i\pi(\theta_{r,t})} |v_{\pi(r,t)}\rangle\langle e_r| \in B(S). \tag{41} $$

The matrices $\{L_i^\pi(\Theta)\}_{i=1}^T$ also satisfy Lemma 1 for any $\pi \in S_n$ and $\Theta \in \mathbb{R}^n$. The generalization of (40) for $\pi \in S_n$ and $\Theta \in \mathbb{R}^n$ is then

$$ \mathcal{L}^\pi(\Theta) = L_1^\pi(\Theta)^\dagger L_1(\Theta) + \dots + L_T^\pi(\Theta)^\dagger L_T(\Theta). \tag{42} $$

Our aim is to find $\pi \in S_n$ and $\Theta \in \mathbb{R}^n$ such that $\|\mathcal{L}^\pi(\Theta)\|_{\text{op}}$ is as small as possible. Using the probabilistic method from combinatorics we can show the following.

**Proposition 1.** Let $\mathcal{L}^\pi(\Theta)$ be defined in (42). There exists a constant $c > 0$ such that for any $r \ge 2$ and $T \ge T(r) \ge 1$, there exists a permutation $\pi^* \in S_n$, and a choice of frame modified by $\Theta^* \in \mathbb{R}^n$ such that

$$ \|\mathcal{L}^{\pi^*}(\Theta^*)\|_{\text{op}} < c \log(r). \tag{43} $$

Proposition 1 contains a dimension-dependent term $\log(r)$, which is small enough for our purposes and crucially holds for $T$—that is, for $n$—large enough. To show Proposition 1 we consider the random matrix $\mathcal{L}^\pi(\Theta)$ with a random permutation $\pi \sim \text{Unif}(S_m)$, and a random phase $\exp(i\Theta_i) \sim \text{Unif}(S^1)$ for all $i \in [n]$. The method of moments is used to estimate the operator norm of $\mathcal{L}^\pi(\Theta)$, and is a well-known method in random matrix theory [33]. This typically involves using that for any positive-semidefinite Hermitian matrix $A$, $\|A\|_{\text{op}}^k \le \text{Tr}[A^k]$ for any $k \ge 1$. Therefore, we can compute the expectation of the operator norm by estimating the expected trace

$$ \mathbb{E}[\|\mathcal{L}^\pi(\Theta)\|_{\text{op}}^k] \le \mathbb{E}[\text{Tr}[\mathcal{L}^\pi(\Theta)^k]] = F(k). \tag{44} $$

By showing that $F(k)$ is small enough, from (44) we deduce that for some permutation $\pi \in S_n$, and frame modifier $\Theta$ the operator norm is also small enough. Differently to common results in random matrix theory, the entries of $\mathcal{L}^\pi(\Theta)$ are not independent, but strongly correlated depending on the frame. Nonetheless, we are able to obtain a bound of the operator norm by leveraging the frame properties. The following bound characterizes the expectation (44).

**Lemma 2.** Under the assumptions of Proposition 1, there exists $c > 0$ such that for any $r \ge 2$, $T \ge 2$ and $r \ge k \ge 1$,

$$ F(k) \le c \left( rk^k + \frac{k!k^{2k}r^k}{T} \right). \tag{45} $$
Let us show first that Lemma 2 implies Proposition 1.

*Proof (of Proposition 1).* Fix $k = \lfloor \log(r) \rfloor$, and choose $T = T(r) \ge 1$ large enough such that

$$F(k) \le 2crk^k. \qquad (46)$$

Then, there exists a constants $c_1, C > 0$ such that for all $r \ge 2$,

$$ \begin{aligned} \mathbb{E}[\|\mathcal{L}^{\pi}(\Theta)\|_{\text{op}}] &\le \mathbb{E}[\|\mathcal{L}^{\pi}(\Theta)\|_{\text{op}}^k]^{1/k} \\ &\le F(k)^{1/k} \\ &\le c_1^{1/\log(r)} r^{1/\log(r)} \log(r) \\ &\le C \log(r). \end{aligned} \qquad (47) $$

From (47), we deduce that there exists a permutation $\pi^*$ and frame modifier $\Theta^*$ such that

$$\|\mathcal{L}^{\pi^*}(\Theta^*)\|_{\text{op}} \le C \log(r). \qquad (48)$$

□

The proof of Lemma 2 is involved, and is deferred to Appendix A. The intuition behind the proof is that the correlations that the different vectors $|v_i\rangle$ of the frame may have—encoded in the inner products $\langle v_i|v_j\rangle$—either are small when $T$ is large, or they are concentrated in a handful of vectors. In the former case, for a random permutation and frame modifier, the matrix $\mathcal{L}^{\pi}(\Theta)$ will be approximately homogeneous and thus have operator norm of order $O(1)$. In the latter case, most permutations will ‘separate’ the significant vectors well so that we will only need to worry about the diagonal of $\mathcal{L}^{\pi}(\Theta)$. We can then estimate the expectation of the operator norm when significant vectors add up in the diagonal entries. This is quantified by the leading term in (45). It also turns out that when there are only significant vectors (when $L_1 = 1_S$, for example), the order of (48) is almost sharp. Specifically, the expected operator norm in this case is the expected maximum of a multinomial random variable with uniform probability $(1/r, \dots, 1/r)$ and with $r$ trials, which has order $\log(r)/\log(\log(r))$ [28].

In (47) the choice of $k \approx \log(r)$ is optimal, since for larger or smaller order of $k$, we would obtain a worse bound on $F(k)$.

## 4.3 Randomization

We assume for the time being that $T$ is large enough so that by Proposition 1 we can choose the equipartition of the frame induced by $\mathcal{P}$ in Lemma 1 that satisfies both (33) and

$$\|L_1^\dagger L_1 + \dots + L_T^\dagger L_T\|_{\text{op}} \le c \log(r). \qquad (49)$$

We namely omit in the notation the selected permutation $\pi^*$ and phase $\Theta^*$ that Proposition 1 guarantees, that is, we will denote $L_t = L_t^*(\Theta^*)$ for all $t \in [T]$. Later on in Section 4.6, we will show that we by enlarging the Hilbert space $\mathcal{H}$, the assumption that $T$ is large enough will become superfluous.

Let $g_t$ for $t \in [T]$ be i.i.d. $N(0, 1)$ random variables. Define the operator-valued random variable

$$\hat{L} = \sum_{t=1}^{T} g_t L_t. \qquad (50)$$

By using this random matrix as a weight, we can decouple the dimension $T$ from the sum of $T$ weighted measurments in Lemma 1, and transfer its dependence to the variance of $\hat{L}$.

**Lemma 3.** In the same setting of Lemma 1, let $\hat{L}$ be defined in (50), and let $Q \in P(S)$, then

$$\sum_{t=1}^{T} \mathrm{Tr}[\rho Q_{L_t}[\tau]] \le 3\mathbb{E}[\mathrm{Tr}[\rho Q_{\hat{L}}[\tau]]]. \qquad (51)$$
Before showing Lemma 3 at the end of this section, we require some intermediate results first. First, we find a proxy that in expectation bounds the sum of the weighted PM on the left side of (51). Let $\hat{B}$ be an independent copy of $\hat{L}$, and $Q \in P(S)$. We denote by $Q_{\hat{L},\hat{B}}$ the random biweighted measurement that satisfies

$$ 
\begin{align} 
\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]] &= \sum_{i=1}^{r} \mathrm{Tr}[\rho \hat{L} Q_i \hat{L}^{\dagger}] \mathrm{Tr}[\tau \hat{B} Q_i \hat{B}^{\dagger}] \nonumber \\
&= \sum_{i=1}^{r} \mathrm{Tr}[\rho \hat{L} Q_i \hat{L}^{\dagger} \otimes \tau \hat{B} Q_i \hat{B}^{\dagger}] \nonumber \\
&= \sum_{i=1}^{r} \mathrm{Tr}[(\rho \otimes \tau)(\hat{L} \otimes \hat{B})(Q_i \otimes Q_i)(\hat{L}^{\dagger} \otimes \hat{B}^{\dagger})]. \tag{52}
\end{align} 
$$

Note that we also have $\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]] \ge 0$.

**Lemma 4.** Let $\rho, \tau \in D(S)$, $Q \in P(S)$, and $\{L_t\}_{t \in [T]}$ be weight matrices. Let $\hat{L}, \hat{B}$ be independent copies of (50). Then,

$$ \sum_{t=1}^{T} \mathrm{Tr}[\rho Q_{L_t}[\tau]] \le \mathbb{E}[\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]] \quad (53) $$

*Proof.* From the fact that $\hat{L}$ and $\hat{B}$ are independent, we readily obtain from (52) that

$$ 
\begin{align} 
\mathbb{E}[\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]] &= \sum_{i=1}^{r} \mathbb{E}[\mathrm{Tr}[(\rho \otimes \tau)(\hat{L} \otimes \hat{B})(Q_i \otimes Q_i)(\hat{L}^{\dagger} \otimes \hat{B}^{\dagger})]] \nonumber \\
&= \sum_{i=1}^{r} \sum_{t,z=1}^{T} \mathrm{Tr}[(\rho \otimes \tau)(L_t \otimes L_z)(Q_i \otimes Q_i)(L_t^{\dagger} \otimes L_z^{\dagger})] \nonumber \\
&= \sum_{t,z=1}^{T} \sum_{l=1}^{r} \mathrm{Tr}[(\rho \otimes \tau)(L_t \otimes L_z)(Q_i \otimes Q_i)(L_t^{\dagger} \otimes L_z^{\dagger})] \nonumber \\
&\ge \sum_{t=1}^{T} \sum_{l=1}^{r} \mathrm{Tr}[(\rho \otimes \tau)(L_t \otimes L_z)(Q_i \otimes Q_i)(L_t^{\dagger} \otimes L_z^{\dagger})] \quad \text{(all terms positive)} \nonumber \\
&= \sum_{t=1}^{T} \sum_{l=1}^{r} \mathrm{Tr}[\rho L_t Q_i L_t^{\dagger} \tau L_t Q_i L_t^{\dagger}] \quad \{\{Q_i\}_{i=1}^r \text{ are rank one projectors}\} \nonumber \\
&= \sum_{t=1}^{T} \mathrm{Tr}[\rho Q_{L_t}[\tau]]. \tag{54}
\end{align} 
$$

□

The biweighted measurement $Q_{\hat{L},\hat{B}}$ in (52) does not have the single weighted measurement structure that we need. To overcome this problem we use the following two results based on trace convexity to upper bound $\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]$ by several weighted measurements.

**Lemma 5.** (Adapted from [23, Corollary 1.1]). Let $A, B \in B_{\ge}^{\mathrm{sa}}(S)$ and let $G_1, G_2 \in B(S)$. For any $\lambda \in [0, 1]$, let

$$ G = \lambda G_1 + (1 - \lambda) G_2. \quad (55) $$

The following inequality holds

$$ \mathrm{Tr}[A G B G^{\dagger}] \le \lambda \mathrm{Tr}[A G_1 B G_1^{\dagger}] + (1 - \lambda) \mathrm{Tr}[A G_2 B G_2^{\dagger}]. \quad (56) $$
For the following result we require some additional notation. For any $J \in B(\mathcal{S})$, and $M \in B^{\text{sa}}(\mathcal{S} \otimes \mathcal{S})$, we let

$$ \mathrm{Ad}_J[M] = (J \otimes J) M (J \otimes J)^{\dagger}. \qquad (57) $$

We define the set of separable operators of $B_{\ge}^{\text{sa}}(\mathcal{S} \otimes \mathcal{S})$ as

$$ \mathrm{Sep}(B_{\ge}^{\text{sa}}(\mathcal{S} \otimes \mathcal{S})) = \left\{ \sum_{i=1}^{a} \lambda_i A_1^i \otimes A_2^i \middle| a \in \mathbb{N}, A_1^i, A_2^i \in B_{\ge}^{\text{sa}}(\mathcal{S}), \text{ and } \lambda_i \ge 0 \text{ for all } i \in [a] \right\}. \quad (58) $$

**Lemma 6.** Let $C, D \in \mathrm{Sep}(B_{\ge}^{\text{sa}}(\mathcal{S} \otimes \mathcal{S}))$ and $X, Y \in B(\mathcal{S})$, then in the notation of (57),

$$ \mathrm{Tr}[C(X \otimes Y)D(X \otimes Y)^{\dagger}] + \mathrm{Tr}[C(Y \otimes X)D(Y \otimes X)^{\dagger}] \le \frac{1}{2} \left( \mathrm{Tr}[C\mathrm{Ad}_{X+Y}[D]] + \mathrm{Tr}[C\mathrm{Ad}_{X-Y}[D]] \right) + \mathrm{Tr}[C\mathrm{Ad}_X[D]] + \mathrm{Tr}[C\mathrm{Ad}_Y[D]]. \quad (59) $$

*Proof.* We will first change variables. Define

$$ \mathcal{M}_+ = X \otimes Y + Y \otimes X. \qquad (60) $$

We can check that expanding the terms of $\mathcal{M}_+$ gives the following identity

$$ \begin{aligned} \mathrm{Tr}[C(X \otimes Y)D(X \otimes Y)^{\dagger}] + \mathrm{Tr}[C(Y \otimes X)D(Y \otimes X)^{\dagger}] &= \mathrm{Tr}[C\mathcal{M}_+D\mathcal{M}_+^{\dagger}] \\ &\quad - \mathrm{Tr}[C(X \otimes Y)D(Y \otimes X)^{\dagger}] - \mathrm{Tr}[C(Y \otimes X)D(X \otimes Y)^{\dagger}] \\ &\le \mathrm{Tr}[C\mathcal{M}_+D\mathcal{M}_+^{\dagger}] + |\mathrm{Tr}[C(X \otimes Y)D(Y \otimes X)^{\dagger}]| + |\mathrm{Tr}[C(Y \otimes X)D(X \otimes Y)^{\dagger}]|. \end{aligned} \quad (61) $$

We examine the term involving $\mathcal{M}_+$ in (61) closely. Note the identity

$$ \begin{aligned} \mathcal{M}_+ &= \frac{1}{2} \left( (X + Y) \otimes (X + Y) - (X - Y) \otimes (X - Y) \right) \\ &= \frac{1}{2} \left( (X + Y) \otimes (X + Y) + i(X - Y) \otimes i(X - Y) \right), \end{aligned} \quad (62) $$

We can use the trace convexity of Lemma 5 with the identity (62) of $\mathcal{M}_+$. Trace convexity yields the following inequality

$$ \mathrm{Tr}[C\mathcal{M}_+D\mathcal{M}_+^{\dagger}] \le \frac{1}{2} \left( \mathrm{Tr}[C\mathrm{Ad}_{X+Y}[D]] + \mathrm{Tr}[C\mathrm{Ad}_{X-Y}[D]] \right). \quad (63) $$

We bound the remaining terms of (61). We assume for the time being that $C$, and $D$ are elementary tensors, that is, $C = C_1 \otimes C_2$, and $D = D_1 \otimes D_2$, where $C_1, C_2, D_1, D_2 \in B_{\ge}^{\text{sa}}(\mathcal{S})$. We will use (i) Cauchy-Schwartz inequality in $\mathrm{Tr}[C_1XD_1Y^{\dagger}] = \mathrm{Tr}[(C_1^{1/2}XD_1^{1/2})(C_1^{1/2}YD_1^{1/2})^{\dagger}]$, and similarly with $\mathrm{Tr}[C_2YD_2X^{\dagger}]$. The inequality reads

$$ \begin{aligned} |\mathrm{Tr}[C(X \otimes Y)D(Y \otimes X)^{\dagger}]| &= |\mathrm{Tr}[C_1XD_1Y^{\dagger}]\mathrm{Tr}[C_2YD_2X^{\dagger}]| \\ &\stackrel{(i)}{\le} \mathrm{Tr}[C_1XD_1X^{\dagger}]^{\frac{1}{2}}\mathrm{Tr}[C_1YD_1Y^{\dagger}]^{\frac{1}{2}}\mathrm{Tr}[C_2XD_2X^{\dagger}]^{\frac{1}{2}}\mathrm{Tr}[C_2YD_2Y^{\dagger}]^{\frac{1}{2}} \\ &= \mathrm{Tr}[C(X \otimes X)D(X \otimes X)^{\dagger}]^{\frac{1}{2}}\mathrm{Tr}[C(Y \otimes Y)D(Y \otimes Y)^{\dagger}]^{\frac{1}{2}} \\ &= \mathrm{Tr}[C\mathrm{Ad}_X[D]]^{\frac{1}{2}}\mathrm{Tr}[C\mathrm{Ad}_Y[D]]^{\frac{1}{2}}. \end{aligned} \quad (64) $$

We similarly obtain (64) for the remaining term in (61). In particular, we have

$$ \begin{aligned} |\mathrm{Tr}[C(X \otimes Y)D(Y \otimes X)^{\dagger}]| + |\mathrm{Tr}[C(Y \otimes X)D(Y \otimes X)^{\dagger}]| &\le 2\mathrm{Tr}[C\mathrm{Ad}_X[D]]^{\frac{1}{2}}\mathrm{Tr}[C\mathrm{Ad}_Y[D]]^{\frac{1}{2}} \\ &\le \mathrm{Tr}[C\mathrm{Ad}_X[D]] + \mathrm{Tr}[C\mathrm{Ad}_Y[D]]. \end{aligned} \quad (65) $$

Finally, we can substitute the bounds of (63) and (65) into (61) to show the result in the case that $C$, and $D$ are elementary tensors. To extend the result to all $C, D \in \mathrm{Sep}(B_{\ge}^{\text{sa}}(\mathcal{S} \otimes \mathcal{S}))$, note that if $C$ is separable, we can decompose $C = \sum_{i=1}^a \lambda_i C_1^i \otimes C_2^i$ with $C_j \in B_{\ge}^{\text{sa}}(\mathcal{S})$ for $j \in [2]$, and $\lambda_i \ge 0$ for $i \in [a]$. We can do a similar decomposition with $D$. Now, from the bilinearity of both sides of the inequality (59) with respect to $C$, and $D$, we can extend (59) to all positive linear combinations of tensors in $B_{\ge}^{\text{sa}}(\mathcal{S}) \otimes B_{\ge}^{\text{sa}}(\mathcal{S})$. $\square$
We are now in position to show Lemma 3.

*Proof (of Lemma 3).* From Lemma 4, we have the inequality

$$ \sum_{t=1}^{T} \mathrm{Tr}[\rho Q_{L_t}[\tau]] \leq \mathbb{E}[\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]]. \quad (66) $$

We symmetrize the expectation in (66) noting that since $\hat{L}$ and $\hat{B}$ are identically and independently distributed we have

$$ \begin{aligned} \mathbb{E}[\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]] &= \frac{1}{2}\mathbb{E}[\mathrm{Tr}[Q_{\hat{L},\hat{B}}[\rho, \tau]]] + \frac{1}{2}\mathbb{E}[\mathrm{Tr}[Q_{\hat{B},\hat{L}}[\rho, \tau]]] \\ &= \frac{1}{2}\sum_{i=1}^{r}\mathbb{E}[\mathrm{Tr}[(\rho \otimes \tau)(\hat{L} \otimes \hat{B})(Q_i \otimes Q_i)(\hat{L}^{\dagger} \otimes \hat{B}^{\dagger})] \\ &\quad + \mathrm{Tr}[(\rho \otimes \tau)(\hat{B} \otimes \hat{L})(Q_i \otimes Q_i)(\hat{B}^{\dagger} \otimes \hat{L}^{\dagger})]] \end{aligned} \quad (67) $$

We use now Lemma 6 for each pair of summands in the expectation of (67). We obtain

$$ \begin{aligned} (67) \leq & \sum_{i=1}^{r} \frac{1}{4} \mathbb{E} \left( \mathrm{Tr}[(\rho \otimes \tau) \mathrm{Ad}_{\hat{L}+\hat{B}}[Q_i \otimes Q_i]] + \mathrm{Tr}[(\rho \otimes \tau) \mathrm{Ad}_{\hat{L}-\hat{B}}[Q_i \otimes Q_i]] \right) \\ & + \frac{1}{2} \mathbb{E} \left( \mathrm{Tr}[(\rho \otimes \tau) \mathrm{Ad}_{\hat{L}}[Q_i \otimes Q_i]] \right) + \frac{1}{2} \mathbb{E} \left( \mathrm{Tr}[(\rho \otimes \tau) \mathrm{Ad}_{\hat{B}}[Q_i \otimes Q_i]] \right) \\ = & \frac{1}{4} \mathbb{E} \left( \mathrm{Tr}[\rho Q_{\hat{L}+\hat{B}}[\tau]] + \mathrm{Tr}[\rho Q_{\hat{L}-\hat{B}}[\tau]] \right) + \mathbb{E} \left( \mathrm{Tr}[\rho Q_{\hat{L}}[\tau]] \right). \quad (\hat{B} \text{ distributed like } \hat{L}) \end{aligned} $$

From independence and since $\hat{L}$, and $\hat{B}$ have identical symmetric Gaussian distributions, $\hat{L} + \hat{B}$ possesses the same distribution as $\hat{L} - \hat{B}$. Moreover, from its definition in (50), $\hat{L} + \hat{B}$ is a sum of i.i.d. centered Gaussian random matrices with double the variance than $\hat{L}$, that is, $\hat{L} + \hat{B}$ will have the same distribution as $\sqrt{2}\hat{L}$. Using these identities we can write

$$ \begin{aligned} \frac{1}{4} \mathbb{E} \left( \mathrm{Tr}[\rho Q_{\hat{L}+\hat{B}}[\tau]] + \mathrm{Tr}[\rho Q_{\hat{L}-\hat{B}}[\tau]] \right) &= \frac{1}{2} \mathbb{E} \left( \mathrm{Tr}[\rho Q_{\sqrt{2}\hat{L}}[\tau]] \right) \\ &= 2 \mathbb{E} \left( \mathrm{Tr}[\rho Q_{\hat{L}}[\tau]] \right) \end{aligned} \quad (68) $$

Together with the previous inequality, this last bound completes the proof. $\square$

In (51), we have randomized the weighted measurements with $\hat{L}$, and $\hat{B}$, but we are still left with weighted measurements that cannot be directly compared with PMs. Later in Section 4.5, we show that traces of weighted measurements are upper bounded by traces of PM up to a factor depending on the weights.

## 4.4 Concentration

In the previous section, we have decoupled the dimension $n$ in the number of summands in the decomposition by weighted PM in (23). However, the dependence may still be present in the form of large variance of $\hat{L}$. A key value that characterizes how large $\hat{L}$ can be is its operator norm $\|\hat{L}\|_{\mathrm{op}}$. The order of an operator norm of a random matrix has been thoroughly studied for independent series of Gaussian random matrices [34, 33], which is our case.

We will use the following result that relates the magnitude of the operator norm to that of its expected variance.

**Lemma 7.** (Adapted from [34, Theorem 4.1.1])

Let $B = \{B_1, \dots, B_T\}$ be complex matrices of dimension $r$ and define the variance statistic by

$$ \nu(B) = \max \left( \left\| \sum_{t=1}^{T} B_t B_t^\dagger \right\|_{\mathrm{op}}, \left\| \sum_{t=1}^{T} B_t^\dagger B_t \right\|_{\mathrm{op}} \right). \quad (69) $$
Let $g_1, \dots, g_T$ be i.i.d. real $N(0, 1)$ random variables. Then for any $l > 0$, we have

$$ \mathbb{P}\left[\left\|\sum_{t=1}^{T} g_t B_t\right\|_{\text{op}} > l\right] \le 2r \exp\left(-\frac{l^2}{\nu(B)}\right). \qquad (70) $$

Recall that we assume for the time being that $T$ is large enough so that $\mathcal{L} = L_1^\dagger L_1 + \dots + L_T^\dagger L_T$ satisfies Proposition 1. Together with (33), the variance statistic satisfies for some $c > 0$

$$ \begin{aligned} \nu(\{L_t\}_{t=1}^T) &= \max(\|1_S\|_{\text{op}}, \|\mathcal{L}\|_{\text{op}}) \\ &= \max(1, c \log(r)). \end{aligned} \qquad (71) $$

Using Lemma 7, we directly obtain a bound on the operator norm of $\hat{L}$.

**Lemma 8.** Suppose $r \ge 2$ and let $\hat{L}$ be defined in (50) with weight matrices $\{L_t\}_{t=1}^T$ that satisfy Proposition 1. There exists $c > 0$ such that if $l \ge 0$, with probability at least $1-2r \exp(-l^2/(c \log(r)))$,

$$ \|\hat{L}\|_{\text{op}} \le l. \qquad (72) $$

The following moment estimate will be used later on and is key in determining $K_{n,r}$.

**Corollary 2.** In the same setting as Lemma 8, if the weight matrices $\{L_t\}_{t=1}^T$ satisfy Proposition 1 there exists $c > 0$ such that

$$ \mathbb{E}[\|\hat{L}\|_{\text{op}}^4] \le c \log(r)^4. \qquad (73) $$

*Proof.* By Fubini's theorem for the expectation of a positive random variable $X$, we have the identity

$$ \mathbb{E}[X^4] = \int_0^\infty \mathbb{P}[X > s] 4s^3 ds. \qquad (74) $$

From Lemma 8, for $r \ge 2$ we also have the bound

$$ \mathbb{P}[\|\hat{L}\|_{\text{op}} > s] \le \min\left(1, 2r \exp\left(-\frac{s^2}{c \log(r)}\right)\right). \qquad (75) $$

The value 1 is attained by the second factor of (75) at $l^*$, with $c_1 \log(r) \le l^* \le c_2 \log(r)$ for some $c_1, c_2 > 0$. Hence, using (74) with the bound (75) yields

$$ \begin{aligned} \mathbb{E}[\|\hat{L}\|_{\text{op}}^4] &\le \int_0^{l^*} 4s^3 ds + \int_{l^*}^{\infty} 8r \exp\left(-\frac{s^2}{c \log(r)}\right) s^3 ds \\ &\le (c_2)^4 \log(r)^4 + 8r \int_{c_1 \log(r)}^{\infty} \exp\left(-\frac{s^2}{c \log(r)}\right) s^3 ds. \end{aligned} \qquad (76) $$

We can compute the last term in (76) by using the change of variables $s^2 = c \log(r)y$,

$$ \begin{aligned} \int_{c_1 \log(r)}^{\infty} \exp\left(-\frac{s^2}{c \log(r)}\right) s^3 ds &= c_4 \log(r)^2 \int_{c_3 \log(r)}^{\infty} \exp(-y) y dy \\ &= c_4 \log(r)^2 \left(-\exp(-y) - \exp(-y)\right) \Big|_{c_3 \log(r)}^{\infty} \\ &\le c_5 \frac{\log(r)^3}{r}, \end{aligned} \qquad (77) $$

for some constants $c_3, c_4, c_5 > 0$ independent of $r \ge 2$. Finally, substitute (77) in (76). $\square$
**Remark 3.** We note that the bound in Proposition 1 is sufficient to obtain a polylogarithmic bound on the expected value of $||\hat{L}||_{op}$, which will eventually determine the order of $K_{n,r}$. However, if the logarithmic bound of Proposition 1 can be improved to $||\hat{L}||_{op} = O(1)$, we still have the intrinsic dimensional dependence on $r$ in the the concentration inequality for random matrices; the $r$ factor in Lemma 7. The polylogarithmic terms in the final bound of $K_{n,r}$ are thus unavoidable unless there is an additional low-rank structure of the matrices $\{L_t\}_{t \in [T]}$ that can be exploited. This fact showcases the limits of this approach, as we are not biasing the probability space towards the optimum of (19), e.g., by considering only Parseval frames that have already a certain low-rank structure.

## 4.5 Interpolation bound

In Lemma 3 of Section 4.4, we have upper bounded the sum of $T$ weighted measurements by an expectation over a single random weighted measurement $Q_{\hat{L}}$ that depends on the Gaussian random matrix $\hat{L}$. In this section, we will ‘extract’ the weight $\hat{L}$ of the weighted measurement. Specifically, we will show the following inequality for weighted measurements; recall Definition 2.

**Proposition 2.** Let $\rho, \tau \in D(S)$ be density matrices, $L \in B(S)$, and $Q \in P(S)$ be a PM. There exists $\mathcal{Z} \in P(S)$ such that

$$ \mathrm{Tr}[\rho Q_L[\tau]] \le ||L||_{op}^4 \mathrm{Tr}[\rho \mathcal{Z}[\tau]] \quad (78) $$

Proposition 2 shows that we can upper bound traces of weighted measurements by traces of PMs, and at most a multiplicative factor is added depending only on the weight matrices.

To show Proposition 2, we require two intermediate results. The first lemma shows an integral representation of the conjugation by an operator that has norm less than one.

**Lemma 9.** Let $K \in B^{\mathrm{sa}}(S)$ be such that $||K||_{op} \le 1$ and let $A \in B(S)$. There exists a probability measure $\mu$ over $\mathbb{R}$ and a unitary $D \in U(S)$ such that if $|K| = \sqrt{KK^\dagger}$,

$$ KAK = \int_{\mathbb{R}} |K|^{-it} DAD |K|^{-it} \mu(dt). \quad (79) $$

Moreover, if $K \in B_{\ge}^{\mathrm{sa}}(S)$, then $D = \mathbb{1}_S$.

*Proof.* We assume first that $K \in B_{>}^{\mathrm{sa}}(S)$ so that $K = \sum_{i=1}^r \lambda_i K_i = |K|$, where $1 \ge \lambda_i > 0$ and $K_i$ are rank-one projectors. Let $K^{-it} = \sum_{i=1}^r e^{-ix_i t} K_i$, where $x_i = \log(\lambda_i) \le 0$. We expand the terms $K$ and $K^{-it}$ in both sides of (79) in terms of the projectors $K_i$ and examine at the term in the expansion corresponding to $K_i AK_j$. For (79) to hold, we must namely have the following equality for all $i, j \in [r]$

$$ \lambda_i \lambda_j = \int_{\mathbb{R}} e^{-i(x_i+x_j)t} \mu(dt). \quad (80) $$

Observe that the right-hand side of (80) is the Fourier transform $\hat{\mu}$ of $\mu$ at $x_i + x_j$. The following equality for all $i, j \in [r]$ must then hold.

$$ \lambda_i \lambda_j = \hat{\mu}(x_j + x_i). \quad (81) $$

Since $x_i \le 0$ for all $i \in [r]$, a function $\hat{\mu}$ satisfying (81) is $\hat{\mu}(x) = \exp(-|x|)$. By applying the inverse Fourier transform to the Ansatz for $\hat{\mu}(x)$ yields

$$ \mu(t) = \frac{1}{2\pi} \int_{\mathbb{R}} e^{itx} \hat{\mu}(x) dx = \frac{1}{2\pi} \int_{\mathbb{R}} e^{itx} e^{-|x|} dx = \frac{1}{\pi(1+t^2)}. \quad (82) $$

Moreover, by integrating directly we have $\int_{\mathbb{R}} \mu(t)dt = 1$, so that $\mu$ is also a distribution over $\mathbb{R}$. This shows (79) for the case $K \in B_{>}^{\mathrm{sa}}(S)$.

If $K$ is full rank but possesses negative eigenvalues, we can consider the polar decomposition $K = |K|D$, where $|K| = \sqrt{KK^\dagger} \in B_{>}^{\mathrm{sa}}(S)$ and $D \in U(S)$ is such that $|K|D = K$. The unitary $D$
will encode the signs of the eigenvalues of K, and satisfies D = D†. Apply the same arguments as in the case K ∈ Bsa(S), now using |K|, and DAD instead. After doing so, we also obtain

$$
KAK = \int_{\mathbb{R}} |K|^{-it} DAD |K|^{-it} \mu(dt). \qquad (83)
$$

Finally, if K has null eigenvalues, there exists a sequence of operators Z₁, . . . , Zₗ, . . . ∈ Bsa( S ) such that Zₗ ∈ Bsa( S ), ‖ Zₗ ‖op ≤ 1, ker( Zₗ ) =  , and ‖ Zₗ − K ‖op → 0 as j → ∞ . From the fact that ‖‖ Zₗ |<sup>−it</sup> DAD |Zₗ |<sup>−it</sup> ‖op ≤ ‖ A ‖op for any j ∈ N , the integral in (79) is uniformly bounded. By the dominated convergence theorem, the limit as j → ∞ exists and will be equal to KAK . □

The second lemma we need is a commonly used interpolation result from complex analysis:

**Lemma 10.** (Hadamard Three Lines Theorem, [29, p. 33]) Let Ψ( z ) be a complex-valued function, bounded and continious on the closed strip B = { z ∈ C : 0 ≤ Re( z ) ≤ 1 } , analytic in the interior of B and satisfying

$$
|\Psi(z)| \leq M_0 \quad \text{if} \quad \mathrm{Re}(z) = 0 \tag{84}
$$

$$
|\Psi(z)| \leq M_1 \quad \text{if} \quad \text{Re}(z) = 1. \tag{85}
$$

Then, for z ∈ B , | Ψ( z ) | ≤ M Re( z ) 0 M 1 − Re( z ) .

We are now in position to show the proposition.

Proof (of Proposition 2) . We may assume that L ∈ Bsa( H ) and L is full rank. Indeed, by the polar decomposition, if L ∈ B( S ), there exists U ∈ U( S ) such that L = | L | U . We can then consider the PM ˜ Q = { UQ 1 U † , . . . , UQ$_{r}$U † } ∈ P( S ) that satisfies the equality Tr[ ρQ$_{L}$ ( τ )] = Tr[ ρ ˜ Q$_{|}$$_{L}$ | ( τ )] . Additionally, if L has null eigenvalues, we can use a sequence Z 1 , . . . , Z$_{j}$, · · · ⊂ B( S ) with Z$_{j}$ of full rank for all j ∈ N such that Z$_{j}$ → L in operator norm in a similar manner as used in Lemma 9 to prove the claim. We assume in the rest of the proof that L ∈ Bsa( H ) .

We set ˜ L = L/ ‖ L ‖$_{op}$ , so that ‖ ˜ L ‖$_{op}$ ≤ 1 . Therefore,

$$
\mathrm{Tr}[\rho Q_L[\tau]] = \|L\|_{\mathrm{op}}^4 \mathrm{Tr}[\rho Q_{\tilde{L}}[\tau]]. \quad (86)
$$

We focus on the last term. Define the complex-valued function

$$
\Psi(z) = \sum_{i=1}^{r} \mathrm{Tr} \left[ \rho L^z Q_i \tilde{L}^{2-z} \tau \tilde{L}^z Q_i L^{2-z} \right]. \qquad (87)
$$

Note that since ˜ L is self-adjoint, Ψ(1) = Tr[ ρQ$_{˜}$ $_{L}$( τ )] . The conditions ‖ ˜ L ‖$_{op}$ ≤ 1 and ˜ L ≥ 0 imply that if 0 ≤ Re( z ) ≤ 2 , then ‖ ˜ L $^{z}$‖$_{op}$ ≤ 1 and ‖ ˜ L 2 − z ‖$_{op}$ ≤ 1 . Therefore, the function Ψ is analytic, and also bounded and continuous on the strip S = { z ∈ C : 0 ≤ Re( z ) ≤ 2 } . Define

$$
\begin{align}
M_0 &= \sup_{\mathrm{Re}(z)=0} |\Psi(z)| = \sup_{t \in \mathbb{R}} |\Psi(0 + it)|, \nonumber \\
M_2 &= \sup_{\mathrm{Re}(z)=2} |\Psi(z)| = \sup_{t \in \mathbb{R}} |\Psi(2 + it)|. \tag{88}
\end{align}
$$

By Lemma 10, the upper bound Ψ(1) ≤ max( M 2 , M 0 ) holds.

Without loss of generality, we assume that the maximum is attained at M 2 —the case of M 0 is analogous. For an expression of the supremum M 2 in (88), we can consider the continious map f : R → U( S ) given by f ( t ) = ˜ L $^{it}$, and notice that if ˜ Ψ( t ) = Ψ(2 + it ) , then

$$
\tilde{\Psi}(t) = \sum_{i=1}^{r} \mathrm{Tr} \left[ \rho \tilde{L}^2 f(t) Q_i f(t)^{\dagger} \tau \tilde{L}^2 f(t) Q_i f(t)^{\dagger} \right]. \quad (89)
$$

By compactness of U( S ) , sup$_{t}$$_{∈}$$_{R}$ | ˜ Ψ( t ) | is attained at some unitary U ∈ U( S ) in the closure of Im( f ) , and satisfies

$$
M_2 = \left| \sum_{i=1}^{r} \mathrm{Tr} \left[ \rho \tilde{L}^2 U Q_i U^\dagger \tau \tilde{L}^2 U Q_i U^\dagger \right] \right|. \quad (90)
$$
Let $\tilde{Q} = (UQ_1U^\dagger, \dots, UQ_rU^\dagger) = (\tilde{Q}_1, \dots, \tilde{Q}_r) \in P(S)$. Using the inequality $\Psi(1) \le M_2$, the following holds

$$ \begin{aligned} \mathrm{Tr}[\rho Q_L(\tau)] &\le \left| \sum_{i=1}^r \mathrm{Tr}[\rho \tilde{L}^2 U Q_i U^\dagger \tau \tilde{L}^2 U Q_i U^\dagger] \right| \\ &= \left| \sum_{i=1}^r \mathrm{Tr}[\rho \tilde{L}^2 \tilde{Q}_i \tau \tilde{L}^2 \tilde{Q}_i] \right|. \end{aligned} \quad (91) $$

We are now in position to apply Lemma 9 to (91).

$$ \left| \sum_{i=1}^{r} \mathrm{Tr}[\rho \tilde{L}^2 \tilde{Q}_i \tau \tilde{L}^2 \tilde{Q}_i] \right| = \left| \int_{\mathbb{R}} \sum_{i=1}^{r} \mathrm{Tr}[\rho \tilde{L}^{-2it} \tilde{Q}_i \tau \tilde{L}^{-2it} \tilde{Q}_i] \mu(dt) \right| \quad (\text{Lemma 9}) $$

$$ \le \int_{\mathbb{R}} \left| \sum_{i=1}^{r} \mathrm{Tr}[\rho \tilde{L}^{-2it} \tilde{Q}_i \tau \tilde{L}^{-2it} \tilde{Q}_i] \right| \mu(dt) $$

$$ \le \sup_{t \in \mathbb{R}} \left| \sum_{i=1}^{r} \mathrm{Tr}[\rho \tilde{L}^{-2it} \tilde{Q}_i \tau \tilde{L}^{-2it} \tilde{Q}_i] \right|. \quad (92) $$

By compactness of $U(S)$, the supremum in (92) is attained at some $V \in U(S)$ in the closure of $\{L^{-2it}|t \in \mathbb{R}\}$.

With $V$ at hand, we have a sequence of inequalities that use the following facts: (i) $\tilde{Q}_i$ are rank one for $i \in [r]$, (ii) the Cauchy-Schwartz inequality $|\mathrm{Tr}[AB]| \le \mathrm{Tr}[AA^\dagger]^{1/2}\mathrm{Tr}[BB^\dagger]^{1/2}$ with $A = \rho^{1/2}V\tilde{Q}_i^{1/2}$, $B = \tilde{Q}_i^{1/2}\rho^{1/2}$ for each $i \in [r]$, and also in the case of $\tau$, respectively. Finally we also use (iii) Cauchy-Schwartz inequality for vectors.

$$ \begin{aligned} \left| \sum_{i=1}^{r} \mathrm{Tr}[\rho V \tilde{Q}_i \tau V \tilde{Q}_i] \right| &\le \sum_{i=1}^{r} \left| \mathrm{Tr}[\rho V \tilde{Q}_i \tau V \tilde{Q}_i] \right| \\ &\le \sum_{i=1}^{r} \left| \mathrm{Tr}[\rho V \tilde{Q}_i] \mathrm{Tr}[\tau V \tilde{Q}_i] \right| \end{aligned} \quad (i) $$

$$ \le \sum_{i=1}^{r} \mathrm{Tr}[\rho V \tilde{Q}_i V^\dagger]^{\frac{1}{2}} \mathrm{Tr}[\rho \tilde{Q}_i]^{\frac{1}{2}} \mathrm{Tr}[\tau V \tilde{Q}_i V^\dagger]^{\frac{1}{2}} \mathrm{Tr}[\tau \tilde{Q}_i]^{\frac{1}{2}} \quad (ii) $$

$$ \le \left( \sum_{i=1}^{r} \mathrm{Tr}[\rho V \tilde{Q}_i V^\dagger] \mathrm{Tr}[\tau V \tilde{Q}_i V^\dagger] \right)^{\frac{1}{2}} \left( \sum_{i=1}^{r} \mathrm{Tr}[\rho \tilde{Q}_i] \mathrm{Tr}[\tau \tilde{Q}_i] \right)^{\frac{1}{2}} \quad (iii) $$

$$ \le \left( \mathrm{Tr}[\rho \mathcal{Y}[\tau]] \right)^{\frac{1}{2}} \left( \mathrm{Tr}[\rho \tilde{Q}[\tau]] \right)^{\frac{1}{2}} \quad (i) $$

$$ \le \max \left( \mathrm{Tr}[\rho \mathcal{Y}(\tau)], \mathrm{Tr}[\rho \tilde{Q}(\tau)] \right), \quad (93) $$

where $\mathcal{Y} = (V\tilde{Q}_1V^\dagger, \dots, V\tilde{Q}_rV^\dagger) \in P(S)$. From (86), combining the inequalities in (91), (92), and (93) we conclude that there exists $\mathcal{Z} \in P(S)$ such that

$$ \mathrm{Tr}[\rho Q_L[\tau]] \le \|L\|_{\mathrm{op}}^4 \mathrm{Tr}[\rho \mathcal{Z}[\tau]]. \quad (94) $$

□

**Remark 4.** We note that Proposition 2 can be generalized to measurements other than PMs. Indeed, we have not used the assumption that $Q = (Q_1, \dots, Q_r)$ is a PM, only that each $Q_i$ for $i \in [r]$, is symmetric and rank one. This suggests that we can extend Proposition 2 to symmetric Kraus representations of rank-one POVMs.
## 4.6 Combining all steps

For any $\mathcal{P} \in P(\mathcal{H})$, we use Lemma 1 together with Proposition 2 in Lemma 3, to conclude that the following inequalities hold.

$$ \mathrm{Tr}[\rho\mathcal{P}[\tau]] = \sum_{i=1}^{T} \mathrm{Tr}[\rho Q_{L_i}[\tau]] \quad (\text{Lemma 1}) $$

$$ \leq 3\mathbb{E}[\mathrm{Tr}[\rho Q_{\tilde{L}}[\tau]]] \quad (\text{Lemma 3}) $$

$$ \leq 3\mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4 \mathrm{Tr}[\rho\mathcal{Z}[\tau]]] \quad (\text{Proposition 2}) $$

$$ \leq 3\mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4 \max_{\mathcal{Y} \in P(\mathcal{S})} \mathrm{Tr}[\rho\mathcal{Y}[\tau]]] $$

$$ \leq 3(\mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4]) \max_{\mathcal{Y} \in P(\mathcal{S})} \mathrm{Tr}[\rho\mathcal{Y}[\tau]]. \quad (95) $$

We assume first that $T$—that is, $n$— is large enough so that Proposition 1 holds. Corollary 2 then implies that there exists $c > 0$ such that for $r \geq 2$,

$$ \mathbb{E}[\|\hat{L}\|_{\mathrm{op}}^4] \leq c \log(r)^4. \quad (96) $$

In this case, we can use (96) in (95) to conclude that there exists a constant $c > 0$ such that for any $\mathcal{P} \in P(\mathcal{H})$,

$$ \mathrm{Tr}[\rho\mathcal{P}[\tau]] \leq c \log(r)^4 \max_{\mathcal{Y} \in P(\mathcal{S})} \mathrm{Tr}[\rho\mathcal{Y}[\tau]]. \quad (97) $$

Taking the maximum over $\mathcal{P} \in P(\mathcal{H})$ yields Theorem 1 in the case $n$ is large enough.

If $T$—that is, $n$—is small compared to $r$, and the assumptions of Proposition 1 do not hold, we can still show the result of Theorem 1. Indeed, (97) shows that there exists a constant $C > 0$, and $n(r)$ such that when $n \geq n(r)$

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \mathrm{Tr}[\rho\mathcal{P}[\tau]] \leq C \log(r)^4 \max_{\mathcal{Y} \in P(\mathcal{S})} \mathrm{Tr}[\rho\mathcal{Y}[\tau]]. \quad (98) $$

We need to check that (98) also holds whenever $r \leq n < n(r)$. To do so simply note that we can enlarge the space $\mathcal{H}$ into a larger Hilbert space $\tilde{\mathcal{H}}$ of dimension $n(r) > n$, and consider the same optimization problem in (20) over $P(\tilde{\mathcal{H}})$ instead. In this case, there exists an inclusion $\iota: P(\mathcal{H}) \to P(\tilde{\mathcal{H}})$ that preserves the value of $\mathrm{Tr}[\rho\mathcal{P}[\tau]]$ as shown for the case of $P(\mathcal{S})$ in (18). From this inclusion, we can conclude

$$ \max_{\mathcal{P} \in P(\mathcal{H})} \mathrm{Tr}[\rho\mathcal{P}[\tau]] = \max_{\mathcal{P} \in P(\mathcal{H})} \mathrm{Tr}[\rho\iota(\mathcal{P})[\tau]] \quad (\text{inclusion } \iota: P(\mathcal{H}) \to P(\tilde{\mathcal{H}})) $$

$$ \leq \max_{\tilde{\mathcal{P}} \in P(\tilde{\mathcal{H}})} \mathrm{Tr}[\rho\tilde{\mathcal{P}}[\tau]] $$

$$ \stackrel{(98)}{\leq} C \log(r)^4 \max_{\mathcal{Y} \in P(\mathcal{S})} \mathrm{Tr}[\rho\mathcal{Y}[\tau]]. \quad (99) $$

This last step shows the claim of Theorem 1 for any $n \geq r \geq 2$.

# 5 Numerical experiments

We numerically examine the value of $K_{n,r} = K_r$, defined in (20), and observe its dependency on $r$ for different values. To do so, in dimension $n$, we use the formulation in (15) by setting

$$ S_n(U) = \mathrm{Tr}[\rho\mathcal{E}(U)[\tau]] \quad U \in U(n), \quad (100) $$

where $\mathcal{E}$ is the measurement in the canonical basis of $\mathbb{C}^n$, and $\mathcal{E}(U) = (UE_1U^\dagger, \dots, UE_nU^\dagger)$. For $U \in U(n)$, can then find the gradient of $S_n(U)$ restricted to the tangent space of $U(n)$, by projecting

$$ P_n(U) = \mathrm{Proj}_{T_U U(n)}(\nabla S_n(U)). \quad (101) $$
We refer to Appendix B for additional implementation details such as for (101). The projected gradient ascent on the manifold $U(n)$ is given by initializing $U_0 \in U(n)$, and setting

$$U_{t+1} = \exp_{U_t} (\beta_t P_n(U_t)) \quad \text{for} \quad t \in [t_{\text{max}}], \qquad (102)$$

where $\exp_{U_t}$ is the exponential map $\exp: T_{U_t} U(n) \to U(n)$, and $\beta_t > 0$ is the stepsize. Estimating (102) is computationally expensive so we will use instead the following approximation

$$U_{t+1} = \text{Proj}_{U(n)} (U_t + \beta_t P_n(U_t)U_t) \quad \text{for} \quad t \in [t_{\text{max}}], \qquad (103)$$

where the projection to $U(n)$ is given by the unitary obtained from the polar decomposition.

We will choose $\rho, \tau \in D(S)$ at random, and $U_0 \in U(n)$ such that $U_0|_S \sim \text{Unif}(U(r))$, and $U_0|_{S^\perp} = \mathbb{1}_{S^\perp}$. For optimizing $S_r(V)$ we will use the initialization $V_0 \sim \text{Unif}(U(r))$. After $t_{\text{max}}$ iterations of (103), we denote the empirical estimator of $K_r$ by

$$\hat{K}_r = \frac{\max_{t \in [t_{\text{max}}]} S_n(U_t)}{\max_{t \in [t_{\text{max}}]} S_r(V_t)}. \qquad (104)$$

The estimated values of $\hat{K}_r$ can be found in Figure 1. They seem to suggest $K_r \approx 1$ for $r \le 20$. Note that the estimator can satisfy $\hat{K}_r < 1$, since the optimization problem over $U(n)$ for $n > r$ commonly requires a larger horizon $t_{\text{max}}$, and smaller stepsize to achieve the same suboptimality due to larger dimension. Similarly, the optimization of $S_r(V)$ appears to have saddle points and local maxima that allow for $\hat{K}_r > 1$ to occur when $V_t$ converges to those. Therefore, we cannot rule out that with other initializations—also for $\rho$, and $\tau$—a different behavior of $\hat{K}_r$ may be observed.

<figure><img src="image_2.png" /><figcaption>Figure 1: Evaluation of $\hat{K}_r$ for $2 \le r \le 20$, and $n \in \{r+1, r+2, r+3\}$ by using (104), $t_{\text{max}} = 10^4$, and $\beta_t = 10^{-2}$.</figcaption></figure>

It would be interesting to understand if there is no benefit in using PMs that are not fully aligned with the subspace $S$. In this case, (2) could be solved more efficiently when $\tau$, and $\rho$ have low-rank. In this regard, inspired by previous remarks and numerical results we pose the following conjecture relative to (20).

**Conjecture 5.** There exists $C \ge 1$ such that $K_{n,r} \le C$ for all $n, r \ge 1$.

If Conjecture 5 holds for $C = 1$, it would additionally distance the maximization problems in (20) from those in quantum information that bound maximal correlations of (entangled) quantum states, showcased by, e.g., Grothendieck's inequality [8].
References

[1] P-A. Absil, Robert Mahony, and Rodolphe Sepulchre. *Optimization algorithms on matrix manifolds*. Princeton University Press, 2008.

[2] Noga Alon and Joel H. Spencer. *The probabilistic method*. John Wiley & Sons, 2016.

[3] Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. *Inventiones mathematicae*, 163(3):499–522, 2006.

[4] Mohit Kumar Baghel, Nicolas Gillis, and Punit Sharma. On the non-symmetric semidefinite procrustes problem. *Linear Algebra and its Applications*, 648:133–159, 2022.

[5] Afonso S Bandeira, Christopher Kennedy, and Amit Singer. Approximating the little grothendieck problem over the orthogonal and unitary groups. *Mathematical programming*, 160:433–475, 2016.

[6] Rajendra Bhatia and Marco Congedo. Procrustes problems in riemannian manifolds of positive definite matrices. *Linear Algebra and its Applications*, 563:440–445, 2019.

[7] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti. Optimal quantum tomography. *IEEE Journal of Selected Topics in Quantum Electronics*, 15(6):1646–1660, 2009.

[8] Ron Blei. *The Grothendieck inequality revisited*, volume 232. American Mathematical Society, 2014.

[9] Hans J. Briegel, David E. Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. *Nature Physics*, 5(1):19–26, 2009.

[10] Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. *Theory OF Computing*, 10(4):77–105, 2014.

[11] Anthony Chefles. Quantum state discrimination. *Contemporary Physics*, 41(6):401–424, 2000.

[12] Boris S. Cirel’son. Quantum generalizations of bell’s inequality. *Letters in Mathematical Physics*, 4:93–100, 1980.

[13] Mikael de La Salle. Orthogonalization of positive operator valued measures. *arXiv preprint arXiv:2103.14126*, 2021.

[14] Terézia Fulová and Mária Trnovská. Solving constrained procrustes problems: a conic optimization approach. *arXiv preprint arXiv:2304.14961*, 2023.

[15] Carlos E. González-Guillén, Marius Junge, and Ion Nechita. On the spectral gap of random quantum channels. *arXiv preprint arXiv:1811.08847*, 2018.

[16] John C. Gower and Garmt B. Dijksterhuis. *Procrustes problems*, volume 30. OUP Oxford, 2004.

[17] Matthew B. Hastings. Random unitaries give quantum expanders. *Physical Review A—Atomic, Molecular, and Optical Physics*, 76(3):032315, 2007.

[18] Amir Kalev, Ady Mann, and Michael Revzen. Choice of measurement as the signal. *Physical Review Letters*, 110(26):260502, 2013.

[19] Jean-Louis Krivine. Constantes de grothendieck et fonctions de type positif sur les spheres. *Séminaire Maurey-Schwartz*, pages 1–17, 1978.

[20] Cécilia Lancien. Optimal quantum (tensor product) expanders from unitary designs. *arXiv preprint arXiv:2409.17971*, 2024.

[21] Cécilia Lancien and Andreas Winter. Approximating quantum channels by completely positive maps with small kraus rank. *Quantum*, 8:1320, 2024.
[22] Cécilia Lancien, Patrick Oliveira Santos, and Pierre Youssef. Limiting spectral distribution of random self-adjoint quantum channels. *Mathematical Physics, Analysis and Geometry*, 27(3): 15, 2024.

[23] Elliott H. Lieb. Convex trace functions and the wigner-yanase-dyson conjecture. *Les rencontres physiciens-mathématiciens de Strasbourg-RCP25*, 19:0-35, 1973.

[24] Bin Liu, Fei Gao, Su-Juan Qin, Wei Huang, Feng Liu, and Qiao-Yan Wen. Choice of measurement as the secret. *Physical Review A*, 89(4):042318, 2014.

[25] Michał Oszmaniec, Filip B. Maciejewski, and Zbigniew Puchała. Simulating all quantum measurements using only projective measurements and postselection. *Physical Review A*, 100 (1):012351, 2019.

[26] Alexander Pechen, Nikolai Il'in, Feng Shuang, and Herschel Rabitz. Quantum control by von neumann measurements. *Physical Review A*, 74(5):052102, 2006.

[27] Alexander Pechen, Dmitrii Prokhorenko, Rebing Wu, and Herschel Rabitz. Control landscapes for two-level open quantum systems. *Journal of Physics A: Mathematical and Theoretical*, 41 (4):045205, 2008.

[28] Martin Raab and Angelika Steger. “Balls into bins”—a simple and tight analysis. In *International Workshop on Randomization and Approximation Techniques in Computer Science*, pages 159–170. Springer, 1998.

[29] Michael Reed and Barry Simon. *II: Fourier Analysis, Self-Adjointness*, volume 2. Elsevier, 1975.

[30] Peter H. Schönemann. A generalized solution of the orthogonal procrustes problem. *Psychometrika*, 31(1):1–10, 1966.

[31] Richard P. Stanley. Enumerative combinatorics volume 1 second edition. *Cambridge studies in advanced mathematics*, 2011.

[32] David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace inequalities. *Communications in Mathematical Physics*, 352:37–58, 2017.

[33] Terence Tao. *Topics in random matrix theory*, volume 132. American Mathematical Soc., 2012.

[34] Joel A. Tropp et al. An introduction to matrix concentration inequalities. *Foundations and Trends® in Machine Learning*, 8(1-2):1–230, 2015.

[35] Shayne F.D. Waldron. *An introduction to finite tight frames*. Springer, 2018.

[36] Yaoxiong Wang, Rebing Wu, Xin Chen, Yunjian Ge, Junhui Shi, Herschel Rabitz, and Feng Shuang. Quantum state transformation by optimal projective measurements. *Journal of mathematical chemistry*, 49:507–519, 2011.

[37] Joong-Ho Won, Hua Zhou, and Kenneth L. Lange. Orthogonal trace-sum maximization: Applications, local algorithms, and global optimality. *SIAM journal on matrix analysis and applications: a publication of the Society for Industrial and Applied Mathematics*, 42 2:859–882, 2018.

A Proof of Lemma 2

The proof of Lemma 2 consists of tracking and estimating the moments of the matrix $L^\pi(\Theta)$. In Appendix A.1, we introduce the problem and the objects that will help with counting, such as cycles, and factors. In Appendix A.2 we estimate the chance that certain factors appear in the expansion, and how they depend on $T$. Next in Appendix A.3 we characterize symmetries in the expansion of $F(k)$ that will simplify the counting later on. In Appendix A.4, we bound some of the products in $F(k)$, and finally in Appendix A.5 we use all previous work to estimate the asymptotic expansion as $T$ becomes large; see Lemma 18.
## A.1 Preliminaries

For simplicity we will assume that there are $m = Tr \ge n$ frame vectors exactly—we complete with the null vector, if necessary. Recall (42), and define for all $t \in [T]$, and $i, j \in [r]$,

$$ 
\begin{aligned}
\mathcal{L}_t^\pi(\Theta) &= L_t^\pi(\Theta)^\dagger L_t^\pi(\Theta) \quad \text{and} \\
(\mathcal{L}_t^\pi(\Theta))_{ij} &= \langle v_{\pi(r(t-1)+i)}(\Theta) | v_{\pi(r(t-1)+j)}(\Theta) \rangle \\
&= \exp(i\theta_{\pi(r(t-1)+j)} - i\theta_{\pi(r(t-1)+i)}) \langle v_{\pi(r(t-1)+i)} | v_{\pi(r(t-1)+j)} \rangle. \quad (105)
\end{aligned}
$$

In this notation, we have

$$ 
\begin{aligned}
\mathcal{L}^{\pi}(\Theta) &= \sum_{t=1}^{T} \mathcal{L}_{t}^{\pi}(\Theta), \quad \text{and} \\
(\mathcal{L}^{\pi}(\Theta))_{ij} &= \sum_{t=1}^{T} \langle v_{\pi(r(t-1)+i)}(\Theta) | v_{\pi(r(t-1)+j)}(\Theta) \rangle \\
&= \sum_{t=1}^{T} \exp(i(\theta_{\pi(r(t-1)+j)} - \theta_{\pi(r(t-1)+i)})) \langle v_{\pi(r(t-1)+i)} | v_{\pi(r(t-1)+j)} \rangle \quad (106)
\end{aligned}
$$

Recall that

$$ F(k) = \mathbb{E}_{\pi, \Theta} \left[ \mathrm{Tr} \left[ \mathcal{L}^{\pi}(\Theta)^{k} \right] \right]. \quad (107) $$

For a fixed $t \in [T]$, consider one of the factors appearing in the expansion of $\mathrm{Tr}[\mathcal{L}^{\pi}(\Theta)^k]$, say

$$ \langle v_{\pi(i_1)}(\Theta) | v_{\pi(i_2)}(\Theta) \rangle \cdots \langle v_{\pi(i_k)}(\Theta) | v_{\pi(i_{k+1})}(\Theta) \rangle. \quad (108) $$

Corresponding to an index $\pi(i_1)$, if the vector $|v_{\pi(i_1)}(\Theta)\rangle$ does not appear the same number of times in the primal and dual variables of inner product $\langle \cdot | \cdot \rangle$ in (108), the expectation over $\Theta$ will be zero. This is due to the fact that if $\theta \sim \mathrm{Unif}([0, 2\pi])$,

$$ \mathbb{E}_{\theta} \left[ \exp(i\theta) \right] = \begin{cases} 0 & \text{if } l \in \mathbb{Z} \setminus \{0\} \\ 1 & \text{if } l = 0. \end{cases} \quad (109) $$

Only vectors with the same number of appearances in the primal and dual arguments will thus avoid the cancellation by the expectation over the phase modifier $\Theta$. For other matrix products appearing in the expansion $\mathrm{Tr}[\mathcal{L}^{\pi}(\Theta)^k]$ the same argument applies. This limits the amount of possible factors such as (108) appearing in $F(k)$. For a fixed $\pi$, we need first to characterize the type of factors that appear in the expansion

$$ F(k, \pi) = \mathbb{E}_{\Theta} \left[ \mathrm{Tr} \left[ \mathcal{L}^{\pi}(\Theta)^{k} \right] \right]. \quad (110) $$

A permutation $\pi \in S_m$ will induce a partition $\mathcal{V}^\pi$ of $[m]$, given by the partition sets

$$ 
\begin{aligned}
\mathcal{V}_1^\pi &= \{\pi(1), \dots, \pi(r)\} \\
\mathcal{V}_T^\pi &= \{\pi(r(T-1)+1), \dots, \pi(Tr)\}.
\end{aligned} 
\quad (111) $$

If $i \in \mathcal{V}_t^\pi$, the matrix $L_t^\pi(\Theta)$ will contain the vector $|v_i\rangle$. Then, only when $i, j \in \mathcal{V}_t^\pi$ for some $t \in [T]$, can the inner products $\langle v_i | v_j \rangle$ or $\langle v_j | v_i \rangle$ appear in the expansion of terms in (110) that contain the matrix $\mathcal{L}_t^\pi(\Theta)$. Similarly, if the term $\langle v_i | v_j \rangle \langle v_k | v_l \rangle$ appears adjacent in the trace of some factor in (110), but for that permutation $\pi$ we have that $j \in \mathcal{V}_t^\pi$, and $k \in \mathcal{V}_s^\pi$ belong to different partitions, it implies that $j$, and $k$ have same position as vectors in the matrices $\mathcal{L}_t^\pi(\Theta)$, and $\mathcal{L}_s^\pi(\Theta)$ respectively, and the matrix product $\mathcal{L}_t^\pi(\Theta)\mathcal{L}_s^\pi(\Theta)$ appears in the trace.

A useful representation for a partition (111) is encoded in its associated graph, depicted in Figure 2. If $K_z$ is the complete graph with $z$ vertices, the graph associated to $\pi$ is isomorphic to
the Cartesian product $K_r \square K_T$. The Cartesian product satisfies that $(i, t), (j, s) \in K_r \square K_T$ are adjacent if and only if $i = j$, and $t$ is adjacent to $s$ or $i$ is adjacent to $j$, and $t = s$. In our setting, only the edges corresponding to the component $K_r$ will give factors $\langle v_i | v_j \rangle$, while each edge on the component $K_T$ indicate that the partition has changed, that is, the trace contains a product of different matrices, e.g., $\mathcal{L}_t^\pi(\Theta)\mathcal{L}_s^\pi(\Theta)$. The type of factors that appear in $F(k, \pi)$ will depend on cycles on $K_r \square K_T$ that are compatible with the permutation. We characterize such cycles in the following definition.

<figure><img src="image_3.png" /><figcaption>Figure 2: The graph associated to a partition $V^\pi$ with examples of cycles starting at $\pi(1)$. Solid lines represent the transitions between partition sets, and can only be horizontal. Dashed lines represent transitions within partitions and add a factor $\langle v_i, v_j \rangle$ to a product such as (108). (a) An example of a representation of a nonvanishing cycle $\gamma = \pi(1, 2, 5, 6, 6, 5, 2, 1)$. (b) Example of a cycle $\delta$ that will not appear in $F(k)$. Indeed, there are edges within partitions that are visited only once. Hence, the product in (108) associated to the cycle will have expectation zero over $\Theta$.</figcaption></figure>

**Definition 6.** For a permutation $\pi$, a valid cycle $\gamma$ (in our context) is a concatenation of 2k indices in $[m]$ up to permutation that generate a cycle in the graph induced by the partition $V^\pi$, and such that

(i) Restricted to each partition set $V_t^\pi$ for $t \in [T]$, the cycle is union of disjoint cycles.

(ii) Transitions of the cycle $\gamma$ between partition sets only occur between indices, $i, j \in [m]$ such that $\pi^{-1}(i) \equiv \pi^{-1}(j) \mod r$.

If $\gamma$ is a valid cycle for $\pi$, the expectation over $\Theta$ of its associated factor

$$V_{\gamma}(\Theta) = \langle v_{\gamma_1}(\Theta), v_{\gamma_2}(\Theta) \rangle \cdots \langle v_{\gamma_k}(\Theta), v_{\gamma_{k+1}}(\Theta) \rangle, \quad (112)$$

does not vanish because of Definition 6 (i). That is, $V_\gamma(\Theta) = V_\gamma$ is independent of $\Theta$. Moreover, the transitions between partitions of $\gamma$ will constrain the matrix product in (110) that generated $V_\gamma$.

The order of the product elements in a multinomial product of matrices in (107) will determine the constraints of the cycles—the transition between partitions—that can appear from this product. For a fixed permutation $\pi$, depending on the matrix multinomials in the expansion of (110) and how ‘commutative’ they are, a cycle $\gamma$ may not be in the trace of that product. See Figure 3 for an example. Alternatively, if the permutation $\pi$ is random, the more a matrix product is ‘mixed’, the larger amount of constraints imposes to the cycles appearing in its trace, and so generally less cycles will appear. We will thus need to track the exponents of the matrices in the expansion of $F(k)$ to determine how often a cycle appears for a (random) permutation.

## A.2 Tracking factors and their chance of occurring

We examine the noncommutative expansion of $F(k)$, and we track the exponents depending on the matrix indices. We define the set $\mathcal{L}(k)$ of possible indices for the $k$ different matrices appearing on
<figure><img src="image_4.png" /><figcaption>Figure 3: For the permutation $\pi$, the depicted cycle appears in the expansion of the trace of (omitting $\pi$ and $\Theta$) $\mathcal{L}_1^2\mathcal{L}_2\mathcal{L}_1\mathcal{L}_2$, but not in the trace of $\mathcal{L}_1^3\mathcal{L}_2^2$. Indeed, there must be 4 transitions between partition sets.</figcaption></figure>

each term in the expansion of (110). Concretely, the set of exp-indices is defined as

$$ \mathcal{L}(k) = [T]^k. \qquad (113) $$

and each $\ell = (\ell_1, \dots, \ell_k) \in \mathcal{L}(k)$ will track the matrix indices in the expansion of

$$ \mathbb{E}_{\Theta} \left[ \mathrm{Tr} \left[ \prod_{j=1}^{k} \mathcal{L}_{\ell_j}^{\pi}(\Theta) \right] \right]. \qquad (114) $$

For $\ell \in \mathcal{L}(k)$, we will denote the set of different indices appearing in $\ell$ by $N(\ell) = \cup_{i=1}^k \{\ell_i\}$, and $n(\ell) = |N(\ell)|$ its amount. Recall (112). Given $\ell \in \mathcal{L}(k)$, for a fixed permutation $\pi \in S_m$, we will denote the set of factors in (137) as

$$ B(\ell, \pi) = \left\{ V_{\gamma} \mid \text{ for some valid } \gamma, V_{\gamma} \text{ appears in } \mathbb{E}_{\Theta} \left[ \mathrm{Tr} \left[ \prod_{j=1}^{k} \mathcal{L}_{\ell_j}^{\pi}(\Theta) \right] \right] \right\}, \quad \text{and define} \\ B(\ell) = \cup_{\pi \in S_m} B(\ell, \pi), \qquad (115) $$

as well as the set

$$ \mathcal{G}(k) = \bigsqcup_{\ell \in \mathcal{L}(k)} \{\ell, B(\ell)\}. \qquad (116) $$

**Definition 7.** We will say that a factor $V$ appears in $\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)$ for a permutation $\pi \in S_m$, and denote so by $V \in B(\Gamma, \pi)$, if $V \in B(\ell, \pi)$. We will also simply say that a factor $V$ appears in $\Gamma$ if $V \in B(\Gamma)$.

We denote the set of different indices in $\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)$ and their number by $N(\Gamma) = N(\ell)$, and $n(\Gamma) = n(\ell)$, respectively. Similarly, we will denote the vectors appearing in a factor $V \in B(\Gamma)$ by $N(V)$, and their number by $n(V)$. If a factor $V$ appears in $\Gamma$, the probability that $V$ appears for a random permutation $\pi \in S_m$ is positive, and will depend on the constraints imposed by $\Gamma$, and its valid cycles.

With the notation of Definition 7, if $V \in B(\Gamma, \pi)$ for some permutation $\pi$, each index in $N(V) \subset [m]$ must belong to only one of the partition sets from (111) with label in $N(\Gamma) \subset [T]$. Moreover, in this case a cycle $\gamma$ such that $V_{\gamma} = V$ will satisfy the constraints that come from the order in the multiplication of the matrices $\{L_{\ell}^{\pi}\}_{\ell \in [T]}$ associated to $\Gamma$, encoded by the exp-index of $\Gamma$. With this information, in the following Lemma 11 we obtain necessary conditions for $\gamma$ to satisfy $V_{\gamma} \in B(\Gamma, \pi)$, which we will use to bound the chance that this happens when $\pi$ is random later on.

**Lemma 11.** For a permutation $\pi \in S_m$ and $\Gamma \in \mathcal{G}(k)$, if a cycle $\gamma$ satisfies $V_{\gamma} \in B(\Gamma, \pi)$, then the following conditions hold.

(A) The cycle $\gamma$ restricted to each partition set of $V^{\pi}$ in (111), will be a disjoint union of cycles (or the emptyset). Only partitions with index in $N(\Gamma)$ may have nonempty intersection with $\gamma$, and any index in $N(V_{\gamma}) \cap V_{\ell}^{\pi}$ for $t \in N(\Gamma)$ will appear as many times in the primal as in the dual arguments of the inner products of $V_{\gamma}$.
(B) The cycle $\gamma$ changes partitions in the graph associated to the permutation $\pi$ only between indices $i, j \in N(V_\gamma)$ that satisfy $\pi^{-1}(i) \equiv \pi^{-1}(j) \mod r$, that is, if $i \in V_t^\pi$, $j \in V_{t'}^\pi$, both indices appear in the same relative position within their respective partitions $t, t'$.

**Proof.** For a fixed $\pi$ and $\Gamma \in \mathcal{G}(k)$, condition (A) is implied by the cycle being valid, and not vanishing in $F(k, \pi)$. Thus, in each partition set $V_t^\pi$ the condition must also hold.

For condition (B), note that transitions between partitions correspond to changes of matrix index $l \in N(\Gamma)$ as they appear in the noncommutative product corresponding to $\prod_{j=1}^k \mathcal{L}_{\ell_j}^\pi(\Theta)$ for $\Gamma = \{\ell, N(\ell)\}$. Indices of $\gamma$ will change partitions in the graph associated to $\pi$ if their corresponding vectors belong to different matrices that are consecutive in the matrix product. For two indices $i, j \in N(V_\gamma)$ that change between partitions in the graph, from the multiplication rule of matrices, the locations of these indices in the matrices share row and column number. This implies that the vectors corresponding to these indices are in the same position within their respective partitions. If $i = \pi(d_i)$, and $j = \pi(d_j)$, for some $d_i, d_j \in [m]$, then $d_i$ must be the same as $d_j$ modulo $r$. $\square$

The rules in Lemma 11 yield necessary conditions for $\gamma$ to satisfy $V_\gamma \in B(\Gamma, \pi)$. For example, if a product $\langle v_{i_1}, v_{i_2} \rangle \langle v_{i_3}, v_{i_4} \rangle$ appears in $V$ and $i_2$ and $i_3$ belong to different partition sets in the graph of $\gamma$, then the factor $\langle v_{i_4}, v_{i_1} \rangle$ cannot appear in $V_\gamma$ by condition (A).

In the following lemmas, we use the previous necessary conditions to bound the probability that a factor $V$ appears for a random permutation $\pi$ and $\Gamma \in \mathcal{G}(k)$. We take especial interest in the contributions by the diagonal terms of the matrices $\mathcal{L}_t^\pi(\Theta)$—factors $V$ that contain only norms—in the expansion of $F(k)$; they will become leading terms later on.

**Lemma 12.** Suppose that $V$ appears in $\Gamma$ and is such that $n(V) = n(\Gamma)$. Then $V$ is composed only of diagonal elements of $\{\mathcal{L}_t^\pi(\Theta)\}_{i \in [T]}$ and thus $V = \prod_{i \in N(V)} |v_i|^{2k_i}$ where $\mathbf{k} = (k_1, \dots, k_n(\Gamma))$ are the multiplicities of the vectors with indices in $N(V)$.

**Proof.** If $n(V) = n(\Gamma)$ for $\Gamma = \{\ell, N(\ell)\}$, the product $\prod_{i=1}^k \mathcal{L}_{\ell_i}^\pi(\Theta)$ that has $n(\Gamma)$ distinct matrices— not counting multiplicities—can only have a cycle $\gamma$ with $n(V)$ different indices if and only if for each index in $N(\Gamma)$, there is exactly one index in $N(V_\gamma)$. This happens only when diagonal elements of $\mathcal{L}_t^\pi(\Theta)$ appear in $V_\gamma$. Therefore, the identity $V = V_\gamma = \prod_{i \in N(V)} |v_i|^{2k_i}$ must hold for some $\gamma$, where $\mathbf{k} = (k_1, \dots, k_n(\Gamma))$ are the multiplicities of the indices $t \in N(\Gamma)$ in $\ell$, as well as of $N(V)$. $\square$

**Lemma 13.** (Adapted from [31, Sec. 1.9]) Let $d \ge n$. The number of ways to partition $d$ labeled items into $n$ labeled classes such that no class is empty is given by

$$n! \binom{d}{n} = \sum_{j=0}^{n-1} (-1)^j (n-j)^d \binom{d}{j}, \qquad (117)$$

where $\binom{d}{n}$ is the Stirling number of the second kind that satisfies $\binom{d}{n} = \binom{d}{1} = 1$, and $\binom{d}{n} \le \frac{n^d}{n!}$.

A cycle $\gamma$ that satisfies condition (A), on each partition it is decomposed in smaller disjoint cycles $\delta_1, \dots, \delta_s$ for some $s \ge 1$. We can choose the decomposition such that each cycle cannot be further decomposed, and the indices of each subcycle belong to a single partition. We denote the maximal number of disjoint cycles that decompose $\gamma$ by $d(\gamma)$. This maximal decomposition is independent of partition set $V^\pi$, and satisfies

$$V_{\gamma} = V_{\delta_1} \cdots V_{d(\gamma)}. \qquad (118)$$

Note that the subcycles $\delta_1, \dots, \delta_{d(\gamma)}$ do not keep track of the transitions between the partitions of $\gamma$; this is instead in $\Gamma$. Crucially, for any $\Gamma \in \mathcal{G}(k)$ such that condition (A) holds for some $\gamma$, we must then have $n(\Gamma) \le d(\gamma) \le n(V_\gamma)$.

The number of maximal subcycles allows us to bound in the next lemma how many permutations $\pi$ allow the expansion term in (110) corresponding to $\Gamma$ to have a factor $V$ appearing. For the following Lemma, if $\mathbf{k}(\Gamma) = (k_1, \dots, k_{n(\Gamma)})$ are the multiplicities of the exp-index $\ell$ of $\Gamma$, we let $z_1$ be the different number of times that $k_1$ appears in $\mathbf{k}(\Gamma)$, $z_2$ the number of times a different
multiplicity than $k_1$ appears in $\mathbf{k}(\Gamma)$, and so on. Denote the number different multiplicities of $\mathbf{k}(\Gamma)$ in this way by $Z(\Gamma)$. The vector

$$ \mathbf{z}(\Gamma) = (z_1, \dots, z_{Z(\Gamma)}) \qquad (119) $$

will contain the multiplicities of $\mathbf{k}(\Gamma)$, and

$$ \sum_{i=1}^{Z(\Gamma)} z_i = n(\Gamma). \qquad (120) $$

With slight abuse of notation, the vectors $\mathbf{k}(\Gamma)$, or $\mathbf{z}(\Gamma)$ will also be considered as lists whenever used in a multinomial number, e.g, $\binom{k}{\mathbf{k}(\Gamma)}$.

**Lemma 14.** Suppose that $\Gamma \in \mathcal{G}(k)$, and let $V \in B(\Gamma)$. If $\pi \sim \text{Unif}(S_m)$, then
(i) If $n(V) > n(\Gamma)$,

$$ C_{V,\Gamma} = \mathbb{P}[V \in B(\Gamma, \pi)] \le \frac{n(\Gamma)! \{\binom{d(V)}{n(\Gamma)}\} r^{n(V)-n(\Gamma)+1}}{\binom{Tr}{n(V)} n(V)!}. \qquad (121) $$

(ii) If $n(V) = n(\Gamma)$, let $\mathbf{z}(\Gamma)$ be the multiplicities of $\mathbf{k}(\Gamma)$ defined in (119), then

$$ C_{V,\Gamma} = \mathbb{P}[V \in B(\Gamma, \pi)] = \frac{r}{\binom{Tr}{n(V)} \binom{n(\Gamma)}{\mathbf{z}(\Gamma)}}. \qquad (122) $$

*Proof.* We count first the number of ways that permutations of $[m]$ can rearrange the indices of $V$. Out of $m = Tr$ possible total index locations, $n(V)$ must be chosen. By symmetry, there are

$$ \frac{(Tr)!}{(Tr - n(V))!} = \binom{Tr}{n(V)} n(V)! \qquad (123) $$

possible ordered choices of locations for the $n(V)$ indices that can be attained by a permutation $\pi \in S_m$. We bound how many of these permutations allow the existence of a cycle $\delta$ compatible with $\Gamma$ and the permutation $\pi$, such that $V_{\delta} = V$. We show first part (ii).

**Case (ii)** If $n(V) = n(\Gamma)$, by Lemma 12, we only need to look at the diagonal elements of the matrices $\mathcal{L}_{\pi}^t$ for $t \in N(\Gamma)$ and see where the indices of $V$ are sent by $\pi$. From the assumption $V \in B(\Gamma)$, by Lemma 12 we must have $V = \prod_{i \in N(V)} |v_i|^{2k_i}$, where $k_i$ coincide with the multiplicities of the $\ell$ index of $\Gamma$. For any permutation $\pi$ such that $V \in B(\Gamma, \pi)$, each $|v_i\rangle$ with $i \in N(V)$ must belong to a unique partition $\mathcal{V}_{\pi}^t$ with $t \in N(\Gamma)$, and also satisfy condition (B) from Lemma 11. If there exists a cycle $\delta$ such that $V_{\delta} = V$, then all indices of $V$ must satisfy condition (B) pairwise since they are all adjacent to each other. There are $r$ different values modulo $r$ such that condition (B) can be satisfied simultaneously for all $i \in N(V)$. Furthermore, for each of the choices, we can try to assign differently the indices of $N(\gamma)$ within the partitions available in $N(\Gamma)$. However, the multiplicities of $\Gamma$ have to match the multiplicity of the vectors in $V$ for the factor to appear for that index assignment. Only if multiplicities coincide will the factor $V$ appear for the permutation. For $i, j \in N(\gamma)$, we can only exchange $i$ with the position of $j$, if $k_i = k_j$. Let $\mathbf{z}(\Gamma)$ be the vector of multiplicities of $\{k_i\}_{i \in N(\Gamma)}$. From the previous discussion, for a fixed value modulo $r$, there are exactly $\prod_{i=1}^{z(\Gamma)} z_i!$ ways to permute indices in $N(V)$ within the different partitions corresponding to $N(\Gamma)$ such that the product $V$ appears for that permutation. There are at most $r \prod_{i=1}^{z(\Gamma)} z_i!$ permutations that satisfy $V \in B(\Gamma, \pi)$. Conversely, any permutation satisfying these constraints will also imply that $V \in B(\Gamma, \pi)$. We conclude

$$ \mathbb{P}[V \in B(\Gamma, \pi)] = \frac{r \prod_{i=1}^{z(\Gamma)} z_i!}{\binom{Tr}{n(V)} n(V)!} = \frac{r}{\binom{Tr}{n(V)} \binom{n(\Gamma)}{\mathbf{z}(\Gamma)}}. \qquad (124) $$

**Case (i)** We assume that $n(V) > n(\Gamma)$. To upper bound the amount of permutations that allow $V \in B(\Gamma, \pi)$, we consider cycles that satisfy the necessary conditions (A) and (B) from Lemma 11.
Let $\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)$, and $\gamma$ a cycle satisfying $V = V_\gamma$. The chance that $V \in B(\Gamma, \pi)$ is at most the chance that there exists $\gamma$ such that $V = V_\gamma$ and $\gamma$ satisfies the necessary conditions (A) and (B) in Lemma 11 for $\pi$ and $\Gamma$,

$$ \mathbb{P}[V \in B(\Gamma, \pi)] \le \mathbb{P}[\exists \gamma \text{ s.t. } V_{\gamma} = V, \gamma \text{ satisfies (A) and (B) for } \pi \text{ and } \Gamma] \quad (125) $$

We count how many cycles $\gamma$ may satisfy all conditions simultaneously. For a permutation $\pi$, if a cycle $\gamma$ exists that satisfies $V = V_\gamma$, for each index $t \in N(\Gamma)$ corresponding to a partition set $V_t^\pi$, there exist at least one constraint for the position of the indices of $N(V) \cap V_t^\pi$ when the cycle $\gamma$ either arrives from, or leaves to another partition. This constraint is imposed by the fact that the positions must be up to $\pi$ equal modulo $r$—see Lemma 11.

Denote by $\gamma|_{V_t^\pi}$ for each $t \in N(\Gamma)$ the maximal set of subcycles of $\gamma$ that are contained in the partition set $V_t(\pi)$. Since there are at least two transitions—arrival and departure—of $\gamma$ for each partition set, we show that there are at least $n(\Gamma) - 1$ indices of $V$ whose positions in the associated graph are fixed by the positions of other indices in $N(V)$ in the graph. Indeed, for each $t \in N(\Gamma)$ at least one index $u_t \in N(V) \cap V_t^\pi$ must be adjacent in the graph of $\gamma$ to at least another index $u_{t'}$ belonging to another partition $t' \in N(\Gamma)$. If this was not the case, then for at least one index $t \in N(\Gamma)$, $\gamma$ would arrive to the partition corresponding to $t$, but not leave, which would contradict the fact that $\gamma$ is a cycle. A connected graph with the $n(\Gamma)$ partitions is generated by $\gamma$ tracking arrivals and departures of partition sets. It is well-known that the the connected graph with minimal amount of edges that we can construct with $n(\Gamma)$ vertices has $n(\Gamma) - 1$ edges. Hence, there will be at least $n(\Gamma) - 1$ indices in $N(V)$ whose positions are determined by other indices of $N(V)$ whenever there is a cycle $\gamma$ such that $V = V_\gamma$.

We now upper bound how many permutations $\pi$ allow for a cycle $\gamma$ to exist with $V = V_\gamma$ satisfying conditions (A), and (B). Conditional on $V = V_\gamma$, consider the maximal decomposition of $V$ by disjoint subcycles described in (118). Let $d(V)$ be the number of disjoint subcycles for this decomposition and denote the set of subcycles by $D(V) = \{\delta_1, \dots, \delta_{d(V)}\}$. Condition (A) requires that the indices of any subcycle $\delta_i$, $i \in [d(V)]$ belong to the same partition. Any $\gamma$ satisfying $V = V_\gamma$, and (A) will have these $d(V)$ labeled maximal subcycles distributed among $n(\Gamma)$ labeled partition sets, with at least one subcycle per partition set. By Lemma 13, the different number of ways to distribute the subcycles is

$$ n(\Gamma)! \left\{ \begin{matrix} d(V) \\ n(\Gamma) \end{matrix} \right\} = \sum_{i=0}^{n(\Gamma)-1} (-1)^j (n(\Gamma) - j)^{d(V)} \binom{d(V)}{j}, \quad (126) $$

where $\binom{d(V)}{n(\Gamma)}$ is the Stirling number of second kind.

For each fixed distribution of the subcycles, each index $i \in N(V)$ within a partition $t \in N(\Gamma)$ can be assigned to at most $r$ positions in its corresponding partition. However, from the previous discussion, in order to generate a connected cycle $\gamma$ such that $V_\gamma = V$, there are at least $n(\Gamma) - 1$ indices of $V$ whose locations are determined by other indices in $N(V)$. Therefore, there are at most $r^{n(V)-n(\Gamma)+1}$ possible ways to distribute the indices for each given subcycle assignment, and satisfy (B). Combining the previous bounds, the number of different ways to allow a cycle $\gamma$ to exists with $V = V_\gamma$, while also satisfying (B) and (A) for $\Gamma$ is at most

$$ n(\Gamma)! \left\{ \begin{matrix} d(V) \\ n(\Gamma) \end{matrix} \right\} r^{n(V)-n(\Gamma)+1}. \quad (127) $$

Combining (127) with (123), we obtain that

$$ \mathbb{P}[V \in B(\Gamma, \pi)] \le \frac{n(\Gamma)! \binom{d(V)}{n(\Gamma)} r^{n(V)-n(\Gamma)+1}}{\binom{Tr}{n(V)} n(V)!} \quad (128) $$

□

Lemma 14 bounds the probability $C_{V,\Gamma}$ of a factor $V$ appearing for $\Gamma \in \mathcal{G}(k)$ and a random permutation. In the next section, we examine the symmetries of $\mathcal{G}(k)$ that will simplify the computations later, and are key in obtaining a leading order of $F(k)$ independent of $T$.
### A.3 Characterizing symmetries in the expansion

The set $\mathcal{G}(k)$ possesses several additional symmetries that we can exploit by using groups. There are namely two group actions of $S_k$ and $S_T$ on $\mathcal{G}(k)$. Both actions will allow us to decouple the combinatorial problem of counting exp-indices to counting only factors.

**First action by $S_k$.** We define the action $\mathfrak{h} : S_k \to \mathrm{Aut}(\mathcal{G}(k))$ that permutes the location of the indices of $\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)$, that is, for $g \in S_k$,

$$ g(\ell_1, \dots, \ell_k) = (\ell_{g(1)}, \dots, \ell_{g(k)}) \\ \mathfrak{h}[g](\{\ell, B(\ell)\}) = \{g(\ell), B(g(\ell))\}. \qquad (129) $$

This group action tracks how many $\Gamma' \in \mathcal{G}(k)$ in the expansion of (107) have similar indices to those of $\Gamma$, up to reordering. For example, they track if

$$ \mathbb{E}_{\Theta, \pi} \left[ \mathrm{Tr} \left[ \left( \mathcal{L}_1^{\pi}(\Theta) \right)^2 \left( \mathcal{L}_2^{\pi}(\Theta) \right)^2 \right] \right] \quad \text{and} \quad \mathbb{E}_{\Theta, \pi} \left[ \mathrm{Tr} \left[ \mathcal{L}_1^{\pi}(\Theta) \mathcal{L}_2^{\pi}(\Theta) \mathcal{L}_1^{\pi}(\Theta) \mathcal{L}_2^{\pi}(\Theta) \right] \right], \qquad (130) $$

may share some of the factors. We define the set of orbits of this action on $\mathcal{G}(k)$ as

$$ \bar{\mathcal{G}}(k) = \frac{\mathcal{G}(k)}{S_k}. \qquad (131) $$

We bound the number of elements of an orbit $\bar{\Gamma} \in \bar{\mathcal{G}}(k)$. Given $\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)$ we denote the multiplicities of $\ell$ by $\mathbf{k}(\Gamma) = (k_1, \dots, k_{n(\Gamma)})$. A group element $g \in S_k$ will permute the entries of the vector $\ell$ but not their multiplicities. The orbit of $\Gamma \in \mathcal{G}(k)$ thus contains at most all possible different ways of choosing out of $k$ locations in the exp-indices $\ell$, $n(\Gamma)$ labels with their respective multiplicities in $\mathbf{k}(\Gamma)$. If $\bar{\Gamma}$ denotes the orbit of $\Gamma$ under this action, the number of elements is given by the multinomial number

$$ |\bar{\Gamma}| = \binom{k}{k_1, \dots, k_{n(\Gamma)}} = \binom{k}{\mathbf{k}(\Gamma)}. \qquad (132) $$

The number, and index labels of $\Gamma \in \mathcal{G}(k)$ are invariant under $\mathfrak{h}$. We can define $n(\bar{\Gamma}) = n(\Gamma)$, and $N(\bar{\Gamma}) = N(\Gamma)$ for any representative $\Gamma \in \bar{\Gamma}$.

Note that the action of $S_k$ is in general not well-defined for factors of $\Gamma$ since $B(\ell) \neq B(g(\ell))$, as the following example shows.

**Example 8.** For $k = 4$, let $\ell_1 = (1, 1, 2, 2)$, and $\ell_2 = (1, 2, 1, 2)$—in (130)—be exp-indices in the same equivalence class under action $\mathfrak{h}$, and consider the following factor corresponding to some cycle $\gamma$

$$ V_{\gamma} = \langle v_1, v_2 \rangle \langle v_2, v_1 \rangle \langle v_3, v_4 \rangle \langle v_4, v_3 \rangle \in B(\ell_1), \qquad (133) $$

where $\{1, 2\} \subset \mathcal{V}_1$, $\{3, 4\} \subset \mathcal{V}_2$ belong to different partition sets. In order for $V_{\gamma}$ to also appear in $B(\ell_2)$, only the following product or its conjugate could appear in the expansion corresponding to $B(\ell_2)$ according to Definition 6,

$$ \langle v_1, v_2 \rangle \langle v_3, v_4 \rangle \langle v_2, v_1 \rangle \langle v_4, v_3 \rangle. \qquad (134) $$

Here, the indices 2 and 3 satisfy constrain (B) of Lemma 11, and appear in the same position for both partitions. However, the same should occur with indices 2 and 4. The constraints (B) cannot be satisfied and so $V_{\gamma} \notin B(\ell_2)$.

Nonetheless, the action of $\mathfrak{h}$ will be well-defined for some factors; see Remark 9 below. We will use this symmetry to estimate their contribution to $F(k)$, which will become the leading term.

**Remark 9.** For a factor $V \in B(\ell)$ composed only of diagonal elements, that is, $V$ is a product of norms of vectors $|v_i\rangle$, the action $\mathfrak{h}$ is well-defined. Indeed, the diagonal parts of the matrices $\{\mathcal{L}_t^{\pi}(\Theta)\}_{t \in [T]}$ commute for any exp-index, that is, $V \in B(g(\ell))$ for any $g \in S_k$.
**Second action by $S_T$.** We can also define an action $\mathfrak{g}: S_T \to \mathrm{Aut}(\bar{\mathcal{G}}(k))$. A permutation $h \in S_T$ acts on $\ell \in [T]^k$ by permuting its indices

$$h(\bar{\ell}_1, \dots, \bar{\ell}_k) = (h(\ell_1), \dots, h(\ell_k)). \qquad (135)$$

The action on a representative $[\{\bar{\ell}, B(\bar{\ell})\}] \in \bar{\Gamma}$ is

$$\mathfrak{g}[h]([\{\bar{\ell}, B(\bar{\ell})\}]) = [\{h(\bar{\ell}), B(h(\bar{\ell}))\}]. \qquad (136)$$

Differently to $\mathfrak{h}$, the action $\mathfrak{g}$ is well defined for factors due to symmetry, e.g., we expect the same factors $V$ occurring in

$$\mathbb{E}_{\Theta, \pi} \left[ \mathrm{Tr} \left[ \left( \mathcal{L}_1^{\pi}(\Theta) \right)^2 \left( \mathcal{L}_2^{\pi}(\Theta) \right)^2 \right] \right] \quad \text{and} \quad \mathbb{E}_{\Theta, \pi} \left[ \mathrm{Tr} \left[ \left( \mathcal{L}_3^{\pi}(\Theta) \right)^2 \left( \mathcal{L}_4^{\pi}(\Theta) \right)^2 \right] \right]. \qquad (137)$$

Indeed, if a factor $V \in B(\Gamma, \pi)$, the effect of permuting the indices of $\Gamma$ with $h$ for a fixed $\pi$ is equivalent to permuting the partition sets with label $t \in N(\Gamma)$, while leaving $V$ and $\pi$ fixed. We can then compensate this change by using another permutation $\pi' \in S_m$ such that $V \in B(h(\Gamma), \pi')$ instead. From the definition of $B(\ell)$ in (115) we obtain that the factors appearing for a representative of $\bar{\Gamma}$ are invariant under the action $\mathfrak{g}$. We denote the set of orbits under this action by

$$G(k) = \frac{\bar{\mathcal{G}}(k)}{S_T} \qquad (138)$$

Let $\Delta \in G(k)$ be the orbit of $\bar{\Gamma}$ under $\mathfrak{g}$. The number of different exp-indices of any of its representatives in $\bar{\Gamma}$ is $n(\Delta) = n(\bar{\Gamma})$, and their multiplicities are $\mathbf{k}(\Delta) = \bar{\Gamma}$. We will also use the notation $\mathbf{z}(\Delta)$ to denote the multiplicities of $\mathbf{k}(\Delta)$ similarly to (119).

We compute the size of $\Delta$. Recall that $\bar{\Gamma}$ contains all permutations of the exp-index $\ell$ of a representative $\Gamma \in \bar{\Gamma}$. We find a representative $\Gamma$ such that its exp-indices are equal adjacent to each other

$$\underbrace{(\ell_1, \dots, \ell_1)}_{k_1 \text{ times}}, \dots, \underbrace{(\ell_{n(\Gamma)}, \dots, \ell_{n(\Gamma)})}_{k_{n(\Gamma)} \text{ times}} \qquad (139)$$

In this manner, we can identify $\bar{\Gamma}$ with a commutative multinomial of order $k$ in $[T]$ variables

$$\prod_{i=1}^{n(\Gamma)} (x_{\ell_i})^{k_i}. \qquad (140)$$

A permutation $h \in S_T$ sends the labels $i \in N(\Gamma)$ to any other different labels in $[T]$ while leaving the multiplicities invariant. If all multiplicities are different, then the amount of different multinomials under this action will be equivalent to the number of injective maps from the set $N(\Gamma)$ to $[T]$, which is given by the multinomial coefficient

$$\frac{T!}{(T - n(\Gamma))!} = \binom{T}{n(\Gamma)} n(\Gamma)! = \binom{T}{n(\Delta)} n(\Delta)! \qquad (141)$$

However, if some of the multiplicities in $\mathbf{k}(\Gamma)$ are equal, some of the previous maps for the labels in $N(\Gamma)$ will be sent to the same multinomial. Let $\mathbf{z}(\Gamma)$ be the vector of size $n(\Gamma)$ with the multiplicities of $\mathbf{k}(\Gamma)$. This vector satisfies

$$n(\Gamma) = \sum_{i=1}^{Z(\Gamma)} z_i. \qquad (142)$$

For a fixed multinomial of the type (140) with multiplicities $\mathbf{k}(\Gamma)$ there are $\prod_{i=1}^{Z(\Gamma)} z_i!$ different relabeling of its indices that leave the multinomial invariant. Therefore, the number of commutative monomials of order $k$ in $[T]$ variables with multiplicities $\mathbf{k}(\Gamma)$ is given by

$$|\Delta| = \binom{T}{n(\Gamma)} \binom{n(\Gamma)}{\mathbf{z}(\Gamma)} = \binom{T}{n(\Delta)} \binom{n(\Delta)}{\mathbf{z}(\Delta)}. \qquad (143)$$
## A.4 Combinatorial inequalities

We have examined exp-indices and their symmetries. We now define sets that will help us with the counting of factors.

$$ \mathcal{M}(k, l) = \left\{ (k_1, \dots, k_m) \in ([k] \cup \{0\})^{\times m} \middle| \sum_{i=1}^{m} k_i = k, k_i > 0 \text{ for exactly } l \text{ indices } i \in [m] \right\}. \quad (144) $$

The set $\mathcal{M}(k, l)$ can be identified with the set of different multinomials of order $k$ with $l$ variables out of $m$. The set of different multinomials of order $k$ with $m$ variables $\mathcal{M}(k)$ is then one-to-one with

$$ \mathcal{M}(k) = \bigsqcup_{1 \le l \le k} \mathcal{M}(k, l). \quad (145) $$

For a vector $\mathbf{k} \in \mathcal{M}(k)$ (of dimension $m$), we denote its number of nonzero entries by $n(\mathbf{k})$.

**Definition 10.** Let a vector $\mathbf{k} \in \mathcal{M}(k)$, we denote its frequency by $f(\mathbf{k}) = (k_{[1]}, \dots, k_{[k]})$, where $k_{[i]}$ is the $i$th largest entry of $\mathbf{k}$, and we complete with zeros if necessary. Similarly, for any $\Gamma \in \bar{\Gamma} \in \Delta \in G(k)$, we define $f(\Delta) = f(\bar{\Gamma}) = f(\Gamma) = (\mathbf{k}(\Gamma), 0_{k-n(\Gamma)})$, which is the vector of multiplicities of $\Gamma$ in order with added zeros if necessary. We denote the set of frequencies with at most $k$ different items by $\mathfrak{F}(k) = f(\mathcal{M}(k))$.

Note that any $f \in \mathfrak{F}(k)$ can be represented by a decreasing vector $(f_1, \dots, f_k)$, where we complete with zeros if necessary. If $\Delta \in \mathcal{G}(k)$ and $n(\Delta) = l$, we can define the subset of (144) that have the same frequencies as $\Delta$.

$$ \mathcal{M}(k, l)[\Delta] = \left\{ \mathbf{k} \in \mathcal{M}(k, l) \mid f(\mathbf{k}) = f(\Delta) \right\}. \quad (146) $$

The set $\mathcal{M}(k, l)[\Delta]$ is one-to-one with the set of multinomials of order $k$ with $l$ variables out of $m$, such that their vectors of multiplicities is $\mathbf{k}(\Delta)$ up to reordering. Crucially, the frequencies of different elements in $G(k)$ are also different as shown in the following lemma.

**Lemma 15.** Let $\Delta_1, \Delta_2 \in G(k)$. Then $f(\Delta_1) = f(\Delta_2)$, or equivalently $\mathbf{k}(\Delta_1)$ is $\mathbf{k}(\Delta_2)$ up to reordering, if and only if $\Delta_1 = \Delta_2$.

*Proof.* If $f(\Delta_1) = f(\Delta_2)$, then $\Delta_1$ has a representative $\Gamma_1 = \{\ell_1, B(\ell_1)\}$ that satisfies $i_1 \in \ell_1 k_1$ times, $i_2 \in \ell_1 k_2$ times, ..., and $i_{n(\Gamma_1)} \in \ell_1 k_{n(\Gamma_1)}$ times for some $i_1, \dots, i_{n(\Gamma_1)} \in N(\Gamma_1)$. Similarly for $\Delta_2$ with a representative $\Gamma_2 = \{\ell_2, B(\ell_2)\}$ that satisfies $j_1 \in \ell_2 k_1$ times, $j_2 \in \ell_2 k_2$ times, ..., and $j_{n(\Gamma_1)} \in \ell_2 k_{n(\Gamma_1)}$ times for some $j_1, \dots, j_{n(\Gamma_2)} \in N(\Gamma_2)$. Since $n(\Delta_1) = n(\Gamma_1) = n(\Gamma_2) = n(\Delta_2)$, there exists a permutation $h \in S_T$ that takes $i_1, \dots, i_{n(\Gamma_1)}$ to $j_1, \dots, j_{n(\Gamma_2)}$. In particular, $\Delta_1$, and $\Delta_2$ have the same representatives, and so they must be equal. $\square$

If we consider the disjoint union of (146) over all $\Delta \in G(k)$, we recover (144)

$$ \mathcal{M}(k, l) = \bigsqcup_{\substack{\Delta \in G(k) \\ n(\Delta) = l}} \mathcal{M}(k, l)[\Delta]. \quad (147) $$

We introduce a partial order over frequencies in $\mathfrak{F}(k)$.

**Definition 11.** A frequency $f = (f_1, \dots, f_k)$ is dominated by $g = (g_1, \dots, g_k)$ in $\mathfrak{F}(k)$, denoted by $g \prec f$, if for a partition $\{A_i\}_{i=1}^l$ of $[k]$ with some $l \ge 1$, we have for all $j \in [k]$ such that $f_j \ne 0$,

$$ f_j = \sum_{i \in A_j} g_i. \quad (148) $$

For $\Delta \in G(k)$ such that $d > n(\Delta)$, we define

$$ \mathcal{M}(k, d)[\Delta] = \left\{ \mathbf{k} \in \mathcal{M}(k, d) \mid f(\mathbf{k}) \prec f(\Delta) \right\}, \quad (149) $$

We use the previous definitions to simplify the computations with the following results.
**Lemma 16.** In the notation of this section, let $\Gamma \in \bar{\Gamma} \in \Delta \in G(k)$ be such that $n(\Gamma) = l$.

$$ \sum_{\substack{V \in B(\Gamma) \\ n(V) = l}} C_{V, \Gamma} V = \frac{r}{\binom{Tr}{n(\Delta)} \binom{n(\Delta)}{\mathbf{z}(\Delta)}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} \prod_{i=1}^{m} |v_i|^{2k_i}, \qquad (150) $$

and

$$ \sum_{\substack{V \in B(\Gamma) \\ n(V) > l}} C_{V, \Gamma} V \le \sum_{d=l+1}^{k} \frac{n(\Gamma)! \{n(\Gamma)\}^{d} r^{d-n(\Gamma)+1}}{\binom{Tr}{d} d!} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i}. \qquad (151) $$

*Proof.* We show (150) first. Since we consider the case $n(V) = n(\Gamma) = l$, by Lemma 12, $V$ is product of norms of the vectors $\{|v_i\}\}_{i \in [m]}$, and there will be exactly $n(\Gamma)$ different norms in the product, up to multiplicities. The indices $t \in N(\Gamma)$ are one to one with indices in $N(V)$, and the multiplicites will be $\mathbf{k}(\Gamma) = (k_1, \dots, k_l)$. Thus, we can find as many factors $V \in B(\Gamma)$ with exactly $n(V) = n(\Gamma)$ different norms as there are multinomials of the type

$$ x_{i_1}^{k_1} \cdots x_{i_l}^{k_l}, \qquad (152) $$

with $i_1, \dots, i_l \in [m]$ different, that is, vectors $\mathbf{k} \in \mathcal{M}(k)$, with the frequencies equal to $f(\Gamma) = f(\Delta)$. This is exactly the definition of $\mathcal{M}(k,l)[\Delta]$ in (146). If we denote the factor with only norms with indices and multiplicities corresponding to $\mathbf{k}$ by $V(\mathbf{k})$, then

$$ \sum_{\substack{V \in B(\Gamma) \\ n(V) = l}} C_{V, \Gamma} V = \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} C_{V(\mathbf{k}), \Gamma} \prod_{i=1}^{m} |v_i|^{2k_i} \qquad (f(\Gamma) = f(\mathbf{k})) \\ = \frac{r}{\binom{Tr}{n(\Delta)} \binom{n(\Delta)}{\mathbf{z}(\Delta)}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} \prod_{i=1}^{m} |v_i|^{2k_i} \qquad (\text{Lemma 14, and } n(\Gamma) = n(\Delta) = l) $$

We show now (151). Suppose $\Gamma$ has multiplicities $\mathbf{k}(\Gamma) = (k_1, \dots, k_l)$, and $V$ is such that $N(V) = \{1, \dots, n(V)\} \subset [m]$, where $n(V) > n(\Gamma) = l$. Let $\mathbf{g} = (g_1, \dots, g_{n(V)})$ be the multiplicities of the indices in $V$, which satisfy

$$ k = \sum_{i=1}^{n(V)} g_i. \qquad (153) $$

Using Cauchy-Schwartz in all inner products of $V$ we obtain the bound

$$ |V| \le \prod_{i=1}^{n(V)} |v_i|^{2g_i}. \qquad (154) $$

Differently to the previous case, elements $t \in N(\Gamma)$ are not one to one with indices in $N(V)$. However, if $V \in B(\Gamma, \pi)$ for some permutation $\pi$ there is an assignment that maps each $t \in N(\Gamma)$ to a set $V_t^\pi \cap N(V)$. In this case, the multiplicity $k_t$ of each $t \in N(\Gamma)$ must be equal to the sum of the multiplicities of the indices of $V$ in $V_t^\pi \cap N(V)$. That is, there exists a partition $\{A_i\}_{i=1}^{n(\Gamma)}$ of $N(V)$ such that

$$ k_t = \sum_{i \in A_t} g_i \quad \text{for each} \quad t \in N(\Gamma). \qquad (155) $$

This is the domination condition from Definition 11. We can thus upper bound the sum in (151) by a sum over multinomials such as (154) whose multiplicities are dominated by $f(\Gamma) = f(\Delta)$, which is $\mathcal{M}(k, d)[\Delta]$ by definition in (149). We are left to count how many $V \in B(\Gamma)$ have the same multinomial in (154) that upper bounds the factor $V$. Let $\mathcal{N}$ be this number. Any other factor $V'$ with (154) as upper bound will have the same indices $i \in N(V') = N(V)$ appearing in $V'$ with
some other order. We can upper bound the number of ways to order the indices by the number of ways to partition $k$ items in $n(V)$ labeled classes with multiplicities $g = (g_1, \dots, g_{n(V)})$, that is

$$ \mathcal{N} \le \mathcal{N}(\mathbf{g}) = \binom{k}{\mathbf{g}}. \qquad (156) $$

The previous argument implies that if $\Gamma \in \bar{\Gamma} \in \Delta$,

$$ \sum_{\substack{V \in B(\Gamma) \\ n(V) > l}} C_{V,\Gamma} V \le \sum_{d=l+1}^{k} \sum_{\substack{V \in B(\Gamma) \\ n(V)=d}} C_{V,\Gamma} \prod_{i \in N(V)} |v_i|^{2g_i} \qquad (\text{From } (154)) $$

$$ \le \sum_{d=l+1}^{k} \sum_{\substack{V \in B(\Gamma) \\ n(V)=d}} \frac{n(\Gamma)! \{n(V)\} r^{n(V)-n(\Gamma)+1}}{\binom{Tr}{n(V)} n(V)!} \prod_{i \in N(V)} |v_i|^{2g_i} \qquad (\text{Lemma 14}) $$

$$ \le \sum_{d=l+1}^{k} \frac{n(\Gamma)! \{n(\Gamma)\} r^{d-n(\Gamma)+1}}{\binom{Tr}{d} d!} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \mathcal{N}(\mathbf{g}) \prod_{i=1}^{m} |v_i|^{2g_i} $$

$$ \le \sum_{d=l+1}^{k} \frac{n(\Delta)! \{n(\Delta)\} r^{d-n(\Delta)+1}}{\binom{Tr}{d} d!} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \qquad (\text{From } (156)) $$

□

Let

$$ W_{\Delta}(T) = \frac{r}{\binom{Tr}{n(\Delta)} \binom{n(\Delta)}{\mathbf{z}(\Delta)}} \qquad (157) $$

$$ W_{d,\Delta}(T) = \frac{n(\Delta)! \{n(\Delta)\} r^{d-n(\Delta)+1}}{\binom{Tr}{d} d!} \quad \text{if } d > n(\Delta). \qquad (158) $$

the following lemma characterizes the fact that the leading term of $F(k)$ is independent of $T$. The following asymptotic in $T$ will be key in the computation.

**Lemma 17.** Let $\Delta \in G(k)$, and recall that $|\Delta| = |\Delta|(T)$ is (143) and depends on $T$. As $T \to \infty$:

$$ (a) \quad |\Delta|(T)W_{\Delta}(T) = \frac{1 + O(T^{-1})}{r^{n(\Delta)-1}} $$

$$ (b) \quad |\Delta|(T)W_{d,\Delta}(T) = O\left(\frac{k^k}{r^{n(\Delta)-1}T^{d-n(\Delta)}}\right). $$

*Proof.* We show (a) first. From Lemma 14, and the bound in (143), we immediately have

$$ \begin{aligned} |\Delta|(T)W_{\Delta}(T) &= \binom{T}{n(\Delta)} \frac{r}{\binom{Tr}{n(\Delta)}} = \frac{rT(T-1)\cdots(T-n(\Delta)+1)}{rT(rT-1)\cdots(rT-n(\Delta)+1)} \\ &= \frac{1+O(T^{-1})}{r^{n(\Delta)-1}}. \end{aligned} \qquad (159) $$

For (b), we again use the bound of Lemma 14, and (143) to obtain

$$ \begin{aligned} |\Delta|(T)W_{d,\Delta}(T) &= \binom{T}{n(\Delta)} \binom{n(\Delta)}{\mathbf{z}(\Delta)} \frac{n(\Delta)! \{n(\Delta)\} r^{d-n(\Delta)+1}}{\binom{Tr}{d} d!} \\ &\le \binom{T}{n(\Delta)} \frac{n(\Delta)! \{n(\Delta)\} r^{d-n(\Delta)+1}}{\binom{Tr}{d}} \quad (\text{Since } \binom{n(\Delta)}{\mathbf{z}(\Delta)} \le d!, \text{ and } d > n(\Delta)) \\ &\le \frac{T(T-1)\cdots(T-n(\Delta)+1)}{rT(rT-1)\cdots(rT-d+1)} d! \frac{n(\Delta)^d}{n(\Delta)!} r^{d-n(\Delta)+1} \quad (\text{Lemma 13, } \{n(\Delta)\} \le \frac{n(\Delta)^d}{n(\Delta)!}) \\ &= O\left(\frac{k^k}{r^{n(\Delta)-1}T^{d-n(\Delta)}}\right). \end{aligned} \qquad (\text{From } \frac{n(\Delta)^d}{n(\Delta)!} \le \frac{d^d}{d!}) $$

□
## A.5 Estimating the k-th moment

We can now estimate the moments. Expanding $F(k)$, we obtain from the definition in (138) that

$$F(k) = \sum_{\Gamma = \{\ell, B(\ell)\} \in \mathcal{G}(k)} \mathbb{E} \left[ \mathrm{Tr} \left[ \prod_{i=1}^{k} \mathcal{L}_{\ell_i}^{\pi}(\theta) \right] \right]. \quad (160)$$

We present the asymptotic expansion of $F(k)$ as $T \to \infty$ in the following lemma.

**Lemma 18.** Let the expectation of $F(k)$ in (107) be with respect to a random permutation $\pi \sim \mathrm{Unif}(S_m)$ and phases $\exp(i\Theta_i) \sim \mathrm{Unif}(S^1)$ for all $i \in [m]$. Then as $T \to \infty$ we have

$$F(k) = \sum_{l=1}^{k} \frac{1}{r^{l-1}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} + O\left(\frac{k!k^{2k}r^k}{T}\right). \quad (161)$$

*Proof.* We expand

$$\begin{aligned}
F(k) &= \sum_{\Gamma \in \mathcal{G}(k)} \sum_{V \in B(\Gamma)} C_{V,\Gamma} V \\
&= \sum_{l=1}^{k} \sum_{\Gamma \in \mathcal{G}(k) \atop n(\Gamma)=l} \left( \sum_{V \in B(\Gamma) \atop n(V)=l} C_{V,\Gamma} V + \sum_{\gamma \in B(\Gamma) \atop n(V)>l} C_{V,\Gamma} V \right) \\
&= I_1 + I_2.
\end{aligned} \quad (162)$$

We are left to bound both terms $I_1$ and $I_2$ from (162).

*Bound of $I_1$.* The following inequalities hold:

$$I_1 = \sum_{l=1}^{k} \sum_{\Delta \in G(k) \atop n(\Delta)=l} \sum_{\bar{\Gamma} \in \Delta \atop n(V)=l} \sum_{V \in B(\Gamma)} C_{V,\Gamma} V \quad (\text{From (131) and (138)})$$

$$= \sum_{l=1}^{k} \sum_{\Delta \in G(k) \atop n(\Delta)=l} \sum_{\bar{\Gamma} \in \Delta \atop n(V)=l} \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} W_{\Delta} \prod_{i=1}^{m} |v_i|^{2k_i} \quad (\text{Lemma 16, and (157)})$$

$$= \sum_{l=1}^{k} \sum_{\Delta \in G(k) \atop n(\Delta)=l} |\Delta| |\bar{\Gamma}| \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} W_{\Delta} \prod_{i=1}^{m} |v_i|^{2k_i} \quad (\text{From (132)})$$

$$= \sum_{l=1}^{k} \sum_{\Delta \in G(k) \atop n(\Delta)=l} |\Delta| W_{\Delta} \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} \quad (\text{From } f(\Delta) = f(\mathbf{k}))$$

$$= \sum_{l=1}^{k} \frac{1 + O(T^{-1})}{r^{l-1}} \sum_{\Delta \in G(k) \atop n(\Delta)=l} \sum_{\mathbf{k} \in \mathcal{M}(k,l)[\Delta]} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} \quad (\text{Lemma 17})$$

$$= \sum_{l=1}^{k} \frac{1}{r^{l-1}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} + O\left(\frac{r^k}{T}\right), \quad (163)$$
where in (163) we have used (147), and the bound

$$ \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} \le \sum_{\mathbf{k} \in \mathcal{M}(k)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} = \left(\sum_{i=1}^{m} |v_i|^2\right)^k \stackrel{(39)}{=} r^k. \quad (164) $$

Bound of $I_2$. Recall that if $\Gamma \in \bar{\Gamma} \in \Delta$, we have $n(\Delta) = n(\Gamma)$.

$$ I_2 = \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{\substack{\bar{\Gamma} \in \Delta \\ \Gamma \in \bar{\Gamma}}} \sum_{\substack{V \in B(\Gamma) \\ n(V)>l}} C_{V,\Gamma}V \quad (\text{From } (131), \text{ and } (138)) $$

$$ \le \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{\substack{\bar{\Gamma} \in \Delta \\ \Gamma \in \bar{\Gamma}}} \sum_{d=l+1}^{k} W_{d,\Delta} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \quad (\text{Lemma 16}) $$

$$ \le \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} |\Delta| |\bar{\Gamma}| \sum_{d=l+1}^{k} W_{d,\Delta} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} $$

$$ \le \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{d=l+1}^{k} |\Delta| W_{d,\Delta} \binom{k}{\mathbf{k}(\Delta)} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \quad (\text{From } (132)) $$

$$ \le \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{d=l+1}^{k} O\left(\frac{k^k}{r^{l-1}T^{d-l}}\right) \binom{k}{\mathbf{k}(\Delta)} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \quad (\text{Lemma 17}) $$

$$ \le O\left(\frac{k!k^k}{T}\right) \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{d=l+1}^{k} \sum_{\mathbf{g} \in \mathcal{M}(k,d)[\Delta]} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \quad (\text{From } \binom{k}{\mathbf{k}(\Delta)} \le k!) $$

$$ \le O\left(\frac{k!k^k}{T}\right) \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} \sum_{\mathbf{g} \in \mathcal{M}(k)} \binom{k}{\mathbf{g}} \prod_{i=1}^{m} |v_i|^{2g_i} \quad (\square_{d=l+1}^{k} \mathcal{M}(k,d)[\Delta] \subset \mathcal{M}(k)) $$

$$ \le O\left(\frac{k!k^k}{T}\right) \sum_{l=1}^{k} \sum_{\substack{\Delta \in G(k) \\ n(\Delta)=l}} r^k \quad (\text{From } (164)) $$

$$ \le O\left(\frac{k!k^k r^k}{T}\right) |G(k)| \\ = O\left(\frac{k!k^{2k} r^k}{T}\right), \quad (165) $$

where in (165) we have used that $|G(k)| \le k^k$. This follows from the fact that each $\Delta \in G(k)$ is in one-to-one correspondance with $f(\Delta) \in \mathfrak{F}(k)$ by Lemma 15, and the number of multiplicities that can be attained is far less than $k^k$. Combining the terms (163) and (165) yields the claim. $\square$

We are left to estimate the leading term in Lemma 18, which will finally show Lemma 2.

**Lemma 19.** Let $\{v_i\}_{i=1}^m \subset \mathbb{C}^r$ be a frame in dimension $r$ satisfying (39). There exists a constant $c > 0$ independent of $k$ and $r$ such that

$$ \sum_{l=1}^{k} \frac{1}{r^{l-1}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i} \le c r k^k. \quad (166) $$

*Proof.* Define

$$ M_l(k) = \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{m} |v_i|^{2k_i}. \quad (167) $$
In particular, from (39) and the fact that $|v_i| \le 1$ we have that for any $k \ge 1$,

$$M_1(k) = \sum_{i=1}^{m} |v_i|^{2k} \le r. \qquad (168)$$

In (167), note that up to multiplicities, there are exactly $l$ different vector norms appearing in each multinomial. From comparing coefficients, and since all are positive, we can readily see that the following inequality holds for all $l \le k$,

$$M_l(k) \le \sum_{\substack{\mathbf{b}=(b_1, \dots, b_l) \\ \sum_{i=1}^l b_i=k, b_i \ge 0}} \binom{k}{\mathbf{b}} \prod_{i=1}^l M_1(b_i). \qquad (169)$$

Using (168) in (169), and the multinomial coefficient formula

$$\sum_{\substack{\mathbf{b}=(b_1, \dots, b_l) \\ \sum_{i=1}^l b_i=k, b_i \ge 0}} \binom{k}{\mathbf{b}} \le l^k, \qquad (170)$$

yields the bound

$$M_l(k) \le r^l \sum_{\substack{\mathbf{b}=(b_1, \dots, b_l) \\ \sum_{i=1}^l b_i=k, b_i > 0}} \binom{k}{\mathbf{b}} \le r^l l^k. \qquad (171)$$

Using this last bound, we have the following inequality

$$\sum_{l=1}^{k} \frac{1}{r^{l-1}} \sum_{\mathbf{k} \in \mathcal{M}(k,l)} \binom{k}{\mathbf{k}} \prod_{i=1}^{k} |v_i|^{2k_i} \le \sum_{l=1}^{k} \frac{1}{r^{l-1}} r^l l^k \\ \le r \sum_{l=1}^{k} l^k \\ \le c r k^k, \qquad (172)$$

where in the last step we have used that there exists a constant $c > 0$ independent of $k \ge 1$ such that

$$\sum_{l=1}^{k} l^k \le c \int_{1}^{k} x^k dx \le c \frac{k^{k+1}}{k+1} \le ck^k. \qquad (173)$$

□

# B Appendix on numerical experiments

Our implementation code in Python can be shared upon request. The following are other comments about the implementation.

* *Projection on the tangent space:* Consider $U(\delta) = \exp(\delta A)U$ in (100) and differentiate with respect to $\delta$. If we let $UE_iU^\dagger = P_i(U)$, by evaluating the gradient at $\delta = 0$ we obtain its projection onto the tangent space of $U(n)$ at $U$, which is

$$P_n(U) = \sum_{i=1}^{n} \left( \rho P_i(U) \tau P_i(U) - P_i(U) \tau P_i(U) \rho \right) + \left( \tau P_i(U) \rho P_i(U) - P_i(U) \rho P_i(U) \tau \right). \quad (174)$$

This matrix is skew-symmetric and belongs to the Lie algebra of $U(n)$.
* *Initialization of quantum states:* We initialize $\rho$ by evaluating $W \sim \text{Unif}(U(r))$, the vector $d = (d_1, \dots, d_r)$ uniformly distributed in the simplex, and setting $\rho = W \text{Diag}(d) W^\dagger$, where $\text{Diag}(d)$ is the matrix with $d$ in the diagonal and zeros elsewhere. We perform a similar, and independent initialization of $\tau$.

* *Landscape complexity:* From trying different settings, our simulations suggests that there are several local maxima or saddle points in the optimization landscape of (15), and convergence to those is dependent on the initialization.