Local measurement strategies for multipartite entanglement quantification

In this work, we consider the estimation of the family of multipartite entanglement measures defined in Ref. Beckey et al. (2021). This family includes the pure state entanglement measures from Refs. Meyer and Wallach (2002); Brennen (2003); Carvalho et al. (2004) as special cases and has several properties that make them interesting (see Ref. Beckey et al. (2021) for details). That work shows how to compute the measures using a parallelized controlled-SWAP circuit, which requires two identical copies of an $n$-qubit state and $n$ ancillary qubits. In a follow-up work Beckey et al. (2023), the requirements were decreased to two identical copies of the state of interest using Bell basis measurements. Still, creating two identical copies of a moderately-sized quantum state and acting coherently on it is at the cutting edge of quantum information processing Bluvstein et al. (2022, 2023).

Before constructing estimators of the CEs, we must introduce the quantities themselves. To that end, we now define the CEs and mention some useful facts about them.

Crucial to the present work is the following expression for the CEs Beckey et al. (2023)

where $\Pi_{+}^{i}:=\mathbb{I}_{1}\otimes\dotsm\otimes\mathbb{I}_{i-1}\otimes\Pi_{+}^{i}\otimes\mathbb{I}_{i+1}\otimes\dotsm\otimes\mathbb{I}_{n}$ denotes the symmetric subspace projector on the $i$-th qubit of the first and second copy of $\rho$ and identities for all $j\in S$ such that $j\neq i$. Note this convention for the representation of operators is used throughout.

Importantly, when $S=[n]$, the CE is related to the multipartite concurrence defined in Ref. Carvalho et al. (2004), denoted $c_{n}(|\psi\rangle)$, via the simple expression

which is the measure Ref. Ohnemus et al. (2023) consider estimating using local random measurements. Our results will hold for that measure as well as all others obtained by choice of any $S\subseteq[n]$. While there are many interesting formulas for the CEs given in Refs. Beckey et al. (2021, 2023), these will suffice to appreciate our main results. We now turn to some facts from classical statistics that will be needed to prove our sample complexity upper bounds.

In this work, we will work exclusively with bounded random variables $X_{1},\dots,X_{M}$, such that each $X_{i}\in[a,b]$ and $a,b\in\mathbb{R}$. We will denote the expectation value of a random variable $X$ by $\mathbb{E}[X]$ and its variance by $\textnormal{Var}(X)$. We denote the covariance of two (possibly dependent) random variables $X$ and $Y$ by $\textnormal{Cov}[X,Y]=(X-\operatorname{\mathbb{E}}[X])(Y-\operatorname{\mathbb{E}}[Y])$. We denote estimators of statistical quantities with hats. For example, if the actual parameter of interest is denoted $\theta$, we will denote an estimator of the parameter as $\hat{\theta}$. We say an estimator is unbiased if $\operatorname{\mathbb{E}}[\hat{\theta}]=\theta$. Many of our estimators will be expressed using indicator functions, which are defined as

For example, given a fixed, length $s$ bitstring $\boldsymbol{z}_{0}\in\{0,1\}^{s}$, $\textnormal{ind}[\boldsymbol{Z}=\boldsymbol{z}_{0}]$ takes the value $1$ when the random variable $\boldsymbol{Z}$ is equal to $\boldsymbol{z}_{0}$, and takes the value $0$ otherwise. Crucially, the probability of obtaining a particular bitstring, $\boldsymbol{z}_{0}$ can be expressed as $\operatorname{\mathbb{E}}[\textnormal{ind}[\boldsymbol{Z}=\boldsymbol{z}_{0}]]=P(\boldsymbol{z}_{0}).$ Note that we will use uppercase letters to denote random variables, and the corresponding lowercase letter to denote a specific instance of the random variable.

In practice, finite sample statistics prohibit us from exactly determining quantities of interest. A natural approach is then to ask how many measurements are sufficient to guarantee that our estimate is close to the true value with high probability. This is a well-studied problem in classical statistics and results in so-called sample complexity upper bounds. We now present the two methods that will allow us to provide analytical performance guarantees on our estimators of multipartite entanglement.

We start with a well-known result called Hoeffding’s inequality, which provides exponential concentration for sums of independent bounded random variables. We will state it without proof as it is a standard result proven in most mathematical statistics textbooks (e.g. Sec. 2.2 of Ref. Vershynin (2018)).

If, however, the random variables in question have a large allowed range (but small variance), Hoeffding will often be looser than bounds that utilize the information about this second moment. In other words, the number of measurements required to achieve $\epsilon$-precision will be overestimated. To provide stronger concentration, we will make use of MoM estimation (e.g. Sec. 2.3 of Ref. Lerasle (2019)).

Both of these results allow us to derive analytical performance guarantees in the form of upper bounds on the sample complexity of an estimator. With these preliminaries in mind, we turn now to our main results.

As mentioned above, randomized measurements have been studied in many estimation tasks, but most relevant to our work is the recent work of Ref. Ohnemus et al. (2023) in which the authors present a method of estimating the multipartite concurrence Carvalho et al. (2004) using local randomized measurement data. Because one recovers the generalized concurrence easily from the CEs (see Eq. (6)), Ref. Ohnemus et al. (2023) is easily generalizable to the entire family of CEs.

As depicted in Fig. 1, the LRM protocol entails preparing the state of interest, applying $U=\prod_{i=1}^{n}U_{i}$, where each $U_{i}$ is taken from some single qubit matrix distribution (e.g. Haar distribution or single-qubit Cliffords Mele (2023)), to our state and then measuring in the computational basis $\{|\mathbf{z}\rangle\}$. Note that This yields a bitstring $\mathbf{z}$, where $\boldsymbol{z}:=z_{1}\cdot z_{2}\cdot\dotsm z_{n}$, with $z_{i}\in\{0,1\}$, and where the probability of obtaining $\mathbf{z}$ is given as $P(\mathbf{z})=\textnormal{tr}\left[U\rho U^{\dagger}|\hskip 1.0pt\mathbf{z}\rangle\langle\mathbf{z}\hskip 1.0pt|\right]$. Note that if one only cares about a subset $S\subseteq[n]$ of qubits, then one can restrict the unitary rotation and subsequent computational basis measurement to the subsystems defined by $S$. Specifically, this corresponds to rotation by the unitary $U=\prod_{i\in S}U_{i}$, by which mean $U_{i}\in U(2)$ is a unitary acting on the $i$th qubit for $i\in S$, and we implicitly assume that the action of the unitary is trivial (i.e., $\openone$) on qubits not in the set $S$. We then have the following proposition.

The proof of this theorem relies on the fact that

which follows from Schur’s lemma and Eq. (5). We include a detailed proof in Appendix B.1. Crucially, we emphasize that this holds for any fixed bitstring $\mathbf{z}\in\{0,1\}^{s}$. Because this expression is equally valid for all bitstrings, it follows that we can simply take a uniform average over all bitstrings

which is a crucial experimental consideration because the probability of obtaining any particular bitstring decays exponentially with the number of qubits being probed. Moreover, taking such an average enables improved statistical estimators for two key reasons. First, as we will see below, the uniform average allows us to reduce the constant factor that appears in the sample complexity from $3^{s}$ to $\left(\frac{3}{2}\right)^{s}$. And second, the uniform average allows us to focus on estimating the sum of squared probabilities, rather than the squared probabilities themselves. As we will see, this is exponentially more efficient in terms of classical post-processing for many cases of interest.

In practice, one cannot compute this average exactly over the Haar measure, but instead samples $L$ unitaries from the Haar measure (or a unitary design of the appropriate degree Mele (2023)) and approximates the exact average. Moreover, Eq. (10) depends on the probability, at a fixed unitary, of obtaining the bitstring $\mathbf{z}$. This too, cannot be computed exactly, but is estimated by repeating, for each random unitary, the computational basis measurement $K$ times and taking the sample average. This yields a total measurement budget of $M=LK$. Because of these two sources of finite-sampling error, providing convergence guarantees for estimators based on LRM data can be challenging, with many groups resorting to various approximations, special cases, or numerical simulations Brydges et al. (2019); Elben et al. (2018, 2019); Vermersch et al. (2018); Ohnemus et al. (2023). While these methods are still informative, it would be preferable to obtain analytical performance guarantees. Before showing how to obtain such guarantees, let us understand the methods used in Ref. Ohnemus et al. (2023), where they construct unbiased estimators of $P^{2}_{U}(\mathbf{z})$ to then approximate the actual quantity of interest $\operatorname{\mathbb{E}}_{U}[P_{U}(\mathbf{z})^{2}]$.

To understand their result, let $\boldsymbol{z}\in\{0,1\}^{s}$ denote a bitstring resulting from an LRM as depicted in Fig. 1. Ohnemus et al. Ohnemus et al. (2023) show that

is an unbiased estimator of the squared probability $P_{U}(\boldsymbol{z})^{2}$, for a fixed unitary $U$. Here, $\widehat{P}_{U}({\boldsymbol{z}})=\frac{1}{K}\sum_{k=1}^{K}\textnormal{ind}[\boldsymbol{Z}_{k}=\boldsymbol{z}]$ denotes the fraction of the $K$ outcomes equal to $\boldsymbol{z}$. However, the classical run-time of estimating each probability is $O(K)$, and there are $2^{s}$ terms in the sum that appears in Eq. (12). Thus, the classical post-processing scales exponentially in the number of subsystems being probed, i.e. $O(K2^{s})$. Moreover, proving upper bounds on the sample complexity of the CEs is difficult if one estimates the squared probabilities. Hoeffding’s inequality and the union bound give an analytical sample complexity upper bound, but it is very loose. Alternatively, one could attempt to compute or bound the variance of this estimator and use the Chebyshev-Cantelli inequality, as done in Ref. Ohnemus et al. (2023), but this requires control of up to the fourth moment of a multinomial distribution, which is difficult to compute for general input states. We address these limitations with a simple shift in the estimation procedure.

As mentioned previously, the sample complexity of an estimation protocol is not the only relevant experimental consideration. While each measurement setting used in LRMs is easily implementable, we saw above that guaranteeing $\epsilon$-close estimation of the CEs requires an exponential number of measurement settings. Inspired by Ref. Stricker et al. (2022), we propose a “de-randomization” of the LRM protocol that requires only a single experimental setting. That such a protocol is possible follows from Eq. (5) and the definition of a projective 2-design Scott (2006) as stated below.

From this definition and Schur’s lemma, we have

where $\mathbb{E}_{\phi}[(|\hskip 1.0pt\phi\rangle\langle\phi\hskip 1.0pt|)^{\otimes 2}]:=\sum_{i}p_{i}(|\phi_{i}\rangle\langle\phi_{i}|)^{\otimes 2}$. Note that the state in $\mathbb{E}_{\phi}[(|\hskip 1.0pt\phi\rangle\langle\phi\hskip 1.0pt|)^{\otimes 2}]$ denotes a random variable while $|\hskip 1.0pt\phi_{i}\rangle\langle\phi_{i}\hskip 1.0pt|$ is a specific state. Thus, we may estimate all of the CEs by appropriately post-processing the measurement data from any POVM that also forms a projective 2-design. This motivates the following theorem.

The proof is a direct application of Eq. (23) and Eq. (5), keeping in mind that each $|\hskip 1.0pt\phi\rangle\langle\phi\hskip 1.0pt|$ is independent. The details are provided in Appendix B.2.

While Thm. 3 holds for all projective 2-designs, we will restrict our attention to SIC POVMs, because they are minimal among single-qubit projective $2$-designs. That is, they saturate the lower bound on the number of elements, $N$, needed to form a projective $t$-design in a $d$-dimensional space Scott (2006)

which becomes $N\geqslant 4$ for $2$-designs for the $2$-dimensional case on which we focus. Their minimal nature has important bearing on experimental implementations. Because the size of ancillary space required for implementation through Neumark’s (Naimark’s) Theorem (see Supp. Theorem A.1) is proportional to the number of design elements Chen et al. (2007), SIC POVMs are the cheapest to implement experimentally. We refer the reader to Refs. Renes et al. (2004); Scott (2006); Fuchs et al. (2017) for more about SICs generally, and to Ref. Scott (2006) for a detailed overview of SICs and projective 2-designs as we use them.

For qubits, and as depicted in Fig. 3c), the simplest SIC has the following 4 elements

which obey the following relation,

By defining $|\tilde{\phi}_{i}\rangle=\frac{1}{\sqrt{2}}|\phi_{i}\rangle$, we can turn these SIC elements into a well-defined POVM satisfying

With this notation in place, we can state a corollary to Theorem 3 that yields a very simple expression for the CEs via local SICs.

Because we do not have to average over unitaries as in LRMs, the finite sampling error incurred when estimating Eq. (30) will only be due to approximating the probability of obtaining a particular bitstring. This important distinction between SICs and LRMs means we just need to estimate the sum of the squared probabilities obtained from a local SIC measurements. While this theorem implies one can quantify multipartite entanglement with a single experimental measurement setting, this simplicity comes at the cost of implementing a generalized POVM.

As shown schematically in Fig. 3, this can be achieved by employing one additional ancilla qubit for each system qubit Chen et al. (2007) or, as has been demonstrated experimentally in Refs. Stricker et al. (2022); Fischer et al. (2022), by encoding qubit states into 4-dimensional qudits (ququarts). Experimentally, Cor. 3 amounts to transforming each state-ancilla qubit pair or ququart by the unitary $U_{\mathrm{SIC}}^{\dagger}$, where

and then performing a computational basis measurement. The construction of $U_{\mathrm{SIC}}$ follows from Neumark’s Theorem, which we prove carefully in Appendix A.1 for the reader’s convenience. The intuition is to convert the SIC elements into a $4$-dimensional orthonormal basis by appending to each $|\tilde{\phi}_{i}\rangle$ a respective $|\tilde{\phi}^{\perp}_{i}\rangle$ such that $\langle\tilde{\phi}_{i}\hskip 1.0pt|\hskip 1.0pt\tilde{\phi}^{\perp}_{i}\rangle=0$.

An estimator based on SIC POVMs follows naturally from Theorem 1 and Eq. (5). Because we saw that MoM gives tighter sample complexity upper bounds, we focus only on MoM estimation for SICs.

The proof of this theorem can be found in Appendix B.1. Note that we have restricted our attention to the $K=2$ case in the main text. Evidently, this sample complexity is substantially worse than the LRMs. We can improve upon this by optimizing the number of samples used to construct a single estimate of the CE using SIC measurements (i.e. by optimizing $K$). As we show in Appendix B.2, the optimal value of $K$ is given as

which corresponds to the value of $K$ that minimizes the bound on the variance of the estimator for CE determined by SIC measurements. As shown in Appendix B.2, setting $K=K_{\mathrm{opt}}$ and appropriately modifying Theorem 4, it follows that $O\left(\left[\left(\frac{3}{2}\right)^{s}\epsilon^{-2}+\sqrt{3^{s}}\epsilon^{-1}\right]\log\left(\frac{1}{\delta}\right)\right)$ total measurements are sufficient to guarantee that

With this optimization, we have shown that using a single experimental measurement setting, one can obtain an upper bound on the sample complexity that is similar to the bound obtained for LRMs, which requires an exponential number of different measurement settings. However, as noted in Table 1, the classical post-processing in this optimized case is more costly. Moreover, the local measurement itself is more difficult to implement than in the case of the simple projective measurements used in LRM protocols.

Nonetheless, we hope that our results will be useful to experimentalists that would like to quantify multipartite entanglement without the need to prepare and coherently manipulate multiple identical copies of a quantum state. While this capability is becoming possible on neutral atom platforms Bluvstein et al. (2022, 2023), it remains very challenging on other architectures.

Our motivation in this work was to improve upon protocols in the literature and find the most resource efficient method for multipartite entanglement quantification using only local measurements. While we have accomplished this, we also aimed to provide tools that experimentalists can use in current and near-term experiments where states are not perfectly pure. While there are a number of ways one could quantify mixed state entanglement, we sketch one technique to which the methods above could be directly applied.

Our motivation in this work was to optimize and compare various methods of quantifying pure state multipartite entanglement using only local POVMs. As such, we focused on pure states with ideal unitary evolution and perfect measurements. While this question is of theoretical interest, to be useful in practice, one must be able to handle mixed states. While we save the full treatment of mixed states for a future work (more on this below), we mention here one potential way forward that would utilize our results here.

A standard method of extending pure state entanglement measures to mixed state ones is via a convex roof extension Bennett et al. (1996); Uhlmann (2010). This was done for the CEs in Ref. Beckey et al. (2023), but we sketch the argument here to illustrate the main points. The convex roof extension can be expressed as

where the infimum is over the set of decompositions of the form $\rho=\sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$, with $p_{i}\geqslant 0$ for all $i$ and $\sum_{i}p_{i}=1$. Because this optimization is generally difficult, one often considers a lower bound on Eq. (36). We will show how one could construct such lower bounds for the CEs and compute them from local measurement data alone, allowing one to bound the mixed state entanglement within the above framework developed for estimating pure state entanglement.

First we note that the bipartite concurrence Wootters (2001); Rungta et al. (2001) of a pure quantum state $|\psi\rangle_{AB}$ can be expressed as

We can use this to express the CE in terms of the bipartite concurrences by defining $c_{\alpha}:=\sqrt{2(1-\textnormal{tr}\left[\rho_{\alpha^{2}}\right])}$, leading to

Then, one could use the observable lower bound on the bipartite concurrence introduced in Ref. Mintert and Buchleitner (2007) to construct a lower bound on the CEs. For example, when the $S=[n]$ and the CE is simply related to the multipartite concurrence of Ref. Carvalho et al. (2004), one obtains a lower bound of the form

Throughout this work, we have shown how to estimate the last term using various local measurement strategies. The middle term depends only on the quantum state’s purity, $\textnormal{tr}\left[\rho^{2}\right]$. There exists a number of theoretical van Enk and Beenakker (2012); Elben et al. (2019) and experimental Daley et al. (2012); Islam et al. (2015); Kaufman et al. (2016); Vermersch et al. (2018); Brydges et al. (2019) works showing how to estimate the purity of quantum states using local random measurements, and local SICs were implemented experimentally in Ref. Stricker et al. (2022) to estimate purity. In fact, the purity of a quantum state is a quantity of great practical interest in its own right, and we suspect our results will be of interest to those researchers interested in proving rigorous performance guarantees on its estimation.

Coupled with these results from the literature, one could use the framework and techniques described above to probe mixed state entanglement in this manner. We further note that, for high-purity states that are becoming increasingly common in today’s state of the art experiments, this bound is very close to the pure state theoretical value. This can be seen by noting that $C_{|\psi\rangle}([n])-\mathcal{C}_{\rho}^{\ell}([n])=(1-2^{-n})(1-\textnormal{tr}\left[\rho^{2}\right]),$ which is very close to zero for nearly pure states.

Such a procedure described above would generalize the method used in Ref. Ohnemus et al. (2023) for the multipartite concurrence Mintert et al. (2005); Mintert and Buchleitner (2007), but is just one possible extension of our methods to mixed state entanglement. There have been a number of interesting works in the recent years that use local random measurement strategies to probe mixed state entanglement Elben et al. (2020); Neven et al. (2021); Vermersch et al. (2023), and exploring the connections between our proposed method and theirs is an interesting direction we save for future work.