Efficient unitary designs and pseudorandom unitaries from permutations
Chi-Fang Chen Adam Bouland Fernando G. S. L. Brandão Jordan Docter Patrick Hayden Michelle Xu








In this work we give an efficient construction of unitary k-designs using Õ(k·(n)) quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over (N) to random unitaries over (N) for N=2^n. In particular, we show that products of exponentiated sums of (N) permutations with random phases approximately match the first 2^Ω(n) moments of the Haar measure. By substituting either Õ(k)-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-N) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-N by interpolating from the much simpler large-N limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-N expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension N.



Institute for Quantum Information and Matter,
California Institute of Technology, Pasadena, CA, USA



Department of Computer Science, Stanford University


Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA
AWS Center for Quantum Computing, Pasadena, CA

Department of Computer Science, Stanford University 

Stanford Institute for Theoretical Physics
Department of Physics, Stanford University

Stanford Institute for Theoretical Physics
Department of Physics, Stanford University

Efficient unitary designs and pseudorandom unitaries from permutations

    Michelle Xu
    
========================================================================










§ INTRODUCTION


Pseudorandom states and unitaries are fundamental tools in
quantum information.
By efficiently creating ensembles of states/unitaries that mimic the Haar measure, we can access Haar random properties without paying a cost exponential in the number of qubits.
Broadly speaking, two types of quantum pseudorandomness have been previously considered.
The first is information-theoretic pseudorandomness, where the goal is to generate unitary or state k-designs, i.e., ensembles that match the first k moments of the Haar measure. 
These are the natural quantum analogs of k-wise independent functions or permutations.
This yields information-theoretic k-copy security, and suffices for many applications, such as randomized benchmarking <cit.>, cryptography <cit.>, shadow tomography <cit.>, communication <cit.>, and phase retrieval <cit.>. The second is computational pseudorandomness, where the goal is to create pseudorandom states and unitaries (PRSs and PRUs) that are computationally indistinguishable from Haar <cit.>. These are the quantum analogs of pseudorandom functions (PRFs) or permutations (PRPs), and have found significant applications both in quantum cryptography (e.g., <cit.>) and in the complexity of physical systems, e.g., <cit.>.
This relaxed security notion allows one to obtain properties impossible in information-theoretic settings, such as small ensemble (key) sizes, many copy security, and low entanglement <cit.>.

Many questions remain open in both branches of the quantum pseudorandomness family tree.
On the k-design side, a significant open problem has been to efficiently generate unitary k-designs on n qubits. It is known that this task requires at least Ω(nk) quantum gates <cit.> but so far existing constructions have not achieved the bound, despite much work in the area  <cit.>.
The first efficient and systematic constructions of approximate unitary k-designs which work for large values of k were given by <cit.>, who showed that random local circuits achieved the goal in (k^10.5 n^2) time. This was followed by an improvement to (k^5 n^2) by <cit.> using an improved analysis.
Very recently, this was improved to Õ(k^2n^2) quantum gates by two independent works with different constructions <cit.>, which is still quadratically off from the lower bound.
This stands in contrast to related k-wise independent objects, as optimal constructions with linear scaling in k are known for quantum state designs (e.g., <cit.>) as well as for analogous classical objects, namely k-wise independent functions <cit.> or approximate k-wise independent permutations <cit.>. We note that linear scaling[We emphasize that this refers to the quantum gate count – which is typically the bottleneck in applications – rather than the scaling in the number of bits of classical randomness which was recently achieved by <cit.>. ] in k has previously been shown[We note there have also been plausible arguments that certain continuous time Brownian motions should attain linear scaling <cit.> but the cost of simulating them on a quantum computer remains to be analyzed.] only in restricted cases, such as the limit of large local dimension <cit.>, or if the number of moments matched is small (k≪(√(n))) <cit.>. This problem is not only a fundamental and natural question in theoretical computer science, but has also gathered the attention of the quantum gravity community, because the linear growth in circuit complexity associated with an efficient t-design ensemble (see e.g., <cit.>) is believed to play a role in resolving certain paradoxes in quantum gravity <cit.>.

On the computational pseudorandomness side, a significant open problem is to construct pseudorandom unitaries (PRUs) from standard cryptographic assumptions, such as the existence of quantum-secure one-way functions (OWFs).
While several efficient constructions of pseudorandom state ensembles are known <cit.>, progress has been much more difficult in the unitary case.
While several PRU candidates have been proposed <cit.>, none of them have proven security.
However, a number of objects intermediate between a PRS and a PRU have been rigorously constructed.
For example, Ananth et al. constructed pseudorandom function-like states, a generalization of a PRS that allows one to create polynomially many independent PRSs <cit.>.
Subsequently, Lu et al. constructed what they call pseudorandom state scramblers, which are ensembles of unitaries that produce a PRS from any fixed input state <cit.>.
There has also been a recent construction of parallel-secure pseudorandom isometries between spaces of differing dimensions <cit.>, as well as another variant of a pseudorandom state scrambler for real (orthogonal) states <cit.>.
However, the existence of efficient pseudorandom unitaries with general query security remains open.

In this work, we make progress on both quantum pseudorandomness open problems simultaneously. First, we give a construction of a unitary k-design using quantum gates scaling near-linearly with k, which matches the lower bound on k-dependence up to logarithmic factors.

    There exists an efficient quantum algorithm to generate an ϵ-approximate unitary k-design (in diamond norm) using (k (n)) one and two-qubit quantum gates. The (·) absorbs polylogarithmic dependence on n, k, ϵ^-1.


Second, we also give a construction of a pseudorandom unitary ensemble with nonadaptive security.

    The existence of a one-way function secure against quantum attack implies an efficient quantum algorithm to generate parallel-secure pseudorandom unitaries.

We recently became aware of independent work of Metger, Poremba, Sinha and Yuen <cit.> which obtain similar results for parallel-secure PRUs and k-designs, via a completely different construction and analysis. 

To achieve the above results, we demonstrate that the following meta-result:

    (Pseudo)random permutations can be efficiently lifted to (pseudo)random unitaries.

More formally, we show there is an efficient quantum algorithm which, given black-box access to random permutations (and their inverses) in (N) for N=2^n, creates an ensemble of n-qubit unitaries that is close to the Haar measure in an appropriate sense.
In particular, we show that the ensemble is an approximate unitary k-design for a large value of k, namely k=2^Ω(n).
Our main results are then obtained by substituting different forms of pseudorandomness for the black box permutations from (N). To obtain our k-design result, we show that it suffices to substitute in approximate Õ(k)-wise independent permutations <cit.>. (See <ref>.) Here, the key point is that high-precision k-wise independent permutations are known to be implementable in ((n)k)-time, so this efficiency then directly lifts to our unitary construction. To obtain our parallel PRU, we substitute in quantum secure pseudorandom permutations (PRPs, inverse allowed), which can be derived from quantum-secure one-way functions <cit.>.



 §.§ Main results


To describe our main construction, the basic building blocks are random phased permutations,
random permutation with random complex signs:

    := _z·,  whererandom phased permutations
       unif∼(N) uniformly random permutations on N elements
    _z   : (_z)_ij = δ_ij z_i  where   z_ii.i.d.∼(1).random diagonal complex phases

While we will eventually pursue pseudorandomness, in most of our discussions, it will suffice to treat the  as truly random. Eventually, they will be replaced as needed by suitable classical pseudorandom counterparts.

The central object we build from random phased permutations  is the matrix exponential

    ^θ_m _m  for  θ_m = (1),

where these 2m-sparse Hermitian matrices _m are made of i.i.d. copies of  and their adjoints

    _m    := 1/√(2m)∑_a=1^m (_a+^†_a)   where  _ai.i.d.∼,

which can be thought of as the adjacency matrix for a random graph weighted by random phases. 

The main result of this work is that the product of a few independent copies of these exponentiated sparse random matrices ^θ_m _m, left and right multiplied by independent phased permutations _L and _R, approximates a Haar random unitary for quantum computers making nonadaptive (i.e., parallel) queries. Formally, this nonadaptive query access model considers the quantum channel associated with the k-fold tensor product of random unitary 

    _2k,[]:= _ [ ^⊗ k^†⊗ k ]   with the diamond norm  _1-_2♢: =  (_1-_2) ⊗1-1,

to quantify the probability of distinguishing our construction from Haar using arbitrary entangled inputs and measurements. We say that an ensemble of unitaries is an ϵ-approximate k-design (see, e.g., <cit.>) if the induced channel is close to the k-fold Haar channel in the diamond norm. That is, no possible quantum experiment (with arbitrary computation and ancillas) can distinguish the ensemble from the Haar measure given parallel access to k copies of the unitary.


    An ensemble of unitaries  is an ϵ-approximate k-design if _2k,-_2k,_Haar♢≤ϵ, where _Haar is drawn from Haar random unitaries (N).



We can now state the main technical result: the product of exponentials of sums of random phased permutations is an ϵ-approximate k-design for large values of k and small values of ϵ.

[Unitary designs from product of sparse exponentials]thmparallelPRU
    For each m,ℓ∈ℤ^+, let  be the N-dimensional random unitary formed by a product of the ℓ independent exponentials of the random matrices ^(1)_m, ^(2)_m,⋯, ^(ℓ)_m, left and right multiplied by random permutations _L, _R, i.e.
    
    :=_L Ł( ∏_j=1^ℓ^θ_m ^(j)_m)_R,

    for some m-dependent angle θ_m= (1). Then,  is an approximate k-design in diamond distance. More precisely, for N = 2^n,
    
    _2k,-  _2k,_Haar♢≤Ł(k^8ℓ^8(m^4n^8+ n^8)/N+k^4/m^ℓ).


The point is that the ensemble is an approximate k-design for a superpolynomial value of k, using only very few, specifically (mℓ), random permutations from (N). Since sampling uniformly random permutations requires exponentially many bits of randomness, we are not evading known lower bounds on the cardinality of a unitary design <cit.>.
Crucially, however, the number of iterations ℓ can be small. For example, setting m=2 and ℓ=n yields an approximate  k-design for very large value of k=2^Ω(n), but
even m=2 and ℓ = log^2(n) suffices for a superpolynomial design; on the contrary, spectral gap approaches (e.g., <cit.>) to unitary designs often cost Ω(nk) rounds of products. 

While truly random permutations are still costly to sample from, the key point is that by substituting pseudorandom permutations in their place, we establish the link between classical pseudorandom permutations and quantum pseudorandom unitaries, as seen from the following two corollaries, establishing the aforementioned <ref> and <ref>. First, we consider substituting information-theoretically secure pseudorandom permutations (i.e., k-wise independent permutations) in place of the truly random permutations to obtain an efficient unitary k-design. This requires choosing suitable parameters m and ℓ (see <ref> for completeness).
[Unitary k-designs from k'-wise independence (informal)]corwisetodesign
There is a constant c such that for k ≤ 2^cn, an ϵ-approximate quantum unitary k-design can be efficiently implemented by applying our construction with
 k'-wise independent (discrete) phases and k'-wise independent permutations in place of the truly random phases/permutations, where
 
    k' = (klog(k/ϵ)).



Here, we are making key use of the fact that our construction only relies on k'=(k)-th moments of the permutations via efficient Hamiltonian simulation algorithms (e.g. <cit.>).
Thus our result “lifts”
the efficient construction of k'-wise independent permutations and functions to the construction of unitary k-designs. This is in a similar spirit to recent results of Brakerski and Shmueli that lift 2k-wise independent functions to approximate quantum state k-designs <cit.>.

To achieve an efficient unitary design, we now need to leverage the fact that
k'-wise independent permutations and functions can be implemented in only ((n)k') time.
 However, one caveat is that the best known classical k'-wise independent permutations (<ref>) are only approximately k'-wise independent. Fortunately, explicit, high-accuracy classical k-wise independent permutations do exist, which are of sufficiently low error to not affect the construction.
 This gives us unitary k-designs that are nearly algorithmically and information-theoretically optimal (in terms of k dependence and in the diamond distance). See <ref> for further discussion.
 
    There is a constant c such that for k ≤ 2^cn, an ϵ-approximate unitary k-design can be implemented using 

    ((n) k )     one and two-qubit gates  and  (nk)   bits of classical randomness

where the notation  absorbs factors polylogarithmic in n,k and 1/ϵ. Thus, the k-dependence in the gate complexity and the seed length are both (nearly) optimal. 

Previously, the best known systematic construction of unitary k-designs for superpolynomially large k has gate complexity (n^2k^2)  <cit.>. 

Moving on to computational pseudorandomness, we substitute cryptographically secure pseudorandom permutations (i.e., PRPs) in place of the truly random permutations to obtain a parallel-secure PRU:

 Suppose quantum-secure pseudorandom permutations exist. Then our construction  gives a pseudorandom unitary under nonadaptive queries.


Implement our unitary  using any efficient quantum algorithm given query access to polynomially many _i to super-polynomial precision. We obtain computational pseudorandomness from information-theoretic pseudorandomness by replacing the random phased permutations with the pseudorandom alternatives and applying a simple hybrid argument. Note that the controlled permutations can be efficiently implemented given function queries of permutations (and their inverses).


Note that the existence of quantum-secure PRPs (with inverses) only requires assuming the existence of quantum-secure pseudorandom functions <cit.>, which is a standard cryptographic assumption. Furthermore, if there exists a low-depth implementation of quantum-secure PRPs, then our PRU can also be low-depth with suitable parameters m,ℓ and standard quantum algorithmic implementations. 



 §.§ Proof idea


In a nutshell, multiplying sparse matrices is an efficient way to get a dense matrix, but controlling the diamond distance from Haar requires careful analysis. Prior approaches to unitary k-designs have often been based on the spectral gaps of random walks (e.g., <cit.>), which bootstrap the statistical distance from a comparatively more tractable spectral gap. However, this approach necessarily requires a log-dimensional factor ( log(N^k)) = (nk) multiplicative blowup in the gate complexity due to the conversion from 2-norm to 1-norm. For cryptographic applications, the attacker may perform an arbitrary polynomial number of queries, so security requires a fixed poly-time construction of a superpolynomial k-design, posing a fundamental barrier for spectral gap approaches.

The essence of our alternative argument can be captured in the following observation:

    (1)≈1/√(m^ℓ)∑^m^ℓ_i=1_i(2)≈Ł(1/√(m)∑^m_i=1^(ℓ)_i)⋯Ł(1/√(m)∑^m_i=1^(1)_i),

where the _i are i.i.d. copies of a random phased permutation. The first approximation (1) is nothing more than a central limit theorem (CLT) established using a matrix Lindeberg argument similar to those in <cit.>, but it allows us to obtain a very nice random matrix:  is drawn from the Ginibre ensemble <cit.>, which is a complex Gaussian matrix that is both left and right unitarily invariant. However, the CLT-type convergence rate is too slow (polynomial in the number of summands) and will incur a large Ω((k))-cost scaling with the number of queries k.

The crux of our argument for circumventing the large number of i.i.d. copies is the second approximation (2): a product of sums reproduces the statistics of an independent sum but using many fewer ((mℓ)) copies of _i, as stated in following loosely stated principle:


In the large-N limit, distinct words of permutations are effectively independent of each other.



As an instructive example, when the dimension N is large, the following correlated words of _1,_2 acting on |i⟩ are almost independent of each other:

    Ł(_1|i⟩, _2|i⟩, _1_2|i⟩, _2_1|i⟩) dist≈Ł(_1|i⟩, _2|i⟩, _3|i⟩, _4|i⟩).

Indeed, knowing _1|i⟩ and _2|i⟩ tells us nothing about _2_1|i⟩, unless the very unlikely collision _2|i⟩∝|i⟩ occurs. Applying this intuition to the product of sums, we can get m^ℓ independent s from merely (mℓ) many truly independent s!

At first glance, the above analysis may appear strange, as if we get “more randomness for free” from a much smaller (m ℓ) number of independent elements. Careful thought reveals the approximation in Eq. (<ref>) is possible because we
only consider low-moment properties of the permutations, i.e., we are fixing k≪ N and then taking a large-N limit.
In the N→∞ limit, the large amount of randomness in the permutations themselves effectively “decouples” the different terms, as collisions become vanishingly improbable. Strictly speaking, this precise statement only holds in a non-adaptive setting, i.e., when the inputs are fixed in advance. Of course, sequential/adaptive queries would reveal correlations between these words – for example, if one were able to query _2 after knowing the result of _1|i⟩, it would coincide with _2_1|i⟩.
However, the key point is that under non-adaptive queries[We conjecture our ensemble also gives adaptive security, but we note this would require further proof ideas, such as defining a more refined notion of independence of different words.], such attacks are not possible, and the words effectively decouple.



Unfortunately, proving the validity of the argument above in finite dimensions N is nontrivial. There are nonasymptotic correlations, however tiny, between the distinct words because those words are made of only (mℓ)-many independent random phased permutations. To complete the proof, the remaining and most substantial technical argument is a framework to control those finite-N corrections effectively.

In principle, since permutations are reasonably nice objects, we could brute force through the combinatorics using diagrammatic calculations. With more work, it is possible to go beyond the limit and perform a large-N expansion: for “nice” random matrices ensembles, the Weingarten calculus and its variants frequently yield sums over diagrams with coefficients being rational functions of N. To prove our results, however, it is necessary to control the total contribution coming from all orders in the 1/N expansion. Moreover, it is very challenging to systematically capture the fine-grained combinatorics and cancellations required to deliver strong enough nonasymptotic bounds.


Our main strategy is the following large-N-interpolation principle that guides the path forward:



“Nice” random matrix properties at finite N are controlled by the large-N limit.




Conceptually, we are looking for an interpolation argument: instead of directly calculating a complicated random matrix quantity at finite N, we start with the much simpler large-N limit, and control the finite-N corrections by arguing that the function “changes slowly” as a function of 1/N.

The crucial mathematical tool is a basic fact in polynomial approximation (see <ref>): Markov's “other” inequality states that a real-valued, low-degree polynomial f(x) whose values are bounded on an interval will have bounded derivatives. This seemingly innocent property of polynomials has found profound implications in establishing lower bounds in classical circuit <cit.> and quantum query complexity, a strategy referred to as the polynomial method, e.g., <cit.>. By identifying an often nonobvious interpolation parameter x such that f(x_1) and f(x_2) correspond to the acceptance probabilities of the quantum algorithm on the two cases to distinguish, one can prove that the difference of the distinguishing probabilities f(x_1)-f(x_2) is extremely small. While explicitly understanding all possible adversarial quantum algorithms is essentially impossible, we often do have sufficient structural restrictions to guarantee that f(x_1)-f(x_2) is a bounded degree polynomial which, remarkably, proves to be sufficient.

Our key insight is to draw a direct connection between the large-N expansion in random matrix theory and polynomial approximation by setting the interpolation parameter to be (<ref>)

    x = 1/N  to control the finite-N corrections  f(1/∞)-f(1/N),

which requires constructing a suitable function that fulfills the requirements of the polynomial methods, as the most substantial part of our proof.


We further explain the above high-level intuition in the following sections.  The sum of permutations is not unitary, so we need to consider an exponential of sums, introducing an infinite series in <ref>; in <ref>, we argue that the distinct words _1_3⋯ are independent in the large-N limit; in <ref>, we spell out the central limit theorem for independent sums; in <ref>, we explain how to control the finite-N corrections through interpolation, which is the most involved step.



  §.§.§ A single exponential as a sum of words


To begin with, let us study one exponential of our sparse random matrices ^θ_m. The Taylor series expansion can be formally expressed as a weighted sum over words:[This is also known as the free group when there are no nontrivial relations between the generators.] any product of symbols _1,⋯ ,_m and their inverses _a^-1 = _a^† subject only to the trivial cancellations _a^†_a=^†_a_a=, such as

    _1,_1^†,^†_2_1, _1^3 _2^†_1, …

We denote the set of such words by ({_a}_a=1^m).

    ^θ_m   =  + θ/√(2m)∑_a=1^m Ł(_a+^†_a) - θ^2/21/2mŁ(∑_a=1^m _a+^†_a)^2 + ⋯
        = ∑_i w_i_i   where  _i ∈({_a}_a=1^m).

The expression above is basically a sum over m independent _i and their adjoints but with higher-order corrections due to unitarity. Now, we take iterated products of independent copies of these sparse exponentials 

    ∏_j=1^ℓ^θ^(j)_m = ∑_i⃗=(i_1,⋯,i_ℓ) w_i⃗_i⃗  where   w_i⃗ = (w_i_1,…,w_i_ℓ)   and  _i⃗= _i_1⋯_i_ℓ.*(distinct words: _i⃗_j⃗ for each i⃗j⃗)

We expect the sparsity (and the number of distinct words) to increase exponentially with ℓ, so that merely ℓ∼log(N) iteration may already produce a very dense matrix. To see that the above product is anywhere close to Haar, the hints come from first analyzing the large-N limit where the structure drastically simplifies. 



  §.§.§ Large N limit



<ref> will establish that in the limit of infinite dimension N, fixing the length of the words and the number of queries k, all distinct nontrivial (i.e., non-identity) words can be simultaneously replaced with independent phased permutations. This means that we may replace our complicated, correlated sum with an independent sum in the diamond norm

    _L Ł(∑_i⃗ w_i⃗_i⃗)_R   N→∞=_L Ł(∑_i⃗ w_i⃗_i⃗) _R.*(distinct words are independent in the large-N limit: <ref>)

The additional left and right symmetrizations help prove independence in the parallel query model while also being algorithmically affordable.[We expect the result to hold even without such symmetrization.] The (phased) permutation symmetry reduces the effective dimension so much that the input state can be restricted to a space of dimension depending only on k and independent of N, which allows us to control the statistical distance (diamond norm) without paying an N-dependent conversion loss, which could have been problematic when taking the large-N limit. 


  §.§.§  Central limit theorem


The nice feature of independent sums is that we can invoke the central limit theorem 

    ∑_i⃗ w_i⃗(θ)_i⃗m^ℓ≫ 1≈  since  [ ^(†)_i ⊗^(†)_i] = [ ^(†)_i ⊗^(†)_i] in the sense of k-fold CP channels

where  is the Ginibre ensemble <cit.>, a random nonhermitian matrix with i.i.d. Gaussian entries. (See <ref> for the definition.) Indeed, since the second (mixed) moments match, in the limit of many summands,[ and with some requirement that weights are all reasonably small.] the fine-grained details of the weights w_i⃗ are washed away, and the sum converges to a Gaussian random matrix; see <ref> for nonasymptotic bounds demonstrated using a Lindeberg principle <cit.>. While the Ginibre ensemble is not unitary, its effect in a k-fold Completely positive channel is equal to Haar in the large-N limit (<ref>)

    N→∞=_Haar. in the sense of k-fold CP channels

Intuitively, the Ginibre ensemble  has the same symmetry as a Haar random unitary (left and right unitary invariance) and also behaves like a unitary for fixed input states, as seen by the expectation [^†]=. 



  §.§.§ Verifying the requirements for interpolation


The last and most significant step in our argument is to control the finite-N corrections through an interpolation argument from the large-N limit.
In particular, we choose the function of interest f to be the distinguishing probability between the unitaries =_LŁ(∏_j=1^ℓ^θ_m^(j)_m)_R and _Haar
by defining the key quantity

    f_,(1/N):=Ł[_1] - Ł[_2]  for each    and

where _1 = _2k, and _2 = _2k,_Haar are the corresponding channels.

We aim to control the finite-N distinguishing probability f_,(1/N) from the large-N limit f_,(1/∞) for arbitrary fixed  and  that the quantum attacks may use. We spell out the structural requirements for f_,(1/N) for interpolation:

Low-degree rational functions of N (<ref>). The random permutations are very nice objects that are defined consistently across dimensions N' N, inducing channels _1^(N') and _2^(N'). In particular, the average over permutations can be calculated using a well-defined diagrammatic expansion (<ref>), with coefficients that are low-degree rational functions of N.[Qualitatively, this can be regarded as the analog of Weingarten expansion in the unitary case.] However, the problem is that the test quantum state  and the test operator , which are selected adversarially, do not obviously apply in other dimensions. Finding the suitable extension requires a few arguments: first, the permutation symmetry substantially reduces the number of parameters. Specifically, the Schur-Weyl duality for the commutant of permutations restricts the effective input state  to a much smaller object, the partition algebra _k(N) (<ref>), whose algebraic structure only depends on the number of copies k, in particular being independent of N as long as the dimension is large N ≥ 2k <cit.>.[In fact, the partition algebras stabilize and are all isomorphic for large enough dimension N≥ 2k (<ref>).]  
    While the partition algebra has been studied in the algebraic combinatorics literature, our argument necessitates explicitly describing the embedding with respect to the computational basis in order to verify that the embedding “does not change too quickly” as N increases. This requires a detailed foray into the structure of the partition algebra and writing down an explicit orthogonal basis (<ref>) as a diagrammatic sum to establish that the basis coefficients are rational polynomials in 1/N.

    The above understanding of the algebraic structure allows us to handcraft the suitable extension f_, for other dimensions N'  N
    
    f_,(1/N')    =  Ł[^(N')^(N')_1^(N')]-Ł[^(N')^(N')_2^(N')]

    by defining a family of test operators
    
    Ł(^(N'), ^(N'))   for each    2k ≤  N' ≤∞
    such that     Ł(^(N), ^(N))= Ł(, ).

    The operators ^(N),^(N) for other dimensions N' relate to the original , in dimension N by substituting the basis we found for the partition algebra. In the end, the function f_,(1/N) is (approximately[We need to truncate the rapidly converging Taylor expansion for the exponential function.]) a rational polynomial of N with degree (k) and poles at small integers 1,…, (2kℓ). 
    
    A priori bounds. The expression is a difference between probabilities such that

    f_,(1/N')≤ 2   for each integer   N'.


    Large-N limits (<ref>). The large-N limits of each channel coincide a pair of nicer ones: _1 to the sum over independent permutations ∑ w_i⃗_i⃗→∑ w_i⃗_i⃗, and _2 to the “Gaussian” model: _Haar→_Ginibre.

    Ł[_N'_1_N']    N'→∞=Ł[_N'^(free)_1_N']
    Ł[_N'_2_N']    N'→∞=Ł[_N'^(Ginibre)_2_N'].

    The independent sums ^(free)_1 and Gaussian ^(Ginibre)_1 can be compared by the Lindeberg principle <cit.>, with an error suppressed by (1/m^ℓ) typical in central limit theorems (<ref>). While the most general Lindeberg argument works in any finite dimension N, the large-N limits simplify the calculations.



 §.§ Road map

The remaining sections begin with a summary of the notation and the various random matrix ensembles we will encounter (<ref>), followed by preliminary background (<ref>): Markov's other inequality (<ref>), basic notions in algebra (<ref>), the representation theory of the symmetric group (<ref>), and lastly a self-contained introduction to the partition algebra (<ref>).  

We then derive the main lemmas: how distinct words of permutations can be replaced by independent permutations in the large-N limit (<ref>), deriving an explicit basis for the partition algebra that is low degree in N (<ref>), then extending the test state  and observable  across dimensions (<ref>). The complete proof of the main result is assembled in <ref>.



 §.§ Acknowledgments

We thank Chris Bowman, Dmitry Grinko, Jeongwan Haah, Aram Harrow, Jonas Haferkamp, Tom Halverson, William He, Hsin-Yuan Huang, Martin Kassabov, Yunchao Liu, Fermi Ma, Tony Metger, Quynh Nguyen, Ryan O'Donnell, Alexander Poremba, Arun Ram,  Makrand Sinha, Norah Tan, Joel Tropp, Jorge Garza Vargas, and Henry Yuen for stimulating discussions. We thank the Simons Institute for the Theory of Computing. A.B. was supported in part by the DOE QuantISED grant DE-SC0020360, the AFOSR under grant FA9550-21-1-0392, and by the U.S. DOE Office of Science under Award Number DE-SC0020266. P.H. acknowledges support from AFOSR (award FA9550-19-1-0369), DOE (Q-NEXT), CIFAR and the Simons Foundation.




§ NOTATION

This section summarizes our notation.
We write constants and integration elements in roman font (, π, and t, x ), scalar variables in lowercase (a,b), vectors in bras and kets |ψ⟩, matrices in bold uppercase (,), and vectorized matrices in curly bras and kets |).  We use curly font for several objects: super-operators (), sets (), and algorithms ().


    n       number of qubits
    
      N    (=2^n)    local dimension
    
      k       number of copies
    
      z∈      complex numbers
    [·]       Expectation

Linear algebra:

    |ψ⟩   :      the Euclidean norm of a vector |ψ⟩
    
     |)   :      vectorized operator 
       := sup_|ψ⟩,|ϕ⟩⟨ϕ||ψ⟩/|ψ⟩·|ϕ⟩     the operator norm of a matrix 
    ^*   :      the entry-wise complex conjugate of a matrix 
    ^†   :      the Hermitian conjugate of a matrix 
    ^T   :      the transpose of a matrix 
    _p   := (^p)^1/p     the Schatten p-norm of a matrix 
    _p-p   := sup_[]p/p     the induced p-p norm of a superoperator 
    ♢   :=⊗1-1   the diamond distance to capture inputs entangled with ancillas
    _2k,   :=^⊗ k[·] ^†⊗ k   the CP map associated with k-fold tensor product of

Representation theory:

    λ⃗   ⊢ m    integer partitions (λ_1,λ_2,⋯) of m such that ∑_i λ_i = m, λ_1≥λ_2≥⋯
    λ⃗^*    = (λ_2, ⋯)    integer partitions with the first entry removed
    Π   ⊢ [2k]     set-partitions for 2k elements
    _Π      diagram corresponding to set-partition Π acting on (^N)^⊗ k
    '_Π      like _Π, but distinct blocks have distinct indices
    _k(N)      the partition algebra for (^N)^⊗ k
    Λ_k,N      set of integer partitions corresponding to irreps of _k(N)
    _m       span of diagrams with at most m propagating blocks
    ∈_m       Symmetry group acting on m elements
    p⃗_μ      Young symmetrizer corresponding to irreps labeled by integer partition μ⃗
    
      t ∈ SYT(μ⃗)       the set of standard Young tableaux associated with shape μ⃗⊢ m.





 §.§ Random matrix ensembles

Our technical argument relies on specific properties of several random matrix ensembles. In dimension N (which is often 2^n for n qubits), we denote 

    Haar∼(N) Haar random unitaries
       unif∼(N) uniformly random permutations
    _z   : (_z)_ij = δ_ij z_i  where   z_iHaar∼(1)  random diagonal phases
       : ()_ij∼g + g'/√(2N). Ginibre ensemble

We will use different notations for the symmetric group to highlight the two distinct roles that the group plays in the paper. (N) acts on individual N-dimensional systems while _m acts by permuting copies of those systems for m≤ k. In the above, all Gaussians are i.i.d. centered with unit variance [g]=0, [g^2] =1. The Ginibre ensemble consists of non-Hermitian random matrices, which we normalize such that 

    [^†] = 1·,

making it behave like a unitary in some regards. The random diagonal matrices are not interesting on their own and are meant to multiply with the permutation by

    := _z random phased permutations.

These 1-sparse matrices are basic building blocks enabled by standard pseudorandomness assumptions (Q-PRPs, <ref>; inverses allowed). The central object we consider is the exponential ^θ_m of the sparse random matrices

    _m    := 1/√(2m)∑_a=1^m (_a+^†_a)   where  _ai.i.d.∼. adjacency matrix for phased random graph

The normalization ensures that [_m^†_m] = . The exponentials of the above sparse random matrices can be efficiently simulated on quantum computers using standard algorithms.


For each m, ℓ∈ℤ^+ and θ∈ℝ, the unitary for ^θ_m _m can be implemented at precision ϵ at cost

    (log(m)mŁ(θ√(m)+log(1/ϵ)))      one and two-qubit gates,
      (log(m))     ancillas, 
      and  (θ√(m)+log(1/ϵ))     controlled-queries

 to the SELECT operator (or its adjoint)
 
    ∑_a=1^m |a⟩⟨a|⊗_a.



Use LCU with uniform weights (1/√(2m),⋯,1/√(2m)) to create a block-encoding for 1/√(2m)_m. Then, apply QSVT.




 §.§ Pseudorandomness and k-designs

We briefly recall the notions of both computational pseudorandomness and k-designs.

We say a keyed family of permutations _w∈(2^n) is quantum-secure pseudorandom permutation (PRP) if each _w can efficiently generated, and for any poly-time quantum algorithm , 

    _w(_w,^-1_w) -_∈(N)(,^-1)≤1/superpoly(n).

  That is, the difference in the algorithms' acceptance probability on a random element of the PRP ensemble and on a truly random permutation is super-polynomially small.


On the other hand, a quantum unitary k-design (<ref>) is an information-theoretic notion. When the error is zero, this simply amounts to saying that the following 2k-fold tensors are equal:

    _[^⊗ k⊗^*⊗ k ] = __Haar[_Haar^⊗ k⊗_Haar^*⊗ k].

In the presence of error, the diamond distance (<ref>) quantifies the best a quantum computationally unbounded distinguisher can do given parallel access to the unitary ensemble. Various other norms yield qualitatively different operational meanings in the presence of error, but the unconditional interconversion costs can easily scale with the dimension.



§ PRELIMINARIES

In this section, we collect several technical facts that form the raw ingredients of the argument. In particular, we include a largely self-contained summary of the relevant facts from abstract algebra.



 §.§ Markov's “other” inequality for polynomials




One of the very few techniques available for proving query complexity lower bounds is the polynomial method. The starting point is a rather simple classical result in low-degree polynomials. 


        Let f(x):ℝ→ℝ be a real polynomial of degree d.
    
    sup_x∈ [0,1]|f'(x)| ≤ d^2 max_x∈ [0,1]f(x).


The standard recipe for applying the above to lower-bounding the number of queries required for distinguishing tasks goes roughly as follows: cook up a quantity f that depends on an interpolation parameter x such that 

    
  * The values f(x_1) and f(x_2) correspond to the acceptance probabilities for the two cases to be distinguished. 
    
  * The function f(x) is a low-degree polynomial with a degree d roughly the number of queries.
    
  * The function f(x) can be extended to a larger interval [x_1,x_3] with x_3 - x_1 ≫ x_2-x_1 such that its value remains bounded.

Then, the distinguishing probability must not change too quickly between the two cases provided the degree d is small: 

    |f(x_1)-f(x_2)| ≤ d^2|x_1-x_2|/x_1-x_3max_x∈ [x_1,x_3]f(x).


Applying the above requires a case-by-case adaptation, and creativity is often required to satisfy the combination of constraints. In our setting, the natural yet powerful approach is to select the interpolation parameter to be the inverse-dimension

    x= 1/N  with interpolation range   0 ≤ x  ≤ 1,

which connects to the idea of the 1/N expansion in physics and in random matrix theory.

We will use the following specialized versions as a black-box.
[ We thank the authors of <cit.> for allowing us to include this variant of Markov's other inequality for 1/N-interpolation from their upcoming concurrent work pursuing a different direction, initiated around the same time in the early stages.] 

    Let f(x):ℝ→ℝ be a real polynomial of degree d and let N, N_0 be any nonnegative integers. Suppose that d^2 ≤N_0+1/2,
    
    sup_N ≥ N_0 N Ł|fŁ(1/N)-f(0)| 
            ≤sup_x∈ [0, 1/N_0] |f'(x)|    ≤ 2 d^2 · N_0  sup_N ≥ N_0Ł|fŁ(1/N)|.



In our case, the interpolation range will need to effectively shrink

    0≤ x≤ 1 → 0 ≤ x ≤1/N_0

to handle the presence of gaps in the integer reciprocals {1/1, 1/2,⋯, 1/N,⋯}; this will further worsen the dependence on the degree by roughly (d^2)→(d^4) (since N_0 ≥ d^2-1). 

Consider a rational polynomial of integer N

    fŁ(1/N) = a(N)/b(N)  where    b(N) = ∏_i (N - b_i)^m_i.

Suppose the poles b_i are located within a disc of radius b_i≤ B, and the total degree is d = ∑_i m_i. Then, suppose N_0≥ 8dB +d^2 -1, and f(1/∞) < ∞, we have that
    
    sup_N ≥ N_0 N Ł|fŁ(1/N)-fŁ(1/∞)| 
            ≤ 2d^2(N_0+10dB) sup_N≥ N_0fŁ(1/N).



The above allows us to only keep track of the locations and multiplicity of the pole without worrying about the polynomial degree on the numerator. 





 §.§ Basic algebraic notions


The partition algebra represented on the Hilbert space (()^⊗ k) is an algebra (matrix addition and multiplication) with involution (matrix conjugate transpose). This abstract algebraic structure already imposes structure that will be helpful. We introduce the minimal algebraic assumption as follows.  

    A -algebra  is a set of elements such that
    
    
  * (Closed under scalar multiplication) For any z∈ and _1 ∈,
        
    z_1 ∈.

        
  * (Closed under addition and multiplication) For any _1 , _2 ∈,
        
    _1+_2    ∈
    _1 ·_2    ∈.

        
  * (Distributive and associative) For any _1, _2, _3 ∈,
        
    (_1 ·_2 )·_3    = _1 · (_2 ·_3)
    
                (_1 + _2 ) + _3    = _1 + (_2 + _3)

    



    A †-algebra  is an -algebra with involution (·)^† such that
    
        
  * For any _1 ∈, 
        
    (_1^†)^† = _1.

        
  * For any _1, _2 ∈,
        
    (_1 + _2)^†   = _1^† + _2^†
    
                (_1_2)^†   = _2^†_1^†.

        
  * For any z∈,
        
    (z _1)^† = z^* _1^†.

    


    A †-homomorphism is a map between †-algebras f:→' such that 
    
    f(_1+_2)    = f(_1)+f(_2),
    
            f(_1·_2)    = f(_1)· f(_2),
    
            f(_1^†)    = f(_1)^†.



    A left-ideal  of a ring  is a subring that is closed under multiplying the ring on the left
    
    ⊂.

    Vice versa for the right ideals. A two-sided ideal is both a left and right ideal.



    An algebra whose center consists only of multiples of the identity is called a factor.



    For any finite-dimensional complex Hilbert space , the matrix algebra () is the set of linear transformations →. Moreover, the adjoint or, equivalently, the conjugate transpose w.r.t. any orthogonal basis defines a canonical involution of the algebra.




    Any †-subalgebra  of a finite dimensional matrix algebra (^N) is unitarily conjugate to a direct sum of factors (labeled by λ)
    
    ^† = ⊕_λ_λ⊗  where  _λ = (^d_λ).

    Further, any two-sided ideal  of  must have the structure
    
    ^† = ⊕_λ'_λ⊗  where  '_λ = 
        _λ  or  '_λ = 0,

    and the quotient is isomorphic to another ideal 
   
    /≃' ≃⊕_λ”_λ⊗  where  ”_λ = 
        0   or  ”_λ = _λ.

    The quotient can be naturally understood as a projector _: →' ⊂ by _[_λ⊗]= _λ”⊗, which is also a †-homomorphism.


This is a consequence of the Artin-Wedderburn theorem. See <cit.> for a self-contained exposition.


    For a group , the group algebra  consists of formal weighted linear combination of elements _i ∈
    
    ∑_i z_i_i ∈,

    with multiplication given by the group multiplication _1·_2.




 §.§ Representations of the symmetric group


This section includes a minimal review of the representation theory of the symmetric group that will be helpful for working with the partition algebra; see <cit.> for a textbook introduction.


  §.§.§ Integer partitions



For any nonnegative integer N∈ℤ and vector of nonnegative integers λ⃗, we say that λ⃗ is an integer partition of N, or 

    λ⃗ = (λ_1,⋯,λ_ℓ) ⊢ N   whenever  λ_1+⋯+λ_ℓ=N   and  λ_1≥λ_2⋯≥λ_ℓ.

We will also denote the related notions by

    λ⃗:= λ_1+⋯+λ_ℓ  and  λ⃗^* := (λ_2,⋯, λ_ℓ).

In our usage for labeling the irreducible representations of the partition algebra _k(N) by λ⃗∈Λ_k,N, we will often consider a partition of the local dimension N such that the first row is λ⃗-λ⃗^*≥ N-k. Since the length of the first row is fixed by the remaining boxes λ_1 = N- λ⃗^*, we will also only focus on the partition of the remaining boxes, often denoted by λ⃗^⃗*⃗=μ⃗⊢ m.



  §.§.§ Young diagrams and Young tableaux

Any integer partition μ⃗⊢ m corresponds to a Young diagram (Fig. <ref>). In particular, one can fill in numbers 1,…, m in arbitrary order, giving a Young tableau. For a given shape μ⃗⊢ m, a standard Young tableau t ∈ SYT(μ⃗) has its rows increase from left to right, and the columns increase from top to bottom. For each integer partition μ⃗, the column-reading tableau t_c ∈ SYT(μ⃗) fills in the Young diagram by going down the columns from left to right from 1 to m. 



  §.§.§ Irreducible modules


This section describes the irreducible modules of the symmetric group algebra, and the notions presented here will prove useful when studying the partition algebra. For each Young tableau t of shape μ⃗, define the particular permutation

    _t  such that  _t: t_c → t ∈ SYT(μ⃗).

That is, _t is the permutation that sends the column-reading Young tableau t_c to the Young tableau t.

For each integer partition μ⃗⊢ m, consider the Young symmetrizer

    p⃗_μ⃗ := ∑_∈ C(t_c)∑_'∈ R(t_c)sgn()' ∈_m

where _m is the group algebra (<ref>) for the symmetric group _m, C(t_c) is the subgroup of permutations that preserves the rows of t_c, R(t_c) the one for the columns, and sgn() is the sign of the permutation .


For each integer partition μ⃗⊢ m, the space

    -span{_t p⃗_μ⃗}_t∈ SYT(μ⃗)⊂_m

is a copy of the irreducible module ^μ⃗_m labeled by μ⃗ in the left regular representation of _m.



    There exist u⃗_t∈-span{_t'}_t'∈ SYT(μ⃗) such that 

    -span{_t p⃗_μ⃗}_t∈ SYT(μ⃗) = -span{_t p⃗_μ⃗}_t∈ SYT(μ⃗)

and the map 
    
    u⃗_t p⃗_μ⃗p⃗^†_μ⃗u⃗^†_t'→|t⟩⟨t'|  is a †-isomorphism.

 Therefore, the span
    
    -span{u⃗_t p⃗_μ⃗p⃗^†_μ⃗u⃗^†_t'}_t,t'∈ SYT(μ⃗)⊂_m

is a factor as a †-subalgebra.


    For each irrep labeled by μ⃗, run any orthogonalization procedure and fix it. The point is that this solely depends on the irrep label μ for the symmetric group (and not on the dimension of the computation basis).

Note that the above notions can be discussed abstractly without considering the computational basis (or we could represent the permutation by acting on m many copies of N-dimensional Hilbert space _m). 
In contrast, the multiplication rule for the partition algebra _k(N) depends on N, and we expect the basis to also explicitly depend on N. We will see that the inclusion [_m] ⊗_k-m⊂_k(N) will be very helpful in analyzing the structure of the partition algebra, and the objects u⃗_t p⃗_μ⃗∈_k(N) defined above will play a crucial role.



  §.§.§ The computational basis

Consider k copies of N-dimensional Hilbert spaces (ℂ^N)^⊗ k and its matrix algebra ((ℂ^N)^⊗ k). A natural choice of orthonormal basis is the computational (orthonormal) basis |m⟩,
which naturally extends by the tensor product structure

    =ℂ^N   = Span{|m⟩}_m ∈ [N]
    inducing       (ℂ^N)^⊗ k   = Span{|m_1⟩⊗⋯⊗|m_k⟩}_m_i ∈ [N],
      inducing  ((ℂ^N)^⊗ k)     = Span{=:_m⃗|m_1⟩⊗⋯⊗|m_k⟩·⟨m_k+1|⊗⋯⊗⟨m_2k|}_m_i ∈ [N],
       vec.≡Span{=:|_m⃗)|m_1⟩⊗⋯⊗|m_k⟩·|m_k+1⟩⊗⋯⊗|m_2k⟩}_m_i ∈ [N].


The algebra ((ℂ^N)^⊗ k) as a -vector space is naturally endowed with the Hilbert-Schmidt inner product [^†_1_2]. When the multiplication structure is unimportant, we may vectorize (vec. as above) the matrices into vectors of doubled dimension to focus on the Hilbert space structure. The inner produce remains the same by (_1|_2):=[^†_1_2].

Formally, for a matrix , let us denote its vectorization (or purification) by 

    |):= (I ⊗ T)

using the “transpose” map T⟨i|=|i⟩ to turn bras into kets. 
Consequently, the definition extends to the vectorization of a superoperator by

    𝒩[·]=∑_j  α_j _j[·]_j →𝒩⃗=∑_j α_j _j⊗^T_j

where ^T_j denotes the transpose of the matrix _j in the computational basis |i⟩. We use curly fonts  for superoperators and bold fonts  for the vectorized superoperators, which are themselves matrices. 



 §.§ The partition algebra


In quantum information, we often consider the commutant of tensor copies of unitaries

    Ł({^⊗ k}_∈(N))' ⊂((ℂ^N)^⊗ k).

This commutant algebra is completely characterized by Schur-Weyl duality and the representation theory of the symmetric group. In this article, we are interested in the commutant of tensored permutations ^⊗ k, called the partition algebra _k(N), which depends on the number of copies k and the dimension N:

    _k(N) := ({^⊗ k}_∈(N))' ⊂((ℂ^N)^⊗ k)  where  |i⟩ = |S(i)⟩  for each   i = 1,…, N.

In the case N ≥ 2k, Schur-Weyl duality also holds as follows:

    _k(N)    ≡⊕_λ⃗∈Λ_k,N_λ⃗⊗__λ⃗  and  -span{^⊗ k}_∈(N) = ⊕_λ⃗∈Λ_k,N__λ⃗⊗_λ⃗
    acting on   (^N )^⊗ k   ≡⊕_λ⃗∈Λ_k,N__λ⃗⊗__λ⃗

where the irreps are labeled by integer partitions 

    λ⃗∈Λ_k,N := {λ⃗⊢ N | 0 ≤λ⃗^*≤ k}.

Indeed, since the permutations acting naturally on the computational basis are a special subset of the unitaries, (N) ⊂(N), the commutant is larger ({^⊗ k}_∈(N))' ⊂_k(N). Crucially for our later argument, the algebra “stops changing” after N ≥ 2k[This is a different regime from some other applications where N ≪ 2k, e.g., <cit.>.].

    If N ≥ 2k, the dimension of the partition algebra (sum of dimensions of the irreps) is dim(_k(N)) = Bell_2k, which is independent of N. In fact, for each fixed k, the partition algebra stabilizes in terms of N. That is, the irreducible algebra representations are isomorphic (as algebras)
    
    _λ⃗≃_λ⃗'⃗  whenever  λ⃗^⃗*⃗ = λ⃗^⃗'⃗*⃗  and  λ⃗,λ⃗'⃗≥ 2k.



 
The Bell numbers are bounded by
    
    Bell_n≤ n!  for each   n ∈ℤ.


 
    For each integer partition λ⃗∈Λ_k,N, the dimension of the corresponding irreducible representation of the symmetric group is a polynomial of N
    
    _λ⃗ = N!/∏_(i,j)∈λ⃗h(i,j) =  N^b_0(λ)(N - 1)^b_1(λ)· (N - 2k -1)^b_2k-1(λ)/∏_(i,j)∈λ⃗^* h(i,j) = s_λ⃗(N)

    where h(i,j) is the hook length of the Young diagram associated with shape λ⃗
    
    b_j  = 0, 1   and   deg (s_λ⃗) = ∑ b_j = λ⃗^*≤ k.


From <ref>, viewing the dimension as a function of N, we see that the zeros are located at integer values in a bounded range and have multiplicity at most one. Strictly speaking, we can restrict to a stronger symmetry as we actually use phased permutations (see, e.g.,  <ref>). Nevertheless, most of the discussions will consider the permutation (N) as it is more general and well-studied.


  §.§.§ Set-partitions

Following the notation of <cit.>, consider partitions Π of a set with ℓ elements. (It will be convenient to distinguish notationally from the integer partitions discussed in <ref>.)
We write

    
  * Π⊢{1,⋯, ℓ}   iff Π is a set-partition of {1,⋯,ℓ}.

  * (i,j) ∈Π   iff (i, j) are in the same block (also known as a cycle) of Π.

  * Π:= (number of blocks of Π).

  * Π_1 ≤Π_2 iff (i,j) ∈Π_1  (i,j) ∈Π_2, which reads “Π_1 is a refinement of Π_2.”

For example, let Π = {{1,3},{2}}, then

    Π⊢{1,2,3},    (1,3) ∈Π,   and  Π =2.

The partial order structure between integer partitions will become important, and we will make use of generalized inclusion-exclusion principles. This can be understood in linear algebraic terms.


Any finite set with partial order can be extended as a subset of a totally ordered set. Therefore, the partial order can be (nonuniquely) represented as an upper triangular 0/1-matrix  satisfying M_ij = 1 if and only if i≥ j. 


    For any finite set with partial order induced a partial order for any subset. Restriction of an upper triangular matrix on a subset of indices remains upper triangular.


    Any upper triangular matrix with nonzero diagonals is invertible by another upper triangular matrix.


This follows immediately from the expression for the inverse of a matrix in terms of its adjugate <cit.>.




  §.§.§ Explicit presentation




The partition algebra _k(N) can be defined abstractly but, for concreteness, we will explicitly present it in the computational basis throughout this work. We need to introduce new notation to capture this high-dimensional object. In particular, for our purposes, the notation in this section assumes we are in the stable range where N ≥ 2k >0. Let

    m⃗   = (m_1,⋯, m_2k) ∈{1,⋯, N}^2ktuple of indices
    
        M'_Π   := {m⃗: m_i = m_j   iff   (i,j)∈Π}. set of m⃗ whose partition is exactly Π
    
        M_Π   := {m⃗: m_i = m_j   if   (i,j)∈Π}. set of m⃗ whose partition is refined by Π

The two types of sets M_Π, M'_Π are related by the union

    M_Π = ⋃_Π' ≥Π M'_Π',

where each M'_Π' are disjoint from each other.

The cardinality of sets M_Π, M'_Π is given by an elementary calculation:

    M'_Π = N (N-1)⋯ (N- Π+1)  and  M_Π = N^Π.

In particular, observe that both quantities are polynomials in N, and the zeros are located at integer values – this seemingly innocent structure will play a crucial role in our interpolation argument. Using the above notation, the partition algebra _k(N)⊂((ℂ^N)^⊗ k) is a †-algebra presented by a ℂ-linear combination of the following operators (using the notation of (<ref>)): 

    _k(N) = Span_ℂ{_Π}_Π  where  _Π   :=  ∑_m⃗∈ M_Π_m⃗  for each  Π⊢{1, ⋯, 2k}.

These can be described diagrammatically, as illustrated in <ref>.
The involution (i.e., adjoint) acts as 

    ( _Π )^† = _Π^†  where  Π^†⊢{1, ⋯, 2k}.

Graphically, the involuted partition Π^† amounts to flipping it “upside down,” which is consistent with the matrix adjoint. The multiplication operation (realized as matrix multiplication) acts nicely on these operators by 

    _Π_2_Π_1 = _Π_2·Π_1· N^d(Π_2,Π_1),

where the multiplication rule for set-partitions Π_2·Π_1 is summarized in <ref> and given in more detail in <cit.>. The integer d is a function of both Π_1 and Π_2 but independent of N. Graphically, 

    d = # ( components without free legs after multiplying Π_1 and Π_2 ).

While _k(N) depends on both k and N, the algebraic structure is mainly determined by k since Π⊢{1, ⋯, 2k}; the dependence on N only comes in as a multiplicative weight N^d(Π_2,Π_1). Alternatively, we may describe the algebra in the orthogonal basis

    '_Π   :=∑_m⃗∈ M'_Π_m  such that  [ '^†_Π''_Π] = δ_Π,Π'·'_Π^2_2   for each  Π,Π' ⊢{1, ⋯, 2k}.,

as drawn in <ref>.
This new set of operators is related to the original ones by a Möbius inversion (a generalized inclusion-exclusion principle for partial orders, <ref>, <ref>) 

    _Π   =  ∑_Π' ≥Π'_Π'
       = ∑_Π' ⊢{1, ⋯, 2k} K_ΠΠ''_Π'  where   K_ΠΠ' := (Π' ≥Π)
    '_Π   =  ∑_Π' ⊢{1, ⋯, 2k} (K^-1)_ΠΠ'_Π'

where ^-1 is the Möbius inversion of ; indeed, the matrix  is upper triangular with ones on the diagonals and thus invertible (<ref>). Importantly, the entries of matrix  only depend on the combinatorial structure of Π⊢ 2k and are independent of N.

For simplicity, we can ignore the multiplicative structure and vectorize the operators (by turning bras to kets (<ref>)). In this picture, it is convenient to think about the orthogonal basis |'_Π) which, as we've seen, can be expressed by a linear combination of |_Π).

    |'_Π)    :=∑_m⃗∈ M'_Π |_m⃗)   where   ('_Π|'_Π) = '_Π^2_2=M'_Π  for each  Π⊢{1, ⋯, 2k}.


Then, the action of tensored permutations can be written as a superoperator projecting ((ℂ^N)^⊗ k) →_k(N) ⊂((ℂ^N)^⊗ k)

    _2k,:= [^⊗ k( · )^†⊗ k ]   = ∑_Π⊢ 2k'_Π['_Π (·) ]/'_Π^2_2,

or as an operator after vectorization

    _2k, :=  [^⊗ k⊗^*⊗ k ]   = ∑_Π⊢ 2k|'_Π)('_Π|/'_Π^2_2,

where the Hilbert-Schmidt norm reads _2 = √([^†]) = √((|)). Importantly, for each Π, the zeros of the normalization factors M'_Π are contained in the integer set {0,1,⋯, 2k} by <ref>. The operators _Π are also nice in the sense that

    [^†_Π_1_Π_2] = N^c(Π_1,Π_2)  for each partition  Π⊢{1, ⋯, 2k}

for an integer c(Π_1,Π_2) depending only on Π_1,Π_2 (and independent of N); graphically, 

    c(Π_1,Π_2) = # ( connected components after fully contracting Π_1^† and Π_2).

This also gives the inner product 

    [^†_Π_1_Π_2]/_Π_1_2_Π_2_2 = 1/√(N)^δ c(Π_1,Π_2)  where  δ c(Π_1,Π_2) = c(Π_1,Π_1) + c(Π_2,Π_2) - 2c(Π_1,Π_2).







  §.§.§ Algebraic structure

The two-sided ideals _m(N) for 0 ≤ m ≤ k defined by

    _m (N):= -span{_Π | Π⊢ 2k  has at most m propagating blocks}

will play a central role in understanding the algebraic structure.
A block in Π is propagating if it contains both nodes at the bottom and the top (<ref>).
Indeed, since diagram multiplication, from either the left or the right,  cannot increase the number of propagating blocks, we have that

    _k(N)_m(N) = _m(N) _k(N) ⊂_m(N).

These ideals are naturally related by

    _0⊂_1 ⊂⋯_k = _k(N).



The quotient projector acting on the partition algebra _k(N) can be written as

    __m[·] = ∑_λ⃗^⃗*⃗> m Π⃗_λ⃗·Π⃗_λ⃗,
  
where the projectors Π⃗_λ⃗∈_k(N) correspond to the irreps of the partition algebra _k(N) labeled by λ⃗∈Λ_k,N.


    For any λ⃗∈Λ_k,N, consider the orthogonal basis representatives we construct later in <ref>, and note that the matrix element is written as some element in _λ⃗^* modulo _λ⃗^*-1. Therefore, if λ⃗^⃗*⃗>m, __m acts as the identity, and otherwise, it acts as zero, which coincides with the advertised expression.

It will also be crucial to consider the symmetric group algebra as a subalgebra

    _m ⊂_k(N)   for each   1 ≤ m ≤ k

where _m acts on the leftmost m nodes (<ref>).



§ NEW LEMMAS

In this section, we prove the key new lemmas that are foundational for our main results. 



 §.§ Asymptotic freeness of random permutations


The power of large-N limits is that a version of “freeness” kicks in for random permutations: different words are effectively independent from each other. The concepts of free groups and free words will be particularly helpful.

    For a countable set of symbols {s_i}, we denote the set of free words by 
    
    ({s_i}_i) = {e, s_1, s_2, s_1s_2, s_2s_1,s_1^-2, ⋯},

    which are also the elements of the free group generated by {s_i}_i.

 
    Consider the free words generated by a set of m independent uniformly random phased permutations
    
    ({_a}_a=1^m)   where  _a i.i.d.∼.

    Fix integers ℓ,k and fix a set of ℓ distinct words _1,…, _ℓ∈. Consider a corresponding set of ℓ independent permutations
    
    _i := i.i.d.∼     if  _i 
         if  _i= .

    Then, for each j⃗∈ [ℓ]^2k, in the large-N limit,
    
    lim_N→∞_2k,∘( _j⃗, {_i} -_j⃗, {_i})∘_2k,♢ = 0,

    where
    
    _j⃗, {_i}   :=_j_1⊗⋯_j_k [·] ^†_j_k+1⊗^†_j_2k,      j⃗∈ [ℓ]^2k, 
    _2k,   := ^⊗ k [·] ^†⊗ k



Roughly speaking, we want to show that in the large-N limit, distinct nontrivial words can be replaced by independent random permutations {_i}→{_i} (identity remains the identity) in the sense of tensored mixed moments (which may not be completely-positive). Here, we are showing this channel equivalence holds, when the overall channel is first symmetrized by a random phased permutation before and after our words by the channel _2k,. This symmetrization allows us to restrict the test operators to a proper subalgebra of the partition algebra with nicer properties. Let

    B_2k:={Π⊢{1,⋯,2k}| each block has an equal number of sites on top and bottom.}

then, the commutant of phased permutations are exactly the associated diagrams. In particular, every block is propagating.


    (^⊗ k)^' = -Span{'_Π|Π∈ B_2k} = -Span{_Π|Π∈ B_2k}.
    


    Recall that the random phased permutation can be written as := _z. We already have that the commutant of (^⊗ k)^' is the partition algebra _k(N) with orthogonal basis {'_Π| Π⊢ 2k }. It follows that (^⊗ k)^'⊂ (^⊗ k)^' = _k(N). Any '_Π for Π∈ B_2k is contained in the commutant (^⊗ k)^' as the balanced signs from _z cancel each other out, and the unsigned permutations  fixes the diagram
    
    _2k,['_Π]   =_2k,∘_2k,_z['_Π]
       =_2k,['_Π]Since Π∈ B_2k
       = '_Π.Since '_Π∈_k(N)

    Conversely, for any other diagram Π∉ B_2k, there exists a non-balanced block, and thus the operator '_Π would vanish under the symmetrization _2k, due to the unbalanced signs on that block. Next, we show that _Π for Π∈ B_2k also form a basis for the commutant (^⊗ k)^'. This is because each diagram _Π for Π∈ B_2k can written as '_Π for Π∈ B_2k
    
    _Π = ∑_Π'≥Π'_Π'

and that each Π∈ B_2k can only be refinements of Π'∈ B_2k

    Π'≥Π, Π∈ B_2kΠ' ∈ B_2k.

Therefore,

    -Span{_Π|Π∈ B_2k}⊂-Span{'_Π|Π∈ B_2k}.

Since the two vector spaces have the same dimensions, they must be equal.


We can now prove the asymptotic freeness of phased random permutations.

We begin with controlling the 1-norm for particular “factorized” inputs (see (<ref>))

    ( _j⃗, {_i} -_j⃗, {_i})[_m]1  for any fixed   m ∈ M'_Π.

This effectively becomes a classical probability problem since the input is factorized. The case for  is simple

    _j⃗, {_j}[_m] N→∞=
        _Π(j⃗,m)/_Π(j⃗,m)_1     if each block of m is acted by “balanced” top-bottom pairs of _j and ^†_j
    
            0     else

where the convergence is accounted in 1-norm. Basically, the signs need to cancel each other within each block of m for the expression to contribute (i.e., if _3 appears in the top row of a block, then _3^† must appear in the bottom row.). When they are perfectly balanced and the signs all cancelled, they give a mixture of random _m' that (up to 1/N correction in trace distance) corresponds to a particular partition Π(j⃗,m)≥Π which refines the partition Π of m according the types of _j present in the same block. In particular, this newly produced partition remains in Π(j⃗,m) ∈ B_2k, and is propagating.
The case of _j is very much the same, up to a vanishing “collision probability” ∼1/N (fixing the length of words and k). To see this, first sample the permutations within _j without the signs. With high probability 1-(1/N) (“without collision”), the signs for each _j in different blocks will be independent. That is, after sampling over signs (conditioned on the permutations), we have a situation very similar to _is:

    _j⃗, {_i}[_m] N→∞= _Π(j⃗,m)/_Π(j⃗,m)_1     if each block of m is acted by “balanced”_j and its conjugates ^†_j
    
            0     else.

When the signs perfectly cancel out, in the large-N limit, distinct words acting on distinct inputs are independent from each other, which again gives _Π(j⃗,m)/_Π(j⃗,m)_1. That is,

    lim_N→∞( _j⃗, {_i} -_j⃗, {_i})[_m]1 = 0.

Now, we use the above to prove for general unentangled PSD -symmetrized inputs = _2k,[]. Any such input can be written as a weighted sum over (orthogonal) diagram operators squared

    = Ł(∑_Π∈ B_2k c_Π'_Π/'_Π_2)Ł(∑_Π∈ B_2k c_Π'_Π/'_Π_2)^†  such that  ∑_Πc_Π^2 =1,


In particular, we observe that each cross terms has bounded 1-norms

    '_Π/'_Π_2^'†_Π'/'_Π'_21≤ 1 Cauchy-Schwarz

and that

    '_Π'_Π'∝'_Π”  for  Π,Π',Π^”∈ B_2k.

This allows us to study the inputs as individual diagrams '_Π (instead of arbitrary linear combinations). Remarkably, '_Π (when normalization by its 1-norm) behaves very much like a classical probability distribution in the following sense

    '_Π/'_Π_1 = 1/M'_Π∑_m∈ M'_Π_m   where  _m_1 =1.

This is because the “balanced” structure allows us to calculate its 1-norm by permuting the top row _Π_1 = _σ_Π_1 = M'_Π; otherwise the 1-norm normalization may not have a good connection to 1/M'_Π∑_m∈ M'_Π_m. It is crucial here that all blocks are propagating, as a nice feature of these “balanced” diagrams in B_2k.

Based on the above, we can then put together the bounds by decomposing inputs into _ms (at a multiplicative cost depending only on k)

    ( _j⃗, {_i} -_j⃗, {_i})[]1   ≤∑_Π,Π'c_Πc_Π'( _j⃗, {_i} -_j⃗, {_i})['_Π/'_Π_2'_Π'/'_Π'_2]1By (<ref>)
       ≤∑_Π,Π'c_Πc_Π'·sup_Π∈ B_2k( _j⃗, {_i} -_j⃗, {_i})['_Π] 1/'_Π1By (<ref>)
       ≤∑_Π,Π'c_Πc_Π'·sup_Π∈ B_2ksup_m∈ M'_Π( _j⃗, {_i} -_j⃗, {_i})['_m] 1By (<ref>)
       N→∞=0 Since ∑_Π,Π'c_Πc_Π' is independent of N and by (<ref>).

Accounting for ancillas (whose dimension is independent of N) incurring a N-independent multiplicative blowup (<ref>) and inputs with positive and negative parts, we deduce that the diamond norm is also zero in the large N limit.



    Fix an integer ℓ and consider a set of phased permutations _1, ⋯_ℓi.i.d.∼ such that all but at most one of them are independent uniformly random (with at most one identity). 
    Then, in the large-N limit, for each j⃗∈ [ℓ]^2k, 

(1) If _i are paired up:  

    lim_N→∞_2k,^†∘^†_j⃗, {_i}[] - ∞ =0.


(2) Else:

    lim_N→∞_2k,^†∘^†_j⃗, {_i}[]∞=0.


 
We begin by evaluating

    ^†_j⃗, {_i}[] = _i_1⊗⋯⊗_i_k

where the words are each the product of the left and right _i's.  Following the arguments from the proof of <ref>, we optimize over '_Π for Π∈ B_2k due to the symmetrization _2k,^†, and it suffices to control inputs as the “factorized” operators _m:

    [_i_1⊗⋯⊗_i_k_m]   =⟨m_k+1|_i_1|m_1⟩⊗⋯⊗⟨m_2k|_i_k|m_k⟩
       = (k/N)   if any _i_j are nontrivial.

Thus, unless all _i are paired up with their conjugates,

    _2k,^†∘^†_j⃗, {_i}[]∞    = sup__1=1[ _2k,^†[_i_1⊗⋯⊗_i_k]]
       ≤ f(k) sup_m [ _i_1⊗⋯⊗_i_k_m]By (<ref>),(<ref>), and (<ref>).
       N→∞= 0,


as advertised.




    lim_N→∞_2k,^†∘^†_j⃗, {_i}[] - ·[_2k,^†∘^†_j⃗, {_i}[]]∞ = 0.



Suppose ∑_i w_i^2 =1, then the CP map associated with 2k-fold tensor product of ∑_i w_i _i is trace-preserving in the large-N limit
    
    lim_N→∞_2k,^†∘^†_2k,∑_i w_i _i[] - ∞ =0.


That is, _2k,∑_i w_i _i∘_2k, is a rescaled trace-preserving map. They are also completely positive as the _i need to pair up with each other.


    Expand 

    ^†_2k,∑_i w_i _i[]    = (∑_i w_i _i)^†(∑_i w_i _i) ⊗(∑_i w_i _i)^†(∑_i w_i _i)⋯
        = ^⊗ 2k + (cross terms)*(^† =)
       N →∞=^⊗ 2k*(<ref>),

where the cross terms result from multiplying out the bilinear tensor products. For example, for k=2, 

    (∑_i w_i _i)^†(∑_i w_i _i) ⊗ (∑_i w_i _i)^†(∑_i w_i _i)    = Ł( +  ∑_i j w_iw_j _i^†_j )⊗Ł( +  ∑_i j w_iw_j _i^†_j )
       = ⊗ + (cross terms).

Note that the number of cross-terms is independent of N.


    The above holds with any linear combination ∑_i w_i _i + ∑_i w'_i _i provided that ∑_i w_i^2 +∑_i w'_i^2 =1.


    Recall the central limit theorem (for any fixed dimension N)
    
    lim_m→∞∑_i=1^m 1/√(m)_idist.∼.

The error in the central limit theorem is bounded in the operator norm by 

    1/m f_1(w_i,k) +1/m^2 f_2(w_i,k) + ⋯,

where the leading contributions are cases when each _i shows up either two or zero times (reproducing the Wick contractions up to (1/m) corrections), and the subleading contributions are cases when there are terms _i that show up four times.
In particular, the norm bounds of the error terms are functions independent of N (depending on the pattern of the occurrences among the k indices and the w_i coefficients), so the limits m→∞ and N→∞ commute. 



 §.§ Large N structure


In order to use the Markov inequality, we need to confirm that the distinguishing probability is indeed a rational polynomial of N. Nicely, expressions involving random permutations, like random unitary, have a pronounced large-N expansion.


Consider _j⃗, {_i} as in <ref>, and suppose the length of the words is bounded by ℓ. Then, for each pair of partitions Π_1,Π_2 ⊢ 2k,

    Ł[ _Π_2_j⃗, {_i}[_Π_1]]

is a rational function in N where the poles can be located up to 2kℓ-1, each with multiplicity at most 2kℓ.


The strategy is to expand the expression by canonical pieces of tensors (<ref>) and argue that any contraction must yield a polynomial of N. This formal dependence on N is the only structural property we need; no further combinatorial calculations are required.



 The vectorized operator is factorized into individual tensors

    |_Π) = ⊗_i |T_b)   where   |T_b) = ∑_i=1^N |i⟩^⊗ t_b

and ∑_b t_b = 2k.



    For any tensor contraction made of components T_i, it evaluates exactly to 
    
    N^c  where   c = #(connected components after full contraction).


In particular, this implies (<ref>) as a special case.

There exists coefficients α(Π) independent of N such that
    
    |_z^⊗ k⊗_z^†⊗ k) =∑_Π⊢ 4kα(Π)|_Π).



    
    |_z^⊗ k⊗_z^†⊗ k)   =Ł[(∑_i=1^N z_i|i⟩|i⟩)^⊗ k⊗ (∑_i=1^N z^*_i|i⟩|i⟩)^⊗ k]
       = ∑_i=1^N z_i^kz_i^*k (|i⟩|i⟩⊗|i⟩|i⟩)^⊗ k + ∑_N≥ i_2>i_1≥ 1 (·) + ⋯ +∑_N≥ i_2k>⋯ > i_1≥ 1(·)
       = ∑_Π⊢ 4kα'(Π)|'_Π)
       =∑_Π⊢ 4kα(Π)|_Π)*(Möbius inversion (<ref>)).

    The second line sums over possible patterns of distinct z_is, and uses that each z_i must pair with its complex conjugate since 
    
    [ z^b_i] = 
                1    if integer    b=0
    
                0    else.

    Thus, the nonvanishing contribution has merely unity coefficient z_i^2=1. Note that the Hilbert space dimension is N^4k instead of N^2k as the object we consider is a (vectorized) superoperator.



Decompose the phased permutations by the diagonal phases and the permutation = _z. Then, the superoperator _j⃗, {_i} can be decomposed into sum and products of 

    ^a⊗^a,   _z^a⊗_z^*a  for     1≤ a ≤ 2kℓ

which can be written as diagrams _Π and expanded as tensor components (<ref>). After contraction, the poles may accumulate through the occurrences of ^a⊗^a for different possible independent permutations _1,_2.... These expectations produce poles via (<ref>) such that after taking account of all of them, the poles can be located up to 2kℓ-1, each with multiplicity at most 2kℓ. [This is likely a loose bound but is qualitatively sufficient.]




 §.§ Basis for the partition algebra



The crux of our large-N interpolation argument is to extend the distinguishing probability for N to other values of N' N. In particular, we need to “smoothly” extend the test operators , to different other dimensions. Fortunately, we do know that the partition algebra _k(N) stabilizes for large enough N≥ 2k and the individual factors {_λ⃗}_λ⃗ depend only on k and are independent of N if N≥ 2k (<ref>). Naturally, it is tempting to keep the test operator the same in this invariant decomposition into factors.

However, our polynomial interpolation argument requires that the block-diagonalizing unitary transformation “depends nicely” on N in the following sense. 

[Writing irreps in the computation basis] 

For each k, assume N≥ 2k. Does there exist a choice of orthonormal basis |v^λ⃗_i⟩ for each factor _λ⃗ of the partition algebra such that the following holds: the matrix elements _ij^λ⃗ = |v^λ⃗_i⟩⟨v_j^λ⃗|⊗__λ⃗ satisfy that

    [_ij^λ⃗_Π]   is a degree (k) rational polynomial of N for each  λ⃗, i, j, Π?



We do not need any knowledge of the rational polynomial except for its degree, and the polynomial can very well depend on λ⃗, i, j, Π. To answer the above question, we need to dive into the partition algebra and construct an orthogonal basis. Although our ensemble actually uses a stronger symmetry  (random phased permutations) instead of (N), it is sufficient to consider the weaker symmetry.



  §.§.§ An abstract construction of irreps

For each irrep labeled by λ⃗∈Λ_k,N, <cit.> constructed the corresponding irreducible module by taking an abstract quotient

    _λ⃗   := _k(N) e⃗_λ⃗/_m-1(N)   as a -vector space for m:=λ⃗^*
         where  v⃗_1( v⃗_2+ _m-1) ≡v⃗_1 v⃗_2 + _m-1  and
             e⃗_λ⃗: = p⃗_λ⃗^*e⃗_m  for  e⃗_m:= 1/N^k-m^m⊗ (isolated nodes)

such that e⃗_m^2=e⃗_m. The diagrammatic form of e⃗_m is depicted in <ref>.


    The quotient _λ⃗ is isomorphic to the irreducible module labeled by λ⃗∈Λ_k,N.


Since we are interested in finding an orthonormal basis, we first need an inner product on this irreducible module _λ⃗ (which was not discussed in <cit.>). There is a very natural approach: the abstract quotient by the two-sided ideal _m-1 can be realized as the projector __m-1 onto a subalgebra __m-1[_k(N)] ⊂_k(N). (See <ref>.) Therefore, the natural choice for the inner product is then to simply induce from the Hilbert-Schmidt inner product of the partition algebra by

    ⟨ v^λ⃗_1, v^λ⃗_2 |:⟩= 1/[__λ][_[ v⃗^λ⃗_1]^†_[  v⃗^λ⃗_2]]  for each  v⃗^λ⃗_1,v⃗^λ⃗_2 ∈_k(N) e⃗_λ⃗.

We can verify that this inner product is consistent (dropping scripts λ⃗ and m-1 for the moment)

    ⟨ v_1+_1, v_2+_2 |_⟩λ⃗   = 1/[__λ][_[ v⃗_1+_1] _[  v⃗_2+_2]]
       =  1/[__λ][_[ v⃗_1]^†_[  v⃗_2]] 
       = ⟨ v_1, v_2|_⟩λ⃗  for each  v⃗_1,v⃗_2 ∈_k(N) e⃗_λ⃗  and  _1,_2 ∈

and compatible with the adjoint from the Hibert space on which _k(N) is represented

    ⟨ v_1,  v_2 |_⟩λ⃗   =  1/[__λ][_[ v⃗_1]^†_[ v⃗_2]]
       =  1/[__λ][_[ v⃗_1]^†_[ ]_[ v⃗_2]]
       =  1/[__λ][Ł(_[ ]^†_[ v⃗_1])^†_[ v⃗_2]]
       =  1/[__λ][Ł( _[ ^†v⃗_1])^†_[ v⃗_2]] = ⟨^† v_1,  v_2 |_⟩λ⃗.

The second, third, and fourth lines use that _[·] is a †-homomorphism. (Recall <ref> and <ref>.) 

In a nutshell, there is a very simple intuition for this abstract vector space: it is simply one column in the corresponding factor of the partition algebra

    _k(N) e⃗_λ⃗/_m-1(N) ∼-Span{|v^λ⃗_i⟩⟨0|}∈_λ⃗.





  §.§.§ Explicit basis


For our later usage, we will also need to extract the explicit structure of the basis from the abstract construction. We will be building on the basis provided by <cit.>. The construction requires some further concepts from the algebraic structure of the partition algebra (see <ref>).

    For any 0 ≤ m≤ k, the set of m-factors F_m are diagrams where the bottom leftmost m nodes propagate and the rightmost k-m nodes are isolated. 
    In particular, the set of noncrossing m-factors NF_m are those m-factors whose propagating edges do not cross when the diagram is drawn under the rule that propagating edges connect to the rightmost vertex of the block in the top row.

Note that by permuting the bottom row (i.e., concatenating a permutation below), any m-factor can be made noncrossing.


Let m = λ⃗^*. Then,

    _λ⃗ = Span{_ω_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*) }   (mod _m-1).


We now construct an explicit orthonormal basis for the vector space _λ⃗ for each irrep λ⃗∈Λ_k,N. This might be of independent interest in the representation theory of partition algebras.


For each λ⃗∈Λ_k,N, the set of vectors

    {v⃗^λ⃗_i} =  Ł{1/n(ω,t)_ωu⃗_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*) }   (mod  _m-1)

forms an orthornormal basis for the irreducible representation _λ⃗.

Note that as compared to <ref>, _t has been replaced by the u⃗_t introduced in <ref> and _ω was replaced by _ω. Roughly speaking,
for a noncrossing m-factor ω,  

    _ω := (sum over distinct indices for the upper nodes {1,⋯, k} and lower nodes {1,⋯, m}).

The precise definition can be found in the proof of <ref>. These operators are analogs of the '_ω but focus only on a subset of vertices. (That is, when running the inclusion-exclusion principle, we keep the lower right k-m nodes untouched.) This will be crucial for ensuring that the basis vectors are orthogonal and the subspace projector remains a rational function of 1/N.[This point is surprisingly delicate because the subspace dimension is large (superexponential in k), and tiny overlaps can accumulate and wiggle the span.] Later, we will choose the normalization constant n(ω) to ensure the vectors are exactly unit length (<ref>). 
The proof that these operators form an orthonormal basis will take place in two steps.

    
  * The new vectors span the same space (<ref> and <ref>).
    
  * The new vectors are orthogonal (<ref>).






For each integer 1≤ m≤ k,
    
    Span{_ω| ω∈ F_m }≡ Span{_ω| ω∈ F_m}   (mod _m-1 ).



To study m-factors, it suffices to consider diagrams where the bottom right k-m nodes are isolated. To that end, let
T_1^k-m =(∑_i=1^N⟨i|)^⊗ k-m and introduce the shorthand

    _Γ⊗ T_1^k-m =:_Γ  where  Γ⊢[k+m]={1,⋯,k,k+1,⋯ k+m}.

The induced partial order ≥ on Γ⊢ [k+m] (recall <ref>) allows us to run a tailored Möbius inversion argument so that (as in (<ref>),(<ref>))

    _Γ   =  ∑_Γ' ≥Γ,Γ'⊢[k+m]'_Γ' =: ∑_Γ'⊢[k+m] K_ΓΓ''_Γ'
    '_Γ   = ∑_Γ'⊢[k+m] K^-1_ΓΓ'_Γ'

where '_Γ' are orthogonal (recall (<ref>): distinct blocks in Γ have distinct indices) and are related to the original diagrams _Γ by upper triangular matrices K_ΓΓ' and K^-1_ΓΓ' (total order extended from the partial order ≥ by <ref>). Note that the bottom right k-m nodes are untouched throughout the proof. Consider (<ref>) for each m-factor ω∈ F_m, 

    '_ω   = ∑_Γ'⊢[k+m] K^-1_ωΓ'_Γ'
       =∑_ω'∈ F_m K_ωω'^-1_ω' + ∑_Γ'∈_m-1 K_ωΓ'^-1_Γ'Any partition Γ is either in F_m or _m-1
       ≡∑_ω'∈ F_m K_ωω'^-1_ω'   (mod _m-1),
  
where we again use Γ' ∈_m-1 as a shorthand for Γ'⊗ T_1^k-m∈_m-1.
The second line is the observation that any partition Γ⊢[k+m] corresponds to a diagram with at most m propagating blocks (since there are only m nodes at the bottom), and thus any diagram with (1) exactly m-propagating blocks (i.e., an m-factor) is in F_m and those with (2) at most m-1 propagating block is by definition in _m-1. Now, since the restriction of an upper triangular matrix remains upper triangular (or, partial order remains consistent on subsets: <ref>), we have that

    K^-1_ΓΓ'     for  Γ,Γ' ⊢ [k+m]  is upper triangular implies the same for
    
        K^-1_ωω'     for  ω,ω' ∈ F_m.


Further, since the diagonals are nonzero (just ones), there exists a matrix K^(F_m) defined only on F_m→ F_m that inverts K^-1_ωω' on F_m→ F_m:

    ∑_ω'∈ F_m K^(F_m)_ωω' K^-1_ω'ω” = δ_ωω”  for each  ω, ω”∈ F_m.

Thus, 

    ∑_ω'∈ F_m K^(F_m)_ωω''_ω'≡_ω   (mod _m-1),

stating that the two spans are equal up to elements in _m-1.



    For each λ⃗∈Λ_k,N, let m=λ⃗^*, then
    
    Span{_ω_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   ≡Span{_ωu⃗_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   (mod _m-1)



Starting with <ref>, 

    Span{_ω| ω∈ F_m}   ≡  Span{_ω| ω∈ F_m}   (mod _m-1),

we can pull out permutations to make the partitions noncrossing, giving

    Span{_ω | ω∈ NF_m, ∈ S_m }   ≡  Span{_ω | ω∈ NF_m, ∈ S_m }   (mod _m-1),

noting that we drop the distinctness constraint on the permutation as the distinctness of _ω suffices to ensure _ω = _ω' for some ω∈ F_m. Then, we can right multiply the set by

    Span{_ωp⃗_λ⃗^*| ω∈ NF_m, ∈ S_m }   ≡Span{_ωp⃗_λ⃗^*| ω∈ NF_m , ∈ S_m }   (mod _m-1),

noting that we relax the quotient (mod _m-1p⃗_λ^*) to (mod _m-1) by the ideal property _m-1p⃗_λ^*⊂_m-1.

By <ref>, however, {p⃗_λ⃗^*}_∈ S_m={_tp⃗_λ⃗^*}_t ∈ SYT(λ⃗^*), which allows us to restrict the set of permutations by

    Span{_ω_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   ≡Span{_ω_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   (mod _m-1).

Finally, we can use <ref> and, in particular, that Span{u⃗_t p⃗_λ⃗^*}= Span{_t p⃗_λ⃗^*}, to reach

    Span{_ω_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   ≡Span{_ωu⃗_t p⃗_λ⃗^*| ω∈ NF_m , t ∈ SYT(λ⃗^*)}   (mod _m-1),

as advertised.




  §.§.§ Orthogonality and matrix elements


The very nice properties of the basis vectors we chose in <ref> are that they are orthogonal and immediately give the matrix elements of the factors of the partition algebra.

    For each λ⃗∈Λ_k,N, 
    set the normalization such that
    
    n(ω,t) := √(c(ω))  for each  ω∈ NF_m  and   t ∈ SYT(λ⃗^*).

    where 
   
    c(ω) := N^k-m(N-m)!/(N-m-d(ω^†,ω))! = N^k-m· (N-m) · (N-m-1)⋯≤ N^k-m+d(ω^†,ω).
 
   Then, |v_j^λ⃗⟩ forms an orthonormal basis for the irrep labeled by λ⃗∈Λ_k,N, and 
    
    _[v⃗_i^†v⃗_j] ≃|v^λ_i⟩⟨v^λ_j|⊗__λ⃗  for each   i,j

    gives the matrix elements for the irrep labeled by λ⃗∈Λ_k,N.

The proof of orthogonality relies on the following multiplicative properties of _ω.  This is precisely why we define our basis using _ω instead of _ω; despite having a simpler definition, the latter has a more involved algebraic structure.
For all ω, ω' ∈ NF_m, 

    _ω'^†_ω≡ c(ω) δ_ω'ω·e⃗_m
           (mod _m-1).
    

The above will be very helpful in the calculation as it imposes ω = ω'.



 

Step 1: Distinctness implies the set of upper blocks matches. Recall that the Ô_ω were constructed specifically so that the outgoing wires of _ω were distinct. As illustrated in <ref>, this implies that the upper block of ω' must be exactly the same partition as that of ω. Otherwise, two different blocks will be contracted to give zero. 

Step 2: Fixing the propagating blocks. To establish that the product is actually proportional to δ_ω'ω, we need to use the properties of _m-1 and the fact that ω∈ NF_m is noncrossing. Since the quotient _m-1 kills any diagram with fewer than m propagating blocks, the product _ω'^†_ω vanishes unless the number of blocks remains m, which requires that the set of upper propagating blocks of ω' exactly matches the set of upper propagating blocks of ω. Furthermore, since ω' is a noncrossing m-factor, this also uniquely fixes how the propagating blocks of ω' are wired to the lower leftmost  m nodes (according to the rightmost element of each block). 

Step 3: Calculating the constant. Having established orthogonality, we can obtain the final form

    _ω^†_ω   ∝∑^N_distinct  i_1, ⋯, i_m =1 |i_1⟩⟨i_1|⊗|i_2⟩⟨i_2|⋯|i_m⟩⟨i_m|⊗(2k-2m isolated nodes)
       ∝_m ⊗(2k-2m isolated nodes)  (mod _m-1)
       ∝e⃗_m   (mod _m-1)

The second line “completes” the identity by adding suitable elements in _m-1. Lastly, the constant is determined by contracting the upper nonpropagating blocks, which gives the falling factorial in c(ω), and the normalization factor (N^k-m) of e⃗_m. 



We begin by verifying the algebra relation for matrix elements:

    _ij_kℓ = δ_jk_iℓ,  ^†_ij = _ji.

Indeed, we have that

    _[v⃗_iv⃗^†_j] _[v⃗_kv⃗^†_ℓ]    = _[v⃗_iv⃗^†_j v⃗_kv⃗^†_ℓ]*(Since _ is a †-homomorphism)
        = 1/n(ω_1,t_1)n(ω_2,t_2)n(ω_3,t_3)n(ω_4,t_4)_[_ω_1_t_1p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_2_ω_2^†_ω_3_t_3p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_4_ω_4^†]*(i,j,k,ℓ→ω_1,t_1,…,ω_4, t_4)
        = c(ω_2)/n(ω_1,t_1)n(ω_2,t_2)n(ω_3,t_3)n(ω_4,t_4)_[_ω_1e⃗_m_t_1p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_2_t_3p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_4_ω_4^†]*(By <ref>)
        = c(ω_2)/n(ω_1,t_1)n(ω_2,t_2)n(ω_3,t_3)n(ω_4,t_4)_[_ω_1e⃗_m_t_1p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_4_ω_4^†]*(By <ref>)
        = c(ω_2)/n(ω_1,t_1)n(ω_2,t_2)n(ω_3,t_3)n(ω_4,t_4)_[_ω_1_t_1p⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_4_ω_4^†]*(By definition of e⃗_m)
        = δ_jk_[v⃗_iv⃗^†_ℓ],

and that

    Ł( _[v⃗_iv⃗^†_j] )^† = _[v⃗_jv⃗^†_i] *(Since _ is an †-homomorphism),

as required.





  §.§.§ Projector onto irreducible representations as a sum over diagrams
  
We have constructed an explicit orthonormal basis but the abstract quotient projector __m that is required to ensure orthogonality remains somewhat mysterious.

    __m-1[·] = ∑_λ⃗^⃗*⃗≥ m Π⃗_λ⃗·Π⃗_λ⃗.
  
This section further gives a low-degree expansion of Π⃗_λ⃗ in terms of the diagram operator _Π.


For each λ⃗∈Λ_k,N, 

    Π⃗_λ⃗ = ∑_iŁ( v⃗^⃗λ⃗_iv⃗^λ⃗†_i - ∑_μ⃗^*≤λ⃗^*-1 Π⃗_μ⃗v⃗^⃗λ⃗_iv⃗^λ⃗†_i ).

Thus, solving the recursion yields

    Π⃗_λ⃗ = ∑_Π c(Π,λ⃗) _Π

where c(Π,λ⃗) is a rational function of N with poles at integers 0,…, k, each with multiplicity at most k.




    Π⃗_λ⃗    = ∑_i__m-1[ v⃗^⃗λ⃗_iv⃗^λ⃗†_i ]*(Resolution of identity)
        = ∑_iŁ( v⃗^⃗λ⃗_iv⃗^λ⃗†_i - ∑_μ⃗^*≤λ⃗^*-1 Π⃗_μ⃗v⃗^⃗λ⃗_iv⃗^λ⃗†_iΠ⃗_μ⃗)*(Rewriting (<ref>))
        = ∑_iŁ( v⃗^⃗λ⃗_iv⃗^λ⃗†_i - ∑_μ⃗^*≤λ⃗^*-1 Π⃗_μ⃗v⃗^⃗λ⃗_iv⃗^λ⃗†_i )*(Since v⃗^⃗λ⃗_iv⃗^λ⃗†_i∈_k(N)).
 
The third line drops one of the projectors since Π⃗_μ⃗ are projectors for a factor. Solving the recursion implies the projector can be expressed as a formal noncommutative polynomial of the basis representatives

    Π⃗_λ⃗ = Ł({∑_i v⃗^λ⃗_iv⃗^λ⃗†_i}_λ⃗∈Λ_k,N)   of degree  λ⃗.

Further rewriting the basis representatives 

    v⃗^⃗λ⃗_iv⃗^λ⃗†_i    = 1/n(ω)^2_ω_tp⃗_λ⃗^⃗*⃗p⃗_λ⃗^⃗*⃗^†^†_t_ω^†
       = ∑_Π c(Π,λ⃗) _Π

where each c(Π,λ⃗) is a rational function of N with pole at integers 0,…, k with multiplicity at most 1 by <ref>. Thus,

    Π⃗_λ⃗ = ∑_Π c(Π,λ⃗) _Π

with poles at integers 0,⋯, k each with multiplicity at most k. We will not ever need to worry about the numerator degree, as it will already be controlled by the denominator degree for the ultimate quantity of interest (bounded by ( N^0)). 






 §.§ Extending test operators


However, we are still faced with the challenge that the distinguishing probability also depends on the quantum algorithm,  which amounts to all possible input states and observables in the parallel query model. To make the distinguishing probability a polynomial, we must specify how we extend the quantum algorithm to other dimensions N'. In most circumstances, that would be very unnatural but here, the fact that the partition algebra is independent of N for N ≥ 2k allows us to define a family of “equivalent” quantum algorithms across larger and smaller dimensions N'  N. Doing so amounts to choosing the appropriate input state and observable. 

First, we need to reduce the size of the ancilla to control the diamond distances. 

    For any two channels _1, _2, 
    
    _2k,∘( _1 -_2) ∘_2k,♢  = sup_,Ł[ (_1-_2 )Ł[]]

    where the normalized state  and operator  are supported on bipartite Hilbert space with dimension N^k×max_λ⃗∈Λ_k,N d_λ, where d_λ are the dimensions of the factors in the partition algebra.

In particular, assuming the local dimension is large, specifically 2k ≤ N, the irrep dimension d_λ⃗ will only depend on k and is independent of N. 

For any input  that may be entangled with an N^k-dimensional ancilla, the permutation average enforces the structure

    _2k,[]    = ⊕_λ⃗'_λ⃗⊗τ⃗_λ⃗.

where '_λ⃗ acts on the factors of the partition algebra and the ancilla. Further, since the trace distance is convex, the maximum will be attained at a pure input on one of the factors _λ⃗. For such a state, there is a further unitary _anc acting on the ancilla that “compresses” the entanglement (i.e., by Schur decomposition)

    '_λ⃗ = _ancŁ(|0⟩⟨0|⊗_λ⃗)_anc^†

where _λ⃗ is a pure state entangled between 
a d_λ⃗-dimensional subspace _anc and the λ⃗ factor in the partition algebra. Further, the distinguishing operator  achieving maximal distinguishing probability will also be supported on the subspace _anc⊗ (^N)^⊗ k. Thus, the maximal distinguishing probability can be attained using an ancilla dimension as little as the largest dimension of the factors of the partition algebra max_λ⃗∈Λ_k,N d_λ. 

Second, since the input is “fixed,” and is independent of the dimension, we can define a family of “equivalent” states across dimensions.


Consider _j⃗, {_i} as in <ref>. Then, assuming N ≥ 2k, for any observable and state _N,_N∈((ℂ^N)^⊗ k), there exist matrices _N',_N'∈((ℂ^N')^⊗ k) such that function 

    f Ł(1/N') := Ł[ _N'_j⃗, {_i}[_N']]   for each integer   N' ≥ 2k

is rational polynomial of N with poles at integers 0,…, 2kℓ-1 each with multiplicity at most 2kℓ+3k+2.


For ease of notation, we begin with the case without ancillas, and then argue that the same argument works in the presence of ancillas. Indeed, what is changing is the basis for the partition algebra and the ancilla is fixed. Given any operator and state _N,_N∈_k(N) ⊂((ℂ^N)^⊗ k), they can be written as

    _N   =⊕_λ⃗∈Λ_k,N∑_i,jρ_ij^λ⃗|v_i⟩⟨v_j|⊗__λ⃗/[__λ⃗]
       =∑_λ⃗∈Λ_k,N1/[__λ⃗]∑_i,j_λ⃗[v⃗_iv⃗^†_j] ρ_ij^λ⃗
    _N   =⊕_λ⃗∈Λ_k,N∑_i,j A_ij^λ⃗|v_i⟩⟨v_j|⊗__λ⃗
       =∑_λ⃗∈Λ_k,N∑_i,j_λ⃗[v⃗_iv⃗^†_j] A_ij^λ⃗

such that

    [_N] = ∑_λ∈Λ_k,N∑_i_ii^λ⃗ = 1   and  _N_∞ = max_λ^λ⃗_∞

and for each _Π∈_k(N), 

    [_Π_N]   = ∑_λ⃗∈Λ_k,N∑_i,j[_Π_λ⃗[v⃗_iv⃗^†_j]]/[__λ⃗]ρ_ji^λ⃗
    [_Π_N]   = ∑_λ⃗∈Λ_k,N∑_i,j[_Π_λ⃗[v⃗_iv⃗^†_j]]A_ji^λ⃗.

The above can be extended to other dimensions N' ≥ 2k as _N',_N'∈((ℂ^N')^⊗ k), which is

    _N'   =∑_λ⃗' ∈Λ_k,N'1/[__λ⃗']∑_i,j_λ⃗'[v⃗_iv⃗^†_j] ρ_ij^λ⃗
    _N'   =∑_λ⃗' ∈Λ_k,N'∑_i,j_λ⃗'[v⃗_iv⃗^†_j] A_ij^λ⃗'.

Note that

    [_N'] = ∑_λ' ∈Λ_k,N'∑_i_ii^λ⃗' = 1   and  _N'_∞ = max_λ'∈Λ_k,N'^λ⃗'_∞.

Also, we relate the extension N'≥ 2k from N by setting

    ρ_ij^λ⃗'⃗ = ρ_ij^λ⃗  and   A_ij^λ⃗'⃗ = A_ij^λ⃗  for each   i,j,  if  λ⃗^'*=λ⃗^*

since the irreducible representations λ⃗ of _k(N) can be identified with λ⃗' of _k(N'), and similarly for A_ij^λ⃗. We evaluate the expression by inserting resolutions of identity

    Ł[ _N'_j⃗, {_i}[_N']]    = (_N'|_j⃗, {_i}|_N')
       = ∑_Π_1,Π_2⊢ 2k (_N'|'_Π_2)('_Π_2|_j⃗, {_i}|'_Π_1)('_Π_1|_N')/'_Π_2^2_2'_Π_1^2_2
        = ∑_Π_1,Π_2⊢ 2k (_N'|'_Π_2)('_Π_2|_j⃗, {_i}|'_Π_1)('_Π_1|_N')/'_Π_2^2_2'_Π_1^2_2.

Let's count the poles for each:

(i) By (<ref>),

    1/'_Π_2^2_2, 1/'_Π_2^2_2 = 1/N(N-1)⋯

which individually has poles at integers 0,⋯, k each with multiplicity at most 1.

(ii) Rewrite in terms of the _Π's by (<ref>)

    ('_Π_2||'_Π_1)   = ∑_Π'_1,Π'_2⊢ 2k   K^-1*_Π_2Π'_2 K^-1_Π_1Π'_1(_Π'_2||_Π'_1),

which, by <ref>, which has poles at integers 0,…, 2kℓ-1 each with multiplicity at most 2kℓ.

(iii)

    ('_Π_1|_N')    = ∑_Π'_1⊢ 2k  K^-1*_Π_1Π'_1 (_Π'_1|_N') By (<ref>)
        = ∑_Π'_1⊢ 2k ∑_i,j,λ⃗  K^-1*_Π_1Π'_1[_Π'_1_λ⃗[v⃗_iv⃗^†_j]]/[__λ⃗]ρ_ji^λ⃗.


The poles came from _λ⃗ = ∑_λ⃗Π_λ⃗ and v⃗_iv⃗_j^† (<ref>) and [__λ⃗] (<ref>), which has poles at integers 0,…, 2k-1 each with multiplicity at most 2k.


(iv)

    ('_Π_1|_N')    = ∑_Π'_1⊢ 2k  K^-1*_Π_1Π'_1 (_Π'_1|_N') By (<ref>)
       = ∑_Π'_1⊢ 2k ∑_i,j,λ⃗  K^-1*_Π_1Π'_1[_Π'_1_λ⃗[v⃗_iv⃗^†_j]] A_ji^λ⃗

which like the case of (iii), has poles at integers 0,…, 2kℓ-1 each with multiplicity at most 2kℓ+k.

Altogether, 

    f Ł(1/N') := Ł[ _N'_j⃗, {_i}[_N']]   for each integer   N' ≥ 2k,

which has poles at integers 0,…, 2kℓ-1 each with multiplicity at most 2kℓ+3k+2.

To extend to the case with ancillas, we run the above argument for each irrep λ⃗∈Λ_k,N

    _λ⃗   = ∑_i,jρ_ij^λ⃗|v_i⟩⟨v_j|⊗__λ⃗/[__λ⃗]⊗_ij
       =⊕_λ⃗∈Λ_k,N∑_i,j A_ij^λ⃗|v_i⟩⟨v_j|⊗__λ⃗⊗'_ij

were _ij, '_ij acts on space of dimension d_λ⃗, which encompasses all possible operator  acting on (^N)^⊗ k⊗^d_λ⃗ and inheriting the operator norm bounds.


In the setting of <ref>, the Haar random channel evaluates on the same set of extensions _N', _N'
    
    f Ł(1/N') := Ł[ _N'_ 2k, [_N']]   for each integer   N' ≥ 2k

is rational polynomial of N at integers -(k-1), ⋯, 0,1,2k -1, each with multiplicity bounded by 4k+2.


The change in the argument of <ref> is that

    ('_Π_2||'_Π_1)   = ∑_Π'_1,Π'_2⊢ 2k   K^-1*_Π_2Π'_2 K^-1_Π_1Π'_1(_Π'_2||_Π'_1)

And we directly invoke the Weingarten function for the unitary group <cit.>, which has poles at -(k-1),⋯,0,⋯ (k-1) with multiplicity at most k.



§ PROOF OF MAIN RESULT

This section contains the formal proof of our main result (<ref>), which we restate as follows.

*

Since the proof requires several lemmas, we first discuss them locally and combine them in the end.


 §.§ Expanding one exponential into words

We first expand the single exponential and collect the distinct words

    ^θ_m   = expŁ(θ/√(2m)∑_a=1^m (_a+^†_a) )
       =  + θ/√(2m)∑_a=1^m Ł(_a+^†_a) - θ^2/21/2mŁ(∑_a=1^m _a+^†_a)^2 ⋯
        = v(θ)  + ∑_i w_i(m,θ) _i   where  _i ∈({_a}_a=1^m).




    ∑_i w_i^2    = 1
    max_iw_i   ≤1/√(m).



Fix m and taking the large-N limit: 

    1= lim_N→∞[^-θ_m^θ_m]= ∑_i w_i^2large-N limit.


The second inequality uses the fact that the normalization trace of a nontrivial word vanishes in the large-N limit. The second claim follows from the symmetry of the paths: each path with nonzero length must map to m other paths by cycling through the labels (a =1,⋯, m). Thus, there cannot be a path contributing more than 1/√(m) due to the sum constraints ∑_i w_i^2 =1.


The coefficient v(θ) for the identity operator is a sum over weighted trivial words (i.e., loops on the Cayley graph of the free group of m elements). For example, 

    1/2mŁ(∑_a=1^m _a+^†_a)^2    = 1· + (nontrival words)
    1/4m^2Ł(∑_a=1^m _a+^†_a)^2    = (1+ m-1/2m)· + (nontrival words).

The sum over all paths at order p is exactly the moments of Kesten-McKay distribution <cit.>. Thus, the exponentially weighted sum is then the characteristic function

    v_m(θ) = ∫_-∞^∞^θ x p_m(x)  x.



    The Kesten-McKay distribution is defined by
    
    p_m(x) := √(4m-1/m-x^2)/2π(1-x^2/m)     if  x≤ 2√(1-1/m)
    
            0    else.


In the limit m→∞, the Kesten-McKay distribution converges to Wigner's semi-circle

    p_m(x) := √(4-x^2)/2π     if  x≤ 2
    
            0    else,

and the above gives an exact formula for the correction due to m. Thus, we may eliminate the trivial word  by choosing the zeros of this function:

    θ_m   such that   v_m(θ_m) =0,

i.e., making the exponential traceless in the large-N limit. In particular, the angle is always bounded by an absolute constant θ_m = (1) for any m.

The nice consequence of choosing v_m(θ_m)=0 is that there is no cancellation due to taking the product of exponentials. For example, in the product of two independent copies

    ^θ_m^θ'_m   = ∑_i w_i(m,θ) _i  ·∑_i w_i(m,θ) '_i
        =∑_i,j w_i(m,θ) w_j(m,θ) _i'_j,

each of the product words is different so that

    _i'_j = _i''_j'  if and only if   (i,j) = (i',j').

Thus, taking products yields an exponentially growing number of words that we can easily keep track of. Note that taking powers of the same (^θ_m _m)^2 could also work in principle with a more careful combinatorial analysis for the cancellation of words. 



 §.§ Proof of <ref>

We begin with a proof sketch. For any integers m,ℓ, the product of ℓ independent exponentials of 2m-sparse random matrices can be expanded into distinct words

    ∏_j=1^ℓ^θ^(j)_m   = ∑_i⃗ w_i⃗(θ)_i⃗*(Distinct words: _i⃗_j⃗ for each i⃗j⃗.)

with fairly spread-out weights w_i⃗ (calculated from the individual properties (<ref>))

    ∑_i⃗w_i⃗^2    = (∑_iw_i^2)^ℓ = 1
    max_i⃗w_i⃗   = Ł(max_iw_i)^ℓ≤1/√(m)^ℓ.


Intuitively, we expect the resulting product to be a very dense matrix (sparsity Ω(m)^ℓ) as we expect the distinct words of permutations to map the same bit string to distinct bit strings. 



  §.§.§ The large-N limit

Indeed, if the dimension N is infinite (fixing the length of the words and the number of queries k), then there will almost surely be no collision between the distinct words, and we expect them can be replaced with independent permutations. This can be captured by the following equality of limits, with the precise order of limit and choice of norm stated in <ref>. 

    _LŁ(∑_i⃗ w'_i⃗(θ)'_i⃗) _R   N→∞=_LŁ(∑_i⃗ w'_i⃗(θ)_i⃗)_R*(distinct words are free in the large-N limit:<ref>)
       m^ℓ→∞=. *(Matrix central limit theorem in k-fold diamond norm)

Observe that the summands match the second (mixed) moments of a Gaussian matrix

    [ ^(†)_i ⊗^(†)_i] = [ ^(†)_i ⊗^(†)_i].

Thus, in the limit of many summands (with some requirement that the weights all be reasonably small), the sum converges to a Gaussian; see <ref> for the nonasymptotic bounds.

The Gaussian is a simple random matrix that is left and right unitarily invariant. The Gaussian is nonetheless not the same as a Haar random unitary. In fact, it is not even a unitary matrix, as its singular values are distributed according to the Marchenko-Pastur distribution, which differs from the unitary case. Nevertheless, the Gaussian is effectively Haar in the parallel access model. 

    N→∞=_Haarin the diamond distance, <ref>.

Intuitively, for arbitrary fixed input state uncorrelated with , it is nearly isometric with high probability, as can be seen from the expected value ^† =. Regardless of the interpretation, the presence of Gaussians  is merely a proof artifact, and all that matters in this context is merely the k-fold CP map _2k,.

The assertions above together imply that  
_L Ł(∏_j=1^ℓ^θ^(j)_m) _R ≈_Haar as k-fold channels in the limits of N→∞, m^ℓ→∞.



  §.§.§ Interpolating to finite N

To complete the proof, the main technical argument is to handle finite-N corrections. We isolate the finite-N bounds as the following lemma. The crux of the argument is an interpolation argument for the variable x = 1/N from the large-N limits. We begin with a sketch of the argument by invoking the partial results we already proved. 
Define the two channels of interest:

    _1: = _2k,  and  _2: = _2k,_Haar.

By <ref>, the diamond distance can be controlled at ancilla size max_λd_λ
    
    _2k,∘( _1 -_2) ∘_2k,♢   = sup_,Ł[_1] - Ł[_2].

    where the supremum is over symmetrized operators and states that may involve ancillas. (Even though we have in fact a stronger symmetry _2k,, it suffices to exploit the _2k, symmetry.) We will show that the distinguishing probability is small for each input and output by constructing the function 
    
    f_,(1/N')    =  Ł[^(N')^(N')_1^(N')]-Ł[^(N')^(N')_2^(N')]
        = f_1(N') - f_2(N')

    as an extension from the original dimension N'=N by defining a family of operators and superoperators
    
    Ł(^(N'),_1^(N'),_2^(N'), ^(N'))   for each    2k ≤  N' ≤∞
    such that     Ł(^(N),_1^(N),_2^(N), ^(N))= Ł(, _1,_2, ).

    Of course, the operators ^(N),^(N) at other dimensions N' has to be “similar” to the original , at dimension N. In order to interpolate using Markov's inequality, we spell out the requirements for the extension:

    
  * Rational low-degree function (<ref>, <ref>): we extend to other dimensions by choosing the appropriate extensions of the inputs and outputs. Since the exponential is an infinite series, we have to truncate the Taylor expansion (<ref>) to ensure that the product ∏_j=1^ℓ^θ_m^(j)_m is approximated to error ϵ in the operator norm. See <ref> for the proofs of the following lemma.

For any ϵ,k, truncating each exponentials ^θ_m^(j)_m at degree d_1 = ( √(m)log(kℓ/ϵ)) suffices to ensure 

    f_,,1(1/N) - f^(trun)_,,1(1/N)≤ϵ.



Meanwhile, truncated function f^(trun)_,(1/N)
is a rational polynomial of N at integers 

    0,1,⋯, 2kℓ d_1 -1  each with multiplicity at most   2kℓ d_1+ 3k + 2

where ℓ· d_1 is the maximal length of words of permutations, as coming from the product of ℓ-many degree d_1 words.
The case for f_,,2 (<ref>) has fewer multiplicities in a smaller range of integers, and that of f_,,1 will dominate.
The choices for the degrees d_1 will depend on N,m,ℓ, k.
    
    
  * A priori bounds: This merely came from the structural fact that the expression is a difference between probabilities, bounded between one and zero:

    f_,(1/N')≤_1^(N')-^(N')_2_1-1_N'_1 _N'_∞≤ 2  for each integer   N'.

    
  * Large-N limits (<ref>, <ref>): The large-N limit coincide with the “free” model: sum over i.i.d. permutations. Also, the Haar random Channel can be replaced with Ginibre ensembles 

    f_1,,(1/N')     = Ł[_N'_1_N'] N'→∞=Ł[_N'^(free)_1_N'] = f^(free)_1,,(1/N')
    
        f_2,,(1/N')    =Ł[_N'_2_N'] N'→∞=Ł[_N'^(Ginibre)_2_N'] = f^(Ginibre)_2,,(1/N').

    
  * Comparing the “nicer” models (<ref>): We further take a Lindeberg principle to argue that these large-N limits are very close to each other. While the most general Lindeberg argument works at any finite dimension N, the large-N limits simplify the calculations.

    f_,(1/∞)   = lim_N'→∞ f_1,_N',_N' - f_2,_N',_N'
       = lim_N'→∞ f^(free)_1,_N',_N' - f^(Ginibre)_2,_N',_N'(<ref>)
       ≤1/8∑_i⃗Ł( (4kw_i⃗)^4 + (4kw_i⃗)^2k) + 1/8∑_i⃗Ł( (4kw'_i⃗)^4 + (4kw'_i⃗)^2k) Lindeberg argument for both:<ref>
       ≤(4k)^2/8 (∑_i⃗w_i⃗^2)·max_i⃗Ł( (4kw_i⃗)^2 + (4kw_i⃗)^2k-2) + (w_i⃗→ w'_i⃗)Holder's
       ≤(4k)^2/8 1 ·Ł( 16k^2/m^ℓ + (16k^2/m^ℓ)^k-1) + (m,ℓ→ m',ℓ')
    Bounds on the weights w_i⃗:(<ref>)
       ℓ'=2, m' →∞≤(4k)^2/8Ł( 16k^2/m^ℓ+ (16k^2/m^ℓ)^k-1) Second term drops due to m'→∞
       ≤minŁ( 128k^4/m^ℓ,2).

The last inequality recalls the a priori bound f_,(1/∞)≤ 2 to drop the higher order term since we must have 16k^2/m^ℓ≤ 1 for the bound to be better than the a priori bounds.





We put the above together. For any m,ℓ, N,  

    _2k,∘( _1 -_2) ∘_2k,♢   ≤sup_, f_,(1/N).

We further introduce a truncation error (for the exponential in f_1)

    f_,(1/N)≤ f_,(1/N)-f_,^(trun)(1/N) +  f^(trun)_,(1/N)-f_,^(trun)(1/∞)
    
        +  f^(trun)_,(1/∞)-f_,(1/∞) +  f_,(1/∞)

We instantiate the truncation error from _1

    f_,(1/N)-f_,^(trun)(1/N)   ≤ϵBy <ref>  for any N.


The truncated function f_1 now have a total number of poles d = 2kℓ d_1(2kℓ d_1+3k+2) and bound on the pole locations B ≤ 2kℓ d_1 -1 (which is strictly worse than the Haar random channel (<ref>)), so we can invoke Markov's inequality for N_0 ≥ d^2 +8bB-1:

    f^(trun)_,(1/N)-f_,^(trun)(1/∞)   ≤2d^2 (N_0 + 10dB)/Nsup_N≥ N_0f^(trun)_,(1/N)By <ref>
       ≤Ł((k^2 ℓ^2 d_1^2)^4/N),

using that f^(trun)_,(1/N_0)≤f_,(1/N_0)+ϵ≤ 2+ϵ≤ 3.
To consolidate the error,

    _2k,∘( _1 -_2) ∘_2k,♢   ≤ϵ + Ł(k^8ℓ^8(m^4log^8(kℓ/ϵ))/N) + minŁ( 128k^4/m^ℓ,2)
       ≤Ł(k^8ℓ^8m^4n^8/N+k^4/m^ℓ)Setting ϵ = (kℓ/N).
 The last line drops the min(·) since the quantity is a priori bounded by 2.




 §.§ Truncation error for exponentials

This section includes a standard truncation argument for Taylor expansion of exponentials.

For every degree d there exists a polynomial of h_d such that

    ^ - h_d()≤^d+1/(d+1)!  for any Hermitian matrix  .

In particular, choosing 
    
    d = Ł(log(1/ϵ)/log(log(1/ϵ)))   ensures that  ^ - h_d()≤ϵ.




We begin with Taylor expansion
    
    ^θ_m _m - h_d_1(_m)≤θ_m_m^d_1+1/(d_1+1)!.

    Since the exponential appears 2k·ℓ times in f_,,1(1/N), the error can accounted for by triangle inequality 
    
    f_,,1(1/N) - f^(trun)_,,1(1/N)   ≤Ł(1 +  θ_m_m^d_1+1/(d_1+1)!)^2kℓ - 1
       ≤expŁ( 2kℓθ_m_m^d_1+1/(d_1+1)!) - 1 Since 1+x≤^x
       ≤ϵSince θ_m_m≤(√(m))) and ^x≤ 1+ 2 x for x≤ 1..

    That last line chooses the suitable d_1 = (√(m)log(kℓ/ϵ)).




§ LINDEBERG ARGUMENTS

One step of our argument converts an independent sum to a matrix with Gaussian entries. This is not terribly surprising and appeared in <cit.> in a different form. We quickly derive a version suitable for our context.

For any = ∑_j w_j_j such that ∑_i w_i^2 =1, In the large-N limit, 

    lim_N→∞_2k, - _2k, ♢≤1/8∑_j=1Ł( (4kw_j)^4 + (4kw_j)^2k).


This is an adaptation of the matrix Lindeberg argument <cit.> with simplification from the large-N limit. The main observation is that the (complex conjugated) second moments are equal for random permutations and Gaussians:

    [⊗^†]    = [⊗^†],

and all other (mixed) moments vanished up to 3 copies,

    [^(†)]    = [^(†)] = 0
    [^(†)⊗^(†)⊗^(†)]    = [^(†)⊗^(†)⊗^(†)] = 0.

Since we are comparing CP maps, the following polarization identity will be useful to turn any superoperator into a weighted sum over CP maps.
  For any square matrix ,,
    
    [·]^† = _s = ± 1, ± s(+s)[·] (+s)^†.



Define the interpolant

    _j := ∑^j_i=1_i +  ∑^m_j+1_i   where  _j := w_j _j  and  _j := w_j _j.

    Then, 

    _2k, - _2k, ♢   = sup_ρ,[(_2k, - _2k, )].

By <ref>, it suffices to take the state to be entangled with ancilla of dimension max_λ⃗ d_λ⃗. Nevertheless, this will not be used anywhere in the proof. 

We can expand the difference as a telescoping sum where we exchange one term at a time

    [(_2k, - _2k, )] = ∑_j=1^m (n_j-n_j-1)   where  
        n_j := [_2k,_j[]].

In order to analyze the difference, for each intermediate step j,  denote 

    _- := _j-_j = _j-1-_j.

When expanding powers of a sum of matrices, keep in mind the scalar binomial expansion:

    (x+y)^2k   = ∑_q = 0^2k2kq x^2k-qy^q.

For our matrices of interest, the expansion takes the form

    (_- + _j)^⊗ k [·] (_- + _j)^†⊗ k    = ∑_words_- ⊗⋯_j ⊗_-⋯_j_- [·] ⊗ (_j _-⋯)^†
       =:∑_q=0^2k_qregroup by the occurrences q of _j.


To control the norm of the operators _q, we first polarize the error terms to turn the super-operator into a complex linear combination of completely positive maps (By <ref>). There are different patterns of _- and _j:
(1) If all q-many _j only paired with _-, there are q locations where we need to polarize 

    [ _- ⊗⋯_j ⊗_-⋯_j_- [] ⊗ (_j _-⋯)^† ]
        = _s s[ _2,S_-∘_2,(a_j_j+ s s_-_-)∘⋯ [] ]By <ref>
       ≤_s^†_2,S_-∘^†_2,(a_j_j+ s s_-_-)[]∞Norm bounds for CP maps, s =1
       N→∞=_s[ ^†_2,S_-∘^†_2,(a_j_j+ s s_-_-)[] ]By <ref>
       N→∞=Ł[(Ł[_-^†_-])^k - q·Ł[ a_j^2_j^†_j + s_-^2 _-^†_-]^q]
        = _-(Ł[_-^†_-])^2k-q/2·_jŁ[ _j^†_j]^q/2Optimize parameters and exploit independence
       N→∞= (1-w_j^2)^2k-q/2·w_j^q≤w_j^qBy _j^†_j= and <ref>.

    The fourth inequality uses the permutation symmetry of both channels to use <ref>. The last equality minimizes the expression for suitable real random scalar variables

    a_j^2 = √([_-^†_-]/[_j^†_j])  and  s_-^2 = √([_j^†_j]/[_-^†_-]).

The case where _j are paired up with _j^† enjoys the same bound using that the normalization trace is deterministic in the large-N limit for the Gaussian case

    lim_N→∞[^†] dist.= 1.


Likewise, (_- + _j)^⊗ k [·] (_- + _j)^†⊗ k = ∑_i=1^m _i with analogous bounds for the summands. 

To proceed, since the first and second (possibly conjugated) moments of the random matrices _i and _i match for each index i, 

    ^(†)_i ⊗   = ^(†)_i ⊗; 
    _i^(†)⊗^(†)_i⊗   =^(†)_i ⊗^(†)_i ⊗
    _i^(†)⊗_i^(†)⊗^(†)_i⊗   =^(†)_i ⊗^(†)_i ⊗_i^(†)⊗  for arbitrary  independent from _i, _i.

Crucially, this implies that subtracting the expected moments completely cancels the first to third order terms _1,_2, _3 and  _1,_2, _3

    n_j-n_j-1   =∑_q=4^2k[(_q - _q)[]]
       N→∞≤∑_q=4^2k2kqŁ(Ł[ _j^†_j]^q/2 + Ł[_j^†_j]^q/2)
       ≤ 2 ∑_q=4^2k2kqw_j^q
       ≤ 2 ∑_q=4^2k (2k)^qw_j^q Since 2kq≤ (2k)^q
       ≤(4kw_j)^4 + (4kw_j)^2k/8.

The last inequality bounds the geometric series using the elementary numerical inequality 

    ∑_q=4^2kx^q = ∑_q=4^2k2^-q(2x)^q≤1/8( (2x)^4+(2x)^2k)
          for x ≥ 0.

Sum over the index j to conclude the proof.




§ COMPARING THE GAUSSIAN CP MAP WITH A UNITARY CHANNEL





    lim_N→∞_2k, - _2k,♢=0
    


    Since the Ginibre ensemble is left and right unitarily invariant, its action maps between irreps of the commutant of the unitary group. In particular, this commutant algebra has bounded dimensions (k! for fixed k) as the dimension N goes to infinity. We express general normalized PSD symmetrized input in terms of diagrams
    
    = Ł(∑_c__/_2)Ł(∑_c__/_2)^†  such that  []=1.

The normalization can be determined by 
    
    1=Ł[ Ł(∑_c__/_2)Ł(∑_c__/_2)^†]    = ∑_c_^2 + (cross terms.)
       N→∞=∑_c_^2.

    The second line uses that, in the large N limit, the cross terms vanish since different permutations are orthogonal in the limit
    
    [_^†_'] = Ł(1/N_2_'2)  if '.

    Now, we control the difference in 1-norm for any PSD input

    (_2k,-_2k,)[]1   ≤∑_,'c_c_' (_2k,-_2k,)[_/_2^†_'/_'2]1
       ≤Ł(∑_,'c_c_') sup_ (_2k,-_2k,)[_1/_1Since _^†_'=_'^-1.

    
    Therefore, it suffices to compare the limiting behavior between two maps on each individual diagrams:
    
    (_2k,-_2k,)[_]1   =  (_2k,-1)[_]1Haar random channel acts identity
       = (_2k,-1)['_]1 + o(1)__1'_-__1=o(1)__1 is subleading in N
       = (_2k,,',⋯,-1)['_]1+o(1)__1Decouple distinct blocks
       = (_2k,,',⋯,-1)[_]1+o(1)__1Restoring _
       =o(1)__1Since [··^†] =.

    The second line makes the indices distinct at the 1/N cost in 1-norm 
    
    _ = ∑_Π≥'_Π  such that  _ -'__1 ≤f(k)/N__1

    for some combinatorial factors f(k).
    (Since each '_Π have all blocks propagating if Π≥, the 1-norm is '_Π_1= M'_Π, which is at least (1/N) smaller than M'_.) The third line is a decoupling argument: distinct rows of Ginibre matrices are independent. Therefore, the distinct blocks of  (which are the k wires connecting the bottom to the top) are effectively acted by independent pairs of s
    
    _2k,['_] = _2k,,',⋯,['_]

where the non-CP map _2k,,',⋯, depends on the blocks of . The fourth line removes the distinctness constraint at error _2k,,',⋯,[_-'_]_1≤_-'__1 (using asymptotic CPTP property of _2k,,',⋯, <ref>).
To conclude the proof for the diamond norm, consider arbitrary inputs with positive and negative parts, recall that the prefactor ∑_,'c_c_' is finite in the large-N limit, and uses that the ancilla dimension for the diamond norm is also independent of N (similar to <ref>).




§ UNITARY K-DESIGNS FROM K'-WISE PERMUTATIONS


Our construction of random unitaries from random permutations can recover efficient unitary k-designs in the diamond distance by replacing the truly random phased permutations with (k)-wise independent phased permutations. The goal of this section is to prove this argument as the detailed version of <ref>.


There is a constant c such that for k ≤ 2^cn, an ϵ-approximate quantum unitary k-design can be implemented
using 

    (log^2(k/ϵ))     one and two-qubit gates and 
    (log^2(k/ϵ))     controlled-queries

to (log(k/ϵ))-many independent samples of (ϵ N^-4k')-approximate k'-wise random permutations and their inverses, and to the (log(k/ϵ)) independent samples of exact 2k'-wise random functions [N]→ [2k'+1] for some almost linear

    k' = (klog(k/ϵ)).



The first step of the argument is to replace the truly random phases in each term of the product with 2k'-wise independent phases.
If the classical 2k'-wise independent phased permutations are exact, then the substitution argument is immediate (even with inverses; (<ref>)). Indeed, this can be done exactly for the phases by replacing them with efficiently implementable, exact 2k'-wise independent phases.

    For any integer 0<k'<2^cn, consider the set of N evenly spread points on the unit circle
    
    S_N := { 1, ^1/N2π,^2/N2π,⋯}.

    Then, a 2k'-wise independent function f: [N] → S_N acting on the diagonal matches exactly the 2k' (mixed) moments of diagonal random phases 
    
    [ _f^(†)2k' ] = [ _z^(†)2k' ].

    Further, _f can be implemented using (nk') gates.


    First, we use 2k'-wise independence to replace f with truly random functions on the diagonal. Now that each of the entries is decoupled, and we merely require the discrete points on the unit circle to reproduce the moments,  
    
    _S_N[z^p] =  _(1)[z^p] = 0   for each integer  p≤ 2k'

    which can be seen from the properties of the discrete Fourier transform. The implementation cost has two parts: first, the cost of classically evaluating a k'-wise independent function f:[N] → [N], which is merely Õ(nk'). This is obtained using the classic construction using a random degree k'-1 polynomial over the field 𝔽_2^n  <cit.>).
    Second, is the cost of then applying these values in [N] as phases in S_N, which can be done by the usual controlled tower of geometrically decreasing rotations at cost O(n).
    Third, we then uncompute the function f. 
    The net cost is Õ(nk').



The second step of the argument is to replace the truly random permutations with (approximate) 2k'-wise independent permutations.
While the independence of the phases can be exact, the best known efficient classical k-wise independent permutation for large values of k is approximate. Thus, we have to demand the classical k-wise independent permutation to achieve very high precision at very low costs to compensate for the distance conversion rates against quantum queries.

    We say an ensemble of permutations gives a classical ϵ-approximate k-wise independent permutations if
    
    _'^'k|i⃗⟩ - _^k|i⃗⟩1≤ϵ  for each  i⃗∈ [1,N]^k.


In the above, we defined the vector ℓ_1 norm

    ∑_i⃗ c_i⃗|i⃗⟩1 := ∑_i⃗c_i⃗

which captures the statistical distance when applied to the difference of two probability distributions.

In our use cases, the above classical statistical notion of distance is not immediately applicable because (1) the quantum inputs can be entangled and (2) our implementation of the unitary makes adaptive queries to both  and ^-1. Fortunately, the above complication can be circumvented entirely by a powerful black-box result that allows us to effectively use 2k-wise independent permutations as exact in other parts of the paper, provided the precision is high enough.

    Suppose there exists an ϵ-approximate classical k-wise independent permutation _approx. Then, there exists an exact classical k-wise independent permutation _exact that is (ϵ· N^4k)-statistically close on the distribution of permutations.


This Theorem of <cit.> is very powerful, as it allows one to transfer the error ϵ in the k-design to an error in the distinguishing probability of the algorithm. This is by a simple hybrid argument: it's easy to see that for any distributions D,D' on inputs, the probability a quantum (or classical) algorithm accepts on a random input from D vs D' is upper bounded by twice their total variation distance[This is simply because the probability the quantum algorithm accepts is a bounded function in [0,1] over the domain – so a change of the input distribution by ϵ can change the value of the expectation by at most 2ϵ. ]. So given a quantum algorithm  trying to distinguish our ensemble (built from ϵ-approximate k-wise independent permutations) from Haar, substituting in our ensemble with the same one built with _exact at most changes the acceptance probability[Here one must invoke data processing inequality as well to say the “lifted” ensembles on unitaries are also close in total variation distance.] (diamond norm value) by ϵ N^4k. As we will discuss shortly, ϵ can be set to be exponentially small which makes this change negligible.



Recall that our construction

    :=_L Ł( ∏_j=1^ℓ^θ_m ^(j)_m)_R,

    can be implemented to precision (ϵ/k) using 2+mℓ-many random samples of k'-wise independent permutations and their inverses (<ref>) with

    k' = Ł( k·queries per ^θ_m_m(√(m) +log(kℓ/ϵ))).

In particular, we may choose (assuming k≤ 2^cn), 

    m = 2,  ℓ = ( log(k/ϵ))   such that  _2k,-  _2k,_Haar♢= Ł(k^8ℓ^8(m^4n^8+ n^8)/N+k^4/m^ℓ)≤(ϵ).


If the classical k-wise independent permutations are exact, then the claim follows even in the presence of inverses ^-1 since the partial transpose is linear (and that ^-1=^T)

    _[^⊗ k]    = _'[^'⊗ k]
    implies  _[^⊗ k_1⊗ (^T)^⊗ (k- k_1)]    = _'[^'⊗ k_1⊗ (^'T)^⊗ (k- k_1)].

Now, by <ref>, we may simply replace the truly random permutation  with the exact k-wise independent permutations while paying an additive error ϵ in the distinguishing probability between _exact and _approx. 

Lastly, we invoke the highly nontrivial construction of efficient k-wise independent permutations <cit.> as a black box. Generators that give Cayley graph expanders for the symmetry group (and others) have been known <cit.>. These explicit constructions <cit.> can also be efficiently evaluated (given n-bit inputs) <cit.>. For our purposes, the recent elegant construction (<cit.>)[We thank Martin Kassabov for this pointing us to this reference.] can be efficiently computed classically using finite field arithmetics on large primes, which in turn gives the following classical circuit complexity on k-wise independent permutations on 2^n many elements.



There exist classical ϵ-approximate k-wise independent permutations on 2^n elements with time complexity 

    ((n) Ł(nk+ log(1/ϵ))).


Therefore, we can take a small error ϵ = 1/2^Ω(nk) to feed into <ref> to obtain nearly exact k-wise independent permutations at the overall cost ( k·log(n)).



 §.§ Bootstrapping nonadaptive designs to adaptive designs


Throughout the paper, we have mostly discussed nonadaptive designs in the sense of the diamond norm. This can be bootstrapped to adaptive security at high enough precision (for example, by iterating the same random unitary many times <cit.>.).



Consider two unitary ensembles. The distinguishing probability for any quantum algorithm using k adaptive queries can be controlled by trace distance for parallel distinguishability with additional dimensional factors:

    (_2k,) -(_2k,)≤ 4^k N^4k·_2k, - _2k,1-1.

The above continues to hold if the unitaries at each query are different with _1,⋯, _k and _1,⋯, _k on both RHS and LHS.


    Consider the super operator entries of the channel

    (_2k,) -(_2k,) = ∑_i⃗'⃗i⃗j⃗i⃗'⃗α_i⃗'⃗i⃗j⃗i⃗'⃗⟨i⃗'⃗|δ[ |i⃗⟩⟨j⃗| ]|j⃗'⃗⟩.

for j⃗ = (j_1,⋯,j_k) ∈ [N]^k. Expecting dimensional factors, we will content ourselves with bounding the entry-wise coefficients α_i⃗'⃗i⃗j⃗i⃗'⃗. To do so,
consider a polarization argument (<ref>)
for each system (i,i',j,j'∈ [1,N]) that turns it into a weighted sum over CP maps

    |i'⟩⟨i|⊗|j⟩⟨j'| = _z=±1,±Ł[ z(|i'⟩⟨i| +z|j'⟩⟨j|)⊗(|i'⟩⟨i| +z|j'⟩⟨j|)^†] .

In particular, the Kraus operator is bounded as

    (|i'⟩⟨i| +z|j'⟩⟨j|)^†(|i'⟩⟨i| +z|j'⟩⟨j|) ≤ 4.


Thus, the Kraus operator tensored across systems

    _z⃗:=(|i_1'⟩⟨i_1| +z_1|j'_1⟩⟨j_1|)⊗⋯⊗(|i_k'⟩⟨i_k| +z_k|j'_k⟩⟨j_k|)

and the corresponding CP map (with suitable normalization) 

    _z⃗: = 1/4^k_z⃗[·]_z⃗^†

define a trace-non-increasing map since _z⃗^†[] ≤1/4^k (4 )^⊗ k≤,  and thus (_z⃗) is a “valid experiment,” with some possibility of failure. Thus (_z⃗)≤ 1. 

Combining the above, we obtain the entry-wise bound

    α_i⃗'⃗i⃗j⃗i⃗'⃗ =  4^k_z⃗ z_1⋯ z_k(_z⃗)≤ 4^k_z⃗(_z⃗)≤ 4^k.

Altogether,

    (_2k,) -(_2k,)   = ∑_i⃗'⃗i⃗j⃗i⃗'⃗α_i⃗'⃗i⃗j⃗i⃗'⃗⟨i⃗'⃗|δ[ |i⃗⟩⟨j⃗| ]|j⃗'⃗⟩
       ≤∑_i⃗'⃗i⃗j⃗i⃗'⃗α_i⃗'⃗i⃗j⃗i⃗'⃗δ1-1
       ≤ 4^k N^4k_2k, - _2k,1-1

as advertised. In fact, the identical argument holds if the unitaries at each query are different with _1,⋯, _k and _1,⋯, _k on both RHS and LHS.


amsalpha


