The Exact Replica Threshold for Nonlinear Moments of Quantum States Shuai Zeng∗
Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as tr(ρt ), but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order t ≥ 3, existing protocols show that ⌈t/2⌉ replicas already suffice for polynomial-sample estimation of tr(ρt ), yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to ⌈t/2⌉ − 1 replicas requires dimension-growing sample complexity, while ⌈t/2⌉ replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is ⌈t/2⌉. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments tr(Oρt ), including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.
INTRODUCTION
Access to nonlinear properties of an unknown quantum state requires coherent joint measurements on multiple copies. A central physical question is whether one additional coherent replica merely improves performance, or instead opens an estimation regime that is otherwise inaccessible. This question arises for moments tr(ρt ) and observable-weighted quantities tr(Oρt ), which connect to Renyi-type quantities, spectral diagnostics, and virtual-distillation-type tasks [1–4]. We study it in the sample/copy-access model with replica-limited joint measurements. For fixed-order pure moments, we show that the boundary is sharp. For every fixed t ≥ 3, any protocol restricted to ⌈t/2⌉ − 1 replicas requires sample complexity growing with the dimension, whereas ⌈t/2⌉ replicas already suffice for polynomial-sample estimation by known methods. Thus replica number is not a smooth resource for this problem: in the replica-limited model, one additional coherent replica moves tr(ρt ) from a dimensiongrowing regime into the polynomial-sample regime. This threshold question has become especially timely with the development of shadow-based and replica-based protocols for nonlinear estimation [1, 3–5]. Existing methods already show that ⌈t/2⌉ replicas suffice for fixedorder moments [3], while recent lower bounds for related nonlinear tasks reveal dramatic one-more-replica effects [6]. What remained open for the canonical pure moments was whether ⌈t/2⌉ is merely sufficient or instead the exact resource boundary. We further show that the same threshold persists for a broad family of observable-weighted moments ∗ [email protected]
tr(Oρt ), including Pauli observables and observables with bounded operator norm and macroscopic trace norm. In this sense, coherent replica number behaves as a genuinely discrete resource for nonlinear estimation rather than merely a smooth performance knob. Technically, the lower-bound side closes through a hard pair, matching at k copies, replica-limited indistinguishability, and rounding to exact spectra, while for observable-weighted moments a macroscopic-trace-norm condition embeds the same hard pair into a biased block. Figure 1 summarizes the corresponding staircase ⌈t/2⌉.
exact replica threshold
arXiv:2604.22627v1 [quant-ph] 24 Apr 2026
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China (Dated:)
⌈t/2⌉ 5
4
3
2 3
4
5
6
7
8
9
10
moment order t FIG. 1. Exact replica threshold for nonlinear moments. The staircase ⌈t/2⌉ indicates the exact threshold for the pure moments tr(ρt ) established here, together with its extension to the observable-weighted family tr(Oρt ) considered in this work.
2 EXACT REPLICA THRESHOLD FOR PURE MOMENTS
but X
Problem Setup and Theorem Statement
Proof. t ≥ 3,
samples. Conversely, for fixed t, ⌈t/2⌉-replica protocols achieve constant-additive-error estimation of tr(ρt ) with sample complexity polynomial in d. Thus ⌈t/2⌉ is the exact replica threshold separating the lower-bound side proved here from the known polynomial-sample upper-bound side. The upper-bound half comes from the hybrid framework of Ref. [3] for fixed-degree nonlinear functions. For the pure moment tr(ρt ), one uses the balanced factorization t = a + b with a = ⌈t/2⌉ and b = ⌊t/2⌋, so the required coherent block size is ⌈t/2⌉. The novelty of Theorem 1 is therefore the matching lower-bound half, which closes the exactthreshold picture.
qit ≥ δt .
i
Fix t ≥ 3, set m := s + 1, and choose ai :=
in the sample/copy-access model with replica-limited joint measurements. Here an s-replica protocol may be adaptive across rounds and may use arbitrary classical post-processing, but in each round it performs a joint measurement on at most s fresh copies of the unknown state. Sample complexity always counts the total number of consumed copies. All lower bounds below are asymptotic in the ambient dimension d. Theorem 1 (Exact replica threshold for pure moments). Let t ≥ 3 and define s := ⌈t/2⌉ − 1. Then there exists a constant εt > 0, depending only on t, such that for all sufficiently large d, any s-replica protocol that with success probability at least 2/3 estimates tr(ρt ) up to additive error εt requires at least ! √ d p Ω (s + 1) ln(s + 1)
X
i
We study the pure nonlinear state moments Mt (ρ) := tr(ρt ),
pti −
2i , m(m + 1)
i = 1, . . . , m.
These numbers are distinct, positive, and sum to 1. Let e1 , . . . , em denote the corresponding elementary symmetric polynomials, and write c∗ := em . For a parameter c near c∗ , consider Fc (λ) = λm − e1 λm−1 + e2 λm−2 − · · · + (−1)m c. Since Fc∗ has the simple positive roots a1 , . . . , am , continuity of roots yields an interval I := [c∗ − η0 , c∗ + η0 ] with η0 > 0 depending only on t, such that for every c ∈ I the polynomial Fc has simple positive roots x1 (c), . . . , xm (c). Writing x(c) := (x1 (c), . . . , xm (c)), we P obtain an m-point probability distribution because i xi (c) = e1 = 1. Frozen low moments. For r = 1, . . . , s, define mr (c) :=
m X
xi (c)r .
i=1
Newton’s identities express mr (c) in terms of e1 , . . . , er , which are frozen in Fc . Hence mr (c) is independent of c for every r ≤ s. Derivative formula for higher moments. Let Hc (z) :=
m Y
(1 − xi (c)z)−1 =
i=1
X
hj (c)z j ,
j≥0
where hj (c) is the complete homogeneous symmetric polynomial of degree j in the roots x1 (c), . . . , xm (c). Since X ∂ log Hc (z) mr (c)z r = z ∂z r≥1
Exact-Support Hard Pair of Spectra
and The first ingredient is an explicit algebraic hard pair supported on exactly t m := s + 1 = 2 points. Proposition 2.1 (Exact-support hard pair). There exist probability distributions p, q ∈ ∆m and a constant δt > 0, depending only on t, such that X X pri = qir , r = 1, . . . , s, i
i
Hc (z) =
1 , 1 − e1 z + · · · + (−1)m cz m
differentiation with respect to c gives ∂ log Hc (z) = (−1)m−1 z m Hc (z) ∂c X = (−1)s hj (c)z j+s+1 , j≥0
because m = s + 1. Applying z∂z and comparing coefficients yields ∂ mr (c) = (−1)s r hr−s−1 (c), ∂c
r ≥ s + 1.
3 Quantitative gap at degree t. All roots remain positive on I, so every hj (c) is strictly positive there. In particular, µt := min ht−s−1 (c) > 0. c∈I
The derivative formula therefore implies ∂ mt (c) ≥ tµt , ∂c
c ∈ I.
c1 := c∗ + η0 /2,
and define p := x(c0 ) and q := x(c1 ). By the mean-value theorem, X i
pti −
X
tµt η0 := δt . 2
qit = |mt (c1 ) − mt (c0 )| ≥
i
Proposition 2.2 (Spectrum-testing lower bound for the hard pair). Let p, q be the hard pair from Proposition 2.1. Then, for all sufficiently large d, any s-replica protocol that distinguishes d-dimensional states whose spectra are p or q, up to zero padding when d > m, with success probability at least 2/3 must use at least ! √ d √ Ω m ln m
Choose c0 := c∗ ,
Spectrum-Testing Lower Bound
samples. Proof. Fix a k-replica T -round POVM M . For each x ∈ {p, q}, let Ex be the Haar-assembled ensemble obtained by mixing the weights x against independent Haar-random pure states. Standard Haar-integration identities enter the estimates below [7]. Write ) Γ(T := Eρ←Ex [ρ⊗kT ], x
The first s power sums agree by the frozen-low-moment step, and δt depends only on t. This proves the proposition.
) Π(T := Eρ←Ex [ρ⊗k ] x
⊗T
.
Let Ex′ be the rounded exact-spectrum ensemble constructed in the end matter, and set ) Γ′(T := Eρ←Ex′ [ρ⊗kT ]. x
From Moment Estimation to Spectrum Testing
For a POVM M = {Fy }y , write The reduction from estimation to testing is immediate once Proposition 2.1 is available. Assume that an s-replica protocol estimates tr(ρt ) up to additive error strictly smaller than δt /2 with success probability at least 2/3 for every input state. Consider the promise problem in which the unknown d-dimensional state has spectrum p or q, padding by zeros when d > m. For any such states ρp and ρq , tr(ρtp ) =
X
pti ,
tr(ρtq ) =
X
i
qit ,
i
and Proposition 2.1 gives tr(ρtp ) − tr(ρtq ) ≥ δt . Thresholding the estimator output at the midpoint 1 τ := 2
dM (ρ, σ) :=
1X |tr(Fy ρ) − tr(Fy σ)| 2 y
for the induced total-variation distance on outcomes. By the product-POVM reduction for replica-limited protocols, proved in the Supplemental Material [8], Sec. S1, it suffices to consider product POVMs on kT copies. For the hard pair of Proposition 2.1, the lower bound closes through three ingredients. First, because the first k power sums of p and q agree, the matching-at-k-copies lemma gives ) ) Π(T = Π(T p q .
Second, the joint Haar source is close to the roundwiseproduct source:
! X i
pti +
X
qit
i
therefore yields an s-replica tester for the exact-spectrum promise classes with the same sample complexity and success probability at least 2/3. Consequently, Theorem 1 reduces to proving a replica-limited spectrum-testing lower bound for the hard pair p, q.
(kT )2 + kT ) (T ) dM Γ(T ≤ . x , Πx d This bound holds for both x = p and x = q. Third, rounding to exact spectra costs at most √ √ ) ′(T ) dM Γ(T ≤ 0.01 + C kT m ln m/ d, x , Γx
4 again for both x = p and x = q, with an absolute constant C. Therefore
EXTENSION TO OBSERVABLE-WEIGHTED MOMENTS
′(T ) (T ) ) ′(T ) ≤ d Γ , Γ dM Γ′(T , Γ M p p p q ) (T ) + dM Γ(T p , Πp (T ) ′(T ) ) (T ) + d Γ , Γ + dM Π(T , Γ M q q q q
Observable-Weighted Moments and Statement
4(kT )2 √d C ′ kT m ln m √ + , d ≤ 0.02 +
for another absolute constant C ′ . Since success probability at least 2/3 under equal priors requires dM ≥ 1/3, this forces ! √ d √ kT = Ω . m ln m Setting k = s and m = s + 1 gives Proposition 2.2. The point is that matching at k copies blocks discrimination at the accessible replica level, while exact-spectrum rounding transfers this indistinguishability to the exact promise spectra relevant for tr(ρt ). This is why Proposition 2.2 closes the lower-bound side for pure-moment estimation itself, rather than merely for an auxiliary surrogate task. The end matter below records how the closure is assembled, while detailed proofs of the monomial-topower-sum reduction, the permutation-sector inequality, and the rounding estimates are deferred to the Supplemental Material [8], especially Secs. S3–S6.
Completion and Interpretation
Taking any εt < δt /2, Proposition 2.1 and the reduction above turn any s-replica estimator for tr(ρt ) into an s-replica tester for the hard promise spectra. Proposition 2.2 then yields the lower-bound side of Theorem 1. Since the upper-bound side is already known at ⌈t/2⌉ replicas [3], this pins the exact replica threshold for estimating tr(ρt ) at t . 2 Equivalently, one fewer replica necessarily places the problem in a dimension-growing lower-bound regime, while ⌈t/2⌉ replicas already reach the known attainable regime. This is the exact resource boundary on the replica axis for pure nonlinear moments.
We now turn to Mt,O (ρ) := tr(Oρt ), which extend the pure moments through the special case O = I. In this setting, the same exact-threshold law persists for a broad observable family. Theorem 2 (Observable-weighted exact-threshold extension). Fix an integer t ≥ 3, let s := ⌈t/2⌉ − 1, and let O be a d-dimensional Hermitian observable satisfying ∥O∥∞ ≤ 1,
∥O∥1 ≥ ηd
for some constant η > 0 independent of d. Then there exists a constant εt,η > 0, depending only on t and η, such that for all sufficiently large d, any s-replica protocol that with success probability at least 2/3 estimates tr(Oρt ) up to additive error εt,η requires at least ! √ d p Ω (s + 1) ln(s + 1) samples. Together with the known (s + 1)-replica upper bound [3], this yields the same exact threshold ⌈t/2⌉ for this observable family. Biased-Block Reduction
The key structural input is that macroscopic trace norm forces a large block with nonvanishing normalized bias. Lemma (Biased-block reduction). If ∥O∥∞ ≤ 1 and ∥O∥1 ≥ ηd, then for D := ⌊d/2⌋ there exists a rank-D projection Π such that the compressed block ΠOΠ satisfies ∥ΠOΠ∥∞ ≤ 1,
| tr(ΠOΠ)| ≥
η D. 2
Pd Proof. Diagonalize O = i=1 λi |i⟩⟨i| with λ1 ≥ · · · ≥ λd . Replacing O by −O if necessary does not change the estimation complexity, so we may assume that the total positive mass X P := λi λi ≥0
is at least the total negative mass X N := |λi |, λi <0
5 hence P ≥ ηd/2. Let Π project onto the top D eigenvectors of O, let B := ΠOΠ, and let r be the number of nonnegative eigenvalues. If r ≥ D, then tr(B) =
D X
λi ≥
i=1
D η D P ≥ P ≥ D. r d 2
Proof.
Because V † V = ID , we have
ρp (U )t = V U Ap U † V † ,
ρq (U )t = V U Aq U † V † .
Therefore, by cyclicity of the trace, Xp (U ) = tr(B U Ap U † ),
Xq (U ) = tr(B U Aq U † ).
More generally, for Hermitian A ∈ MD , define
If r < D, then the negative eigenvalues inside the top-D block are the least negative ones, so their total magnitude is at most D−r 1 N ≤ N. d−r 2 Therefore 1 1 ηd η tr(B) ≥ P − N ≥ P ≥ ≥ D. 2 2 4 2 The operator-norm bound is inherited from O.
XA (U ) := tr(B U AU † ). The Haar first- and second-moment formulas, proved in the Supplemental Material [8], Sec. S7, using standard unitary-twirling identities [7], state that E[XA ] =
tr(A) tr(B) , D
and D tr(A2 ) − tr(A)2 D tr(B 2 ) − tr(B)2 Var(XA ) = . D2 (D2 − 1)
Embedded Hard-Pair Gap
Lemma (Embedded hard-pair gap). Let D := ⌊d/2⌋, let p, q be the hard pair from Proposition 2.1, let m := s + 1, and let Π be a rank-D projection furnished by the biased-block lemma. Fix an isometry V : CD → Cd ,
Applying the first-moment identity to Ap and Aq gives ! tr(B) X t X t pi − qi . E[Xp ] − E[Xq ] = D i i Since the biased-block lemma ensures tr(B) ≥ ηD/2 after the harmless sign choice above, and Proposition 2.1 gives
V V † = Π,
and define the compressed observable X
B := V † OV. For sufficiently large d, we have D ≥ m, so the hard pair embeds into this D-dimensional block. Define Ap := diag(pt1 , . . . , ptm , 0, . . . , 0), t Aq := diag(q1t , . . . , qm , 0, . . . , 0),
where the trailing zeros fill the D-dimensional block. For Haar-random U ∈ U (D), set †
σp (U ) := U diag(p1 , . . . , pm , 0, . . . , 0) U , and define σq (U ) similarly. Embedding into the ambient space by ρp (U ) := V σp (U )V † ,
ρq (U ) := V σq (U )V † ,
let Xp (U ) := tr(Oρp (U )t ),
Xq (U ) := tr(Oρq (U )t ).
Then there exists a constant η ∆t,η := δt > 0 4 such that, for all sufficiently large d, there are two disjoint intervals centered at E[Xp ] and E[Xq ], each of radius ∆t,η /2, and Xp and Xq fall into their respective intervals with probability at least 11/12.
pti −
i
X
qit ≥ δt ,
i
the two means are separated by at least ηδt /2 = 2∆t,η . Next, since Ap and Aq are diagonal positive semidefinite matrices with 0 ≤ tr(Ap ), tr(Aq ) ≤ 1,
0 ≤ tr(A2p ), tr(A2q ) ≤ 1,
and since ∥B∥∞ ≤ 1 implies tr(B 2 ) ≤ D, the variance formula gives Var(Xp ) = Ot (D−1 ),
Var(Xq ) = Ot (D−1 ).
Hence for sufficiently large D, Var(Xp ), Var(Xq ) ≤
∆2t,η . 48
Chebyshev’s inequality therefore yields ∆t,η 1 , Pr |Xp − E[Xp ]| ≥ ≤ 2 12 and similarly for Xq . Thus each variable lies within distance ∆t,η /2 of its mean with probability at least 11/12, and the corresponding intervals are disjoint.
6 Completion and Corollaries
Assume there exists an s-replica estimator for tr(Oρt ) with additive error below ∆t,η /2 and success probability at least 2/3 on every d-dimensional input state. Let Π and V be as in the previous subsection. Given copies of an unknown D-dimensional state whose spectrum is promised to be either p or q, up to zero padding to dimension D, we Haar-conjugate the input inside the Ddimensional block and then apply the fixed isometric embedding V into the image of Π. These preprocessing operations do not increase the replica number used in any round and do not change the sample count. By the embedded-gap lemma, thresholding the estimator output at the midpoint between the two interval centers yields a tester with success probability at least 7 1 11 2 + −1= > . 12 3 12 2 Constant repetition and majority vote amplify this to success probability at least 2/3 at only constant-factor overhead. Proposition 2.2 then applies in dimension D = ⌊d/2⌋ and gives ! ! √ √ D d p p Ω =Ω . (s + 1) ln(s + 1) (s + 1) ln(s + 1) Taking any εt,η < ∆t,η /2 proves Theorem 2. Two immediate consequences are worth recording. Corollary 1 (Large-trace observables). If a Hermitian observable satisfies ∥O∥∞ ≤ 1 and | tr(O)| ≥ τ d for some constant τ > 0, then ∥O∥1 ≥ τ d, so Theorem 2 applies directly with η = τ . Corollary 2 (Pauli observables). Every Hermitian Pauli string P satisfies ∥P ∥∞ = 1 and ∥P ∥1 = d, so Theorem 2 applies directly to tr(P ρt ). Thus the exact threshold is not an isolated feature of the scalar moments tr(ρt ); it persists for a broad and natural family of observable-weighted nonlinear moments. DISCUSSION AND OUTLOOK
We have shown that for fixed-order nonlinear moments the gain from one additional coherent replica is qualitative rather than merely quantitative. For the pure moments tr(ρt ), crossing from ⌈t/2⌉ − 1 to ⌈t/2⌉ replicas moves the problem from a dimension-growing regime to the known polynomial-sample regime. The conceptual core is the matching lower-bound closure built from the exact-support hard pair and the exact-spectrum testing lower bound for that hard pair. The observable-weighted extension shows that the same exact-threshold boundary is robust beyond the identity observable. In particular, the same separation between the proved lower-bound side and the known
upper-bound side persists for observables with bounded operator norm and macroscopic trace norm, including large-trace observables and Pauli observables. Thus coherent multi-copy access behaves as a genuine resource threshold rather than a smooth performance knob. For nonlinear observables connected to virtual-distillationtype diagnostics within this class, the result identifies a true access boundary in the replica-limited model. In this sense, the accessible replica number is part of the access structure itself: it determines which nonlinear information is operationally available at polynomial sample cost, not merely how efficiently an already accessible quantity can be estimated. Several directions remain open. It would be natural to understand how far this behavior extends beyond observables with macroscopic trace norm, and whether comparable exact-threshold phenomena survive for ratiotype tasks related to virtual distillation or in finitedimensional and noisy settings where asymptotic constructions may need refinement.
[1] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nature Reviews Physics 5, 9 (2023). [2] W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Virtual distillation for quantum error mitigation, Physical Review X 11, 041036 (2021). [3] Y. Zhou and Z. Liu, A hybrid framework for estimating nonlinear functions of quantum states, npj Quantum Information 10, 62 (2024). [4] Q. Liu, Z. Li, X. Yuan, H. Zhu, and Y. Zhou, Auxiliary-free replica shadows: Efficient estimation of multiple nonlinear quantum properties, Phys. Rev. Lett. 136, 100602 (2026). [5] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020). [6] Q. Ye, Z. Liu, and D.-L. Deng, Exponential advantage from one more replica in estimating nonlinear properties of quantum states, arXiv preprint arXiv:2509.24000 (2025), arXiv:2509.24000 [quant-ph]. [7] B. Collins and P. Śniady, Integration with respect to the Haar measure on unitary, orthogonal and symplectic group, Communications in Mathematical Physics 264, 773 (2006). [8] Supplemental material (2026), see Supplemental Material at [URL will be inserted by publisher] for detailed proofs of the hard-pair construction, moment matching, permutation-sector machinery, indistinguishability, rounding, and the Haar mean/variance formulas.
7 which is √ incompatible with success probability 2/3 unless √ kT = Ω( d/(m ln m)).
END MATTER Spectrum-Testing Lower-Bound Closure
We complete the lower-bound closure for a slightly more general statement, reducing it to three ingredients proved in the Supplemental Material [8]. Let k ≥ 1, let m := k + 1, and let p, q be probabilityPdistributions Pmsupm ported on exactly m points such that i=1 pri = i=1 qir for r = 1, . . . , k. We show that any k-replica protocol distinguishing d-dimensional states whose spectra are up to zero padding when d > m, needs √p or q, √ Ω d/(m ln m) samples. Proposition 2.2 is the case k = s and m = s + 1. Haar-Assembled Hard Ensembles
Let ψ1 , . . . , ψm be independent Haar-random pure states in Cd , identified with their rank-one projectors. Define (m ) X Ep := p r ψr , r=1
Eq :=
(m X
Lemma (Matching at k copies). and Eq satisfy
The ensembles Ep
Eρ←Ep [ρ⊗k ] = Eρ←Eq [ρ⊗k ]. P Proof. For a finite index set I, let S I := σ∈S(I) Uσ and d↑r := d(d + 1) · · · (d + r − 1). The Haar moment 1 I ⊗k ⊗I for identity Pmgives Eψ [ψ ] = d↑|I| S . Expanding ρ ρ = p ψ , each term is indexed by a partition r=1 r r λ ⊢ k, and the corresponding coefficient is the monomial symmetric polynomial mλ (p). Thus Eρ←Ep [ρ⊗k ] =
X
mλ (p)
λ⊢k
X
×
ℓ(λ) O S Bj
B1 ,...,Bℓ(λ) partition of [k] j=1 |Bj |=λj
d↑λj
.
ψ1 ,...,ψm ←µHaar (d)
) q r ψr
r=1
. ψ1 ,...,ψm ←µHaar (d)
For a k-replica T -round protocol, write ) Γ(T := Eρ←Ep [ρ⊗kT ], p ⊗T ) Π(T := Eρ←Ep [ρ⊗k ] , p (T )
Matching at k Copies
(T )
analogously. As in the main and define Γq and Πq P text, write dM (ρ, σ) := 21 y | tr(Fy ρ) − tr(Fy σ)| for a POVM M = {Fy }y . Under equal priors, success probability at least 2/3 requires dM ≥ 1/3. By the productPOVM reduction for replica-limited protocols, proved in the Supplemental Material [8], Sec. S1, it suffices to consider measurements of the form M = {Fy }y with Fy = Fy,1 ⊗ · · · ⊗ Fy,T . (T ) The proof compares the genuine joint Haar source Γx , (T ) the roundwise-product surrogate Πx , and the exact′(T ) spectrum rounded source Γx . It closes once we establish ) ) Π(T = Π(T p q , (kT )2 + kT ) (T ) , dM Γ(T , Π ≤ x x d √ √ ) ′(T ) dM Γ(T ≤ 0.01 + C kT m ln m/ d, x , Γx
The same expansion holds for q. By the monomial-topower-sum reduction in the Supplemental Material [8], Sec. S3, P every mλ is a polynomial in s1 , . . . , sk , where su (x) := i xui . Since these power sums agree for p and q, the expectations coincide.
Indistinguishability under Replica-Limited Protocols
Lemma (Hard-instance indistinguishability). For every k-replica T -round POVM M , one has (T ) (T ) ≤ ((kT )2 + kT )/d, and the same dM Γp , Πp bound holds with p replaced by q. Proof. Fix p; the case q is identical. Expanding both the joint Haar source and the roundwise-product source (t) by per-round label configurations α = (br , It,r ) yields a common mixture, so it suffices to compare the correPT (t) sponding conditional states. Let Ar := and t=1 br ST Qr := t=1 It,r . For this configuration, the joint Haarassembled source uses the same Haar state for label r across all rounds, whereas the roundwise-product source resamples independently round by round. Hence the corresponding conditional states are E[ωjoint,α ] =
m O S Qr r=1
for x = p, q. Their combination gives √ √ 4(kT )2 ) ′(T ) dM Γ′(T , Γ ≤ 0.02 + + C ′ kT m ln m/ d, p q d
d
, ↑Ar
E[ωprod,α ] =
T O m O S It,r (t)
↑br t=1 r=1 d
.
If Pα and Qα are the induced outcome distributions under M , then the permutation inequality for positive product POVMs, proved in the Supplemental Material [8],
8 ΨG−1/2 , the columns of Φ are orthonormal, so σ := Φ diag(a1 , . . . , am ) Φ† has exact spectrum a. Writing H := G1/2 − I, a direct expansion gives ρ − σ = Φ HA + AH + HAH Φ† ,
Sec. S4, implies m m QT ↑b(t) X Y r A2r Pα (y) t=1 d ≥ exp − ≥ ↑A Qα (y) r=1 d r d r=1
!
QT ↑ut whenever Qα (y) ̸= 0, since /d↑U ≥ t=1 d exp(−U 2 /d) for nonnegative integers u , . . . , uT sumPm 1 ming to U . Hence dTV (Pα , Qα ) ≤ r=1 A2r /d, and averaging over α gives m X E[A2r ] ) (T ) ≤ dM Γ(T , Π . p p d r=1
Because the round counts are i.i.d. multinomial with 2 parameters (k; p1 , . . . , pm ), one has E[Ar ] = T (T − 2 2 1)(kpr ) + T k(k − 1)pr + kpr . Summing over r yields m X E[A2 ] r
r=1
d
2
2
k T − kT X 2 kT (kT )2 + kT = pr + ≤ , d d d r
P since r p2r ≤ 1. This proves the claim. Corollary (Indistinguishability of the hard ensembles). k-replica T -round POVM M , one has For every (T )
(T )
dM Γp , Γq
≤ 4(kT )2 /d.
(T )
Proof. By the matching-at-k-copies lemma, Πp = Hence the triangle inequality and the previous lemma give ) (T ) ) (T ) ) (T ) dM Γ(T ≤ dM Γ(T + dM Π(T p , Γq p , Πp q , Γq (T ) Πq .
4(kT )2 2((kT )2 + kT ) ≤ . ≤ d d Rounding and Completion
Lemma (Rounding to exact spectrum). Let a = (a 1 Pm, . . . , am ) be a probability vector and let ρ := r=1 ar ψr with independent Haar-random pure states ψ1 , . . . , ψm ∈ Cd . Then with probability at least 0.99, the state ρ is ! √ m ln m √ O d close in trace norm to a state with exact spectrum a. Proof. Let Ψ be the d × m matrix with columns |ψ1 ⟩, . . . , |ψm ⟩ and let G := Ψ† Ψ be the Gram matrix. The Haar overlap tail bound from the Supplemental Material [8], Sec. S6, and a union bound give ! √ m ln m √ ∥G − I∥F = O d with probability at least 0.99. For sufficiently large d, all eigenvalues of G lie in [1/2, 3/2]. Setting Φ :=
A := diag(a1 , . . . , am ), and therefore ! √ ln m m √ ∥ρ − σ∥1 ≤ 2∥H∥2 + ∥H∥22 = O . d Choose measurable rounding maps, for example by a fixed tie-breaking rule for nearest exact-spectrum states as in the Supplemental Material [8], Sec. S6, and let Ep′ and Eq′ be the resulting exact-spectrum ensembles. Writ′(T )
′(T )
ing Γp := Eρ←Ep′ [ρ⊗kT ] and Γq := Eρ←Eq′ [ρ⊗kT ], the tensor-power trace inequality ∥ρ⊗n − σ ⊗n ∥1 ≤ n∥ρ − σ∥1 gives, for every k-replica T -round POVM M , √ √ ) ′(T ) dM Γ(T ≤ 0.01 + C kT m ln m/ d, p , Γp and the same bound holds with p replaced by q, for an absolute constant C. Combining this rounding estimate with the previous corollary yields √ √ 4(kT )2 ) ) dM Γ′(T , Γ′(T ≤ 0.02 + + C ′ kT m ln m/ d p q d for some absolute constant C ′ . A success probability at least 2/3 would require the left-hand side to be at least 1/3, so √ √ 4(kT )2 1 + C ′ kT m ln m/ d ≥ . d 3 √ √ Hence kT = Ω d/(m ln m) , since otherwise both √ √ (kT )2 /d and kT m ln m/ d would be o(1). Applying this with k = s and m = s + 1 proves Proposition 2.2. 0.02 +
9 SUPPLEMENTAL MATERIAL FOR “THE EXACT REPLICA THRESHOLD FOR NONLINEAR MOMENTS OF QUANTUM STATES”
This Supplemental Material contains the technical proofs deferred from the main text. In particular, it supplies the detailed arguments behind the hard-pair construction, the moment-matching step, the permutation-sector machinery, the indistinguishability proof, the rounding step, and the Haar second-moment calculations used in the observableweighted extension.
STANDARD BACKGROUND FACTS
This section collects a few routine facts that are used repeatedly later. None of the statements is new, but recording them here keeps the later sections focused on the problem-specific arguments. Lemma (Binary testing under a fixed POVM). Let M = {Fx }x be a POVM and define dM (ρ, σ) :=
1X |tr(Fx ρ) − tr(Fx σ)| . 2 x
For the binary problem of distinguishing ρ from σ under equal priors using the fixed measurement M , the optimal success probability is 1 1 + dM (ρ, σ). 2 2 In particular, success probability at least 2/3 requires dM (ρ, σ) ≥ 1/3. Proof. After measuring with M , one obtains two classical outcome distributions P (x) := tr(Fx ρ),
Q(x) := tr(Fx σ).
For equal priors, the optimal decision rule is maximum likelihood on each outcome x, so the success probability is 1X 1 1X max{P (x), Q(x)} = + |P (x) − Q(x)| 2 x 2 4 x =
1 1 + dM (ρ, σ). 2 2
The final claim is immediate. Lemma (Product-POVM reduction for replica-limited protocols). there exists a POVM
Let A be a k-replica T -round protocol. Then
M = {Fy }y on kT copies, indexed by full transcripts y = (y1 , . . . , yT ), such that Fy = Fy,1 ⊗ · · · ⊗ Fy,T , where each Fy,t ⪰ 0 acts on the tth block of k copies, and such that for every input state ρ the transcript law of A is given by Pr[Y = y | ρ] = tr(Fy ρ⊗kT ). A
If some rounds use fewer than k copies, one may pad the corresponding local operator by the identity on the unused tensor factors. Proof. For each round t, and each past transcript y<t := (y1 , . . . , yt−1 ), the protocol chooses a POVM on at most k fresh copies. After padding by identities if necessary, write that POVM as X (t) (t) {Fyt |y<t }yt , Fyt |y<t = I. yt
10 For a full transcript y = (y1 , . . . , yT ), define (t)
Fy := Fy,1 ⊗ · · · ⊗ Fy,T .
Fy,t := Fyt |y<t ,
Because round t acts only on the tth fresh block of k copies, the probability of seeing the full transcript y on input ρ is T Y
tr(Fy,t ρ⊗k ) = tr(Fy ρ⊗kT ).
t=1
It remains to check completeness. Summing first over yT and using the conditional POVM identity gives X Fy = (Fy,1 ⊗ · · · ⊗ Fy,T −1 ) ⊗ I. yT
Iterating this elimination round by round yields X
Fy = I.
y
Hence {Fy }y is a POVM with the claimed transcript law. Lemma (Haar tensor-power identity). Let ψ = |u⟩⟨u| with u Haar-random in Cd . For any finite index set I, let S(I) be the symmetric group on I, let Uσ be the induced permutation operator on the tensor factors indexed by I, and define X S I := Uσ , d↑r := d(d + 1) · · · (d + r − 1). σ∈S(I)
Then Eψ [ψ ⊗I ] =
1 d↑|I|
SI .
Proof. The expectation commutes with U ⊗|I| for every U ∈ U (d), so by Schur-Weyl duality it must be a scalar multiple of the projector onto the symmetric subspace. Since S I equals |I|! times that projector and d + |I| − 1 I tr(S ) = |I|! = d↑|I| , |I| the scalar is fixed by the normalization condition tr Eψ [ψ ⊗I ] = 1. Lemma (Pointwise domination implies total-variation control). finite set and suppose there is a constant c ∈ [0, 1] such that P (x) ≥ c Q(x)
Let P, Q be probability distributions on the same
for all x.
Then dTV (P, Q) ≤ 1 − c. Proof.
Using dTV (P, Q) = 1 −
X
min{P (x), Q(x)},
x
we obtain X x
which proves the claim.
min{P (x), Q(x)} ≥
X x
c Q(x) = c,
11 Lemma (Convexity of total variation under a common mixture). Let {λα }α be nonnegative weights summing to 1, and let X X P = λ α Pα , Q= λα Qα α
α
be probability distributions on a common finite outcome space. Then X dTV (P, Q) ≤ λα dTV (Pα , Qα ). α
Proof.
By the triangle inequality, 2dTV (P, Q) =
X X X
λα
X
α
=2
α
x
≤
λα Pα (x) − Qα (x) |Pα (x) − Qα (x)|
x
X
λα dTV (Pα , Qα ).
α
Lemma (Tensor-power trace inequality).
For density matrices ρ, σ and every integer n ≥ 1, ∥ρ⊗n − σ ⊗n ∥1 ≤ n∥ρ − σ∥1 .
Proof.
The telescoping identity gives ρ⊗n − σ ⊗n =
n X
ρ⊗(r−1) ⊗ (ρ − σ) ⊗ σ ⊗(n−r) .
r=1
Taking trace norms and using ∥ρ∥1 = ∥σ∥1 = 1 yields ∥ρ⊗n − σ ⊗n ∥1 ≤
n X
∥ρ − σ∥1 = n∥ρ − σ∥1 .
r=1
Lemma (Square-root stability near the identity).
Let G ⪰ 0. If ∥G − I∥2 ≤
1 , 2
then every eigenvalue of G lies in [1/2, 3/2], and ∥G1/2 − I∥2 ≤ ∥G − I∥2 . Proof.
If λ is an eigenvalue of G, then |λ − 1| ≤ ∥G − I∥2 ≤
1 , 2
so λ ∈ [1/2, 3/2]. By the spectral theorem, √ ∥G1/2 − I∥2 = max | λ − 1|, λ
where the maximum runs over the eigenvalues of G. Since √ |λ − 1| | λ − 1| = √ ≤ |λ − 1| λ+1 for every λ ≥ 0, we obtain ∥G1/2 − I∥2 ≤ max |λ − 1| = ∥G − I∥2 . λ
12 FULL PROOF OF THE HARD-PAIR CONSTRUCTION
This section gives the full algebraic proof of Proposition 2.1 from the main text. The construction produces two m-point probability distributions whose first s power sums agree exactly while the degree-t power sums differ by a constant depending only on t. Setup. Fix t ≥ 3 and set t t − 1, m := s + 1 = . s := 2 2 Choose the reference points 2i , m(m + 1)
ai :=
i = 1, . . . , m.
These numbers are distinct, positive, and sum to 1. Let e1 , . . . , em denote the corresponding elementary symmetric polynomials, and write c∗ := em . For a parameter c near c∗ , consider the monic polynomial Fc (λ) = λm − e1 λm−1 + e2 λm−2 − · · · + (−1)m c, whose first m − 1 coefficients are frozen while only the constant term varies. Since Fc∗ has the simple positive roots a1 , . . . , am , continuity of roots yields an interval I := [c∗ − η, c∗ + η] with η > 0 depending only on the fixed initial choice a1 , . . . , am , such that for every c ∈ I the polynomial Fc has m simple positive roots x1 (c), . . . , xm (c). Their sum remains equal to e1 = 1, so x(c) = (x1 (c), . . . , xm (c)) defines an m-point probability distribution for every c ∈ I. Lemma (Frozen low moments). For every r = 1, . . . , s, the power sum mr (c) :=
m X
xi (c)r
i=1
is independent of c ∈ I. Proof. Newton’s identities express mr (c) in terms of the elementary symmetric polynomials e1 , . . . , er for each r ≤ s. These coefficients are frozen in the polynomial Fc , so the quantities mr (c) are constant on I. Lemma (Derivative formula for higher moments). For every r ≥ s + 1, ∂ mr (c) = (−1)s r hr−s−1 (c), ∂c where hj (c) denotes the complete homogeneous symmetric polynomial of degree j in the roots x1 (c), . . . , xm (c). Proof. Consider the generating function Hc (z) =
m Y
(1 − xi (c)z)−1 =
i=1
X
hj (c)z j ,
j≥0
which also satisfies X
mr (c)z r = z
r≥1
∂ log Hc (z). ∂z
Since Hc (z) =
1 1 − e1 z + · · · + (−1)m cz m
13 and m = s + 1, differentiation with respect to c gives ∂ log Hc (z) = (−1)m−1 z m Hc (z) ∂c X = (−1)s hj (c)z j+s+1 . j≥0
Applying z∂z to both sides yields z
X ∂ ∂ log Hc (z) = (−1)s (j + s + 1) hj (c)z j+s+1 ∂z ∂c j≥0 X s = (−1) r hr−s−1 (c)z r . r≥s+1
Comparing this with X ∂ r≥1
yields the stated formula. Lemma (Quantitative gap at degree t). that the spectral distributions
∂c
mr (c)z r = z
∂ ∂ log Hc (z) ∂z ∂c
There exist c0 , c1 ∈ I and a constant δt > 0, depending only on t, such
p := x(c0 ),
q := x(c1 )
satisfy X
pri =
i
X
qir ,
r = 1, . . . , s,
i
while ∆t :=
X
pti −
X
i
qit ≥ δt .
i
Proof. Because all roots remain positive on I, every complete homogeneous symmetric polynomial hj (c) is strictly positive there. In particular, µt := min ht−s−1 (c) > 0. c∈I
The derivative formula therefore implies ∂ mt (c) ≥ tµt , ∂c
c ∈ I.
Choose c0 := c∗ ,
c1 := c∗ + η/2.
By the mean-value theorem, ∆t = |mt (c1 ) − mt (c0 )| ≥
tµt η := δt . 2
Since the initial choice of ai , the interval I, the quantity µt , and the chosen points c0 , c1 all depend only on t, so does δt .
14 Completion of Proposition 2.1.
Define p := x(c0 ),
q := x(c1 ).
The frozen-low-moment lemma gives X
pri =
X
i
qir ,
r = 1, . . . , s,
i
while the quantitative-gap lemma gives X
pti −
X
i
qit ≥ δt .
i
Thus p and q form the exact-support hard pair used in the main text. In particular, any choice εt < δt /2 is valid in Theorem 1.
FULL PROOF OF MOMENT MATCHING
We record here the combinatorial reduction that turns equality of the low-order power sums of p and q into exact equality of the Haar-assembled k-copy averages. Setup. For a partition λ = {λ1 , . . . , λℓ } ⊢ t, define the monomial symmetric polynomial X
mλ (x) :=
xλi11 · · · xλiℓℓ ,
i1 ,...,iℓ ∈[m] distinct
and the power sums su (x) :=
m X
xui .
i=1
Lemma (Monomial-to-power-sum reduction). gλ such that
For every partition λ = {λ1 , . . . , λℓ } ⊢ t, there exists a polynomial
mλ (x) = (−1)ℓ−1 (ℓ − 1)! st (x) + gλ (s1 (x), . . . , st−1 (x)). Proof.
We induct on ℓ. The case ℓ = 1 is immediate. For ℓ > 1, expand m{λ1 ,...,λℓ−1 } (x) sλℓ (x).
The terms with all indices distinct give mλ (x), while the terms with one collision give ℓ−1 X
mλj←ℓ (x),
j=1
where λj←ℓ is formed by replacing λj with λj + λℓ . By the induction hypothesis, each collision term contributes (−1)ℓ−2 (ℓ − 2)! st (x) plus terms depending only on s1 , . . . , st−1 . Rearranging yields the stated formula. Lemma (Matching at k copies). If m X i=1
pri =
m X
qir ,
r = 1, . . . , k,
i=1
then Eρ←Ep [ρ⊗k ] = Eρ←Eq [ρ⊗k ].
15 Proof.
Write ρ=
m X
pr ψr .
r=1
When ρ⊗k is expanded, each term is determined by a partition of [k] into nonempty blocks B1 , . . . , Bℓ , where every tensor slot in a given block uses the same Haar-random pure state. For any finite index set I, let S(I) be the symmetric group on I, let Uσ be the induced permutation operator on the tensor factors indexed by I, write X S I := Uσ , σ∈S(I)
and let d↑r := d(d + 1) · · · (d + r − 1). By the Haar tensor-power identity from Sec. , Eψ [ψ ⊗I ] =
1 d↑|I|
SI .
Therefore Eρ←Ep [ρ⊗k ] =
X λ⊢k
X
mλ (p)
B1 ,...,Bℓ(λ) partition of [k] |Bj |=λj
S B1 S Bℓ(λ) ⊗ · · · ⊗ ↑|B | . ↑|B | d 1 d ℓ(λ)
The same expansion holds for q. By the previous lemma, each mλ is a polynomial in s1 , . . . , sk , and these power sums agree for p and q. Hence the expectations coincide. FULL PROOF OF THE PERMUTATION-SECTOR MACHINERY
This section records the group-theoretic ingredient that compares “merged across rounds” permutation sectors with “kept separate round by round” sectors. Lemma (Single-label sector identity). Let A, B be disjoint finite sets with |A| = a and |B| = b. Let HA,B := S(A) × S(B) ⊆ S(A ⊔ B), fix an integer 0 ≤ j ≤ min(a, b), and let πj ∈ S(A ⊔ B) be the standard permutation that swaps a fixed j-element subset of A with a fixed j-element subset of B and fixes the remaining points. For σ ∈ S(A ⊔ B) define the crossing number j(σ) := σ(A) ∩ B , and the sector operator SjA⊔B :=
X
Uσ .
σ∈S(A⊔B): j(σ)=j
Then there exists a positive integer mA,B,j such that (S A ⊗ S B ) Uπj (S A ⊗ S B ) = mA,B,j SjA⊔B . Proof.
First, the permutations with crossing number j form exactly the double coset {σ ∈ S(A ⊔ B) : j(σ) = j} = HA,B πj HA,B .
The inclusion from right to left is immediate, because left and right multiplication by HA,B only reorders elements inside A and inside B, and therefore preserves the number of points of A sent into B. For the reverse inclusion, let σ have crossing number j and define A→B := {x ∈ A : σ(x) ∈ B},
A→A := {x ∈ A : σ(x) ∈ A},
B→A := {y ∈ B : σ(y) ∈ A},
B→B := {y ∈ B : σ(y) ∈ B}.
16 Then |A→B | = |B→A | = j, |A→A | = a − j, and |B→B | = b − j. A right multiplication by an element of HA,B sends the fixed standard swapping and nonswapping subsets of A and B to these four domain blocks. A left multiplication by an element of HA,B then sends the four image blocks σ(A→B ), σ(A→A ), σ(B→A ), and σ(B→B ) to the corresponding standard codomain blocks. After these two normalizations, the resulting permutation maps each of the four standard blocks to the corresponding standard block. A final right multiplication by blockwise permutations trivializes the four induced bijections, reducing the normalized permutation exactly to πj . Hence σ ∈ HA,B πj HA,B . Now expand X Uh . SA ⊗ SB = h∈HA,B
Then X
(S A ⊗ S B ) Uπj (S A ⊗ S B ) =
X
UhL πj hR .
hL ∈HA,B hR ∈HA,B
Group this sum by the resulting permutation σ ∈ HA,B πj HA,B . If σ = aπj b with a, b ∈ HA,B , then (hL , hR ) 7−→ (a−1 hL , hR b−1 ) gives a bijection between the fiber over σ and the fiber over πj . Hence every element of the double coset appears with the same multiplicity, say mA,B,j > 0. This proves the identity. Lemma (Permutation inequality). Let I be a set of tensor factors, let T, m ≥ 1, and let {It,r }t∈[T ], r∈[m] be a partition of I. Write Pt :=
m [
It,r ,
T [
Qr :=
r=1
It,r .
t=1
Suppose G is a positive semidefinite operator on the tensor factors indexed by I and factorizes across the partition {Pt }t∈[T ] : G = G1 ⊗ · · · ⊗ GT , with Gt acting on Pt . Then tr G
m O
! S Qr
≥ tr G
m T O O
! S It,r
.
t=1 r=1
r=1
Proof. The left-hand side corresponds to merging all slots carrying the same label r across the T rounds into the single set Qr , while the right-hand side keeps the same label separated round by round in the sets It,r . We prove that this merging cannot decrease the trace contribution against a positive operator that factorizes across rounds. We induct on T . The case T = 1 is immediate. For T = 2, write Ar := I1,r ,
Qr = Ar ⊔ Br ,
Br := I2,r ,
and G = G1 ⊗ G2 . For each r, decompose min(|Ar |,|Br |)
S Qr =
X
SjQrr ,
jr =0
where SjQrr is the sum of permutations on Qr with crossing number jr . Therefore m O r=1
S Qr =
X
m O
(j1 ,...,jm ) r=1
SjQrr .
17 The sector with all jr = 0 is exactly m O
! S
Ar
m O
⊗
r=1
! S
Br
,
r=1
which is precisely the fully separated operator on the right-hand side of the lemma. It is therefore enough to show that every other sector contributes a nonnegative trace against G1 ⊗ G2 . Fix j = (j1 , . . . , jm ). By the single-label sector identity, for each r there is a positive integer mr such that Ar ⊗ S Br )(SWAPr,jr ⊗ Ir )(S Ar ⊗ S Br ), SjQrr = m−1 r (S
where SWAPr,jr swaps the jr tensor factors selected by the standard representative πjr and Ir denotes the identity on the unswapped factors of Qr . Taking the tensor product over r gives m O
SjQrr = cj (S1 ⊗ S2 )(Fj ⊗ IR1 ⊗ IR2 )(S1 ⊗ S2 ),
r=1
where cj :=
m Y
m−1 r > 0,
S1 :=
r=1
m O
S Ar ,
S2 :=
r=1
m O
S Br ,
r=1
Fj is the product of the labelwise swap operators, and R1 , R2 are the unswapped tensor factors on the two sides. Hence ! m O Qr = cj tr((S1 G1 S1 ⊗ S2 G2 S2 )(Fj ⊗ IR1 ⊗ IR2 )) . tr (G1 ⊗ G2 ) Sjr r=1
Taking partial traces over the unswapped registers, define Xj := trR1 (S1 G1 S1 ) ⪰ 0,
Yj := trR2 (S2 G2 S2 ) ⪰ 0.
Then tr((S1 G1 S1 ⊗ S2 G2 S2 )(Fj ⊗ IR1 ⊗ IR2 )) = tr((Xj ⊗ Yj )Fj ) = tr(Xj Yj ) ≥ 0. In the second equality we used the standard swap identity tr((X ⊗ Y )F ) = tr(XY ) on the swapped tensor factors. Thus every sector contribution is nonnegative, proving the case T = 2. For the induction step from T − 1 to T , define G′1 := G1 ⊗ · · · ⊗ GT −1 ,
G′2 := GT ,
and ′ I1,r :=
T[ −1
′ I2,r := IT,r .
It,r ,
t=1
Applying the proved T = 2 case to the bipartition T[ −1
! Pt
⊔ PT
m O
′ I1,r
t=1
gives tr G
m O
! S
Qr
≥ tr
r=1
G′1
! S
tr GT
r=1
m O
! S
r=1
Now apply the induction hypothesis to the first factor: ! T −1 ! m m O Y O ′ ′ I1,r It,r tr G1 S ≥ tr Gt S . r=1
t=1
Multiplying by the remaining t = T factor proves the claim.
r=1
IT ,r
.
18 FULL PROOF OF INDISTINGUISHABILITY
We now compare the genuine joint Haar-assembled source with the source obtained by independently resampling the Haar states in each round. Throughout this section, dM (·, ·) denotes the total-variation distance between the classical outcome distributions induced by the POVM M . Lemma (Common configuration decomposition). Let M = {Fs }s be a (dk , T )-product POVM. For the comparison between the joint Haar-assembled source Eρ←Ep [ρ⊗kT ] and the roundwise-product source Eρ←Ep [ρ⊗k ]⊗T , there exists a common index set of configurations α and common nonnegative weights λα , with the full outcome distributions satisfy X X P = λα Pα , Q= λα Qα . α
P
α λα = 1, such that
α
The same construction, with the same notion of configuration, applies separately when p is replaced by q. P (t) (t) (t) Proof. A configuration α consists of one count vector b(t) = (b1 , . . . , bm ) for each round t, with r br = k, (t) together with one placement partition I (t) = (It,1 , . . . , It,m ) of the k tensor slots in round t, with |It,r | = br . Expanding m X
!⊗k pr ψr
r=1
in each round gives exactly the multinomial weight k
Y m
(t) (t) b1 , . . . , b m
r=1
T Y t=1
b(t)
prr
for the count vectors, and conditional on the count vector, each placement partition occurs with the same combinatorial multiplicity. For the roundwise-product source, the same per-round expansion occurs independently in each round. Hence the same full configuration weights arise in both models, and pushing these common mixture decompositions through the POVM M gives the claim. Lemma (Hard-instance indistinguishability). For every k-replica T -round POVM M , (kT )2 + kT , dM Eρ←Ep [ρ⊗kT ], Eρ←Ep [ρ⊗k ]⊗T ≤ d and the same bound holds with p replaced by q. Proof. By the product-POVM reduction from Sec. , we may assume M = {Fs }s ,
Fs = Fs,1 ⊗ · · · ⊗ Fs,T .
Fix a configuration α as above and write Qr :=
T [
It,r ,
Ar := |Qr | =
t=1
T X
b(t) r .
t=1
For any finite index set I, write ψ ⊗I for the tensor product of |I| copies placed on the factors indexed by I. Define the conditional joint Haar-assembled state ωjoint,α :=
m O r=1
ψr⊗Qr ,
19 and the conditional roundwise-product state ωprod,α :=
T O m O
⊗I
ψt,r t,r ,
t=1 r=1
where the ψt,r are independent Haar-random pure states. Their induced conditional outcome distributions are Pα (s) := tr(Fs E[ωjoint,α ]) ,
Qα (s) := tr(Fs E[ωprod,α ]) .
Using the Haar moment identity, E[ωjoint,α ] =
m O S Qr r=1
d
, ↑Ar
E[ωprod,α ] =
T O m O S It,r (t)
↑br t=1 r=1 d
.
Hence whenever Qα (s) ̸= 0, Pα (s) = Qα (s)
Nm QT Qm ↑b(t) tr Fs r=1 S Qr d r t=1 r=1 . Qm ↑A · N Nm r T r=1 d S It,r tr Fs r=1
t=1
Here the numerator trace corresponds to the conditional source in which every label-r sector is merged across all rounds into Qr , whereas the denominator keeps those sectors separated as It,r round by round. Since each Fs is positive semidefinite and factorizes across rounds, the permutation inequality gives Nm tr Fs r=1 S Qr N ≥ 1. Nm T tr Fs t=1 r=1 S It,r Therefore Pα (s) ≥ Qα (s)
QT Qm ↑b(t) d r t=1 Qm r=1↑A . r r=1 d
We now estimate the Pochhammer ratio. For nonnegative integers y1 , . . . , yT with Y := y1 + · · · + yT and st := y1 + · · · + yt−1 , QT yt T yY T t −1 ↑yt Y Y X d+u d Y2 t=1 d − 1 = ≥ y y ≥ exp − , ≥ exp u t d↑Y d + st + u t=1 d + st d d t=1 u=0 1≤u<t≤T
where we used log(1 + u) ≤ u for u ≥ 0. Applying this independently to each label r yields the pointwise bound ! m X A2r Pα (s) ≥ cα Qα (s), cα := exp − . d r=1 By the pointwise-domination lemma from Sec. , dTV (Pα , Qα ) ≤ 1 − cα ≤
m X A2 r
d r=1
.
Now let P, Q be the unconditional outcome distributions for the joint Haar-assembled and roundwise-product sources. By the common configuration decomposition, X X P = λα Pα , Q= λα Qα , α
α
with the same coefficients λα . Because the two sources share exactly the same configuration weights, the conditional total-variation bound can now be averaged directly. By the convexity lemma from Sec. , dTV (P, Q) ≤
X α
λα dTV (Pα , Qα ) ≤
X α
λα
m X Ar (α)2 r=1
d
.
20 It remains to average the quadratic counts. (k; p1 , . . . , pm ), so
The round count vectors are i.i.d.
multinomial with parameters
E[Ar ] = kT pr , and E[A2r ] = T (T − 1)(kpr )2 + T k(k − 1)p2r + kpr . Hence m X E[A2 ] r
r=1
d
=
k 2 T 2 − kT X 2 kT X (kT )2 + kT pr + pr ≤ , d d r d r
P P since r pr = 1 and r p2r ≤ 1. This proves the claim. Corollary (Indistinguishability of Ep and Eq ). For every k-replica T -round POVM M , 4(kT )2 dM Eρ←Ep [ρ⊗kT ], Eρ←Eq [ρ⊗kT ] ≤ . d Proof.
By the matching-at-k-copies lemma from Sec. , Eρ←Ep [ρ⊗k ] = Eρ←Eq [ρ⊗k ],
so the claim follows from the triangle inequality and the preceding indistinguishability lemma applied once to p and once to q. FULL PROOF OF ROUNDING
The states in Ep and Eq have the desired eigenvalue weights only approximately, because the underlying Haar-random pure states need not be orthogonal. We now round them to nearby states with exact spectra. Lemma (Rounding to exact spectrum). Let a = (a1 , . . . , am ) be a probability vector and let ψ1 , . . . , ψm be independent Haar-random pure states in Cd . Then with probability at least 0.99, ρ :=
m X
ar ψr
r=1
√ √ is O(m ln m/ d)-close in trace norm to a state with exact spectrum a. Proof. Let Ψ be the d × m matrix whose columns are unit vectors |ψ1 ⟩, . . . , |ψm ⟩, and let G := Ψ† Ψ be the Gram matrix. For two independent Haar-random pure states ψ, ϕ, the overlap satisfies Pr |⟨ψ, ϕ⟩|2 ≥ u ≤ e−(d−1)u , 0 ≤ u ≤ 1. By a union bound, with probability at least 0.99,
ln m max |⟨ψi , ψj ⟩| = O i̸=j d 2
.
Therefore 1/2 ! √ X m ln m 2 √ ∥G − I∥F ≤ |⟨ψi , ψj ⟩| =O . d i̸=j For sufficiently large d, the right-hand side is smaller than 1/2, so the square-root stability lemma from Sec. gives ∥G1/2 − I∥2 ≤ ∥G − I∥2 .
21 Define Φ := ΨG−1/2 , whose columns are orthonormal, and let A := diag(a1 , . . . , am ),
σ := ΦAΦ† .
Then σ has exact spectrum a. Since ρ = ΨAΨ† = Φ G1/2 AG1/2 Φ† , we have ∥ρ − σ∥1 = ∥G1/2 AG1/2 − A∥1 . Writing H := G1/2 − I, we obtain G1/2 AG1/2 − A = HA + AH + HAH, and therefore ∥ρ − σ∥1 ≤ 2∥H∥2 + ∥H∥22 = O
! √ m ln m √ . d
This proves the claim. For each of the two spectra, choose a measurable rounding map and define the exact-spectrum rounded ensembles Ep′ := {fp (ρ)}ρ←Ep ,
Eq′ := {fq (ρ)}ρ←Eq ,
so every state in Ep′ has exact spectrum p and every state in Eq′ has exact spectrum q. Lemma (Rounding error under k-replica protocols). For every k-replica T -round POVM M , √ √ dM Eρ←Ep [ρ⊗kT ], Eρ←Ep′ [ρ⊗kT ] ≤ 0.01 + C kT m ln m/ d, and the same holds with p replaced by q, for some absolute constant C. Proof. By convexity of the induced classical total variation, dM Eρ←Ep [ρ⊗kT ], Eρ←Ep′ [ρ⊗kT ] ≤ Eρ←Ep dM ρ⊗kT , fp (ρ)⊗kT . On the good event from the rounding lemma, 1 ⊗kT ρ − fp (ρ)⊗kT dM ρ⊗kT , fp (ρ)⊗kT ≤ 2
1
.
By the tensor-power trace inequality from Sec. , ∥ρ⊗n − σ ⊗n ∥1 ≤ n∥ρ − σ∥1 , so on the good event, dM ρ⊗kT , fp (ρ)
⊗kT
! √ kT kT m ln m √ ≤ ∥ρ − fp (ρ)∥1 = O . 2 d
On the bad event we use the trivial bound dM ≤ 1, whose contribution is at most 0.01. This proves the claim. ADDITIONAL DETAILS FOR OBSERVABLE-WEIGHTED MOMENTS
This section records the calculations deferred from the observable-weighted extension in the main text. The main input is a unitary second-moment formula for XA (U ) := tr(B U AU † ), followed by its application to the embedded hard-pair construction.
22 Lemma (Haar mean and fluctuation formula).
For fixed Hermitian D × D matrices A and B, let
XA (U ) := tr(B U AU † ) for Haar-random U ∈ U (D). Then E[XA ] =
tr(A) tr(B) , D
and Var(XA ) = Proof.
D tr(A2 ) − tr(A)2 D tr(B 2 ) − tr(B)2 . D2 (D2 − 1)
The first moment is immediate from unitary invariance: E[U AU † ] =
tr(A) I, D
hence tr(A) tr(B) . E[XA ] = tr B E[U AU † ] = D For the second moment, unitary invariance of the twirl implies the standard second-order unitary-twirling decomposition; see, for example, Ref. [7]. Thus E (U AU † )⊗2 = αA I ⊗ I + βA F, where F is the swap operator on (CD )⊗2 . Taking the trace against I ⊗ I gives αA D2 + βA D = tr(A)2 , while taking the trace against F gives αA D + βA D2 = tr(A2 ). Solving this linear system yields αA =
D tr(A)2 − tr(A2 ) , D(D2 − 1)
βA =
D tr(A2 ) − tr(A)2 . D(D2 − 1)
Therefore 2 E[XA ] = tr (B ⊗ B) E[(U AU † )⊗2 ] = αA tr(B)2 + βA tr(B 2 ). Subtracting E[XA ]2 =
tr(A)2 tr(B)2 D2
and simplifying gives the stated variance formula. Application to the embedded hard pair. Retain the notation of the observable-weighted extension in the main text. Thus D := ⌊d/2⌋, Π is the rank-D projection from the biased-block reduction, V : CD → Cd is a fixed isometry with V V † = Π, and B := V † OV is the compressed observable with ∥B∥∞ ≤ 1,
| tr(B)| ≥
η D, 2
23 and p, q are the hard distributions from Sec. , so X
pti −
X
i
qit ≥ δt .
i
Define Ap := diag(pt1 , . . . , ptm , 0, . . . , 0), t Aq := diag(q1t , . . . , qm , 0, . . . , 0),
where the trailing zeros fill the D-dimensional block. For Haar-random U ∈ U (D), let σp (U ) := U diag(p1 , . . . , pm , 0, . . . , 0) U † , define σq (U ) analogously, and embed them into the ambient space by ρp (U ) := V σp (U )V † ,
ρq (U ) := V σq (U )V † .
Xp (U ) := tr(Oρp (U )t ),
Xq (U ) := tr(Oρq (U )t ).
Xp (U ) = tr(B U Ap U † ),
Xq (U ) = tr(B U Aq U † ).
Finally, write
Since V † V = ID , we have
Lemma (Constant ensemble gap).
Define ∆t,η :=
η δt > 0. 4
Then for all sufficiently large d, there exist two disjoint intervals centered at E[Xp ] and E[Xq ], each of radius ∆t,η /2, such that 11 11 Pr Xp ∈ Ip ≥ , Pr Xq ∈ Iq ≥ . 12 12 Proof.
Applying the Haar mean formula to Ap and Aq gives tr(B) E[Xp ] − E[Xq ] = D
! X i
pti −
X
qit
.
i
After the harmless sign normalization made in the biased-block reduction, we may take tr(B) ≥
η D. 2
Hence |E[Xp ] − E[Xq ]| ≥
η δt = 2∆t,η . 2
Therefore the intervals ∆t,η ∆t,η Ip := E[Xp ] − , E[Xp ] + , 2 2 ∆t,η ∆t,η , E[Xq ] + Iq := E[Xq ] − 2 2 are disjoint. It remains to bound the fluctuations. Because p and q have support size m = s + 1, which depends only on t, both matrices Ap and Aq have rank at most m and entries in [0, 1]. In particular, 0 ≤ tr(Ap ), tr(Aq ) ≤ 1,
0 ≤ tr(A2p ), tr(A2q ) ≤ 1.
24 Also, since ∥B∥∞ ≤ 1, | tr(B)| ≤ D,
tr(B 2 ) ≤ D.
The Haar variance formula therefore yields Var(Xp ) ≤
D D · D2 = 2 = O(D−1 ), 2 2 D (D − 1) D −1
and the same bound holds for Xq , with an implied constant depending only on t through the fixed support size m. Choose d sufficiently large that Var(Xp ), Var(Xq ) ≤
∆2t,η . 48
Then Chebyshev’s inequality gives ∆t,η 4 Var(Xp ) 1 Pr |Xp − E[Xp ]| ≥ ≤ ≤ , 2 2 ∆t,η 12 and similarly for Xq . Equivalently, Pr(Xp ∈ Ip ) ≥
11 , 12
Pr(Xq ∈ Iq ) ≥
11 . 12
This is exactly the quantitative input used in the embedded hard-pair lemma of the main text.