Introduction
The entanglement entropy has emerged as a fundamental quantity for characterizing quantum many-body systems. In states prepared by quantum simulators and similar devices, quantities like the von Neumann entropy and its Rényi counterparts are capable of capturing correlations between interacting qubits in a basis-independent way, without reliance on the knowledge of a broken symmetry or local order parameter. This allows the entanglement to provide signatures of a wide variety of exotic phenomena in closed pure systems, for example topological order [1 , 2 ] or quantum criticality [3 , 4 ] , where universal quantities can emerge in the scaling of the entanglement entropy. More generally, in open, noisy, or otherwise mixed-state systems, recent work has emphasized how some phenomena may be invisible to observables expressed as linear functions of the averaged density matrix, requiring nonlinear information quantities [5 , 6 , 7 ] . Thus the entanglement entropies and related quantities are increasingly playing a central role in identifying exotic phenomena at the frontier of the field, such as measurement-induced phase transitions [8 , 9 ] , quantum-error-correcting phases [10 , 11 ] , and separable and long-range entangled mixed states [12 , 13 , 14 ] .
On an experimental quantum hardware platform that prepares a many-body quantum state, the ability to estimate entanglement entropy and related quantities thus plays a key role. Unlike in in silico simulations, information about an experimental quantum state can only be accessed by measurement. The resource cost that each measurement requires means that quantities that rely on a brute-force tomographic reconstruction of a density matrix, such as the von Neumann entanglement entropy, will be experimentally inaccessible in a many-qubit system. However, other entanglement measures, in particular the integer-order Rényi entropies S ( n ) S^{(n)} S ( n ) , admit direct estimators that are accessible without quantum state tomography.
For an integer n n n , estimating the n t h n^{\mathrm{th}} n th -order Rényi entropy S ( n ) = 1 1 − n log Tr ( ρ n ) S^{(n)} = \frac{1}{1-n}\log\operatorname{Tr}(\rho^n) S ( n ) = 1 − n 1 log Tr ( ρ n ) amounts to evaluating Tr ( ρ n ) \operatorname{Tr}(\rho^n) Tr ( ρ n ) , which can be expressed as the expectation value of a cyclic permutation operator acting on n n n identical replicas of the density matrix ρ \rho ρ [3 ] . The simplest case is n = 2 n=2 n = 2 , for which existing experimental approaches broadly fall into two classes. The first category relies on preparing two physical copies of the quantum state, and directly exploits the equivalence between the purity Tr ( ρ 2 ) \operatorname{Tr}(\rho^2) Tr ( ρ 2 ) and the SWAP expectation value, Tr ( ρ 2 ) = Tr [ SWAP ( ρ ⊗ ρ ) ] \operatorname{Tr}(\rho^2)=\operatorname{Tr}[\operatorname{SWAP}(\rho\otimes\rho)] Tr ( ρ 2 ) = Tr [ SWAP ( ρ ⊗ ρ )] , where SWAP = ∑ i , j ∣ i j ⟩ ⟨ j i ∣ \operatorname{SWAP}=\sum_{i,j}|ij\rangle\langle ji| SWAP = ∑ i , j ∣ ij ⟩ ⟨ j i ∣ in the standard tensor-product basis. Using interference between the two copies, the purity Tr ( ρ 2 ) \operatorname{Tr}(\rho^2) Tr ( ρ 2 ) can be converted into an observable directly measurable in the experiment [15 , 16 , 17 , 18 ] . The second class of methods uses only a single copy of the system and relies on the idea that the SWAP-operator expectation value can be reconstructed from the statistics of a single copy of the quantum state evolved under Haar-random unitaries [19 , 20 , 21 ] .
Due to the limited number of qubits available on current atomic, molecular, and optical (AMO) platforms, single-copy protocols offer a significant practical advantage since they avoid the need to prepare multiple identical copies of the system simultaneously. While there is evidence that multi-copy coherent methods can reduce the sample complexity [22 ] , the SWAP operator requires coherent two-qubit gates acting between copies. These are considerably more challenging to implement experimentally than single-qubit rotations [23 , 24 , 25 , 26 ] , which are all that is required for the single-copy randomized protocol. Specifically, the single-copy randomized protocol measures the state under the action of N U N_U N U random unitary operations, collecting N M N_M N M samples for each unitary. Since the unitaries can be chosen as tensor products of single-qubit random unitaries, this procedure is equivalent to measuring the state in a set of random local bases. From these measurement results, an estimate of S ( 2 ) S^{(2)} S ( 2 ) can be constructed as we describe below.
A key subtlety of this method is that the optimal ratio N U / N M N_U/N_M N U / N M is state-dependent. For example, a maximally mixed state has exactly basis-independent ideal outcome probabilities, so only the finite-shot empirical frequencies vary across different unitaries. In this case, it is more efficient to sample fewer unitaries but perform more measurements per unitary, making N M N_M N M more important than N U N_U N U . In contrast, a product state can exhibit strong basis dependence: there exist bases in which the state is aligned with a computational basis vector, as well as bases in which the measurement outcomes appear completely random. Accurately capturing this variation across bases requires sampling many different unitaries, making N U N_U N U the more important resource in this case. Using a suboptimal parameter ratio could require significantly more experimental resources to reach the same estimation error.
In this work, we build on previous statistical analyses of the randomized measurement protocol to develop an adaptive sampling scheme for S ( 2 ) S^{(2)} S ( 2 ) . Starting from small initial values of N U N_U N U and N M N_M N M , we iteratively update the ratio N U / N M N_U/N_M N U / N M as more measurement data are collected. This update is guided by the information obtained from earlier measurements. All measurement data used in this work are simulated by sampling from computed probabilities. We show that, for representative states covering the maximal, minimal, and intermediate purity values, this adaptive procedure makes the final resource allocation converge to a near-optimal ratio between N U N_U N U and N M N_M N M ; we therefore expect the same behavior for states with arbitrary purity. This effectively extends the randomized protocol into a state-blind method with no additional experimental resource overhead.
Procedure
Randomized Measurement Protocol for Rényi Entropy Revisited
Standard Randomized Protocol
In this section, we briefly review the randomized measurement protocol for estimating the second-order Rényi entropy. Consider a system of N N N interacting qubits and let A A A be a subsystem containing N A N_A N A qubits. The second-order Rényi entropy of A A A is [21 , 27 ]
S ( 2 ) ( ρ , A ) = − log 2 ( Tr [ ρ A 2 ] ) , (1) S^{(2)}(\rho,A)=-\log_2\left(\operatorname{Tr}\left[\rho_A^2\right]\right), \tag*{(1)} S ( 2 ) ( ρ , A ) = − log 2 ( Tr [ ρ A 2 ] ) , (1)
Table 1.
where ρ A \rho_A ρ A is the reduced density matrix of subsystem A A A , obtained from the full system density matrix ρ \rho ρ . From Eq. (1) , S ( 2 ) S^{(2)} S ( 2 ) is fully determined by the purity p ( ρ , A ) ≡ Tr [ ρ A 2 ] p(\rho,A)\equiv\operatorname{Tr}\left[\rho_A^2\right] p ( ρ , A ) ≡ Tr [ ρ A 2 ] .
In the randomized measurement protocol, the state is measured under the action of N U N_U N U random unitaries, with N M N_M N M measurement shots collected for each unitary (Algorithm 1). Throughout this work, the unitaries are drawn from a local unitary 2-design, i.e., tensor products of independently chosen single-qubit random Clifford unitaries [28 ] . For this ensemble, the purity of a subsystem A A A of N A N_A N A qubits can be written as [21 ]
p ( ρ , A ) = 2 N A E U [ p U W p U ] , (2) p(\rho,A)=2^{N_A}\mathbb{E}_U\left[p_U W p_U\right], \tag*{(2)} p ( ρ , A ) = 2 N A E U [ p U W p U ] , (2)
where E U [ ⋅ ] \mathbb{E}_U[\cdot] E U [ ⋅ ] denotes the average over the unitary ensemble, p U p_U p U is the column vector with entries
( p U ) s = p U ( s ) = ⟨ s ∣ U ρ A U † ∣ s ⟩ , (3) (p_U)_s=p_U(s)=\langle s|U\rho_AU^\dagger|s\rangle, \tag*{(3)} ( p U ) s = p U ( s ) = ⟨ s ∣ U ρ A U † ∣ s ⟩ , (3)
collecting the probabilities of measuring each bitstring s ∈ { 0 , 1 } N A s\in\{0,1\}^{N_A} s ∈ { 0 , 1 } N A on subsystem A A A after the state is transformed by U U U , and the Hamming kernel W W W is defined entrywise by
W s s ′ = ( − 2 ) − D [ s , s ′ ] , (4) W_{ss'}=(-2)^{-D[s,s']}, \tag*{(4)} W s s ′ = ( − 2 ) − D [ s , s ′ ] , (4)
where D [ s , s ′ ] D[s,s'] D [ s , s ′ ] is the Hamming distance between s s s and s ′ s' s ′ , i.e., the number of bits on which the two strings differ.
To write the estimator in a more compact operator form, we define the diagonal operator acting on two copies of subsystem A A A ,
X ≡ 2 N A ∑ s , s ′ W s s ′ ∣ s , s ′ ⟩ ⟨ s , s ′ ∣ , (5) X\equiv2^{N_A}\sum_{s,s'}W_{ss'}|s,s'\rangle\langle s,s'|, \tag*{(5)} X ≡ 2 N A s , s ′ ∑ W s s ′ ∣ s , s ′ ⟩ ⟨ s , s ′ ∣ , (5)
where ∣ s , s ′ ⟩ ≡ ∣ s ⟩ ⊗ ∣ s ′ ⟩ |s,s'\rangle\equiv|s\rangle\otimes|s'\rangle ∣ s , s ′ ⟩ ≡ ∣ s ⟩ ⊗ ∣ s ′ ⟩ , and its unitary transformed version
X U = U † ⊗ 2 X U ⊗ 2 , U ⊗ 2 ≡ U ⊗ U . (6) X_U=U^{\dagger\otimes2}XU^{\otimes2},\qquad U^{\otimes2}\equiv U\otimes U. \tag*{(6)} X U = U †⊗ 2 X U ⊗ 2 , U ⊗ 2 ≡ U ⊗ U . (6)
We also write
X U ≡ Tr [ X U ρ A ⊗ 2 ] (7) \mathcal{X}_U \equiv\operatorname{Tr}[\mathcal{X}_U \rho_A^{\otimes2}] \tag*{(7)} X U ≡ Tr [ X U ρ A ⊗ 2 ] (7)
to emphasize that X U \mathcal{X}_U X U is the real scalar obtained from the Hilbert–Schmidt inner product between X U \mathcal{X}_U X U and ρ A ⊗ 2 \rho_A^{\otimes2} ρ A ⊗ 2 . The key identity behind Eq. (2) is that the ensemble average of X U \mathcal{X}_U X U over a unitary 2-design equals the SWAP operator [19 , 20 ] ,
E U [ X U ] = E U [ U † ⊗ 2 X U U ⊗ 2 ] = S W A P . (8) \mathbb{E}_U[\mathcal{X}_U]=\mathbb{E}_U[U^{\dagger\otimes2}X_UU^{\otimes2}]=\mathrm{SWAP}. \tag*{(8)} E U [ X U ] = E U [ U †⊗ 2 X U U ⊗ 2 ] = SWAP . (8)
Using this relation, Eq. (2) follows from a few lines of algebra.
Experimental Estimator of Purity
In experiments, the probabilities P U ( s ) P_U(s) P U ( s ) are not accessible and they need to be estimated from measurement records. Simply replacing each P U ( s ) P_U(s) P U ( s ) in Eq. (2) by the empirical frequency c U ( s ) / N M c_U(s)/N_M c U ( s ) / N M , where c U ( s ) c_U(s) c U ( s ) is the count for string s s s under unitary U U U , yields a biased estimator since purity is quadratic in outcome probabilities, and in general squaring an unbiased estimator for P U ( s ) P_U(s) P U ( s ) will be a biased estimator of P U ( s ) 2 P_U(s)^2 P U ( s ) 2 . An exactly unbiased estimator for X U \mathcal{X}_U X U is given by [29 ]
X ^ U ≡ 2 N A ( N M ) 2 ∑ i , j ∣ i ≠ j W s i s j , (9) \widehat{\mathcal{X}}_U \equiv\frac{2^{N_A}}{(N_M)_2}\sum_{i,j\mid i\ne j}W_{s_i s_j}, \tag*{(9)} X U ≡ ( N M ) 2 2 N A i , j ∣ i = j ∑ W s i s j , (9)
where i i i and j j j are sample indices labeling the i t h i^{\mathrm{th}} i th and j t h j^{\mathrm{th}} j th measurement shots, while s i s_i s i and s j s_j s j are the corresponding outcome strings. The sum ∑ i , j ∣ i ≠ j \sum_{i,j\mid i\ne j} ∑ i , j ∣ i = j denotes that we are summing over both indices i i i and j j j , subject to the constraint i ≠ j i\ne j i = j . The notation n k = n ! / ( n − k ) ! n^k=n!/(n-k)! n k = n ! / ( n − k )! denotes the falling factorial of n n n .
The quantity X ^ U \widehat{\mathcal{X}}_U X U is an unbiased estimator of X U \mathcal{X}_U X U in the sense that E s h o t s ( X ^ U ∣ U ) = X U \mathbb{E}_{\mathrm{shots}}(\widehat{\mathcal{X}}_U\mid U)=\mathcal{X}_U E shots ( X U ∣ U ) = X U , where E s h o t s ( ⋅ ∣ U ) \mathbb{E}_{\mathrm{shots}}(\cdot\mid U) E shots ( ⋅ ∣ U ) denotes the average over the sample space of all N M N_M N M -shot outcome sequences, Ω = { ( s 1 , … , s N M ) : s i ∈ { 0 , 1 } N A } \Omega=\{(s_1,\ldots,s_{N_M}):s_i\in\{0,1\}^{N_A}\} Ω = {( s 1 , … , s N M ) : s i ∈ { 0 , 1 } N A } for a given unitary U U U . It can also be viewed as an unbiased estimator for purity in the sense that
E U [ E s h o t s ( X ^ U ∣ U ) ] = E U [ X U ] = p ( ρ , A ) . (10) \mathbb{E}_U\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)\right]=\mathbb{E}_U[\mathcal{X}_U]=p(\rho,A). \tag*{(10)} E U [ E shots ( X U ∣ U ) ] = E U [ X U ] = p ( ρ , A ) . (10)
In outcome space, we may write the estimator in terms of counts only,
X ^ U = 2 N A ( N M ) 2 ( c U T W c U − N M ) , (11) \widehat{\mathcal{X}}_U=\frac{2^{N_A}}{(N_M)^2}\left(\mathbf{c}_U^{\mathsf{T}}\mathbf{W}\mathbf{c}_U-N_M\right), \tag*{(11)} X U = ( N M ) 2 2 N A ( c U T W c U − N M ) , (11)
where the count vector c U \mathbf{c}_U c U , defined by ( c U ) s A ≡ c U ( s A ) (c_U)_{s_A}\equiv c_U(s_A) ( c U ) s A ≡ c U ( s A ) , collects the counts for each possible outcome string s A s_A s A . We provide a self-contained proof of Eq. (10) and Eq. (11) in Appendix A based on results in Refs. [29 , 30 ] .
Since the average of unbiased estimators is still unbiased, in the actual implementation of the protocol we use
p ^ ≡ 1 N U ∑ r = 1 N U X ^ U r (12) \widehat{p}\equiv\frac{1}{N_U}\sum_{r=1}^{N_U}\widehat{\mathcal{X}}_{U_r} \tag*{(12)} p ≡ N U 1 r = 1 ∑ N U X U r (12)
as the estimator for purity. It is unbiased in the sense that E U 1 , … , U N U [ E s h o t s ( p ^ ∣ U 1 … U N U ) ] = p ( ρ , A ) \mathbb{E}_{U_1,\ldots,U_{N_U}}[\mathbb{E}_{\mathrm{shots}}(\widehat{p}\mid U_1\ldots U_{N_U})]=p(\rho,A) E U 1 , … , U N U [ E shots ( p ∣ U 1 … U N U )] = p ( ρ , A ) . We remark that the unbiasedness is exact when the parameters N U N_U N U and N M N_M N M are fixed across all trials; in the adaptive scheme, where these parameters become data-dependent, we do not claim that the final estimator remains exactly unbiased. However, since the final allocation ( N U , N M ) (N_U,N_M) ( N U , N M ) concentrates across independent trials for any given state (Figure 1 ), the estimator effectively behaves as a fixed-parameter estimator at the concentrated allocation, and we expect any deviation from unbiasedness to be negligible. We also do not claim that taking the logarithm of p ^ \widehat{p} p yields an exactly unbiased estimator of S ( 2 ) S^{(2)} S ( 2 ) ; in practice this bias is negligible, and the same plug-in estimator has been used in previous work to estimate S ( 2 ) S^{(2)} S ( 2 ) [21 ] .
Figure 1. Demonstration of the adaptive protocol for estimating the second Rényi entropy S ( 2 ) S^{(2)} S ( 2 ) on the half-system partition of four classes of 8-qubit states: random mixed states (whose reduced states are nearly maximally mixed), Haar-random pure states (whose reduced states are nearly maximally mixed at large system sizes), GHZ states, and product states. Results are collected from 500 independent adaptive trials with a total experimental budget of N t o t = 20000 N_{\mathrm{tot}}=20000 N tot = 20000 , starting from N U ( 0 ) = 2 N_U^{(0)}=2 N U ( 0 ) = 2 and N M ( 0 ) = 4 N_M^{(0)}=4 N M ( 0 ) = 4 with step sizes Δ N U = Δ N M = 2 \Delta N_U=\Delta N_M=2 Δ N U = Δ N M = 2 . Left column: Histograms of the final estimated S ( 2 ) S^{(2)} S ( 2 ) . The solid vertical line marks the exact entropy value, and the dashed vertical line denotes the mean estimate over the 500 trials. The estimates are approximately normally distributed around the exact value for all four classes of states tested. Right column: Final resource allocation in the ( N U , N M ) (N_U,N_M) ( N U , N M ) plane, where the color scale indicates the number of trials ending at that particular allocation. The cyan star indicates the mode of the allocation among the 500 trials. The protocol successfully adapts the N U / N M N_U/N_M N U / N M ratio to the state’s properties: it shifts toward larger N M N_M N M (N U / N M < 1 N_U/N_M<1 N U / N M < 1 ) for the nearly maximally mixed reduced states of random mixed states, and toward larger N U N_U N U (N U / N M > 1 N_U/N_M>1 N U / N M > 1 ) for GHZ states (whose half-system partition has purity p = 0.5 p=0.5 p = 0.5 ) and product states. The dashed curve plots N M = 20000 / N U N_M=20000/N_U N M = 20000/ N U . All trials run until the measurement budget is saturated.
Adaptive Scheme
Total Variance and Variance Decomposition
In the standard randomized measurement protocol outlined in § 2 A, the numbers of unitaries N U N_U N U and measurements per unitary N M N_M N M are fixed input parameters specified a priori . In the adaptive scheme, by contrast, we begin with an initial set of unitaries and measurements, denoted by N U ( 0 ) N_U^{(0)} N U ( 0 ) and N M ( 0 ) N_M^{(0)} N M ( 0 ) , and iteratively update N U N_U N U and N M N_M N M throughout the protocol. The adaptive process terminates when the available experimental resource budget is exhausted.
At each iteration, the decision to increase either N U N_U N U or N M N_M N M is determined by a gradient-based estimate of the statistical error. The total variance of the purity estimate comes from two sources: the finite number of sampled unitaries and the finite number of measurements performed given a fixed unitary. Using the law of total variance [31 ] , it can be decomposed as
Var ( p ^ ) = V U + V s h o t ( N M ) N U , (13) \operatorname{Var}(\widehat{p})=\frac{V_U+V_{\mathrm{shot}}(N_M)}{N_U}, \tag*{(13)} Var ( p ) = N U V U + V shot ( N M ) , (13)
where
V U ≡ Var U ( X U ) , (14) V_U\equiv\operatorname{Var}_U(\mathcal{X}_U), \tag*{(14)} V U ≡ Var U ( X U ) , (14)
which represents the variance of X U \mathcal{X}_U X U across the sampled unitaries and depends only on the state ρ \rho ρ , and
V s h o t ( N M ) ≡ E U [ Var s h o t s ( X ^ U ∣ U ) ] . (15) V_{\mathrm{shot}}(N_M)\equiv\mathbb{E}_U\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)\right]. \tag*{(15)} V shot ( N M ) ≡ E U [ Var shots ( X U ∣ U ) ] . (15)
Here, we first compute the variance of X ^ U \widehat{\mathcal{X}}_U X U over shots conditional on U U U , and then average over the unitary ensemble.
According to Eq. (13) , increasing N U N_U N U reduces both variance contributions. Intuitively, sampling an additional unitary that is close to some existing unitary is effectively measuring that existing unitary twice. Using U-statistics [32 ] , we can further write the shot noise contribution as
V s h o t ( N M ) = 4 ( N M − 2 ) ζ ˉ 1 + 2 ζ ˉ 2 ( N M ) 2 , (16) V_{\mathrm{shot}}(N_M)=\frac{4(N_M-2)\bar{\zeta}_1+2\bar{\zeta}_2}{(N_M)^2}, \tag*{(16)} V shot ( N M ) = ( N M ) 2 4 ( N M − 2 ) ζ ˉ 1 + 2 ζ ˉ 2 , (16)
where
ζ 1 ( U ) = 4 N A ∑ s 1 , s 2 , s 3 W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) − χ U 2 , \zeta_1(U)=4^{N_A}\sum_{s_1,s_2,s_3}W_{s_1s_2}W_{s_1s_3}P_U(s_1)P_U(s_2)P_U(s_3)-\chi_U^2, ζ 1 ( U ) = 4 N A s 1 , s 2 , s 3 ∑ W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) − χ U 2 ,
ζ 2 ( U ) = 4 N A ∑ s 1 , s 2 W s 1 s 2 2 P U ( s 1 ) P U ( s 2 ) − χ U 2 , (17) \zeta_2(U)=4^{N_A}\sum_{s_1,s_2}W_{s_1s_2}^2P_U(s_1)P_U(s_2)-\chi_U^2, \tag*{(17)} ζ 2 ( U ) = 4 N A s 1 , s 2 ∑ W s 1 s 2 2 P U ( s 1 ) P U ( s 2 ) − χ U 2 , (17)
and
ζ ˉ 1 = E U [ ζ 1 ( U ) ] , ζ ˉ 2 = E U [ ζ 2 ( U ) ] . (18) \bar{\zeta}_1=\mathbb{E}_U[\zeta_1(U)],\qquad\bar{\zeta}_2=\mathbb{E}_U[\zeta_2(U)]. \tag*{(18)} ζ ˉ 1 = E U [ ζ 1 ( U )] , ζ ˉ 2 = E U [ ζ 2 ( U )] . (18)
Note that the coefficients ζ 1 \zeta_1 ζ 1 and ζ 2 \zeta_2 ζ 2 depend on the unitary U U U and implicitly on the state ρ \rho ρ , while ζ ˉ 1 \bar{\zeta}_1 ζ ˉ 1 and ζ ˉ 2 \bar{\zeta}_2 ζ ˉ 2 are their averages over the unitary ensemble and depend only on the state. The coefficients ζ 1 ( U ) \zeta_1(U) ζ 1 ( U ) and ζ 2 ( U ) \zeta_2(U) ζ 2 ( U ) are nonnegative: the former is the variance of a conditional expectation, and the latter is a variance. A proof of Eq. (13) and Eq. (16) is given in Appendix B.
Gradients of Total Error
We define the total error as
ϵ ( N U , N M ) ≡ Var ( p ^ ) = V U + V s h o t ( N M ) N U . (19) \epsilon(N_U,N_M)\equiv\sqrt{\operatorname{Var}(\hat{p})}=\sqrt{\frac{V_U+V_{\mathrm{shot}}(N_M)}{N_U}}. \tag*{(19)} ϵ ( N U , N M ) ≡ Var ( p ^ ) = N U V U + V shot ( N M ) . (19)
By direct computation of derivatives of Eq. (19) with respect to N U N_U N U and N M N_M N M , we obtain
1 N M ∣ ∂ ϵ ( N U , N M ) ∂ N U ∣ = ϵ ( N U , N M ) 2 N U N M (20) \frac{1}{N_M}\left|\frac{\partial\epsilon(N_U,N_M)}{\partial N_U}\right|=\frac{\epsilon(N_U,N_M)}{2N_UN_M} \tag*{(20)} N M 1 ∂ N U ∂ ϵ ( N U , N M ) = 2 N U N M ϵ ( N U , N M ) (20)
and
1 N U ∣ ∂ ϵ ( N U , N M ) ∂ N M ∣ = 1 2 ϵ ( N U , N M ) N U 2 ∣ ∂ V s h o t ( N M ) ∂ N M ∣ , (21) \frac{1}{N_U}\left|\frac{\partial\epsilon(N_U,N_M)}{\partial N_M}\right|=\frac{1}{2\epsilon(N_U,N_M)N_U^2}\left|\frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\right|, \tag*{(21)} N U 1 ∂ N M ∂ ϵ ( N U , N M ) = 2 ϵ ( N U , N M ) N U 2 1 ∂ N M ∂ V shot ( N M ) , (21)
where
∣ ∂ V s h o t ( N M ) ∂ N M ∣ = 1 ( N M ) 2 [ 4 ζ ˉ 1 N M 2 − ( 16 ζ ˉ 1 − 4 ζ ˉ 2 ) N M + ( 8 ζ ˉ 1 − 2 ζ ˉ 2 ) ] . (22) \left|\frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\right|=\frac{1}{(N_M)^2}\left[4\bar{\zeta}_1N_M^2-(16\bar{\zeta}_1-4\bar{\zeta}_2)N_M+(8\bar{\zeta}_1-2\bar{\zeta}_2)\right]. \tag*{(22)} ∂ N M ∂ V shot ( N M ) = ( N M ) 2 1 [ 4 ζ ˉ 1 N M 2 − ( 16 ζ ˉ 1 − 4 ζ ˉ 2 ) N M + ( 8 ζ ˉ 1 − 2 ζ ˉ 2 ) ] . (22)
For the regime N M ≥ 4 N_M\ge4 N M ≥ 4 used throughout this work, we have ∂ V s h o t ( N M ) ∂ N M ≤ 0 \frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\le0 ∂ N M ∂ V shot ( N M ) ≤ 0 . To see this, rewrite the numerator in Eq. (22) as 4 ζ ˉ 1 ( N M 2 − 4 N M + 2 ) + 2 ζ ˉ 2 ( 2 N M − 1 ) 4\bar{\zeta}_1(N_M^2-4N_M+2)+2\bar{\zeta}_2(2N_M-1) 4 ζ ˉ 1 ( N M 2 − 4 N M + 2 ) + 2 ζ ˉ 2 ( 2 N M − 1 ) and use ζ ˉ 1 , ζ ˉ 2 ≥ 0 \bar{\zeta}_1,\bar{\zeta}_2\ge0 ζ ˉ 1 , ζ ˉ 2 ≥ 0 . Hence the absolute value can be safely replaced by an overall minus sign.
Quantities in Eq. (20) and Eq. (21) are relevant for the adaptive decision because they are proportional to the change in total error ϵ \epsilon ϵ when N U N_U N U or N M N_M N M is increased by one unit, with the derivatives understood as a continuous approximation to these integer increments. The factors 1 N M \frac{1}{N_M} N M 1 and 1 N U \frac{1}{N_U} N U 1 in these equations are not part of the gradients; they normalize by the measurement cost of each direction, since increasing N U N_U N U by one unit increases the total resource N U N M N_UN_M N U N M by N M N_M N M , while increasing N M N_M N M by one unit increases it by N U N_U N U . In practice, we are only interested in the relative magnitude of the two gradients, so we can define the effective descents by multiplying both Eq. (20) and Eq. (21) by 2 ϵ ( N U , N M ) N U 2 N M 2\epsilon(N_U,N_M)N_U^2N_M 2 ϵ ( N U , N M ) N U 2 N M :
L U = ϵ ( N U , N M ) 2 N U = V U + V s h o t ( N M ) (23) L_U=\epsilon(N_U,N_M)^2N_U=V_U+V_{\mathrm{shot}}(N_M) \tag*{(23)} L U = ϵ ( N U , N M ) 2 N U = V U + V shot ( N M ) (23)
and
L M = α N M ∣ ∂ V s h o t ( N M ) ∂ N M ∣ , (24) L_M=\alpha N_M\left|\frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\right|, \tag*{(24)} L M = α N M ∂ N M ∂ V shot ( N M ) , (24)
where α \alpha α is an empirical constant; larger values of α \alpha α bias the adaptive decision toward increasing N M N_M N M . We set α = 0.6 \alpha=0.6 α = 0.6 by optimizing the resource scaling at small subsystem sizes (N A = 1 N_A=1 N A = 1 to 4 4 4 ). With this choice of α \alpha α , the adaptive protocol drives the final allocation ( N U , N M ) (N_U,N_M) ( N U , N M ) into the desired regime and exhibits a lower resource-scaling exponent than every fixed-ratio protocol on all states tested (see Section III). We do not, however, claim that this choice is optimal.
Experimental Estimators of Effective Descents
Just like the purity estimator, the effective descents L U L_U L U and L M L_M L M are also state-dependent quantities that are not directly accessible in experiments. We can, however, construct unbiased estimators for them using only experimental counts. We note that V s h o t ( N M ) V_{\mathrm{shot}}(N_M) V shot ( N M ) (Eq. (16) ) and ∣ ∂ V s h o t ( N M ) ∂ N M ∣ \left|\frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\right| ∂ N M ∂ V shot ( N M ) (Eq. (22) ) are both linear combinations of ζ ˉ 1 \bar{\zeta}_1 ζ ˉ 1 and ζ ˉ 2 \bar{\zeta}_2 ζ ˉ 2 . Hence unbiased estimators for V s h o t ( N M ) V_{\mathrm{shot}}(N_M) V shot ( N M ) and ∣ ∂ V s h o t ( N M ) ∂ N M ∣ \left|\frac{\partial V_{\mathrm{shot}}(N_M)}{\partial N_M}\right| ∂ N M ∂ V shot ( N M ) follow from unbiased estimators for ζ ˉ 1 \bar{\zeta}_1 ζ ˉ 1 and ζ ˉ 2 \bar{\zeta}_2 ζ ˉ 2 , and together with the unbiased estimator for V U V_U V U these yield unbiased estimators for L U L_U L U and L M L_M L M .
The unbiased estimator for V U V_U V U is given by
V ^ U = 1 N U ∑ r = 1 N U χ ^ U , r 2 − 1 ( N U ) 2 ∑ r ≠ r ′ χ ^ U , r χ ^ U , r ′ , (25) \widehat{V}_U=\frac{1}{N_U}\sum_{r=1}^{N_U}\widehat{\chi}_{U,r}^2-\frac{1}{(N_U)^2}\sum_{r\ne r'}\widehat{\chi}_{U,r}\widehat{\chi}_{U,r'}, \tag*{(25)} V U = N U 1 r = 1 ∑ N U χ U , r 2 − ( N U ) 2 1 r = r ′ ∑ χ U , r χ U , r ′ , (25)
where χ ^ U 2 \widehat{\chi}_U^2 χ U 2 is an unbiased estimator for χ U 2 \chi_U^2 χ U 2 , which can be represented in count space as
χ ^ U 2 = 4 N A ( N M ) 4 [ A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) ] . (26) \widehat{\chi}_U^2=\frac{4^{N_A}}{(N_M)^4}\left[A_U^2-4T_U-2\left(c_U^{\mathsf{T}}W_2c_U-N_M\right)\right]. \tag*{(26)} χ U 2 = ( N M ) 4 4 N A [ A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) ] . (26)
where
A U ≡ c U T W c U − N M , (27) A_U \equiv\mathbf{c}_U^{\mathsf{T}} W \mathbf{c}_U - N_M, \tag*{(27)} A U ≡ c U T W c U − N M , (27)
and
T U ≡ ∑ s c U ( s ) [ ( ( W c U ) s − 1 ) 2 − ( W 2 c U ) s + 1 ] . (28) T_U \equiv\sum_s c_U(s)\left[\left((W\mathbf{c}_U)_s-1\right)^2-(W_2\mathbf{c}_U)_s+1\right]. \tag*{(28)} T U ≡ s ∑ c U ( s ) [ ( ( W c U ) s − 1 ) 2 − ( W 2 c U ) s + 1 ] . (28)
The matrix W 2 W_2 W 2 is the entrywise squared version of the Hamming kernel ( W 2 ) s s ′ ≡ W s s ′ 2 (W_2)_{ss'} \equiv W_{ss'}^2 ( W 2 ) s s ′ ≡ W s s ′ 2 . Since we need ( N M ) 4 (N_M)^4 ( N M ) 4 to compute χ ^ U 2 \widehat{\chi}_U^2 χ U 2 , we must start with N M ≥ 4 N_M \ge4 N M ≥ 4 . Similarly, since we need ( N U ) 2 (N_U)^2 ( N U ) 2 to compute V ^ U \widehat{V}_U V U , we must start with N U ≥ 2 N_U \ge2 N U ≥ 2 .
The unbiased estimators for ζ ˉ 1 \bar{\zeta}_1 ζ ˉ 1 and ζ ˉ 2 \bar{\zeta}_2 ζ ˉ 2 are given by
ζ ^ 1 = 1 N U ∑ r = 1 N U ( 4 N A ( N M ) 3 T U r − χ ^ U r 2 ) , (29) \widehat{\zeta}_1=\frac{1}{N_U}\sum_{r=1}^{N_U}\left(\frac{4^{N_A}}{(N_M)^3}T_{U_r}-\widehat{\chi}_{U_r}^2\right), \tag*{(29)} ζ 1 = N U 1 r = 1 ∑ N U ( ( N M ) 3 4 N A T U r − χ U r 2 ) , (29)
and
ζ ^ 2 = 1 N U ∑ r = 1 N U ( 4 N A ( N M ) 2 ( c U r T W 2 c U r − N M ) − χ ^ U r 2 ) , (30) \widehat{\zeta}_2=\frac{1}{N_U}\sum_{r=1}^{N_U}\left(\frac{4^{N_A}}{(N_M)^2}\left(\mathbf{c}_{U_r}^{\mathsf{T}}W_2\mathbf{c}_{U_r}-N_M\right)-\widehat{\chi}_{U_r}^2\right), \tag*{(30)} ζ 2 = N U 1 r = 1 ∑ N U ( ( N M ) 2 4 N A ( c U r T W 2 c U r − N M ) − χ U r 2 ) , (30)
respectively, in the sense that
E U 1 , … , U N U [ E s h o t s ( ζ ^ i ∣ U 1 … U N U ) ] = ζ ˉ i for i = 1 , 2. \mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta}_i\mid U_1\ldots U_{N_U}\right)\right]=\bar{\zeta}_i\text{ for }i=1,2. E U 1 , … , U N U [ E shots ( ζ i ∣ U 1 … U N U ) ] = ζ ˉ i for i = 1 , 2.
We provide a proof of Eqs. (25) , (29) and (30) in Appendix C.
It follows that we may write the unbiased estimators for L U L_U L U and L M L_M L M as
L ^ U = V ^ U + 4 ( N M − 2 ) ζ ^ 1 + 2 ζ ^ 2 ( N M ) 2 , \widehat{L}_U=\widehat{V}_U+\frac{4(N_M-2)\widehat{\zeta}_1+2\widehat{\zeta}_2}{(N_M)^2}, L U = V U + ( N M ) 2 4 ( N M − 2 ) ζ 1 + 2 ζ 2 ,
L ^ M = α N M 4 ζ ^ 1 N M 2 − ( 16 ζ ^ 1 − 4 ζ ^ 2 ) N M + ( 8 ζ ^ 1 − 2 ζ ^ 2 ) ( ( N M ) 2 ) 2 , (31) \widehat{L}_M=\alpha N_M\frac{4\widehat{\zeta}_1N_M^2-(16\widehat{\zeta}_1-4\widehat{\zeta}_2)N_M+(8\widehat{\zeta}_1-2\widehat{\zeta}_2)}{((N_M)^2)^2}, \tag*{(31)} L M = α N M (( N M ) 2 ) 2 4 ζ 1 N M 2 − ( 16 ζ 1 − 4 ζ 2 ) N M + ( 8 ζ 1 − 2 ζ 2 ) , (31)
obtained from Eq. (16) and Eq. (22) with ζ ˉ i \bar{\zeta}_i ζ ˉ i replaced by their unbiased estimators ζ ^ i \widehat{\zeta}_i ζ i . Both expressions are linear in these unbiased ingredients.
At each iteration, we compare L ^ U \widehat{L}_U L U and L ^ M \widehat{L}_M L M and update the parameter corresponding to the larger descent direction. Specifically, if L ^ U ≥ L ^ M \widehat{L}_U \ge\widehat{L}_M L U ≥ L M , additional random unitaries are sampled; otherwise, additional measurements are performed for the existing set of unitaries. This procedure is repeated until the experimental budget N t o t N_{\mathrm{tot}} N tot is saturated by N U N M N_U N_M N U N M . As the budget approaches saturation, the remaining resource r = N t o t − N U N M r=N_{\mathrm{tot}}-N_U N_M r = N tot − N U N M may no longer suffice for a full step of Δ N U \Delta N_U Δ N U unitaries or Δ N M \Delta N_M Δ N M additional shots per unitary. In this case, we take the largest partial step that still fits, so that as much of the remaining budget as possible is used: since each new unitary costs N M N_M N M measurements, N U N_U N U is increased by min ( Δ N U , ⌊ r / N M ⌋ ) \min(\Delta N_U,\lfloor r/N_M\rfloor) min ( Δ N U , ⌊ r / N M ⌋) , and since one additional shot on every existing unitary costs N U N_U N U measurements in total, N M N_M N M is increased by min ( Δ N M , ⌊ r / N U ⌋ ) \min(\Delta N_M,\lfloor r/N_U\rfloor) min ( Δ N M , ⌊ r / N U ⌋) , where ⌊ ⋅ ⌋ \lfloor\cdot\rfloor ⌊ ⋅ ⌋
Algorithm 2 Adaptive Randomized Measurement Protocol for Purity Estimation
Input: Quantum state ρ \rho ρ , subsystem A A A , initial parameters N U ( 0 ) ≥ 2 N_U^{(0)}\ge2 N U ( 0 ) ≥ 2 , N M ( 0 ) ≥ 4 N_M^{(0)}\ge4 N M ( 0 ) ≥ 4 , step sizes Δ N U , Δ N M \Delta N_U,\Delta N_M Δ N U , Δ N M , resource budget N t o t N_{\mathrm{tot}} N tot , empirical constant α \alpha α
Guard parameters: N U g u a r d = 20 N_U^{\mathrm{guard}}=20 N U guard = 20 , c max = 8 c_{\max}=8 c m a x = 8
Output: Estimate p ^ \widehat{p} p of the purity p ( ρ , A ) p(\rho,A) p ( ρ , A )
Sample N U ( 0 ) N_U^{(0)} N U ( 0 ) random unitaries { U r } \{U_r\} { U r }
For each unitary, perform N M ( 0 ) N_M^{(0)} N M ( 0 ) measurements
N U ← N U ( 0 ) N_U\leftarrow N_U^{(0)} N U ← N U ( 0 ) , N M ← N M ( 0 ) N_M\leftarrow N_M^{(0)} N M ← N M ( 0 )
c ← 0 c\leftarrow0 c ← 0
while N U N M < N t o t N_U N_M<N_{\mathrm{tot}} N U N M < N tot do
r ← N t o t − N U N M r\leftarrow N_{\mathrm{tot}}-N_U N_M r ← N tot − N U N M ▷ remaining budget
Evaluate χ ^ U r \widehat{\chi}_{U_r} χ U r for each existing unitary U r U_r U r using Eq. (11)
Estimate V ^ U \widehat{V}_U V U , ζ ^ 1 \widehat{\zeta}_1 ζ 1 and ζ ^ 2 \widehat{\zeta}_2 ζ 2 from the counts using Eqs. (25) , (29) and (30)
Compute the estimators L ^ U \widehat{L}_U L U and L ^ M \widehat{L}_M L M using Eq. (31) , with the estimated shot variance and its derivative magnitude clipped at zero
g ← ( N U < N U g u a r d and c ≥ c max ) g\gets(N_U<N_U^{\mathrm{guard}}\text{ and }c\ge c_{\max}) g ← ( N U < N U guard and c ≥ c m a x ) ▷ warm-up anti-cascade guard
if g ∨ ( L ^ U ≥ L ^ M ) g\lor(\widehat{L}_U\ge\widehat{L}_M) g ∨ ( L U ≥ L M ) then
(Increase number of unitaries)
n ← min ( Δ N U , ⌊ r / N M ⌋ ) n\leftarrow\min(\Delta N_U,\lfloor r/N_M\rfloor) n ← min ( Δ N U , ⌊ r / N M ⌋)
if n = 0 n=0 n = 0 then
break ▷ no further unitary fits in the budget
end if
Sample n n n new random unitaries
For each new unitary, perform N M N_M N M measurements
N U ← N U + n N_U\leftarrow N_U+n N U ← N U + n
c ← 0 c\leftarrow0 c ← 0
else
(Increase measurements per unitary)
m ← min ( Δ N M , ⌊ r / N U ⌋ ) m\leftarrow\min(\Delta N_M,\lfloor r/N_U\rfloor) m ← min ( Δ N M , ⌊ r / N U ⌋)
if m = 0 m=0 m = 0 then
break ▷ a uniform extra shot per unitary does not fit the budget
end if
For each existing unitary, perform m m m additional measurements
N M ← N M + m N_M\leftarrow N_M+m N M ← N M + m
c ← c + 1 c\leftarrow c+1 c ← c + 1
end if
end while
Compute p ^ \widehat{p} p using Eq. (12)
return p ^ \widehat{p} p
denotes the floor function. When even a unit increment in the chosen direction no longer fits within the remaining budget, the protocol terminates. At the beginning of the protocol, the adaptive decision can be dominated by shot noise. For example, there is a possibility that for a few initial unitaries that we drew, the state looks almost identical. The protocol would then keep increasing N M N_M N M and never sample new unitaries. To prevent this, we introduce a warm-up anti-cascade guard. If N U N_U N U is below a guard threshold N U g u a r d N_U^{\mathrm{guard}} N U guard , we force the protocol to increase N U N_U N U for at most c max c_{\max} c m a x consecutive iterations that increase N M N_M N M . The complete adaptive protocol is summarized in Algorithm 2.
Results
Demonstration of Adaptive Resource Allocation
To demonstrate the adaptive protocol (Algorithm 2), we numerically simulated 500 independent runs of the protocol on the half-partitions of several 8-qubit states spanning a wide range of subsystem purities: random mixed states, Haar-random pure states, Greenberger–Horne–Zeilinger (GHZ) states, and product states. The random mixed states are drawn from the Hilbert–Schmidt ensemble, i.e., ρ = X X † / Tr ( X X † ) \rho= XX^\dagger/ \operatorname{Tr}(XX^\dagger) ρ = X X † / Tr ( X X † ) with X X X a complex Ginibre random matrix, generated using QuTiP’s rand_dm function [33 ] . For Haar-random pure states, the reduced density matrix of a half-partition is nearly maximally mixed for large Hilbert-space dimension as a consequence of the concentration of measure [34 , 35 ] . In each simulated run, the measurement outcomes are generated by sampling from the exact outcome probability distributions computed from the corresponding density matrices. Figure 1 shows the distribution of the final S ( 2 ) S^{(2)} S ( 2 ) estimates together with a scatter plot of the final ( N U , N M ) (N_U,N_M) ( N U , N M ) allocations.
The adaptive procedure consistently approaches near-optimal resource allocation. We observe that the final allocated ratio N U / N M N_U/N_M N U / N M increases with the purity of the reduced density matrix. In particular, for the product state the final allocation is concentrated around N U / N M ∼ 10 2 N_U/N_M \sim10^2 N U / N M ∼ 1 0 2 , while for the nearly maximally mixed reduced states of random mixed states, the final allocation is concentrated around N U / N M ∼ 10 − 1 N_U/N_M \sim10^{-1} N U / N M ∼ 1 0 − 1 . This is consistent with our grid search plot in Figure 3 , which indicates that for the product state the highest N U / N M N_U/N_M N U / N M ratio gives the smallest error bar, and for the random mixed state the lowest N U / N M N_U/N_M N U / N M ratio gives the smallest error bar.
Figure 3. Comparison between the adaptive protocol and a grid search over fixed (N U N_U N U , N M N_M N M ) parameter choices. For each grid point and for the adaptive protocol, we perform 500 independent estimation trials on the half-system partition of several 6-qubit states: (a) product state, (b) GHZ state, (c) Haar-random pure state, and (d) random mixed state. The plotted points show the mean over the 500 trials, with error bars indicating one standard deviation. The grid consists of 13 parameter sets with N M N_M N M generated through logarithmic spacing. For each N M N_M N M , N U N_U N U is chosen as the smallest integer such that N U N M ≥ 10000 N_U N_M \ge10000 N U N M ≥ 10000 . The adaptive protocol is run with the same total measurement budget, N t o t = 10000 N_{\mathrm{tot}} = 10000 N tot = 10000 , ensuring that the comparison is not biased in favor of the adaptive method. Across all states considered, the adaptive protocol achieves performance comparable to the best grid points: measured by the standard deviation of the estimates, it outperforms 12 of the 13 grid points for the product state, 11 of the 13 grid points for the GHZ state, 9 of the 13 grid points for the Haar-random pure state, and 6 of the 13 grid points for the random mixed state.
Demonstration of Estimating Multiple Subsystem Purities
When the unitary ensemble in Algorithm 1 is chosen as a tensor product of local random unitaries, we can simultaneously estimate the purity of multiple subsystems from a single set of measurement outcomes. This capability is particularly useful for verifying the scaling of entanglement entropy, e.g., distinguishing between area-law and volume-law states. Instead of only measuring qubits in the subsystem, we measure every qubit of the whole system, obtaining a full bitstring s s s . For any subsystem A A A of interest, we simply retain the bits that belong to A A A and discard the rest; the resulting substring is then used to compute the purity of A A A . A single set of measurements therefore gives access to the purity of every subsystem at once. The same property holds for the adaptive protocol of Algorithm 2, with the small subtlety that we must choose a particular target subsystem A t a r g e t A_{\mathrm{target}} A target whose data are used to compute the variance estimates V ^ U \hat{V}_{\mathrm{U}} V ^ U , ζ ^ 1 \hat{\zeta}_{1} ζ ^ 1 and ζ ^ 2 \hat{\zeta}_{2} ζ ^ 2 that determine the adaptive decisions.
Figure 2 demonstrates the simultaneous estimation of Rényi entropies for all contiguous subsystems of the 1D chain starting from the boundary. The subsystem A A A is taken to be the first N A N_{A} N A qubits, and the N A = 0 N_{A}=0 N A = 0 entropy is set to zero. The total measurement budget is N t o t = 20000 N_{\mathrm{tot}}=20000 N tot = 20000 . As the number of iterations grows, the estimated entropy curve steadily approaches the exact curve. The improvement is especially pronounced for larger N A N_{A} N A , because the sample complexity of the protocol scales with the subsystem size [36 ] : at fixed total system size N N N , a larger subsystem requires a larger resource N U N M N_{\mathrm{U}}N_{\mathrm{M}} N U N M to reach the same accuracy, so each increase of the budget yields a more visible improvement for larger subsystems.
Figure 2. Simultaneous estimation of the second Rényi entropy for subsystems A A A of size N A = 1 N_{A}=1 N A = 1 to N N N using the adaptive protocol. The full system consists of N = 8 N=8 N = 8 qubits, and the target subsystem A t a r g e t A_{\mathrm{target}} A target used to determine the adaptive resource allocation is chosen to be the first four qubits, so that N A = 4 N_{A}=4 N A = 4 . The total experimental budget is fixed to N t o t = 20000 N_{\mathrm{tot}}=20000 N tot = 20000 ; the protocol runs until the budget is saturated. For each state, the estimated entropies for all subsystem sizes N A N_{A} N A at a given iteration are shown as a single curve. Four representative iterations are plotted for each case. The shown iteration indices i i i are chosen to be evenly spaced between iteration i = 40 i=40 i = 40 and the final iteration at which the measurement budget is saturated. Four types of quantum states are considered: (a) random mixed states, (b) Haar-random pure states, (c) GHZ states, and (d) product states. A missing data point indicates that the corresponding S ( 2 ) S^{(2)} S ( 2 ) estimate at that subsystem size and iteration is not finite.
Comparison with Non-Adaptive Method
To better demonstrate the power of the adaptive method, we generate a grid of ( N U , N M ) (N_{\mathrm{U}},N_{\mathrm{M}}) ( N U , N M ) pairs, run the randomized protocol at each grid point many times, and compare it with the adaptive method. We repeat this comparison for several classes of states with different purities: product, GHZ, random pure, and random mixed states. The grid experiment and the adaptive trials are given the same total budget N t o t = 10000 N_{\mathrm{tot}}=10000 N tot = 10000 . As shown in Figure 3 , we run each grid point and the adaptive method 500 times. We plot the mean of the purity estimate p ‾ \overline{p} p over the 500 trials together with its standard deviation, and the exact purity is shown as a horizontal line. We see that for the product and GHZ states, the adaptive method performs comparably to the best grid point, while for the random pure and random mixed states its standard deviation remains within a factor of about 1.2 and 2.5 of the best grid point, respectively. The grid analysis also confirms that the randomized protocol performs better with a larger N U / N M N_{\mathrm{U}}/N_{\mathrm{M}} N U / N M ratio for highly pure states, and with a smaller N U / N M N_{\mathrm{U}}/N_{\mathrm{M}} N U / N M ratio for highly mixed states.
Note that Figure 3 only shows the performance of the adaptive protocol at a single system size, N = 6 N=6 N = 6 , where it is not yet able to outperform the best fixed-ratio protocol for the random pure and random mixed states. To better study the effectiveness of the adaptive protocol, we need to determine how its required experimental resource scales with system size and benchmark it against the fixed-ratio protocols.
To this end, we investigate how the total experimental resource N U N M N_{\mathrm{U}}N_{\mathrm{M}} N U N M scales with system size N N N to reach a fixed accuracy ∣ p ^ − p ∣ ≤ 0.1 |\hat{p}-p|\leq0.1 ∣ p ^ − p ∣ ≤ 0.1 . Here we take N A = N N_{A}=N N A = N as the measured subsystem, rather than a half partition of the system as in the previous plots, because this allows us to obtain data points at odd system sizes. The
three states we study are the all-spin-up state ∣ 0 ⟩ ⊗ N |0\rangle^{\otimes N} ∣0 ⟩ ⊗ N with purity 1, the equal mixture 1 2 [ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ N + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ N ] \frac{1}{2}\left[|0\rangle\langle0|^{\otimes N}+|1\rangle\langle1|^{\otimes N}\right] 2 1 [ ∣0 ⟩ ⟨ 0 ∣ ⊗ N + ∣1 ⟩ ⟨ 1 ∣ ⊗ N ] with purity 0.5, and the maximally mixed state with purity 1 / 2 N 1/2^{N} 1/ 2 N . These states cover the maximal and minimal purity allowed at each system size, as well as an intermediate value. They can also be viewed as reduced states of the states tested in the previous plots: the half-partition reduced states of the product state and the maximally mixed state remain product and maximally mixed states, respectively, while the half-partition reduced state of the GHZ state is the equal mixture state.
For each state, we compare the adaptive protocol against three fixed-ratio protocols with large, balanced (N U / N M = 1 N_U/N_M = 1 N U / N M = 1 ), and small N U / N M N_U/N_M N U / N M ratios. The fixed-ratio curves use standard fixed-parameter estimation at each data point, and along each fixed-ratio curve, the N U / N M N_U/N_M N U / N M ratio is kept constant. Given this constraint, the total resource N U N M N_U N_M N U N M is tuned at every system size to find the minimal resource. The resulting scaling curves are fitted to 2 a N + b 2^{aN+b} 2 a N + b , with the exponents a a a reported in the legend of Figure 4 . We expect this scaling behavior on general grounds, since any protocol that estimates the purity of an N N N -qubit state to constant additive error using single-copy measurements requires Ω ( 2 N / 2 ) \Omega(2^{N/2}) Ω ( 2 N /2 ) samples [37 ] .
Figure 4. Scaling of the experimental resources required to achieve an estimation accuracy ∣ p ^ − p ∣ ≤ 0.1 |\hat{p}-p| \le0.1 ∣ p ^ − p ∣ ≤ 0.1 as a function of system size N N N (from N = 2 N=2 N = 2 to N = 9 N=9 N = 9 ), where the measured subsystem is chosen to be the full system (N A = N N_A=N N A = N ). For each state, we compare three fixed-ratio protocols, corresponding to a large N U / N M N_U/N_M N U / N M ratio, the balanced case N U / N M = 1 N_U/N_M=1 N U / N M = 1 , and a small N U / N M N_U/N_M N U / N M ratio; the ratios shown are N U / N M = 50 , 1 , 1 / 20 N_U/N_M=50,1,1/20 N U / N M = 50 , 1 , 1/20 in panel (a), 20 , 1 , 1 / 20 20,1,1/20 20 , 1 , 1/20 in panel (b), and 20 , 1 , 1 / 50 20,1,1/50 20 , 1 , 1/50 in panel (c). In each fixed-ratio protocol, ( N U , N M ) (N_U,N_M) ( N U , N M ) is determined by the prescribed ratio and allocated total resource N U N M N_U N_M N U N M . Along each fixed-ratio curve, all data points therefore share the same value of N U / N M N_U/N_M N U / N M , even though different system sizes require different total resources to reach the target accuracy. The adaptive protocol is shown alongside these fixed-ratio protocols. Each curve is fitted to an exponential form 2 a N + b 2^{aN+b} 2 a N + b , with the fitted exponent a a a reported in the legend. Each plotted data point is represented by an error bar that bounds the minimum resource required to reach the target accuracy. Specifically, the resource value at the top of the error bar is sufficient for the interval defined by the mean estimate over 100 trials plus or minus one standard deviation to lie entirely within p ± 0.1 p\pm0.1 p ± 0.1 . In contrast, the resource value at the bottom of the error bar is insufficient to satisfy this criterion. Thus, each error bar provides an upper and lower bound on the minimum required resource. For the exponential fits, we use the mean value of each error bar. (a) All-spin-up state ∣ 0 ⟩ ⊗ N |0\rangle^{\otimes N} ∣0 ⟩ ⊗ N , with purity 1. (b) Equal mixture 1 2 [ ( ∣ 0 ⟩ ⟨ 0 ∣ ) ⊗ N + ( ∣ 1 ⟩ ⟨ 1 ∣ ) ⊗ N ] \frac{1}{2}\left[(|0\rangle\langle0|)^{\otimes N}+(|1\rangle\langle1|)^{\otimes N}\right] 2 1 [ ( ∣0 ⟩ ⟨ 0∣ ) ⊗ N + ( ∣1 ⟩ ⟨ 1∣ ) ⊗ N ] , with purity 0.5. (c) Maximally mixed state, with purity 1 / 2 N 1/2^N 1/ 2 N . These states of size N N N can be seen as the reduced states of the product, GHZ, and maximally mixed states of size 2 N 2N 2 N , respectively.
As shown in Figure 4 , suboptimal N U / N M N_U/N_M N U / N M ratios require significantly more, sometimes exponentially more, resources. In the all-spin-up state case, the worst N U / N M N_U/N_M N U / N M ratio in the plot (N U / N M = 1 / 20 N_U/N_M = 1/20 N U / N M = 1/20 ) requires 2 8 2^8 2 8 –2 10 2^{10} 2 10 times more resource than the adaptive protocol across system sizes N = 3 N = 3 N = 3 –7 7 7 . For the equal mixture case, the worst ratio scales with both a higher exponent and a larger constant factor. The figure also shows that the adaptive protocol exhibits the slowest growth for all three states tested.
Conclusion
We have presented an adaptive protocol for estimating the second-order Rényi entropy, an important quantity for studying and characterizing quantum many-body systems. Our protocol extends the randomized measurement protocol framework of [21 ] . It begins with a small amount of data and iteratively decides whether to increase N U N_U N U or N M N_M N M until the total measurement budget is exhausted. By running the protocol many times and analyzing the distribution of the final allocation (N U , N M N_U, N_M N U , N M ), and by benchmarking it against a grid of fixed-parameter estimators, we find that, for a given system size, the adaptive protocol reliably adapts to a favorable parameter regime.
We also investigated how the minimal number of samples required to reach a fixed additive error in purity estimation scales with system size, for several representative states covering minimal, intermediate, and maximal purities. For each system size, we plotted the minimum resource required for purity estimation to be within some additive error for the adaptive protocol, as well as three fixed-ratio curves, covering small, balanced, and large N U / N M N_U/N_M N U / N M ratios. We find that the adaptive protocol exhibits a smaller scaling exponent than all three fixed-ratio curves tested, for all representative states tested.
Our work thus extends the randomized measurement protocol to state-blind setting at no additional experimental cost. Identifying the tasks in which adaptivity reduces sample complexity is an important open problem in quantum learning. In particular, whether adaptivity helps may depend on the metric under consideration [38 ] . Here we provide an example in which adaptivity helps in two ways. First, the best parameter ratio depends on the initial state being estimated and cannot be chosen a priori ; the adaptive method finds this favorable regime on its own and, at fixed system size, performs comparably to the best fixed-parameter estimator for states with high and intermediate purity, without prior knowledge of the state. Second, over the range of system sizes studied, the adaptive protocol exhibits a smaller scaling exponent than each of the fixed-ratio protocols tested for states with maximal, intermediate, and minimal purities, so its advantage over any fixed-ratio choice grows with system size. The scaling comparisons are made against fixed-ratio protocols; we do not rule out that a non-adaptive protocol whose ratio is optimally tuned at every system size could achieve the same scaling.
Finally, the adaptive strategy developed here could potentially be extended beyond the second-order Rényi entropy and purity. For instance, estimating the n t h n^{\mathrm{th}} n th order Rényi entropy requires estimating Tr ( ρ n ) \operatorname{Tr}(\rho^n) Tr ( ρ n ) , which, as a generalization of the second-order case, is equivalent to estimating the expectation value of the n n n -copy cyclic permutation operator. Directly measuring this operator requires coherent manipulation of n n n copies of the quantum state. For n > 2 n>2 n > 2 the cyclic permutation operator is no longer Hermitian, and the non-Hermiticity must be bypassed using techniques such as the Hadamard test [39 ] . To the best of our knowledge, there has been no experimental demonstration of a multi-copy coherent generalized SWAP test for estimating Tr ( ρ n ) \operatorname{Tr}(\rho^n) Tr ( ρ n ) with n > 2 n>2 n > 2 . Single-copy randomized measurement estimators of Tr ( ρ n ) \operatorname{Tr}(\rho^n) Tr ( ρ n ) have, however, been demonstrated experimentally [40 ] , even though the estimator involves all ordered n n n -tuples of the N t o t N_{\rm tot} N tot shadows, so that the number of terms grows as N t o t ! / ( N t o t − n ) ! N_{\rm tot}!/(N_{\rm tot}-n)! N tot ! / ( N tot − n )! . The von Neumann entropy can be viewed as an analytic continuation of the Rényi entropies, and estimating it in this way would in principle require the Rényi entropies of all orders. Recent work using a stabilized analytic continuation (SAC) approach reduces this requirement to a finite number of orders [41 ] . Another possible generalization is Tr ( O ρ 2 ) \operatorname{Tr}(O\rho^2) Tr ( O ρ 2 ) with O O O a generic observable, which reduces to the purity for O = I O=I O = I . This problem admits a randomized protocol with an explicit ( N U , N M ) (N_U,N_M) ( N U , N M ) construction [20 ] , to which our adaptive protocol could potentially be applied.
Acknowledgments
We acknowledge financial support from the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery program (RGPIN-2025-06496), the University of Waterloo, and The Strategic Science Fund of the Government of Canada. This work made use of “Symmetry”, the high-performance computing system at Perimeter Institute for Theoretical Physics. Research at the Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Economic Development, Job Creation and Trade.
References
Unbiased Estimator of Purity
We split the proof into two parts. First, we show that the expression in terms of the Hamming kernel in Eq. (9) is an unbiased estimator for the purity. Second, we show that this Hamming kernel form can be written in the count-space form of Eq. (11) .
Lemma A.1. For two distinct samples i i i and j j j (i ≠ j i \ne j i = j ),
E s h o t s ( W s i s j ∣ U ) = p U T W p U . (32) \mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}\mid U\right)=\mathbf{p}_{U}^{\mathsf{T}}W\mathbf{p}_{U}. \tag*{(32)} E shots ( W s i s j ∣ U ) = p U T W p U . (32) Proof.
E s h o t s ( W s i s j ∣ U ) = ∑ s , s ′ Pr ( s i = s , s j = s ′ ∣ U ) W s s ′ = ∑ s , s ′ P U ( s ) P U ( s ′ ) W s s ′ = p U T W p U \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}\mid U\right)
&=\sum_{s,s'}\Pr\left(s_i=s,s_j=s'\mid U\right)W_{ss'}\\
&=\sum_{s,s'}P_U(s)P_U(s')W_{ss'}\\
&=\mathbf{p}_{U}^{\mathsf{T}}W\mathbf{p}_{U}
\end{aligned} E shots ( W s i s j ∣ U ) = s , s ′ ∑ Pr ( s i = s , s j = s ′ ∣ U ) W s s ′ = s , s ′ ∑ P U ( s ) P U ( s ′ ) W s s ′ = p U T W p U where Pr ( s i = s , s j = s ′ ∣ U ) \Pr\left(s_i=s,s_j=s'\mid U\right) Pr ( s i = s , s j = s ′ ∣ U ) denotes the probability that we get string s s s in the i t h i^{\mathrm{th}} i th shot and string s ′ s' s ′ in the j t h j^{\mathrm{th}} j th shot. □
Proposition A.2. X ^ U \widehat{\mathcal{X}}_U X U is an unbiased estimator for X U \mathcal{X}_U X U in the sense that
E s h o t s ( X ^ U ∣ U ) = X U . (33) \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)=\mathcal{X}_U. \tag*{(33)} E shots ( X U ∣ U ) = X U . (33) Proof. We use the definition of X ^ U \widehat{\mathcal{X}}_U X U in Eq. (9) and Lemma A.1
E s h o t s ( X ^ U ∣ U ) = 2 N A ( N M ) 2 ∑ i , j ∣ i ≠ j E s h o t s ( W s i s j ∣ U ) = 2 N A ( N M ) 2 ∑ i , j ∣ i ≠ j p U T W p U = 2 N A p U T W p U \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)
&=\frac{2^{N_A}}{(N_M)^2}\sum_{i,j\mid i\ne j}\mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}\mid U\right)\\
&=\frac{2^{N_A}}{(N_M)^2}\sum_{i,j\mid i\ne j}\mathbf{p}_{U}^{\mathsf{T}}W\mathbf{p}_{U}\\
&=2^{N_A}\mathbf{p}_{U}^{\mathsf{T}}W\mathbf{p}_{U}
\end{aligned} E shots ( X U ∣ U ) = ( N M ) 2 2 N A i , j ∣ i = j ∑ E shots ( W s i s j ∣ U ) = ( N M ) 2 2 N A i , j ∣ i = j ∑ p U T W p U = 2 N A p U T W p U where we used that the number of ordered 2-tuples chosen from N M N_M N M objects is exactly ( N M ) 2 (N_M)^2 ( N M ) 2 . We then expand X U \mathcal{X}_U X U :
X U = Tr [ U † ⊗ 2 X U ⊗ 2 U ⊗ 2 ρ A ⊗ 2 ] = 2 N A ∑ s , s ′ W s s ′ Tr [ ∣ s ⟩ ⟨ s ∣ U ρ A U † ] × Tr [ ∣ s ′ ⟩ ⟨ s ′ ∣ U ρ A U † ] = 2 N A ∑ s , s ′ W s s ′ P U ( s ) P U ( s ′ ) = 2 N A p U T W p U (34) \begin{aligned}
\mathcal{X}_U
&=\operatorname{Tr}\left[U^{\dagger\otimes2}X_U^{\otimes2}U^{\otimes2}\rho_A^{\otimes2}\right]\\
&=2^{N_A}\sum_{s,s'}W_{ss'}\operatorname{Tr}\left[|s\rangle\langle s|U\rho_AU^{\dagger}\right]\\
&\qquad\times\operatorname{Tr}\left[|s'\rangle\langle s'|U\rho_AU^{\dagger}\right]\\
&=2^{N_A}\sum_{s,s'}W_{ss'}P_U(s)P_U(s')\\
&=2^{N_A}\mathbf{p}_{U}^{\mathsf{T}}W\mathbf{p}_{U} \tag*{(34)}
\end{aligned} X U = Tr [ U †⊗ 2 X U ⊗ 2 U ⊗ 2 ρ A ⊗ 2 ] = 2 N A s , s ′ ∑ W s s ′ Tr [ ∣ s ⟩ ⟨ s ∣ U ρ A U † ] × Tr [ ∣ s ′ ⟩ ⟨ s ′ ∣ U ρ A U † ] = 2 N A s , s ′ ∑ W s s ′ P U ( s ) P U ( s ′ ) = 2 N A p U T W p U (34) Hence, E s h o t s ( X ^ U ∣ U ) = X U \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)=\mathcal{X}_U E shots ( X U ∣ U ) = X U . □
Theorem A.3. X ^ U \widehat{X}_U X U is an unbiased estimator for purity p ( ρ , A ) p(\rho,A) p ( ρ , A ) in the sense that
E U [ E s h o t s ( X ^ U ∣ U ) ] = p ( ρ , A ) . \mathbb{E}_U\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{X}_U\mid U\right)\right]=p(\rho,A). E U [ E shots ( X U ∣ U ) ] = p ( ρ , A ) . Proof. It remains to show that E U [ X U ] = p ( ρ , A ) \mathbb{E}_U[\mathcal{X}_U]=p(\rho,A) E U [ X U ] = p ( ρ , A ) .
E U [ X U ] = E U [ Tr [ X U ρ A ⊗ 2 ] ] = Tr [ E U [ X U ] ρ A ⊗ 2 ] = Tr [ SWAP ρ A ⊗ 2 ] = p ( ρ , A ) \begin{aligned}
\mathbb{E}_U[\mathcal{X}_U]&=\mathbb{E}_U\left[\operatorname{Tr}\left[X_U\rho_A^{\otimes2}\right]\right]\\
&=\operatorname{Tr}\left[\mathbb{E}_U[X_U]\rho_A^{\otimes2}\right]\\
&=\operatorname{Tr}\left[\operatorname{SWAP}\rho_A^{\otimes2}\right]\\
&=p(\rho,A)
\end{aligned} E U [ X U ] = E U [ Tr [ X U ρ A ⊗ 2 ] ] = Tr [ E U [ X U ] ρ A ⊗ 2 ] = Tr [ SWAP ρ A ⊗ 2 ] = p ( ρ , A ) Then by Proposition A.2 ,
E U [ E s h o t s ( X ^ U ∣ U ) ] = E U [ X U ] = p ( ρ , A ) \mathbb{E}_U\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{X}_U\mid U\right)\right]=\mathbb{E}_U[\mathcal{X}_U]=p(\rho,A) E U [ E shots ( X U ∣ U ) ] = E U [ X U ] = p ( ρ , A )
Theorem A.4. The unbiased estimator for purity X ^ U \widehat{X}_U X U can be expressed in count space as shown in Eq. (11) , i.e.
X ^ U = 2 N A ( N M ) 2 ( c U T W c U − N M ) . \widehat{X}_U=\frac{2^{N_A}}{(N_M)^2}\left(\mathbf{c}_U^{\mathsf{T}}\mathbf{W}\mathbf{c}_U-N_M\right). X U = ( N M ) 2 2 N A ( c U T W c U − N M ) . Proof. The definition of X ^ U \widehat{X}_U X U in Eq. (9) is a sum over all ordered pairs of distinct shots. Note that two distinct shots i ≠ j i\ne j i = j may still give the same outcome string, and such pairs remain included in the sum. The count space form rewrites this shot sum using the outcome counts. First note that
∑ i , j W s i s j = ∑ s , s ′ c U ( s ) c U ( s ′ ) W s s ′ = c U T W c U \sum_{i,j}W_{s_i s_j}=\sum_{s,s'}c_U(s)c_U(s')W_{ss'}=\mathbf{c}_U^{\mathsf{T}}\mathbf{W}\mathbf{c}_U i , j ∑ W s i s j = s , s ′ ∑ c U ( s ) c U ( s ′ ) W s s ′ = c U T W c U where we group the shots according to the outcome strings obtained at these shots, and used that the kernel value depends only on the pair of strings appearing in the index. The unrestricted sum ∑ i , j \sum_{i,j} ∑ i , j differs from ∑ i , j ∣ i ≠ j \sum_{i,j\mid i\ne j} ∑ i , j ∣ i = j only by the same-shot diagonal terms with i = j i=j i = j : there are N M N_M N M such terms, one for each shot, and each of them contributes W s i s i = 1 W_{s_i s_i}=1 W s i s i = 1 . The count space expression therefore removes only these N M N_M N M same-shot contributions, while pairs of distinct shots with the same outcome string remain included. Hence,
∑ i , j ∣ i ≠ j W s i s j = c U T W c U − N M (35) \sum_{i,j\mid i\ne j}W_{s_i s_j}=\mathbf{c}_U^{\mathsf{T}}\mathbf{W}\mathbf{c}_U-N_M \tag*{(35)} i , j ∣ i = j ∑ W s i s j = c U T W c U − N M (35) Then, substituting Eq. (35) into Eq. (9) , we get the count space form in Eq. (11) .
Variance Analysis of Randomized Protocol
Lemma B.1 (Adam’s Law). For random variables X X X and Y Y Y ,
E [ E ( Y ∣ X ) ] = E [ Y ] \mathbb{E}\left[\mathbb{E}(Y\mid X)\right]=\mathbb{E}[Y] E [ E ( Y ∣ X ) ] = E [ Y ] Proof. Intuitively, averaging the conditional expectation of random variable Y Y Y over all conditions should just give us the expectation of Y Y Y . For a complete proof, see Theorem 9.3.7 in Ref. [31 ] .
Theorem B.2 (Eve’s Law). For random variables X X X and Y Y Y ,
Var ( Y ) = E [ Var ( Y ∣ X ) ] + Var ( E ( Y ∣ X ) ) \operatorname{Var}(Y)=\mathbb{E}[\operatorname{Var}(Y\mid X)]+\operatorname{Var}(\mathbb{E}(Y\mid X)) Var ( Y ) = E [ Var ( Y ∣ X )] + Var ( E ( Y ∣ X )) This is also called the law of total variance.
Proof. We expand the two terms on the right-hand side in turn.
By Lemma B.1, we have E [ E ( Y 2 ∣ X ) ] = E [ Y 2 ] \mathbb{E}[\mathbb{E}(Y^2\mid X)]=\mathbb{E}[Y^2] E [ E ( Y 2 ∣ X )] = E [ Y 2 ] , so
E [ Var ( Y ∣ X ) ] = E [ E ( Y 2 ∣ X ) − E ( Y ∣ X ) 2 ] = E [ Y 2 ] − E [ E ( Y ∣ X ) 2 ] \mathbb{E}[\operatorname{Var}(Y\mid X)]=\mathbb{E}\left[\mathbb{E}(Y^2\mid X)-\mathbb{E}(Y\mid X)^2\right]
=\mathbb{E}[Y^2]-\mathbb{E}\left[\mathbb{E}(Y\mid X)^2\right] E [ Var ( Y ∣ X )] = E [ E ( Y 2 ∣ X ) − E ( Y ∣ X ) 2 ] = E [ Y 2 ] − E [ E ( Y ∣ X ) 2 ] Still by Lemma B.1, we have
Var ( E ( Y ∣ X ) ) = E [ E ( Y ∣ X ) 2 ] − E [ E ( Y ∣ X ) ] 2 = E [ E ( Y ∣ X ) 2 ] − E [ Y ] 2 \operatorname{Var}(\mathbb{E}(Y\mid X))=\mathbb{E}\left[\mathbb{E}(Y\mid X)^2\right]-\mathbb{E}[\mathbb{E}(Y\mid X)]^2
=\mathbb{E}\left[\mathbb{E}(Y\mid X)^2\right]-\mathbb{E}[Y]^2 Var ( E ( Y ∣ X )) = E [ E ( Y ∣ X ) 2 ] − E [ E ( Y ∣ X ) ] 2 = E [ E ( Y ∣ X ) 2 ] − E [ Y ] 2 Then,
E [ Var ( Y ∣ X ) ] + Var ( E ( Y ∣ X ) ) = E [ Y 2 ] − E [ Y ] 2 = Var ( Y ) \mathbb{E}[\operatorname{Var}(Y\mid X)]+\operatorname{Var}(\mathbb{E}(Y\mid X))=\mathbb{E}[Y^2]-\mathbb{E}[Y]^2
=\operatorname{Var}(Y) E [ Var ( Y ∣ X )] + Var ( E ( Y ∣ X )) = E [ Y 2 ] − E [ Y ] 2 = Var ( Y )
Corollary B.3. The variance of purity estimator p ^ ≡ 1 N U ∑ r = 1 N U X ^ U r \widehat{p}\equiv\frac{1}{N_U}\sum_{r=1}^{N_U}\widehat{X}_{U_r} p ≡ N U 1 ∑ r = 1 N U X U r can be expressed as in Eq. (13) , i.e.
Var ( p ^ ) = V U + V s h o t ( N M ) N U \operatorname{Var}(\widehat{p})=\frac{V_U+V_{\mathrm{shot}}(N_M)}{N_U} Var ( p ) = N U V U + V shot ( N M ) where V U = Var U ( X U ) V_U=\operatorname{Var}_U(X_U) V U = Var U ( X U ) and V s h o t ( N M ) = E U [ Var s h o t s ( X ^ U ∣ U ) ] V_{\mathrm{shot}}(N_M)=\mathbb{E}_U\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{X}_U\mid U\right)\right] V shot ( N M ) = E U [ Var shots ( X U ∣ U ) ]
Proof. We first distribute the variance inside the sum using that for a random variable X X X , Var ( c X ) = c 2 Var ( X ) \operatorname{Var}(cX)=c^2\operatorname{Var}(X) Var ( c X ) = c 2 Var ( X ) and that for independent random variables X X X and Y Y Y , Var ( X + Y ) = Var ( X ) + Var ( Y ) \operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y) Var ( X + Y ) = Var ( X ) + Var ( Y ) [42 ] .
Var ( p ^ ) = 1 N U 2 ∑ r = 1 N U Var ( X ^ U r ) (36) \operatorname{Var}(\widehat{p})=\frac{1}{N_U^2}\sum_{r=1}^{N_U}\operatorname{Var}\left(\widehat{X}_{U_r}\right) \tag*{(36)} Var ( p ) = N U 2 1 r = 1 ∑ N U Var ( X U r ) (36)
We apply Theorem B.2 to Var ( X ^ U r ) \operatorname{Var}\left(\widehat{\mathcal{X}}_{U_r}\right) Var ( X U r ) ,
Var ( X ^ U r ) = E U r [ Var s h o t s ( X ^ U r ∣ U r ) ] + Var U r ( E s h o t s ( X ^ U r ∣ U r ) ) (37) \operatorname{Var}\left(\widehat{\mathcal{X}}_{U_r}\right)=\mathbb{E}_{U_r}\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)\right]+\operatorname{Var}_{U_r}\left(\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)\right) \tag*{(37)} Var ( X U r ) = E U r [ Var shots ( X U r ∣ U r ) ] + Var U r ( E shots ( X U r ∣ U r ) ) (37)
The second term can be further simplified since by Proposition A.2
E s h o t s ( X ^ U r ∣ U r ) = X U r \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)=\mathcal{X}_{U_r} E shots ( X U r ∣ U r ) = X U r
Plugging this back into Eq. B2, we get
Var ( X ^ U r ) = E U r [ Var s h o t s ( X ^ U r ∣ U r ) ] + Var U r ( X U r ) \operatorname{Var}\left(\widehat{\mathcal{X}}_{U_r}\right)=\mathbb{E}_{U_r}\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)\right]+\operatorname{Var}_{U_r}\left(\mathcal{X}_{U_r}\right) Var ( X U r ) = E U r [ Var shots ( X U r ∣ U r ) ] + Var U r ( X U r )
Since each of the U r U_r U r is drawn i.i.d. from the same distribution, we have, for all r ∈ { 1 , … , N U } r\in\{1,\ldots,N_U\} r ∈ { 1 , … , N U } ,
E U r [ Var s h o t s ( X ^ U r ∣ U r ) ] = E U [ Var s h o t s ( X ^ U ∣ U ) ] \mathbb{E}_{U_r}\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)\right]=\mathbb{E}_{U}\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U}\mid U\right)\right] E U r [ Var shots ( X U r ∣ U r ) ] = E U [ Var shots ( X U ∣ U ) ]
Var U r ( X U r ) = Var U ( X U ) \operatorname{Var}_{U_r}\left(\mathcal{X}_{U_r}\right)=\operatorname{Var}_{U}\left(\mathcal{X}_{U}\right) Var U r ( X U r ) = Var U ( X U )
There are N U N_U N U terms in the sum in Eq. B1, hence
Var ( p ^ ) = 1 N U ( Var U ( X U ) + E U [ Var s h o t s ( X ^ U ∣ U ) ] ) \operatorname{Var}(\widehat{p})=\frac{1}{N_U}\left(\operatorname{Var}_{U}(\mathcal{X}_{U})+\mathbb{E}_{U}\left[\operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U}\mid U\right)\right]\right) Var ( p ) = N U 1 ( Var U ( X U ) + E U [ Var shots ( X U ∣ U ) ] )
Proposition B.4. The shot variance of X ^ U \widehat{\mathcal{X}}_U X U under a given unitary U U U can be written as
Var s h o t s ( X ^ U ∣ U ) = 4 ( N M − 2 ) ζ 1 ( U ) + 2 ζ 2 ( U ) ( N M ) 2 \operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)=\frac{4(N_M-2)\zeta_1(U)+2\zeta_2(U)}{(N_M)^2} Var shots ( X U ∣ U ) = ( N M ) 2 4 ( N M − 2 ) ζ 1 ( U ) + 2 ζ 2 ( U ) where
ζ 1 ( U ) = 4 N A ∑ s 1 , s 2 , s 3 W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) − X U 2 , \zeta_1(U)=4^{N_A}\sum_{s_1,s_2,s_3}W_{s_1s_2}W_{s_1s_3}P_U(s_1)P_U(s_2)P_U(s_3)-\mathcal{X}_U^2, ζ 1 ( U ) = 4 N A s 1 , s 2 , s 3 ∑ W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) − X U 2 , ζ 2 ( U ) = 4 N A ∑ s 1 , s 2 W s 1 s 2 2 P U ( s 1 ) P U ( s 2 ) − X U 2 . \zeta_2(U)=4^{N_A}\sum_{s_1,s_2}W_{s_1s_2}^2P_U(s_1)P_U(s_2)-\mathcal{X}_U^2. ζ 2 ( U ) = 4 N A s 1 , s 2 ∑ W s 1 s 2 2 P U ( s 1 ) P U ( s 2 ) − X U 2 .
Proof. First we have
Var s h o t s ( X ^ U ∣ U ) = 4 ( N M − 2 ) ζ 1 ( U ) + 2 ζ 2 ( U ) ( N M ) 2 \operatorname{Var}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U\mid U\right)=\frac{4(N_M-2)\zeta_1(U)+2\zeta_2(U)}{(N_M)^2} Var shots ( X U ∣ U ) = ( N M ) 2 4 ( N M − 2 ) ζ 1 ( U ) + 2 ζ 2 ( U )
where ζ 1 ( U ) = Cov s h o t s ( 2 N A W s 1 s 2 , 2 N A W s 1 s 3 ∣ U ) \zeta_1(U)=\operatorname{Cov}_{\mathrm{shots}}\left(2^{N_A}W_{s_1s_2},2^{N_A}W_{s_1s_3}\mid U\right) ζ 1 ( U ) = Cov shots ( 2 N A W s 1 s 2 , 2 N A W s 1 s 3 ∣ U ) and ζ 2 ( U ) = Var s h o t s ( 2 N A W s 1 s 2 ∣ U ) \zeta_2(U)=\operatorname{Var}_{\mathrm{shots}}\left(2^{N_A}W_{s_1s_2}\mid U\right) ζ 2 ( U ) = Var shots ( 2 N A W s 1 s 2 ∣ U ) . This is just the degree-2 special case of Eq. (5.13) in Hoeffding’s U-statistics paper [32 ] . Hence, we just need to show that the ζ 1 ( U ) \zeta_1(U) ζ 1 ( U ) and ζ 2 ( U ) \zeta_2(U) ζ 2 ( U ) can be written in the desired form in the statement of this proposition.
Using the definition of covariance, we expand
ζ 1 ( U ) = Cov s h o t s ( 2 N A W s 1 s 2 , 2 N A W s 1 s 3 ∣ U ) = 4 N A Cov s h o t s ( W s 1 s 2 , W s 1 s 3 ∣ U ) = 4 N A ( E s h o t s ( W s 1 s 2 W s 1 s 3 ∣ U ) − E s h o t s ( W s 1 s 2 ∣ U ) E s h o t s ( W s 1 s 3 ∣ U ) ) = 4 N A ( ∑ s 1 , s 2 , s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) W s 1 s 2 W s 1 s 3 − ( ∑ s 1 , s 2 P U ( s 1 ) P U ( s 2 ) W s 1 s 2 ) ( ∑ s 1 , s 3 P U ( s 1 ) P U ( s 3 ) W s 1 s 3 ) ) = 4 N A ( ∑ s 1 , s 2 , s 3 W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) ) − X U 2 \begin{aligned}
\zeta_1(U)=\operatorname{Cov}_{\mathrm{shots}}\left(2^{N_A}W_{s_1s_2},2^{N_A}W_{s_1s_3}\mid U\right) \\
&=4^{N_A}\operatorname{Cov}_{\mathrm{shots}}\left(W_{s_1s_2},W_{s_1s_3}\mid U\right) \\
&=4^{N_A}\left(\mathbb{E}_{\mathrm{shots}}\left(W_{s_1s_2}W_{s_1s_3}\mid U\right)-\mathbb{E}_{\mathrm{shots}}\left(W_{s_1s_2}\mid U\right)\mathbb{E}_{\mathrm{shots}}\left(W_{s_1s_3}\mid U\right)\right) \\
&=4^{N_A}\left(\sum_{s_1,s_2,s_3}P_U(s_1)P_U(s_2)P_U(s_3)W_{s_1s_2}W_{s_1s_3}-\left(\sum_{s_1,s_2}P_U(s_1)P_U(s_2)W_{s_1s_2}\right)\left(\sum_{s_1,s_3}P_U(s_1)P_U(s_3)W_{s_1s_3}\right)\right) \\
&=4^{N_A}\left(\sum_{s_1,s_2,s_3}W_{s_1s_2}W_{s_1s_3}P_U(s_1)P_U(s_2)P_U(s_3)\right)-\mathcal{X}_U^2
\end{aligned} ζ 1 ( U ) = Cov shots ( 2 N A W s 1 s 2 , 2 N A W s 1 s 3 ∣ U ) = 4 N A Cov shots ( W s 1 s 2 , W s 1 s 3 ∣ U ) = 4 N A ( E shots ( W s 1 s 2 W s 1 s 3 ∣ U ) − E shots ( W s 1 s 2 ∣ U ) E shots ( W s 1 s 3 ∣ U ) ) = 4 N A ( s 1 , s 2 , s 3 ∑ P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) W s 1 s 2 W s 1 s 3 − ( s 1 , s 2 ∑ P U ( s 1 ) P U ( s 2 ) W s 1 s 2 ) ( s 1 , s 3 ∑ P U ( s 1 ) P U ( s 3 ) W s 1 s 3 ) ) = 4 N A ( s 1 , s 2 , s 3 ∑ W s 1 s 2 W s 1 s 3 P U ( s 1 ) P U ( s 2 ) P U ( s 3 ) ) − X U 2
where in the last step we used Eq. (A3).
Next, we similarly expand the variance
ζ 2 ( U ) = Var s h o t s ( 2 N A W s 1 s 2 ∣ U ) = 4 N A Var s h o t s ( W s 1 s 2 ∣ U ) = 4 N A ( E s h o t s ( W s 1 s 2 2 ∣ U ) − E s h o t s ( W s 1 s 2 ∣ U ) 2 ) = 4 N A ( ∑ s 1 , s 2 P U ( s 1 ) P U ( s 2 ) W s 1 s 2 2 ) − X U 2 \begin{aligned}
\zeta_2(U)=\operatorname{Var}_{\mathrm{shots}}\left(2^{N_A}W_{s_1s_2}\mid U\right) \\
&=4^{N_A}\operatorname{Var}_{\mathrm{shots}}\left(W_{s_1s_2}\mid U\right) \\
&=4^{N_A}\left(\mathbb{E}_{\mathrm{shots}}\left(W_{s_1s_2}^2\mid U\right)-\mathbb{E}_{\mathrm{shots}}\left(W_{s_1s_2}\mid U\right)^2\right) \\
&=4^{N_A}\left(\sum_{s_1,s_2}P_U(s_1)P_U(s_2)W_{s_1s_2}^2\right)-\mathcal{X}_U^2
\end{aligned} ζ 2 ( U ) = Var shots ( 2 N A W s 1 s 2 ∣ U ) = 4 N A Var shots ( W s 1 s 2 ∣ U ) = 4 N A ( E shots ( W s 1 s 2 2 ∣ U ) − E shots ( W s 1 s 2 ∣ U ) 2 ) = 4 N A ( s 1 , s 2 ∑ P U ( s 1 ) P U ( s 2 ) W s 1 s 2 2 ) − X U 2
Again, in the last step we used Eq. (A3).
Unbiased Estimators of Quantities in Adaptive Decision
Lemma C.1. The sum over pairwise distinct shot indices of a product of two Hamming kernels that share one index can be written in count space as
∑ j , l pairwise distinct W s i s j W s i s l = ( ( W C U ) s i − 1 ) 2 − ( W 2 C U ) s i + 1 , \sum_{\substack{j,l\\\text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_l}=\left((W_{C_U})_{s_i}-1\right)^2-(W_{2C_U})_{s_i}+1, j , l pairwise distinct ∑ W s i s j W s i s l = ( ( W C U ) s i − 1 ) 2 − ( W 2 C U ) s i + 1 , where W 2 W_2 W 2 is the entrywise square of the Hamming kernel W W W .
Proof. We first consider a simpler case ∑ j ∣ j ≠ i W s i s j \sum_{j\mid j\ne i}W_{s_i s_j} ∑ j ∣ j = i W s i s j . Since the sum runs over the measured string of each shot, we can rewrite it as a sum over the count of every string. Using
∑ j W s i s j = ∑ s W s i s C U ( s ) , \sum_j W_{s_i s_j}=\sum_s W_{s_i s}C_U(s), j ∑ W s i s j = s ∑ W s i s C U ( s ) ,
we can remove the self-pairing at the i t h i^{\mathrm{th}} i th shot to get
∑ j ∣ j ≠ i W s i s j = ∑ s W s i s j c U ( s ) − 1 = ( W c U ) s i − 1 (38) \sum_{j\mid j\ne i} W_{s_i s_j}=\sum_s W_{s_i s_j}c_U(s)-1=(Wc_U)_{s_i}-1 \tag*{(38)} j ∣ j = i ∑ W s i s j = s ∑ W s i s j c U ( s ) − 1 = ( W c U ) s i − 1 (38)
Similarly,
∑ j ∣ j ≠ i W s i s j 2 = ∑ s W s i s j 2 c U ( s ) − 1 = ( W 2 c U ) s i − 1 \sum_{j\mid j\ne i} W_{s_i s_j}^{2}=\sum_s W_{s_i s_j}^{2}c_U(s)-1=(W_2c_U)_{s_i}-1 j ∣ j = i ∑ W s i s j 2 = s ∑ W s i s j 2 c U ( s ) − 1 = ( W 2 c U ) s i − 1
Now consider ( ∑ j ∣ j ≠ i W s i s j ) 2 \left(\sum_{j\mid j\ne i}W_{s_i s_j}\right)^2 ( ∑ j ∣ j = i W s i s j ) 2 . One way to write it is to take the square of the count space form in Eq. (38) . We can also write it by expanding the sum
( ∑ j ∣ j ≠ i W s i s j ) 2 = ( ∑ j ∣ j ≠ i W s i s j ) ( ∑ l ∣ l ≠ i W s i s l ) = ∑ j , l ∣ j ≠ i , l ≠ i W s i s j W s i s l \begin{aligned}
\left(\sum_{j\mid j\ne i}W_{s_i s_j}\right)^2
=
\left(\sum_{j\mid j\ne i}W_{s_i s_j}\right)
\left(\sum_{l\mid l\ne i}W_{s_i s_l}\right) \\
&=\sum_{j,l\mid j\ne i,l\ne i}W_{s_i s_j}W_{s_i s_l}
\end{aligned} j ∣ j = i ∑ W s i s j 2 = j ∣ j = i ∑ W s i s j l ∣ l = i ∑ W s i s l = j , l ∣ j = i , l = i ∑ W s i s j W s i s l
We can split this sum into two disjoint cases. The first case is when i , j , l i,j,l i , j , l are pairwise distinct, while the second case is when j ≠ i j\ne i j = i , l ≠ i l\ne i l = i , and j = l j=l j = l are simultaneously true. Then
∑ j , l ∣ j ≠ i , l ≠ i W s i s j W s i s l = ∑ j , l ∣ i , j , l pairwise distinct W s i s j W s i s l + ∑ j ∣ j ≠ i W s i s j 2 \sum_{j,l\mid j\ne i,l\ne i}W_{s_i s_j}W_{s_i s_l}
=
\sum_{\substack{j,l\mid i,j,l\\\text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_l}
+\sum_{j\mid j\ne i}W_{s_i s_j}^{2} j , l ∣ j = i , l = i ∑ W s i s j W s i s l = j , l ∣ i , j , l pairwise distinct ∑ W s i s j W s i s l + j ∣ j = i ∑ W s i s j 2
Then, we obtain the count space formula
∑ j , l ∣ i , j , l pairwise distinct W s i s j W s i s l = ∑ j , l ∣ j ≠ i , l ≠ i W s i s j W s i s l − ∑ j ∣ j ≠ i W s i s j 2 = ( ∑ j ∣ j ≠ i W s i s j ) 2 − ∑ j ∣ j ≠ i W s i s j 2 = ( ( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1 \begin{aligned}
\sum_{\substack{j,l\mid i,j,l\\\text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_l}
=
\sum_{j,l\mid j\ne i,l\ne i}W_{s_i s_j}W_{s_i s_l}
-\sum_{j\mid j\ne i}W_{s_i s_j}^{2} \\
&=\left(\sum_{j\mid j\ne i}W_{s_i s_j}\right)^2-\sum_{j\mid j\ne i}W_{s_i s_j}^{2} \\
&=\left((Wc_U)_{s_i}-1\right)^2-(W_2c_U)_{s_i}+1
\end{aligned} j , l ∣ i , j , l pairwise distinct ∑ W s i s j W s i s l = j , l ∣ j = i , l = i ∑ W s i s j W s i s l − j ∣ j = i ∑ W s i s j 2 = j ∣ j = i ∑ W s i s j 2 − j ∣ j = i ∑ W s i s j 2 = ( ( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1
Proposition C.2. The unbiased estimator for X U 2 \mathcal{X}_U^2 X U 2 can be written as in Eq. (26) , i.e.
X ^ U 2 = 4 N A ( N M ) 4 [ A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) ] \widehat{\mathcal{X}}_U^2=\frac{4^{N_A}}{(N_M)^4}\left[A_U^2-4T_U-2\left(c_U^{\mathsf T}W_2c_U-N_M\right)\right] X U 2 = ( N M ) 4 4 N A [ A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) ] in the sense that E s h o t s ( X ^ U 2 ∣ U ) = X U 2 \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U^2\mid U\right)=\mathcal{X}_U^2 E shots ( X U 2 ∣ U ) = X U 2 , where
A U ≡ c U T W c U − N M A_U\equiv c_U^{\mathsf T}Wc_U-N_M A U ≡ c U T W c U − N M and
T U ≡ ∑ s c U ( s ) [ ( ( W c U ) s − 1 ) 2 − ( W 2 c U ) s + 1 ] T_U\equiv\sum_s c_U(s)\left[\left((Wc_U)_s-1\right)^2-(W_2c_U)_s+1\right] T U ≡ s ∑ c U ( s ) [ ( ( W c U ) s − 1 ) 2 − ( W 2 c U ) s + 1 ]
Proof. We first consider how to write the unbiased estimator of X U 2 \mathcal{X}_U^2 X U 2 in terms of the Hamming kernel. By Eq. (34) , we know that X U 2 = 4 N A ( p U T W p U ) 2 \mathcal{X}_U^2=4^{N_A}\left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 X U 2 = 4 N A ( p U T W p U ) 2 . Then, we need a sum over Hamming kernels that will give us ( p U T W p U ) 2 \left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 ( p U T W p U ) 2 . Consider E s h o t s ( W s i s j W s m s n ∣ U ) \mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}W_{s_m s_n}\mid U\right) E shots ( W s i s j W s m s n ∣ U ) . If the two Hamming kernels are independent, we can write the expectation of their product as a product of their respective expectations, and by Lemma A.1 that should give us a ( p U T W p U ) 2 \left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 ( p U T W p U ) 2 . When the shot indices i , j , m , n i,j,m,n i , j , m , n are pairwise distinct, the Hamming kernels W s i s j W_{s_i s_j} W s i s j and W s m s n W_{s_m s_n} W s m s n are indeed independent, so we have
E s h o t s ( ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n ∣ U ) = ∑ i , j , m , n ∣ i , j , m , n pairwise distinct E s h o t s ( W s i s j ∣ U ) E s h o t s ( W s m s n ∣ U ) = ∑ i , j , m , n ∣ i , j , m , n pairwise distinct ( p U T W p U ) 2 = ( N M ) 4 ( p U T W p U ) 2 \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(
\left.
\sum_{\substack{i,j,m,n\mid i,j,m,n\\\text{pairwise distinct}}}
W_{s_i s_j}W_{s_m s_n}
\right|U\right) \\
&=
\sum_{\substack{i,j,m,n\mid i,j,m,n\\\text{pairwise distinct}}}
\mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}\mid U\right)
\mathbb{E}_{\mathrm{shots}}\left(W_{s_m s_n}\mid U\right) \\
&=
\sum_{\substack{i,j,m,n\mid i,j,m,n\\\text{pairwise distinct}}}
\left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 \\
&=(N_M)^4\left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2
\end{aligned} E shots i , j , m , n ∣ i , j , m , n pairwise distinct ∑ W s i s j W s m s n U = i , j , m , n ∣ i , j , m , n pairwise distinct ∑ E shots ( W s i s j ∣ U ) E shots ( W s m s n ∣ U ) = i , j , m , n ∣ i , j , m , n pairwise distinct ∑ ( p U T W p U ) 2 = ( N M ) 4 ( p U T W p U ) 2
where in the last step we used that ( p U T W p U ) 2 \left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 ( p U T W p U ) 2 is independent of shot index, so each term in the sum is the same. The number of terms is the number of ways to choose an ordered 4-tuple from N M N_M N M objects, which equals ( N M ) 4 (N_M)^4 ( N M ) 4 . Then,
E s h o t s ( 4 N A ( N M ) 4 ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n ∣ U ) = 4 N A ( p U T W p U ) 2 = X U 2 \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(
\left.
\frac{4^{N_A}}{(N_M)^4}
\sum_{\substack{i,j,m,n\mid i,j,m,n\\\text{pairwise distinct}}}
W_{s_i s_j}W_{s_m s_n}
\right|U\right)
=4^{N_A}\left(\mathbf{p}_U^{\mathsf T}W\mathbf{p}_U\right)^2 \\
&=\mathcal{X}_U^2
\end{aligned} E shots ( N M ) 4 4 N A i , j , m , n ∣ i , j , m , n pairwise distinct ∑ W s i s j W s m s n U = 4 N A ( p U T W p U ) 2 = X U 2
Now we just need to write this Hamming kernel expression in terms of counts. First note that A U A_U A U can be written in terms of the Hamming kernel as A U = ∑ i , j ∣ i ≠ j W s i s j A_U=\sum_{i,j\mid i\ne j}W_{s_i s_j} A U = ∑ i , j ∣ i = j W s i s j . To show this, we sum over one of the indices first and apply Eq. (38)
∑ i , j ∣ i ≠ j W s i s j = ∑ i ∑ j ∣ j ≠ i W s i s j = ∑ i [ ( W c U ) s i − 1 ] = ∑ s i c U ( s i ) ( ( W c U ) s i − 1 ) = c U T W c U − N M = A U (39) \begin{aligned}
\sum_{i,j\mid i\ne j}W_{s_i s_j}
=\sum_i\sum_{j\mid j\ne i}W_{s_i s_j} \\
&=\sum_i\left[(Wc_U)_{s_i}-1\right] \\
&=\sum_{s_i}c_U(s_i)\left((Wc_U)_{s_i}-1\right) \\
&=c_U^{\mathsf T}Wc_U-N_M \\
&=A_U \tag*{(39)}
\end{aligned} i , j ∣ i = j ∑ W s i s j = i ∑ j ∣ j = i ∑ W s i s j = i ∑ [ ( W c U ) s i − 1 ] = s i ∑ c U ( s i ) ( ( W c U ) s i − 1 ) = c U T W c U − N M = A U (39)
To obtain the count-space expression of X U 2 \mathcal{X}_U^2 X U 2 , we use an approach similar to that of Lemma C.1. Squaring a sum of Hamming kernels gives a sum over products of Hamming kernels, and expanding this sum produces the pairwise-distinct term ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n \sum_{\substack{i,j,m,n\mid i,j,m,n\\ \text{pairwise distinct}}} W_{s_i s_j}W_{s_m s_n} ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n . We take the square of A U A_U A U :
A U 2 = ( ∑ i , j ∣ i ≠ j W s i s j ) 2 = ∑ i , j , m , n ∣ i ≠ j , m ≠ n W s i s j W s m s n A_U^2=\left(\sum_{\substack{i,j\mid i\ne j}}W_{s_i s_j}\right)^2=\sum_{\substack{i,j,m,n\mid i\ne j,m\ne n}}W_{s_i s_j}W_{s_m s_n} A U 2 = i , j ∣ i = j ∑ W s i s j 2 = i , j , m , n ∣ i = j , m = n ∑ W s i s j W s m s n
This sum can be split into three disjoint cases. In the first case, i , j , m , n i,j,m,n i , j , m , n are pairwise distinct, which gives exactly the term we want. In the second case, exactly one index repeats; this includes the four subcases i = m i=m i = m , i = n i=n i = n , j = m j=m j = m , and j = n j=n j = n . In the third case, exactly two indices repeat; this includes the two subcases ( i = m ) ∧ ( j = n ) (i=m)\land(j=n) ( i = m ) ∧ ( j = n ) and ( i = n ) ∧ ( j = m ) (i=n)\land(j=m) ( i = n ) ∧ ( j = m ) .
For the second case, consider the subcase i = m i=m i = m as an example; the relevant sum is ∑ i , j , n ∣ i , j , n pairwise distinct W s i s j W s i s n \sum_{\substack{i,j,n\mid i,j,n\\ \text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_n} ∑ i , j , n ∣ i , j , n pairwise distinct W s i s j W s i s n . Summing two of the indices first recovers the form in Lemma C.1:
∑ i , j , n ∣ i , j , n pairwise distinct W s i s j W s i s n = ∑ i ∑ j , n ∣ i , j , n pairwise distinct W s i s j W s i s n = ∑ i [ ( ( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1 ] = ∑ s i c U ( s i ) [ ( ( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1 ] = T U \begin{aligned}
\sum_{\substack{i,j,n\mid i,j,n\\ \text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_n}
&=\sum_i\sum_{\substack{j,n\mid i,j,n\\ \text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_n}\\
&=\sum_i\left[((Wc_U)_{s_i}-1)^2-(W_2c_U)_{s_i}+1\right]\\
&=\sum_{s_i}c_U(s_i)\left[((Wc_U)_{s_i}-1)^2-(W_2c_U)_{s_i}+1\right]\\
&=T_U
\end{aligned} i , j , n ∣ i , j , n pairwise distinct ∑ W s i s j W s i s n = i ∑ j , n ∣ i , j , n pairwise distinct ∑ W s i s j W s i s n = i ∑ [ (( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1 ] = s i ∑ c U ( s i ) [ (( W c U ) s i − 1 ) 2 − ( W 2 c U ) s i + 1 ] = T U
Using the symmetry of the Hamming kernel, the other three subcases can be brought into the same form as the summation above, so their contributions are all equal to T U T_U T U . In total, the case with exactly one repeated index gives 4 T U 4T_U 4 T U .
For the third case, consider the subcase ( i = m ) ∧ ( j = n ) (i=m)\land(j=n) ( i = m ) ∧ ( j = n ) as an example; the relevant sum is ∑ i , j ∣ i ≠ j W s i s j 2 \sum_{i,j\mid i\ne j}W_{s_i s_j}^2 ∑ i , j ∣ i = j W s i s j 2 . By the same procedure as in Eq. (39) , we obtain
∑ i , j ∣ i ≠ j W s i s j 2 = c U T W 2 c U − N M \sum_{i,j\mid i\ne j}W_{s_i s_j}^2=c_U^{\mathsf T}W_2c_U-N_M i , j ∣ i = j ∑ W s i s j 2 = c U T W 2 c U − N M
By the same symmetry of the Hamming kernel, the other subcase contributes equally, so the total contribution is 2 ( c U T W 2 c U − N M ) 2(c_U^{\mathsf T}W_2c_U-N_M) 2 ( c U T W 2 c U − N M ) . Combining all three cases, we get
A U 2 = ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n + 4 T U + 2 ( c U T W 2 c U − N M ) A_U^2=\sum_{\substack{i,j,m,n\mid i,j,m,n\\ \text{pairwise distinct}}}W_{s_i s_j}W_{s_m s_n}+4T_U+2\left(c_U^{\mathsf T}W_2c_U-N_M\right) A U 2 = i , j , m , n ∣ i , j , m , n pairwise distinct ∑ W s i s j W s m s n + 4 T U + 2 ( c U T W 2 c U − N M )
which implies
4 N A ( N M ) 4 ∑ i , j , m , n ∣ i , j , m , n pairwise distinct W s i s j W s m s n = 4 N A ( N M ) 4 ( A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) ) \frac{4^{N_A}}{(N_M)^4}\sum_{\substack{i,j,m,n\mid i,j,m,n\\ \text{pairwise distinct}}}W_{s_i s_j}W_{s_m s_n}
=\frac{4^{N_A}}{(N_M)^4}\left(A_U^2-4T_U-2\left(c_U^{\mathsf T}W_2c_U-N_M\right)\right) ( N M ) 4 4 N A i , j , m , n ∣ i , j , m , n pairwise distinct ∑ W s i s j W s m s n = ( N M ) 4 4 N A ( A U 2 − 4 T U − 2 ( c U T W 2 c U − N M ) )
giving exactly the desired count-space expression. □
Theorem C.3. An exactly unbiased estimator for unitary contribution to total variance V U V_U V U can be written as in Eq. (25) , i.e.
V ^ U = 1 N U ∑ r = 1 N U X ^ U r 2 − 1 ( N U ) 2 ∑ r ≠ r ′ X ^ U r X ^ U r ′ . \widehat{V}_U=\frac{1}{N_U}\sum_{r=1}^{N_U}\widehat{\mathcal{X}}_{U_r}^2-\frac{1}{(N_U)^2}\sum_{r\ne r'}\widehat{\mathcal{X}}_{U_r}\widehat{\mathcal{X}}_{U_{r'}}. V U = N U 1 r = 1 ∑ N U X U r 2 − ( N U ) 2 1 r = r ′ ∑ X U r X U r ′ . in the sense that
E U 1 , … , U N U [ E s h o t s ( V ^ U ∣ U 1 … U N U ) ] = V U \mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{V}_U\mid U_1\ldots U_{N_U}\right)\right]=V_U E U 1 , … , U N U [ E shots ( V U ∣ U 1 … U N U ) ] = V U Proof. We first take the shot average
E s h o t s ( V ^ U ∣ U 1 … U N U ) = 1 N U ∑ r = 1 N U E s h o t s ( X ^ U r 2 ∣ U 1 … U N U ) − 1 ( N U ) 2 ∑ r ≠ r ′ E s h o t s ( X ^ U r X ^ U r ′ ∣ U 1 … U N U ) = 1 N U ∑ r = 1 N U E s h o t s ( X ^ U r 2 ∣ U r ) − 1 ( N U ) 2 ∑ r ≠ r ′ E s h o t s ( X ^ U r ∣ U r ) E s h o t s ( X ^ U r ′ ∣ U r ′ ) \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(\widehat{V}_U\mid U_1\ldots U_{N_U}\right)
&=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}^2\mid U_1\ldots U_{N_U}\right)\\
&\quad-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\widehat{\mathcal{X}}_{U_{r'}}\mid U_1\ldots U_{N_U}\right)\\
&=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}^2\mid U_r\right)\\
&\quad-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right)\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_{r'}}\mid U_{r'}\right)
\end{aligned} E shots ( V U ∣ U 1 … U N U ) = N U 1 r = 1 ∑ N U E shots ( X U r 2 ∣ U 1 … U N U ) − ( N U ) 2 1 r = r ′ ∑ E shots ( X U r X U r ′ ∣ U 1 … U N U ) = N U 1 r = 1 ∑ N U E shots ( X U r 2 ∣ U r ) − ( N U ) 2 1 r = r ′ ∑ E shots ( X U r ∣ U r ) E shots ( X U r ′ ∣ U r ′ ) where in the last step we use that the measurement records obtained under different unitaries are independent, so that X ^ U r \widehat{\mathcal{X}}_{U_r} X U r and X ^ U r ′ \widehat{\mathcal{X}}_{U_{r'}} X U r ′ are independent for r ≠ r ′ r\ne r' r = r ′ . We also use that E s h o t s ( X ^ U r 2 ∣ U 1 … U N U ) = E s h o t s ( X ^ U r 2 ∣ U r ) \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}^2\mid U_1\ldots U_{N_U}\right)=\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}^2\mid U_r\right) E shots ( X U r 2 ∣ U 1 … U N U ) = E shots ( X U r 2 ∣ U r ) and E s h o t s ( X ^ U r ∣ U 1 … U N U ) = E s h o t s ( X ^ U r ∣ U r ) \mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_1\ldots U_{N_U}\right)=\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_{U_r}\mid U_r\right) E shots ( X U r ∣ U 1 … U N U ) = E shots ( X U r ∣ U r ) because keeping additional irrelevant unitaries constant does not affect the probability distribution. Then by Proposition A.2 and Proposition C.2
E s h o t s ( V ^ U ∣ U 1 … U N U ) = 1 N U ∑ r = 1 N U X U r 2 − 1 ( N U ) 2 ∑ r ≠ r ′ X U r X U r ′ \mathbb{E}_{\mathrm{shots}}\left(\widehat{V}_U\mid U_1\ldots U_{N_U}\right)
=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathcal{X}_{U_r}^2-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathcal{X}_{U_r}\mathcal{X}_{U_{r'}} E shots ( V U ∣ U 1 … U N U ) = N U 1 r = 1 ∑ N U X U r 2 − ( N U ) 2 1 r = r ′ ∑ X U r X U r ′
Taking further average over the unitaries, we get
E U 1 , … , U N U [ E s h o t s ( V ^ U ∣ U 1 … U N U ) ] = 1 N U ∑ r = 1 N U E U 1 , … , U N U [ X U r 2 ] − 1 ( N U ) 2 ∑ r ≠ r ′ E U 1 , … , U N U [ X U r X U r ′ ] = 1 N U ∑ r = 1 N U E U 1 , … , U N U [ X U r 2 ] − 1 ( N U ) 2 ∑ r ≠ r ′ E U 1 , … , U N U [ X U r ] E U 1 , … , U N U [ X U r ′ ] = 1 N U ∑ r = 1 N U E U r [ X U r 2 ] − 1 ( N U ) 2 ∑ r ≠ r ′ E U r [ X U r ] E U r ′ [ X U r ′ ] = E U [ X U 2 ] − E U [ X U ] 2 \begin{aligned}
\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{V}_U\mid U_1\ldots U_{N_U}\right)\right] \\
&= \frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathcal{X}_{U_r}^{2}\right]
-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathcal{X}_{U_r}\mathcal{X}_{U_{r'}}\right] \\
&= \frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathcal{X}_{U_r}^{2}\right]
-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathcal{X}_{U_r}\right]\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathcal{X}_{U_{r'}}\right] \\
&= \frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_r}\left[\mathcal{X}_{U_r}^{2}\right]
-\frac{1}{(N_U)^2}\sum_{r\ne r'}\mathbb{E}_{U_r}\left[\mathcal{X}_{U_r}\right]\mathbb{E}_{U_{r'}}\left[\mathcal{X}_{U_{r'}}\right] \\
&= \mathbb{E}_{U}\left[\mathcal{X}_{U}^{2}\right]-\mathbb{E}_{U}\left[\mathcal{X}_{U}\right]^2
\end{aligned} E U 1 , … , U N U [ E shots ( V U ∣ U 1 … U N U ) ] = N U 1 r = 1 ∑ N U E U 1 , … , U N U [ X U r 2 ] − ( N U ) 2 1 r = r ′ ∑ E U 1 , … , U N U [ X U r X U r ′ ] = N U 1 r = 1 ∑ N U E U 1 , … , U N U [ X U r 2 ] − ( N U ) 2 1 r = r ′ ∑ E U 1 , … , U N U [ X U r ] E U 1 , … , U N U [ X U r ′ ] = N U 1 r = 1 ∑ N U E U r [ X U r 2 ] − ( N U ) 2 1 r = r ′ ∑ E U r [ X U r ] E U r ′ [ X U r ′ ] = E U [ X U 2 ] − E U [ X U ] 2
where in the last step we used that E U r [ X U r 2 ] = E U [ X U 2 ] \mathbb{E}_{U_r}\left[\mathcal{X}_{U_r}^{2}\right]=\mathbb{E}_{U}\left[\mathcal{X}_{U}^{2}\right] E U r [ X U r 2 ] = E U [ X U 2 ] and E U r [ X U r ] = E U [ X U ] \mathbb{E}_{U_r}\left[\mathcal{X}_{U_r}\right]=\mathbb{E}_{U}\left[\mathcal{X}_{U}\right] E U r [ X U r ] = E U [ X U ] for any U r U_r U r , since each U r U_r U r is drawn independently and identically from the same distribution. Finally, by Eq. (14) , we have
V U ≡ Var U ( X U ) = E U [ X U 2 ] − E U [ X U ] 2 V_U\equiv\operatorname{Var}_{U}\left(\mathcal{X}_{U}\right)=\mathbb{E}_{U}\left[\mathcal{X}_{U}^{2}\right]-\mathbb{E}_{U}\left[\mathcal{X}_{U}\right]^2 V U ≡ Var U ( X U ) = E U [ X U 2 ] − E U [ X U ] 2
Hence,
E U 1 , … , U N U [ E s h o t s ( V ^ U ∣ U 1 … U N U ) ] = V U \mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{V}_U\mid U_1\ldots U_{N_U}\right)\right]=V_U E U 1 , … , U N U [ E shots ( V U ∣ U 1 … U N U ) ] = V U
Theorem C.4. An exactly unbiased estimator for ζ 1 ( U ) \zeta_1(U) ζ 1 ( U ) defined in Eq. (17) can be written as
ζ ^ 1 ( U ) = 4 N A ( N M ) 3 T U − X ^ U 2 \widehat{\zeta}_1(U)=\frac{4^{N_A}}{(N_M)^3}T_U-\widehat{\mathcal{X}}_U^2 ζ 1 ( U ) = ( N M ) 3 4 N A T U − X U 2 in the sense that
E s h o t s ( ζ ^ 1 ( U ) ∣ U ) = ζ 1 ( U ) \mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta}_1(U)\mid U\right)=\zeta_1(U) E shots ( ζ 1 ( U ) ∣ U ) = ζ 1 ( U ) where T U T_U T U is defined in Eq. (28) .
Proof. We first show that the unbiased estimator can be written in Hamming kernel form as
ζ ^ 1 ( U ) = 4 N A ( N M ) 3 ∑ i , j , k ∣ i , j , k pairwise distinct W s i s j W s i s k − X ^ U 2 ( C 4 ) \widehat{\zeta}_1(U)=\frac{4^{N_A}}{(N_M)^3}\sum_{\substack{i,j,k\mid i,j,k\\\text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_k}-\widehat{\mathcal{X}}_U^2 \qquad(\mathrm{C4}) ζ 1 ( U ) = ( N M ) 3 4 N A i , j , k ∣ i , j , k pairwise distinct ∑ W s i s j W s i s k − X U 2 ( C4 )
This can be done by directly taking the shot average,
E s h o t s ( ζ ^ 1 ( U ) ∣ U ) = 4 N A ( N M ) 3 ∑ i , j , k ∣ i , j , k pairwise distinct E s h o t s ( W s i s j W s i s k ∣ U ) − E s h o t s ( X ^ U 2 ∣ U ) = 4 N A ( N M ) 3 ∑ i , j , k ∣ i , j , k pairwise distinct ∑ s i , s j , s k W s i s j W s i s k P U ( s i ) P U ( s j ) P U ( s k ) − E s h o t s ( X ^ U 2 ∣ U ) = 4 N A ∑ s i , s j , s k W s i s j W s i s k P U ( s i ) P U ( s j ) P U ( s k ) − X U 2 = ζ 1 ( U ) \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta}_1(U)\mid U\right)
=\frac{4^{N_A}}{(N_M)^3}\sum_{\substack{i,j,k\mid i,j,k\\\text{pairwise distinct}}}\mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}W_{s_i s_k}\mid U\right)
-\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U^2\mid U\right) \\
&=\frac{4^{N_A}}{(N_M)^3}\sum_{\substack{i,j,k\mid i,j,k\\\text{pairwise distinct}}}\sum_{s_i,s_j,s_k}W_{s_i s_j}W_{s_i s_k}P_U(s_i)P_U(s_j)P_U(s_k)-\mathbb{E}_{\mathrm{shots}}\left(\widehat{\mathcal{X}}_U^2\mid U\right) \\
&=4^{N_A}\sum_{s_i,s_j,s_k}W_{s_i s_j}W_{s_i s_k}P_U(s_i)P_U(s_j)P_U(s_k)-\mathcal{X}_U^2 \\
&=\zeta_1(U)
\end{aligned} E shots ( ζ 1 ( U ) ∣ U ) = ( N M ) 3 4 N A i , j , k ∣ i , j , k pairwise distinct ∑ E shots ( W s i s j W s i s k ∣ U ) − E shots ( X U 2 ∣ U ) = ( N M ) 3 4 N A i , j , k ∣ i , j , k pairwise distinct ∑ s i , s j , s k ∑ W s i s j W s i s k P U ( s i ) P U ( s j ) P U ( s k ) − E shots ( X U 2 ∣ U ) = 4 N A s i , s j , s k ∑ W s i s j W s i s k P U ( s i ) P U ( s j ) P U ( s k ) − X U 2 = ζ 1 ( U )
where we used that given a fixed unitary, each shot is drawn independently and identically from the same ensemble, so E s h o t s ( W s i s j W s i s k ∣ U ) \mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}W_{s_i s_k}\mid U\right) E shots ( W s i s j W s i s k ∣ U ) should be the same for every set of pairwise distinct indices i , j , k i,j,k i , j , k . Then, we just need to write the Hamming kernel expression in count space. By Eq. (C3), we get that
T U = ∑ i , j , n ∣ i , j , n pairwise distinct W s i s j W s i s n T_U=\sum_{\substack{i,j,n\mid i,j,n\\\text{pairwise distinct}}}W_{s_i s_j}W_{s_i s_n} T U = i , j , n ∣ i , j , n pairwise distinct ∑ W s i s j W s i s n
Substituting into Eq. (C4),
ζ ^ 1 ( U ) = 4 N A ( N M ) 3 T U − X ^ U 2 \widehat{\zeta}_1(U)=\frac{4^{N_A}}{(N_M)^3}T_U-\widehat{\mathcal{X}}_U^2 ζ 1 ( U ) = ( N M ) 3 4 N A T U − X U 2
Theorem C.5. An exactly unbiased estimator for ζ 2 ( U ) \zeta_2(U) ζ 2 ( U ) defined in Eq. (17) can be written as
ζ ^ 2 ( U ) = 4 N A ( N M ) 2 ( c U T W 2 C U − N M ) − X ^ U 2 \widehat{\zeta}_2(U)=\frac{4^{N_A}}{(N_M)^2}\left(c_U^{\mathsf{T}}W_{2\mathrm{CU}}-N_M\right)-\widehat{\mathcal{X}}_U^2 ζ 2 ( U ) = ( N M ) 2 4 N A ( c U T W 2 CU − N M ) − X U 2 in the sense that
E s h o t s ( ζ ^ 2 ( U ) ∣ U ) = ζ 2 ( U ) \mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta}_2(U)\mid U\right)=\zeta_2(U) E shots ( ζ 2 ( U ) ∣ U ) = ζ 2 ( U )
Proof. Again, we first show that the Hamming kernel form
ζ ^ 2 ( U ) = 4 N A ( N M ) 2 ∑ i , j ∣ i ≠ j W s i s j 2 − X ^ U 2 \widehat{\zeta}_2(U)=\frac{4^{N_A}}{(N_M)^2}\sum_{i,j\mid i\ne j}W_{s_i s_j}^{2}-\widehat{\mathcal{X}}_U^2 ζ 2 ( U ) = ( N M ) 2 4 N A i , j ∣ i = j ∑ W s i s j 2 − X U 2
is an unbiased estimator of ζ 2 ( U ) \zeta_2(U) ζ 2 ( U )
E s h o t s ( ζ 2 ( U ) ^ ∣ U ) = 4 N A ( N M ) 2 ∑ i , j ∣ i ≠ j E s h o t s ( W s i s j 2 ∣ U ) − E s h o t s ( X U 2 ∣ U ) = 4 N A ( N M ) 2 ∑ i , j ∣ i ≠ j ∑ s i , s j W s i s j 2 P U ( s i ) P U ( s j ) − X U 2 = 4 N A ∑ s i , s j W s i s j 2 P U ( s i ) P U ( s j ) − X U 2 = ζ 2 ( U ) \begin{aligned}
\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta_2(U)}\mid U\right)
= \frac{4^{N_A}}{(N_M)^2}\sum_{i,j\mid i\ne j}\mathbb{E}_{\mathrm{shots}}\left(W_{s_i s_j}^2\mid U\right)-\mathbb{E}_{\mathrm{shots}}\left(\mathcal{X}_U^2\mid U\right) \\
&= \frac{4^{N_A}}{(N_M)^2}\sum_{i,j\mid i\ne j}\sum_{s_i,s_j}W_{s_i s_j}^2P_U(s_i)P_U(s_j)-\mathcal{X}_U^2 \\
&=4^{N_A}\sum_{s_i,s_j}W_{s_i s_j}^2P_U(s_i)P_U(s_j)-\mathcal{X}_U^2 \\
&=\zeta_2(U)
\end{aligned} E shots ( ζ 2 ( U ) ∣ U ) = ( N M ) 2 4 N A i , j ∣ i = j ∑ E shots ( W s i s j 2 ∣ U ) − E shots ( X U 2 ∣ U ) = ( N M ) 2 4 N A i , j ∣ i = j ∑ s i , s j ∑ W s i s j 2 P U ( s i ) P U ( s j ) − X U 2 = 4 N A s i , s j ∑ W s i s j 2 P U ( s i ) P U ( s j ) − X U 2 = ζ 2 ( U )
Corollary C.6. Unbiased estimators for ζ ^ 1 \widehat{\zeta}_1 ζ 1 and ζ ^ 2 \widehat{\zeta}_2 ζ 2 can be written as
ζ ^ i = 1 N U ∑ r = 1 N U ζ i ( U r ) ^ (40) \widehat{\zeta}_i=\frac{1}{N_U}\sum_{r=1}^{N_U}\widehat{\zeta_i(U_r)} \tag*{(40)} ζ i = N U 1 r = 1 ∑ N U ζ i ( U r ) (40)
in the sense that E U 1 , … , U N U [ E s h o t s ( ζ i ^ ∣ U 1 … U N U ) ] = ζ ˉ i \mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta_i}\mid U_1\ldots U_{N_U}\right)\right]=\bar{\zeta}_i E U 1 , … , U N U [ E shots ( ζ i ∣ U 1 … U N U ) ] = ζ ˉ i for i = 1 , 2 i=1,2 i = 1 , 2
Proof.
E U 1 , … , U N U [ E s h o t s ( ζ ^ i ∣ U 1 … U N U ) ] = 1 N U ∑ r = 1 N U E U 1 , … , U N U [ E s h o t s ( ζ i ( U r ) ^ ∣ U 1 … U N U ) ] = 1 N U ∑ r = 1 N U E U r [ E s h o t s ( ζ i ( U r ) ^ ∣ U r ) ] = 1 N U ∑ r = 1 N U E U r [ ζ i ( U r ) ] = 1 N U ∑ r = 1 N U ζ ˉ i = ζ ˉ i \begin{aligned}
\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta}_i\mid U_1\ldots U_{N_U}\right)\right]
=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_1,\ldots,U_{N_U}}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta_i(U_r)}\mid U_1\ldots U_{N_U}\right)\right] \\
&=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_r}\left[\mathbb{E}_{\mathrm{shots}}\left(\widehat{\zeta_i(U_r)}\mid U_r\right)\right] \\
&=\frac{1}{N_U}\sum_{r=1}^{N_U}\mathbb{E}_{U_r}\left[\zeta_i(U_r)\right] \\
&=\frac{1}{N_U}\sum_{r=1}^{N_U}\bar{\zeta}_i \\
&=\bar{\zeta}_i
\end{aligned} E U 1 , … , U N U [ E shots ( ζ i ∣ U 1 … U N U ) ] = N U 1 r = 1 ∑ N U E U 1 , … , U N U [ E shots ( ζ i ( U r ) ∣ U 1 … U N U ) ] = N U 1 r = 1 ∑ N U E U r [ E shots ( ζ i ( U r ) ∣ U r ) ] = N U 1 r = 1 ∑ N U E U r [ ζ i ( U r ) ] = N U 1 r = 1 ∑ N U ζ ˉ i = ζ ˉ i