Verifying randomness in sets of quantum states via observables
Xavier Bonet-Monroig Hao Wang Adrián Pérez-Salinas



[]bonet@lorentz.leidenuniv.nl



[]h.wang@liacs.leidenuniv.nl



[]perezsalinas@lorentz.leidenuniv.nl




We present a metric, average randomness, that predicts the compatibility of a set of quantum states with the Haar-random distribution, by matching of statistical moments, through a known quantum observable.
We show that Haar-randomness is connected to the Dirichlet distribution, and provide a closed-form expression, and simple bounds of the statistical moments..
We generalize this metric to permutation- and unitary-equivalent observables, ensuring that if the extended average randomness is compatible with a Haar-random distribution, then the set of states is approximately Haar-random.


Verifying randomness in sets of quantum states via observables
    Adrián Pérez-Salinas
    April 29, 2024
==============================================================





  
*Introduction —
Verifying the randomness of a set of quantum states composed of n independent systems (e.g. n=2 in the context of qubits) is computationally challenging primarily due to the exponentially growing dimension of the problem with the system size n.
Sophisticated techniques to verify randomness have been developed with the goal of establishing quantum-classical computational separations <cit.>.
More concretely, to distinguish between random states and the uniform distribution <cit.>.
In a broader context, the randomness of quantum states has been shown to have implications on the trainability and expressivity in variational quantum algorithms <cit.>.

Any set of random states, when measured with respect to an observable , outputs a random variable .
A set of states S is Haar-random if the set itself is invariant under unitary operations S={|ψ⟩}={ U |ψ⟩} <cit.>.
Furthermore, random variables can be fully characterized through their statistical moments = x^t, for all integers t, under reasonable conditions <cit.>.
A set of quantum states is said to be a t-design if their t-th statistical moment ^t matches that of the Haar-random distribution for any observable.

In this letter, we study how to verify Haar-randomness in sets of quantum states S through their expectation values with respect to an observable  with known spectrum.
We define the metric average randomness

    = (, S) - (),

to quantify how close is the ensemble S from the Haar-random distribution, characterized by their statistical moments .
To ensure that the ensemble is truly a t-design, and not only with respect to , we extend <Ref> to permutation- and unitary-equivalent families.



  
*Haar-random and Dirichlet distribution —
We show first that the expectation values of quantum states drawn from a Haar-random distribution can be computed using the Dirichlet distribution.

    Let |ψ⟩ be a random state drawn from the Haar-random distribution, and let x be a random variable defined as x_i = |⟨ψ|U|i⟩|^2, for an arbitrary unitary operation U, where |i⟩ is the i-th element of the reference basis.
    Then
    
    x ∼[ 1 / 2],

    with 1 being a vector where all entries are 1.

One can interpret this lemma easily;
the Dirichlet distribution is the family of probability distributions associated with multidimensional variables x, subject to ‖ x ‖_1 = 1.
The Dirichlet distribution is the natural descriptor for projectors of the form |⟨ψ|U|i⟩|^2 due to normalization constraints of quantum mechanics.
Since we assume Haar-randomness, all those projectors must be equivalent, leading to the symmetric Dirichlet distribution (i.e. all α are equal).
This distribution approaches the Porter-Thomas distribution <cit.>, used in the context of boson sampling, and the so-called quantum supremacy experiments.
See <Ref> for details about the Dirichlet distribution, and a more formal proof of <Ref>.
 
The result in <Ref> allows us to describe the expectation value with respect to an observable  of a set of random quantum states as a random variable with the Dirichlet as its underlying distribution. In the remainder of the paper, we consider  a positive semi-definite Hermitian observable. 

Let |ψ⟩ be random states drawn from the Haar-random distribution.
Let  be an observable, with G distinct eigenvalues = (λ_1, λ_2, …, λ_G), λ_i ≥ 0, and multiplicities = (m_1, m_2, …, m_G).
Then, the expectation value is a random variable 

    = λ· x,

where x is a random variable x∼[ / 2]. 

Since the states |ψ⟩ are by assumption Haar-random, we can express them in any basis, in particular in the one that diagonalizes .
Then, we apply <Ref> in the diagonal basis, yielding the results in the theorem.
The Dirichlet parameters m are a consequence of the aggregation properties of the Dirichlet distribution. A detailed proof can be found in <Ref> for a proof. 

From the results in <Ref>, it is direct to compute the statistical moments of , for Haar-random states.
These computations follow immediately from the multinomial theorem and the properties of Dirichlet (see <Ref>).

Let |ψ⟩ be a random state drawn from the Haar-random distribution.
Let  have G eigenvalues = (λ_1, λ_2, …, λ_G) and multiplicities = (m_1, m_2, …, m_G).
Then, the  is a random variable with statistical moments

    μ_t() = ∫_ d(̋ψ) ⟨ψ||ψ⟩^t = 
    ∑_ k 
    ‖ k ‖_1 = tt k(∏_i=1^G λ_i^k_i) Γ(N/2)/Γ(N/2 + t)∏_i = 1^G Γ(m_i/2 + k_i)/Γ(m_i/2),

where Γ(x) is the Gamma function generalizing the factorial <cit.>, and k are vectors of positive integers. 

A detailed proof of this lemma is provided in <Ref>.

Despite the existence of a closed analytical form to calculate any (), its computation becomes unfeasible at large t.
The reason for this bottleneck is the high number of different elements in the multinomial theorem, and the numerical divergence of the Γ(·) function.
Alternatively, it is possible to efficiently estimate () up to precision 𝒪(t/N) by applying Stirling's approximation to <Ref>.

    In the assumptions of <Ref>, we can upper- and lower-bound the statistical moments as
    
    ()/(/N)^t   ≤(1 + t^2 + 3/8t^2 G/min_i(m_i)^2 + 𝒪(t/N)) 
    ()/(/N)^t   ≥(1 - 𝒪(t/N) ).
 

A proof of this corollary can be found in <Ref>.



  
*Sampling expectation values to verify Haar-randomness —
Our next goal is to demonstrate that the statistics generated by measuring  for |ψ⟩∼ S suffices to verify the Haar-randomness of S with respect to . We focus on the statistical moments

    (, S) = [|ψ⟩∈ S]^t.

When S is omitted, then () is measured with respect to the Haar-random. We say that a set of states S is an -shadowed t-design if 

    ||≤ϵ.


To compute , we must first compute (, S), since () can be obtained analytically, assuming the spectrum of  is known. We estimate (, S) via Monte Carlo sampling, with a number of measurements M, namely

    (, S)= 1/M∑_|ψ⟩∈ S ()^t.

The numerical Monte Carlo error is

    δ() = σ̂_t(, S)/√(M),

where σ̂_t(, S) can be approximated empirically:

    σ̅^2_t(, S) = 1/M - 1∑_|ψ⟩_i ∈ S(()^t - (, S))^2 
     = μ̅_2t(Ô, S) -μ̅^2_t(Ô, S).


In order to verify that S is truly a -shadowed Haar-random up to ϵ error, it is sufficient to check that,

    ||≤δ( ),

which immediately implies a lower bound on the number of Monte Carlo samples required.

Let S be a set of N-dimensional states.
We estimate  via Monte Carlo.
Then, a number of Monte Carlo samples 

    M ≥(2 t/ϵ( ()/N)^t)^2  ( 1 + 3/8G/min_i (m_i^2))

is needed to verify that S is ϵ-close to a -shadowed t-design.

A proof of the theorem can be found in <Ref>.

In this analysis, we assume knowledge of the spectrum of  to compute the analytical values ().
One might be tempted to optimize the eigenvalue distribution to tune the obtained values of (), and the number of Monte Carlo samples required to verify -shadowed Haar-randomness to a certain precision.
To this end, we have not looked at the optimal spectral distribution to minimize this bound, but it is a clear line for future research.



  
*Permutations —
Thus far, we have been able to verify whether S is a -shadowed t-design, but this is not sufficient to unequivocally claim that S is Haar-random.
In our protocol, randomness is lost at two points:
(1) <Ref> implies that any measurement is sensitive to the amplitudes of the coefficients in the eigenbasis of , but the phases are neglected.
(2) the aggregation properties used in <Ref> imply that measurements through  are only capable of distinguishing between eigenspaces, but they are blind to any properties of the states within the subspace.

As an example, consider

    = ∑_k= 1^n 1 - Z_k/2,

which is diagonal in the reference basis, |k⟩ = λ_k |k⟩, with eigenvalues λ_k being the number of 1s in the binary representation of the state.
The spectral distribution of  is λ = {0, 1, … N}, with multiplicity Nk. Consider now the family of random states

    |ψ⟩= ∑_k = 0^N √(p_k)|0⟩^⊗ k|1⟩^⊗ n - k,

with p = {p_1, …, p_n} sampled from a Dirichlet distribution defined by the parameters nk/2, for all k ∈{0, 1, …, n }.
This ensemble is specifically designed to accumulate all the relative sizes of the eigenspaces (defined by ) in a one-dimensional linear subspace.
One can trivially see that such a set of quantum states is not random under the Haar-random measure, yet it appears to be when measured with respect to .
By simply applying a unitary transformation to the states -shadowed is no longer Haar-random, showcasing the limitations of the above protocol.

To overcome such limitations, we can average over permutations on the spectrum of  via Monte Carlo.
We extend <Ref> to the family of observables defined as _Π = ΠΠ, where Π are all permutations of N elements in the eigenbasis of .
We define the set S being a ()-shadowed t-design if 

    =    [Π](_Π, S) - () 
     <    ϵ,

and we extend <Ref> to include permutations.

Let 𝒫 be a set of permutations.
Fix a permutation Π.
For this Π we estimate  via Monte Carlo with M samples.
We repeat the process with M_Π different permutations.
We can verify that S is a ()-shadowed t-design if 

    ≤
    (/N)^t 2 t/√(M_Π M) √(1 + 3/8G/min_i (m_i^2))



Now, we connect the arguments of the Dirichlet distribution with the permutations Π.
The action of Π, as seen from the Dirichlet distribution from which x is sampled, is to permute the coefficients α.
Consider the case where S is a (ΠΠ)-shadowed t-design for some Π.
Then, a subset of α need not be affected by such permutation, and subsequently, the underlying Dirichlet distribution must be symmetric.
We can argue that if = ℛ_t^(ΠΠ)(S) ≈ 0 for sufficiently many permutations Π, then exchanging any set of coefficients leads to the same random variable, and in turn, implies a fully symmetric Dirichlet distribution as in <Ref>.

One can compute (, S) by solving a linear system of equations with unknown variables are the partial statistical moments ∏_i x_i^k_i.
Clearly, this vector has exponential size, and thus one must run over exponentially many permutations to solve the linear system.
In turn, this implies that to verify that the ensemble is compatible with a t-design an exponential amount of additional expectation values is needed.

Alternatively, we can leverage Monte Carlo sampling to statistically estimate how close a set, including permutation, is drawn from a Haar-random distribution.

Let S be a set of states of dimension N.
Let  be a N× N Hermitian matrix, and let 𝒫 be the set of all permutations in the eigenbasis of .
If the set S is ϵ-close to a ()-shadowed t-design for all permutations Π, then x, with x_i = |⟨λ_i|ψ⟩|^2 is a random variable coming from a Dirichlet distribution defined by the parameters α, satisfying

    _Π(( 1· x)^t - ( 1· x^Π)^t) ≤2 ϵ/()^2t ,

where x^Π is the permutation of x, that is

    x    ∼[α] 
     x^Π   ∼[α^Π].

In particular, for t = 1 we obtain

    [i, j](α_i - α_j )^2/‖α‖_1^2≤2ϵ/()^2.



We give an interpretation of <Ref>, for detailed proof see <Ref>.
If the set of permutations statistically leads to a small change in the t-moment, then it means that any permutation on the coordinates α must lead to a similar distribution, that is [α] ≈[α^Π], up to ϵ precision.
For the specific case t = 1, we can obtain explicit constraints in the relationships of coordinates in α, namely α_i ≈α_j, for all pairs (i, j). 
However, t=1 is insufficient to provide constraints on the absolute values of α_i, since this information is only accessible for statistical moments with t≥ 2 <cit.>.



  
*Mutually Unbiased Bases —
Permutations over the eigenbasis of  do not suffice to guarantee that the ensemble of states is a t-design because any projective measurement () is necessarily incomplete in terms of information retrieval.
By simple counting, we observe that only with permutations one can access up to 2^n degrees of freedom.
Yet, fully characterizing a n-qubit quantum state via state tomography requires one to perform at least 2^2n independent measurements <cit.>.
Tomographically complete measurements have been previously connected to mutually unbiased basis (MUB) <cit.>. 

We show first that characterizing , extended to permutations and measurements in a complete set of MUB, suffices to perform full tomography of a set of states. 


Let S be a set of states of dimension N.
Let  be an observable, let 𝒫 be the set of all permutations over the eigenbasis of , and let 𝒰 be a complete set of MUB.
Then, the set of operators {U^†ΠΠ U} for Π∈𝒫, U ∈𝒰 are tomographically complete. 

The operators of the form Π_1 Π_1 - Π_2Π_2, can be used to construct observables as ‖‖(|i⟩⟨i| - |j⟩⟨j|), for any pair (i, j). 
These operators, plus the identity, suffice to obtain all relevant information in the eigenbasis of , which combined with the set of MUB, are sufficient to construct a tomographically complete measurement <cit.>.
See <Ref> for a detailed proof.

This observation motivates the use of MUB for extending -shadowed Haar-randomness.
We define a set of states S to be ϵ-close to a ()-shadowed t-design if 
    
    =
            [Π, U](U^†_Π U, S) - ()  
    ||   <  ϵ,

where 𝒰 is complete set of MUB and 𝒫 is the set of all permutations in the eigenbasis of .

As in previous sections, we can estimate the statistical moments (U^†_Π U) via Monte Carlo to approximately obtain .
This allows us to statistically verify the Haar-randomness of the set of states, irrespective of the observable . 

Let S be a set of states of dimension N.
Let  be a N× N Hermitian matrix, and let {Π} be the set of all permutations, and let 𝒰 be a complete set of MUB.
Fix a basis U ∈𝒰.
For this U we estimate ℛ^(U^†ΠΠ U)_t(S) via Monte Carlo, with M_Π different permutations, each with M samples, and repeat the process with M_U different permutations.
We can verify that S is compatible with a ()-shadowed t-design if 

    ≤(/N)^t 2 t/√(M_U  M_Π M) √(1 + 3/8G/min_i (m_i^2)).


The tomographical completeness of the measurements stated in <Ref>, implies that low values of  are only compatible with S being approximately a t-design. 



  
*Conclusions —
We have introduced a metric, , to verify if a set of quantum states is approximately a -shadowed t-design only requiring the expectation values w.r.t. a known observable .
Our first main result is to show that the expectation values of an observable measured with Haar-random states output values that can be related to a Dirichlet distribution.
The second main result shows that if the spectrum of the observable is known, then the statistical moments of the expectation values of Haar-random states can be calculated exactly, albeit computationally costly.
To overcome this cost, we provide an efficient method to lower- and upper-bound the Haar-random moments.
We can extend these results by artificially increasing the measurements on the ensemble. Permutations in the eigenbasis of , allows us to verify the symmetry of the underlying Dirichlet distributions.
Mutually unbiased bases allow us to perform tomographically complete measurements.
If the measurements are, on average, compatible with a t-design, then the ensemble of states must also be close to a t-design.

3mm
 


  
*Acknowledgements —
The authors would like to thank Carlo Beenakker, Jordi Tura-Brugués, Vedran Dunkjo for their support on this project, and Andrei Udriste, Stefano Polla and Tim Coopmans for useful comments.
The authors would like to extend their gratitude to all members of aQa Leiden for fruitful discussions.
This work was supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme.







§ PROOF OF <REF> AND  <REF>


Consider a set of states {|ψ⟩}∼$̋, where is the Haar-random distribution over the complex projective spaceℂ P^N - 1, defined as

    S^N = {|ψ⟩|ψ⟩∈ℂ^N, ‖|ψ⟩‖ = 1 }.


We begin by defining the Dirichlet distribution.

The Dirichlet distribution x ∼ parameterized by α∈ℝ_>0^N is supported on the (N-1)-standard simplex, i.e., x=(x_1, x_2, …, x_N), ‖ x ‖_1 = 1. It has the following probability density function with respect to the Lebesgue measure on ℝ^N-1: 


    f_ Dir( x, α) = Γ(α_0)/∏_i = 1^NΓ(α_i)∏_i = 1^N x_i^α_i - 1,

where α_0 = ‖α‖_1.
It is possible to exactly compute the statistical moments of arbitrary order k = (k_1, k_2, …, k_N),

    [ x ∼]∏_i = 1^N x_i^k_i = Γ(α_0)/Γ(α_0 + k_0)∏_i = 1^N Γ(α_i + k_i)/Γ(α_i).


We now show the relationship between Haar-random states and the Dirichlet distribution.
By assumption, a Haar-random ensemble{|ψ⟩}and{ U |ψ⟩}are statistically equivalent, for any unitary matrixU ∈𝒮𝒰(N). The projectors|⟨ψ|U |i⟩|^2are now a set of random variables, subject to

    ∑_i = 0^N - 1|⟨ψ|U |i⟩|^2 = 1.

Therefore, the random variablesx_i = |⟨ψ|U |i⟩|^2must follow a Dirichlet distribution. This must hold for anyU. In particular, it must hold for any permutation between elements in the computational basis, and therefore the random variablesx_iandx_jmust be indistinguishable for any pair(i, j). This yields 

    x ∼[α 1],

where1is a vector with all entries equal to 1, andαis a normalization constant, and it is the only missing part. For the normalization, we can recall the known result that coordinates (squared) in a multidimensional sphere can be expressed as Dirichlet distributions with parameters1/2<cit.>. This completes the proof. 

We proceed now to proof <Ref>.
The sets of quantum states are Haar-random. We chooseUas the matrix that diagonalizes the observable. This allows us to express the quantity⟨ψ||ψ⟩in the basis ofas

    ⟨ψ||ψ⟩= ∑_i = 1^N λ_i |⟨λ_i|ψ⟩|^2,

whereλ_iare the eigenvalues ofH. Trivially, we obtain that 

    ⟨ψ||ψ⟩= ∑_i = 1^2^nλ_i x_i,

withx ∼[1 / 2].
 
Notice that the symmetric Dirichlet distribution implies thatis insensitive to any permutation of coordinates(i, j)ifλ_i = λ_j. This can be related to the aggregation property of the Dirichlet distribution, namely

    (x_1, x_2, …, x_N) ∼[α_1, α_2, …, α_N] →
        (x_1, x_2, …, x_i + x_j, …) ∼[α_1, α_2, …, α_i + α_j, …].

Therefore, we can group all coordinates with the same eigenvalue and aggregate them under a single random variable, with the corresponding parameter proportional to the multiplicity of the eigenvalue. This yields the desired result.


§ PROOF OF <REF>


The proof is as follows. In order to compute()we recall the multinomial theorem as 

    [](∑_i = Gλ_i x_i)^t = 
    ∑_ k ∈ℕ^G 
    ‖ k ‖_1 = tt k(∏_i=1^G λ_i^k_i) []∏_i=1^G x_i^k_i,

where the multinomial coefficient is defined as

    t k = t!/∏_i = 1^G k_i!.


We recall now <Ref> for computing the expectation values over products ofx_i. This yields the exact formula

    [](∑_i = Gλ_i x_i)^t = ∑_ k ∈ℕ^G 
    ‖ k ‖_1 = tt k(∏_i=1^G λ_i^k_i) Γ(α_0)/Γ(α_0 + t)∏_i = 1^N Γ(α_i + k_i)/Γ(α_i),

withα_0 = ‖α‖_1.


§ PROOF OF <REF>

For the proof, we resume the proof of <Ref>. As a first approximation, we recall 

    Γ(x + a) ≈ x^a Γ(x).

This simple approximation allows us to write

    [](∑_i = Gλ_i x_i)^t≈1/α_0^t∑_ k ∈ℕ^G 
    ‖ k ‖_1 = tt k∏_i = 1^G (λ_i α_i)^k_i.

By definition, the terms in the sum match the multinomial theorem forα_i = m_i / 2. This yields the easy approximation

    [](∑_i = Gλ_i x_i)^t≈( ()/N)^t.


This first approximation implies that() ≈μ_1()^t, and it is not enough to carry out faithful comparisons. To this end, we simplify the statistical moments by applying Stirling's approximation with more terms.

    logΓ(x) = x log x - x + 1/2log(2π/x) + 𝒪(x^-1).


Then 

    log( []∏_i=1^G x_i^k_i) = 
    α_0 logα_0 - α_0 - (α_0 + t ) log(α_0 + t) + 1/2logα_0 + t/α_0
        + ∑_i = 1^G α_i logα_i - α_i - (α_i + k_i ) log(α_i + k_i) + 1/2logα_i/α_i + k_i = 
    α_0 log( α_0/α_0 + t) - t log(α_0 + t) + 1/2logα_0 + t/α_0 + ∑_i = 1^G α_i log( α_i + k_i/α_i) + k_i log(α_i + k_i) + 1/2logα_i/α_i + k_i.


Therefore 

    []∏_i=1^G x_i^k_i = α_0^α_0/(α_0 + t)^α_0 + t∏_i = 1^G (α_i + k_i)^α_i + k_i/α_i^α_i√(α_0 + t/α_0∏_i = 1^G α_i/α_i + k_i).


We now apply a Taylor expansion on each term 

    (α_i + k_i)^α_i + k_i/α_i^α_i =  α_i^k_i(1 + k_i/α_i)^α_i + k_i    = α_i^k_i( 1 + k_i + k_i^2/2α_i + 1/α_i + 𝒪(k_i^3)) 
    α_i^α_i/(α_i + k_i)^α_i + k_i =  α_i^-k_i(1 + k_i/α_i)^-(α_i + k_i)   = α_i^-k_i( 1 - k_i + k_i^2/2α_i - 1/α_i + 𝒪(k_i^3)). 
    √(α_i/α_i + k_i)    = 1 - k_i/α_i + 3/8k_i^2/α_i^2 + 𝒪( (k_i / α_i)^3) 
    √(α_0 + t/α_0)    = 1 + t/α_0 - 1/8t^2/α_0^2𝒪( (t / α_0)^3)

We now combine these expansions with <Ref>. We drop the error in these expansions for being smaller than the error in <Ref>. Rearranging terms we obtain 

    []∏_i=1^G x_i^k_i = 
    α_0^-t(1 - t + t^2/2 + 𝒪(t^3)) ∏_i = 1^G α_i^k_i(1 + k_i + k_i^2/2 + 𝒪(k_i^3))_<Ref> and <Ref> (1 + t/α_0 - t^2/8 α_0^2 + 𝒪( t^3/α_0^3))∏_i = 1^G(1 - k_i/α_i + 3 k_i^2/8 α_i^2 + 𝒪( k_i^3/α_i^3))_<Ref> and <Ref> = 
    α_0^-t∏_i = 1^G α_i^k_i( 1 + 1/2( t^2 + ∑_i = 1^G k_i^2) + 𝒪(k_i^3)) ( 1 + t/α_0(1 - ∑_i = 1^G k_i/α_i) + 3/8∑_i = 1^G k_i^2/α_i^2 - t^2/8 α_0^2 + 𝒪( k^3/α^3))

where𝒪(k^3/α^3)stands for a shortcut as generic third-degree error. 
We focus momentarily on the zeroeth order approximation. Injecting this term into the multinomial expansion from <Ref>, we obtain

    α_0^-t∑_ k ∈ℕ^G 
    ‖ k ‖_1 = tt k(∏_i=1^G (λ_iα_i)^k_i) = α_0^-t(∑_i = 1^G λ_i α_i )^t = ( H/N)^t.

where the last step is made by identifyingλ_iwith the eigenvalues ofH, andα_iwith the corresponding multiplicities. The correction terms can be expressed as

    ( 1 + 1/2( t^2 + ∑_i = 1^G k_i^2) + 𝒪(k_i^3)) ( 1 + t/α_0(1 - ∑_i = 1^G k_i/α_i) + 3/8∑_i = 1^G k_i^2/α_i^2 - t^2/8 α_0^2 + 𝒪( k^3/α^3)) = 
    
        1 + t/α_0( 1 - ∑_i = 1^G k_i/α_i) + 3/8∑_i = 1^G k_i^2/α_i^2 - t^2/8 α_0^2 + 1/2( t^2 + ∑_i = 1^G k_i^2) + 𝒪((k/α)^3).

We make use of the bounds

    ∑_i = 1^G k_i^2    ≤ t^2 
     
        k_i    ≥ 0
 
to bound

    1 + t/α_0( 1 - ∑_i = 1^G k_i/α_0) + 3/8∑_i = 1^G k_i^2/α_i^2 - t^2/α_0 + 1/2( t^2 + ∑_i = 1^G k_i^2) + 𝒪((k/α)^3)    ≤ 1 + t^2 + 3/8t^2 G/min_i(α_i)^2 + 𝒪(t/α_0) 
    
         1 + t/α_0( 1 - ∑_i = 1^G k_i/α_0) + 3/8∑_i = 1^G k_i^2/α_i^2 - t^2/α_0 + 1/2∑_i = 1^G k_i^2 + 𝒪((k/α)^3)    ≥ 1 - 𝒪(t/α_0)

which injected into the calculations for()yields 

    ()    ≤(/N)^t(1 + t^2 + 3/8t^2 G/min_i(α_i)^2 + 𝒪(t/α_0)) 
    ()    ≥(/N)^t(1 - 𝒪(t/α_0) )


§ PROOF OF <REF>

We start by considering the ensemble of statesS = {|ϕ⟩}, with sizeM.
By Monte Carlo method we obtain the estimate(, S)with error 

    δ(μ̅_t(, S)) = σ̂_t(, S)/√(M).

We compare now the estimateμ̅_t(, S)to the Haar-random theoretical valueμ()available in <Ref>, or <Ref>. This quantity is designed as

    = |μ̅_t(, S) - μ_t()|.

Assuming thatΔ_tis small, we can argue thatSforms at-design w.r.t. the observable. Due to the Monte Carlo error, this claim is only true with a certain confidence, which depends on the varianceσ̂_t(, S), to be computed numerically. In the affirmative case oft-designs, we can estimate the variance easily as

    σ_t() = μ_t(^2) - μ_t()^2 = μ_2t() - μ_t()^2.

This variance can be exactly computed from <Ref>. We can easily upper-bound it through <Ref> and obtain

    σ_t() ≤( ()/N)^t (4 + 3/2G/min_i(m_i^2)) t^2,

which yields the condition

    ≤t^2/√(M)()^t/N^t(4 + 3/2G/min_i(m_i^2)).

Therefore, we can only ensureϵaccuracy in detectingt-designs if the number of samples scales as

    M ≥t^2/ϵ^2( ()/N)^t  ( 4 + 3/2 G/min_i (m_i^2))


§ PROOF OF <REF>

By definition, applying any permutationΠto the observable implies that the random variable given by the expectation value of the observableis invariant under any permutation. For the normalization of quantum mechanics, we define the multidimensional variable

    x^(Π)_i = |⟨ψ|Π(i)⟩|^2.

This variable comes from a Dirichlet distribution as

    x^(Π)∼[Π(α)],

withΠ(α)being a permutation over the parametersαdefining the Dirichlet distribution. In particular, if 

    λ· x^(Π_1) = λ· x^(Π_2),

for any{Π_1, Π_2}, thenαmust be insensitive to permutations. 

We formalize this reasoning under a statistical lens. By assumption, we have, 

    _Π((λ· x^(Π))^t - () ) = ϵ_t,

withλbeing the vector of eigenvalues of. Intuitively, forϵ_t = 0, thenx^(Π_1) = x^(Π_2)for all pairs(Π_1, Π_2), and thereforeαis insensitive to permutations. 

We take two random variables associated with two different sets of permutations and compute the variance of the differences.

    _Π_1, Π_2((λ· x^(Π_1))^t - (λ· x^(Π_2))^t) ≤ 2 ϵ_t.

Notice that the permutations can be seen as redundant runs over the indices ofx. In particular, the first permutation performs the average over all eigenvalues, thus transforming theλinto(). Therefore, we obtain

    _Π_1, Π_2((λ· x^(Π_1))^t - (λ· x^(Π_2))^t) 
        = ()^2t_Π(∑_i x_i^t - ∑_i x_Π(i)^t
        )
        ≤ 2 ϵ_t,

leading to the first result. 

In order to give more comprehensible bounds onα, we focus ont = 1, ϵ_t = ϵ. In this case, we know that

    λ· x^Π = λ·α^Π/‖α‖_1.


We focus now on the variance. Explicitly, this is written as

    _Π_1, Π_2(λ·α_Π_1 - λ·α_Π_2) = 1/‖α‖_1^2_Π_1, Π_2( ∑_i λ_i(α_Π_1(i) - α_Π_2(i)))

Notice that the indexiin the eigenvalues does not play a role since it can be reabsorbed by the permutations, thus

    _Π_1, Π_2( ∑_i λ_i(α_Π_1(i) - α_Π_2(i))) = ()^2 _Π_1, Π_2(α_Π_1(i) - α_Π_2(i)).


For the variance, we compute

    _Π_1, Π_2(α_Π_1(i) - α_Π_2(i)) = [Π_1, Π_2]( α_Π_1(i) - α_Π_2(i))^2 - [Π_1, Π_2]( α_Π_1(i) - α_Π_2(i))^2.

The second term is identically0due to periodicity of permutations, thus we are left with only one term. Notice that the permutations can be seen as redundant runs over the indicesi, j, thus

    [Π_1, Π_2]( α_Π_1(i) - α_Π_2(i))^2 = [Π]( α_i - α_Π(i))^2 = [i,j]( α_i - α_j)^2.

The second permutation can be seen as a permutation over the indexi, thus yielding the desired second result

    [i, j](α_i - α_j )^2/‖α‖_1^2≤2ϵ/()^2.


§ PROOF OF <REF>


To obtain the full tomographic characterization of a quantum state, one needs to conduct experiments over an informationally complete set of positive-operator valued measurements (IC-POVM). Such sets of operators can perfectly distinguish between two different states, providing a sufficient number of copies. While infinitely many ways exist to construct sets of IC-POVM, some of these sets are larger than others. In particular, there exist recipes to construct tight IC-POVM, i.e., sets of operators with a minimal number of projectors. the number of elements of such tight systems scale asN^2. 

An almost tight set of IC-POVM can be obtained by combining a reference basis with a set of mutually unbiased bases (MUB).
Two basesU, Vare MUB if

    |⟨i| V^† U |j⟩|^2 = 1/N,

whereNis the dimensionality of the system. A complete set of MUB is a set of bases that are pairwise unbiased. The number of MUB in a complete set scales as(N + 1). The existence of a complete set of MUB is an open problem in general <cit.>. However, for prime-power dimensionsN = p^n, it is possible to construct complete sets of MUB <cit.>.    

Assume now the set of observables|i⟩ ⟨i|, for any reference basis, are available to measure. Then the set

    M_U, i = U⟨i||U⟩^†,

whereUruns over a complete set of MUB is a set of IC-POVMs <cit.>. 

The only step missing is constructing all measurements corresponding to a single basis through the permutations. 
We consider the observablein the diagonal basis of the form

    = diag(0, …, 0_m_0, λ_1, …, λ_1_m_1, …λ_G, …, λ_G_m_G,  ).

We want to construct operators of the form‖‖(|i⟩ ⟨i| - |j⟩ ⟨j|), with‖‖= λ_G. If|i⟩correspond to the0-th eigenspace, and|j⟩corresponds to theG-th eigenspace, then

    ‖‖(|i⟩⟨i| - |j⟩⟨j|) =  - Π(i ↔ j)  Π(i ↔ j).


The prefactor of‖‖is independent of the eigenstates(i, j)because the permutations allow the coefficients to be freely moved. In the case|i⟩, |j⟩belong to eigenspaces in the middle zone of the spectrum, we just need to apply an extra permutation exchanging|i⟩with|0⟩, and|j⟩with|N - 1⟩. 
The new set of operators is given by 

    M_i, j = |i⟩⟨i|  - |j⟩⟨j|.

These sets of operations, together with the resolution of the identity 

    I = ∑_i = 0^N - 1|i⟩⟨i|

allows us to compute any observable of the form

    M_i = |i⟩⟨i|.

Together with the sets of MUB <cit.>, this leads to a set of IC-POVMs, which are tomographically complete.